離散構造の法則を発見する並列機械学習システムの開発

点击翻译按钮获取中文摘要

本課題では,離散構造の法則を発見する並列機械学習システムの開発に関する研究を行ない,平成12年度は次の2つの結果を得た.1.木構造は多くの分野でデータを表現するために使われており,木構造を持つHTML/XMLファイルに代表される半構造データからの知識発見が注目を集めている.項木とは,木構造をしたデータのパターンを表現するための,変数を含むデータ構造であり,項グラフよりも表現力が小さいが,一階項よりも表現力が大きい.仮説としての項木が表すパターンと木の適合可能性を判定することは,仮説のチェックをする際に解くべき基本的な問題であり,その計算量を調べる必要がある.よって,入力である項木と木の構造的複雑さに注目してこの問題の計算量を考察し,この問題がどのような場合に効率よく解けるかどうかを調べて,そのアルゴリズムを提案した.2.一般に,グラフは事象(頂点)とその関係を表すだけで,事象間の距離は考慮されない.しかし,地図や化学分子など,事象の位置が重要な画像データなどをグラフで表すとき,そのグラフを距離空間上で定義する必要がある.本研究課題では,距離空間上のグラフから効率良く知識を獲得するシステムを設計した.まず,この知識獲得システムの出力である仮説(知識)を表現するために,Layout Formal Graph System(LFGS)を定義した.これは,グラフを項として持つ論理プログラムであるFormal Graph System(FGS)に位置情報を加味した規則である.さらに,LFGSで用いるレイアウト項グラフでの多項式時間同型判定アルゴリズムを与えた.最後に,Brandenburgによって定義されたレイアウトグラフ文法とLFGSとの比較を行い,LFGSがレイアウトグラフ文法より表現力が大きいことを示した.これら2つの理論的結果に基づいて,HTML/XMLといったような半構造を持ったデータを対象とした機械学習システムのプロトタイプを作成し,その有効性を確認した.