確率的近似学習のパラダイムによる遺伝的アルゴリズムの効率の解析および実働化

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

本研究の目的は、理論的な研究はすすんでいるが実用的な応用例に乏しいPAC学習のパラダイムと、理論的解析法の整備されないままにも実用的なアプリケーションが開発されつつある遺伝的アルゴリズムを融合し、理論と応用の両面から、生物学的データからの知識獲得を行なうシステムを開発することである。今年度は、以下の知見が得られた。1.PAC学習可能性を確かめた上でワークステーション上に実働化した知識獲得システム「BONSAI」を、並列化可能性の観点から見直し、そのプロトタイプを作成した。その中で、特に計算量を要する、パターンの検索部分に対し、遺伝的アルゴリズムを適用して、その効果を確かめた。これらの理論的な解析については、今後ともに引き続き重要な研究の課題となると思われる。また、ここで構築したシステムは、実際の遺伝子データのように、もともとの分類のはっきりしない問題に対しても有効であると期待される。2.PAC学習可能性を特徴づける組み合せ量として重要な、VC次元を求めるための計算量の評価を行った。さらに、これを一般の関数に関して拡張した次元についても同様な解析を行った。その結果、この計算量は、変数の個数を限定した論理式の充足可能性問題との還元可能性で特徴づけられ、NP完全にもなりそうにはないがPで解けそうもない、という、計算量理論の観点からも興味ある知見を得た。この結果は、学習アルゴリズムの計算量の評価とは独立した問題ではあるが、今までと異なる観点から学習モデルを評価する際に有用になると思われる。