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

启发式搜索算法的理论与实际应用

基本信息

批准号：
09780344
负责人：
篠原歩
金额：
$ 1.28万
依托单位：
Kyushu University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1997
资助国家：
日本
起止时间：
1997 至 1998
项目状态：
已结题

项目摘要

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

搜索在人工智能的问题解决中始终发挥着关键作用，需要在利用特定问题的知识的同时控制搜索，并设计出处理搜索路径组合爆炸的方法。称为启发式搜索算法，但其性能强烈依赖于每个问题的独特特征，并且很难找到有效的搜索算法。以统一的方式开发和分析这种启发式算法是极其困难的。我们将在计算学习理论的框架下开发这种启发式算法，并旨在使用更具体的问题来证明其有效性。首先，在问题学习模型中，我们。成功地提供了一个统一的表征，允许通过多项式问题来学习概念类，以及它们的组合已经被单独研究，但我们的结果包括它们。这种表征表明，通过问题学习可能性的本质是有效缩小示例空间的问题的存在，我们获得了可以验证问题存在的知识。得到了缩小范围的假设是正确的。接下来，我们基于实践中经常使用的决策树学习算法开发了一种加权分类规则。我们提出了一种算法来检测这一点，通过计算机实验，我们验证了该方法在时间和预测精度方面具有相当于或优于决策树的性能，此外，我们还提出了一种用于检测基因破坏生成的数据的算法。我们将搜索问题中识别基因网络的问题视为探索问题，阐明了该问题的计算复杂性，从理论和实践方面分析了其性能，并进行了计算机实验。