本課題では、グラフ言語の多項式時間学習アルゴリズムとその応用に関する研究を行い、我々は、実世界のグラフ構造データを表現可能ないくつかのグラフパターンを提案し、それらに対する学習アルゴリズムの設計と知識発見システムの開発を行った。主な結果は次のとおりである。
1.ウェブデータを木構造データとみなしたとき、その木の高さはほとんどの場合小さい。そこで、高さ制約代入を用いた木構造パターンの多項式時間照合・発見アルゴリズムを提案し、学習モデルとして正データからの多項式時間帰納推論および質問学習を用いて、現実的に意味のある代入制約の下で提案した木構造パターンのクラスが多項式時間学習可能であることを証明した。
2.区間グラフとは、各頂点が数直線上の互いに異なる区間に対応し、2つの区間が重なっているとき、対応する2つの頂点は辺で結ばれる、というような性質を持つグラフである。我々は、区間グラフに共通するパターンを表現する方法として、単体頂点を変数として持つ区間グラフパターンを定義し、この区間グラフパターン言語のクラスが正データから多項式時間帰納推論可能であることを示した。
3.化学化合物のほとんどが、グラフ理論的には外平面的グラフである。そこで、化学化合物データベースからのデータマイニングを行うために、ブロック保存型外平面的グラフパターン(BPOグラフパターン)を定義し、BPOグラフパターンの...