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

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

人工知能の問題解決において,探索は常に鍵となる役割を果たしている.実際のアプリケーションにおいては,問題固有の知識を利用しながら探索を制御し,探索経路の組み合わせ的爆発に対する工夫を行うことが必要である.このような経験的な知識を利用した探索は,発見的探索アルゴリズムと呼ばれているが,そのパフォーマンスは個々の問題固有の性質に強く依存し,効率の良い探索技法の統一的な開発,解析が極めて困難である.この発見的アルゴリズムを計算論的学習理論の枠組みでとらえ,さらに具体的な問題を用いてその有効性を実証することを目標として研究を展開した.まず,質問学習のモデルにおいて,概念クラスが多項式回の質問によって学習可能になるための統一的な特徴付けを与えることに成功した.この特徴付けは,これまで等価性質問,所属性質問,およびその組み合わせについてそれぞれ個別に研究されてきたものであるが,我々の成果はそれを包含している.この特徴付けにより,質問による学習可能性の本質は例空間を効率よく絞り込む質問の存在と,絞り込んだ仮説が正しいことを検証できる質問の存在にあるという知見が得られた.次に,実際的によく用いられている決定木の学習アルゴリズムを土台にして,重み付き分類規則を見つけるアルゴリズムを提唱した.計算機実験によってこの方式が時間的にも,また予測精度の点からも決定木のものと同等以上の性能を有することを検証した.さらに,遺伝子の破壊と強制発現によるデータから遺伝子ネットワークを同定する問題を探索問題としてとらえ,この問題の計算量を解明し,理論的な面と実際的な面の両面からそのパフォーマンスを解析し,計算機実験を行った.