発見的探索アルゴリズムの理論と実働化

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

人工知能の問題解決において,探索は常に鍵となる役割を果たしている.実際のアプリケーションにおいては,問題固有の知識を利用しながら探索を制御し,探索経路の組み合わせ的爆発に対する工夫を行うことが必要である.このような経験的な知識を利用した探索は,発見的探索アルゴリズムと呼ばれているが,そのパフォーマンスは個々の問題固有の性質に強く依存し,効率の良い探索技法の統一的な開発,解析が極めて困難である.この発見的アルゴリズムを計算論的学習理論の枠組みでとらえ,さらに具体的な問題を用いてその有用性を実証することを目標として研究を展開した.まず,複数の有力なアルゴリズムを統合して,よりパフォーマンスの高いシステムを構築するための手法として,重みつき投票アルゴリズム(WM)の拡張(WM^*)を行った.WMは,各アルゴリズムに予測を投票させ,その投票結果によって全体的な判断を下すものである.我々の拡張によるWM^*は,おのおののアルゴリズムが投票を棄権することを認めるものであり,直観的には,各アルゴリズムは自信のない予測については棄権によって発言権の低下を防ぐことができると期待される.実際に我々は,WM^*による予測の方がWMによる予測よりも原理的に優れていることを理論的に証明した.さらに,このWM*を組み込んだ領域予測システムHAKKEのプロトタイプを作成し,アミノ酸配列データからのαヘリックス部位と膜貫通部位の同定問題に対する計算機実験によって,この優位性を検証した.また,パターン言語の学習可能性を探究し,次のような知見を得た.(1)部分列言語の和集合のクラスは,非常に少ない所属性質問と等価性質問を用いて学習可能である.(2)部分列言語のクラスは,所属性質問のみで学習可能である.(3)パターン言語のある部分クラスは,1つの正例と非常に少ない所属性質問を用いて学習可能である.