| 平成８年度 委託研究ソフトウェアの提案 |
本研究では、我々が行なってきた高速仮説推論法の成果を広く使用できる形態のソフトウェアツール化し、新しい知識処理の枠組みの利用拡大を可能にすることを目的とする。特に、可能な要素仮説に数値的な重みを付し、この重みの和（コスト）の最小な解仮説を求める重み付き（あるいはコストに基づく）仮説推論に焦点を当て、準最適解を多項式時間で求めるネットワーク化バブル伝播法による仮説推論法のツール化を図る。平成７年度には命題論理表現版のソフトウェアNBP1を開発し、 ICOTフリーソフトウェアとしたが、これを利用し本年度はより豊かな表現能力を提供する述語論理版（領域限定の述語ホーン節）の重み付き仮説推論に対して、準最適解計算の多項式時間推論システムを作成する。
ネットワーク化バブル伝播法の述語論理版（正確には関数なし領域限定ホーン節を対象）は既に試作システムを開発し、論文等での発表を行なっている。しかし、この試作版は述語引数の項の部分をネットワークのノードとして巧妙な方法でネットワーク化バブル伝播法の適用を可能としたもので、手法的には興味深い点があるが、必ずしも理解しやすくはない。理解の容易さは、ユーザが安心して使用できる、予期せぬ結果が生じた時の対応、今後の改良等の点で重要である。そこで、この試作版の開発の後、仮説推論の使用する知識の範囲の段階的深化による拡大、 演繹データベースの効率的手法であるQSQR法の援用により、限られた範囲の述語論理知識を命題論理表現に変換し、命題論理版ネットワーク化バブル伝播法（具体的にはNBP1）を反復して適用する推論手法を考案した。理解の容易性、内部構造の複雑性等の点でこの推論手法の方が有望であることから、この推論手法による多項式時間述語論理版仮説推論システムを開発する。
この方法は述語論理表現処理部を命題論理処理部と分離して構成できることから、局所探索による最適化手法等によりネットワーク化バブル伝播法とは別種の命題論理処理部も、プラグイン的に結合可能という利点も有することになる。
述語論理（関数なし領域限定述語ホーン節）表現の重み付き（又はコスト付き）仮説推論における準最適解を多項式時間で求める推論システムである。仮説は基礎代入された単節の述語リテラルであり、数値的な重みを付すことができる（重みのデフォルト値は１）。ルールを仮説にすることもできるが、これは単節の仮説述語を導入し、仮説でない背景知識となるルールと、単節の仮説述語に変換できる。背景知識は矛盾の可能性を有しないのに対し、仮説は矛盾の可能性を有する知識であり、矛盾は'inc'アトム(inconsistentの略でATMSのnogoodに相当）を満たす条件によって定義する。推論のゴールを与えると、このゴールの証明に必要な重みの和（これをコストと定義する）の最小の無矛盾な要素仮説の集合（最適解仮説）を求める。
常に厳密な最適解仮説を求めるようにすると、問題のNP完全性により最悪値で指数オーダの推論時間になってしまうことから、創案したネットワーク化バブル伝播法により準最適解を多項式時間で求める。ネットワーク化バブル伝播法の特徴は、単体法により実数領域の最適解である探索の初期値を非常に効率的に決定し、０-１整数計画法の大変良い近似解法である掃出し補数法に準拠の局所探索動作をネットワーク化した知識上で動作させるようにし、更に知識構造を利用して効率の改善を図っていることである。豊かな表現力を提供する述語論理表現を扱う独自な拡張を実現していることも特徴である。
制約充足やATMS等のツールは存在しているが、問題がNP完全であるために、いずれも問題規模の拡大につれて指数的に増大する推論時間が大きな問題になっていた。本研究の仮説推論システムでは、重み付き仮説推論システムとして必ずしも最適解でない準最適解を求めるようにすることにより、問題規模に対して多項式時間で解を得るという実用性を有する。人間も複雑な問題に対しては必ずしも最適解を求めるのでなく、実用的時間内で準最適解を求めて対処しており、準最適解を求めることはこのような人間の行動に準拠しているともいえる。
更に、関係の記述を許すことで豊かな表現能力を持つ述語論理表現の知識を扱うことができる。また通常プロダクションシステムと結合して使用されるATMSと異なり、論理を基盤とする問題解決機構であり、推論の筋道をガイドする役割を果たす知識の記述を要しない。構造的な知識、深い知識に基づく問題解決（診断、計画、設計等）の有効なソフトウェア・ツールとなる。
本ソフトウェアは次のモジュールから成る:
１）推論深さの段階的拡大を制御し、演繹的データベース手法のQSQR法により述語論理表現部を扱う処理部。（新規）
２）上記１）の結果を命題論理表現に変換し、命題論理版ネットワーク化バブル伝播法を適用して求解を行なう部分。（新規）
３）命題論理版ネットワーク化バブル伝播法のソフトウェア(NBP1)。（インタフェース部の部分的改造）
平成７年度にフリーソフトウェアに登録したネットワーク化バブル伝播法による命題論理版高速仮説推論システムNBP1を使用する。
述語論理処理部にはKLICを使用する。
通常のUNIX環境だが、使用する仮想記憶は100MB程度になる予定。
仮説推論あるいはアブダクションは診断、解釈、設計といった幅広い問題に適用可能な大変有効な知識処理の枠組みである。特に、宣言的知識表現上での求解機構であり、推論の筋道をガイドするヒューリスティック的知識の記述が不要な点で、知識記述、知識獲得の負担を軽減することができる。しかし、これまでは低い推論速度が実用的な利用を妨げていた。
本システムは準最適解を多項式時間という実用的な時間で求めることで、推論速度の問題を克服している。このメカニズムを各自でインプリメントするのは大変であることから、汎用性をもつソフトウェアツールとして提供されれば、広範囲の利用が拡大するものと思われる。
ユーザマニュアルを作成し添付の予定。
推論速度性能の実験的評価も示す。
www-admin@icot.or.jp