科学的知識獲得のための並列探索アルゴリズムの研究

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

本課題では,科学的知識獲得のための並列探索アルゴリズムの研究を行ない,次の成果を得た.近年,盛んに研究がなされている帰納学習あるいは例からの概念学習とよばれる学習方式を,知識獲得システムとして構築するには探索方式の確立が不可避である.特に,「並列」を知識獲得の観点から論ずる場合,1.知識獲得システムのコアとなる検索アルゴリズムの並列化による高速化,2.各種多様なデータに対応できる複数の異なるビューを持ったシステムの構築,を明らかにする必要がある.本研究では,多種多様なデータからinterestingな知識を発見するため,新しいデータマイニングの開発とグラフを表現とした知識発見の2つの研究を行った.データマイニングのおおまかな枠組はIBMのAgrawalらによって確立され,最近盛んに研究されている.我々は,知識の表現の一つである結合ルールに関して研究を行い,結合ルールでは表現し得ない知識の発見を行うため,2分ダイアグラム結合ルールを定義した.さらに,このルールをデータから探索する際に現れる問題に関して計算理論的な考察を行い,遂次および並列計算に関して,いくつかの発見的アルゴリズムを提案した.現在,このルールに基づいたデータマイニングのプロトタイプ作成を行い,ゲノムデータを対象として成果を得ている.また,我々は離散的構造を持ったデータからの知識発見のためにグラフをその知識表現として採用した.実際,RNAやタンパク質の立体構造をグラフで表すいくつかの研究がなされている.本研究では,グラフで表現されたいくつかのデータからそれらに共通したある特徴をもつグラフを発見する問題を帰納推論の枠組で論じた.我々は,内田(広島市立大学)らが定義した項グラフをその表現として用い,グラフ言語の部分クラスであるいくつかのキャタピラ言語が多項式時間推論可能であることを証明した.