（９）ネットワーク化バブル伝播法による
高速仮説推論システム
-- 命題論理版(ver.1) NBP1 


		マ シ ン： UNIXマシン
		環    境： UNIX, X-window
		言    語： C
		ソース量： 82KB
		文    書： マニュアル（日本語）

［概要］

　コストに基づく仮説推論の準最適解を低次多項式時間で求めるシステムの命 題論理版。

［目的］

仮説推論（生成可能な仮説を定義してあるアブダクション）は、知識処理の 有用な枠組みであるが、厳密解の計算には問題サイズに対して指数オーダの推 論時間を要する。本ソフトウェアは、コストに基づく仮説推論の準最適解（解 のコストは解に含まれる仮説の重みの和であり、最適解とは解のコストが最小 なもの）を低次の多項式時間で求めるネットワーク化バブル伝播法（NBP法： Networked Bubble Propagation method）を実装したものである。X-windowに よるグラフィカルなユーザインタフェースも提供している。

　モデル（制約）に基づく診断、モデル（制約）に基づく設計などのような 構造的（深い）知識に基づく問題解決に、高速仮説推論法の適用を試みること が出来る。

［構成］

ソースプログラム（名称：nbp1.C）一つのみ。試験用の例題知識ベースファ イル（名称：kb**.dat）が添付されている。

［機能］

東大石塚研究室で考案、開発されたNBP法は、0-1整数計画の大変良い近似解 法である掃出し補数法(pivot and compliment method)の動作をネットワーク 上で実現し、かつ知識構造を利用した推論効率の向上を達成したものである。 推論速度は要素仮説数の約1.5乗の多項式オーダ時間を達成する。

NBP1は命題ホーン節表現の知識を扱うバージョンであり、これを内部で利用 する述語ホーン節表現の知識を扱うバージョンは別途提供される予定である。

［参考文献］

1) 大澤、石塚：仮説推論における準最適解を多項式時間で計算するネットワー
   ク化バブル伝播法、信学論D-II, Vol.J77-D-II, No.9, pp.1817-1829(1994.9)
2) 大澤、石塚：改良型ネットワーク化バブル伝播法による低次多項式時間仮説
   推論法, 人工知能学会誌, Vol.10, No.1, pp.123-130(1995.1)
3) 大澤、石塚：多項式時間仮説推論を達成するネットワーク化バブル伝播法の
   述語論理への拡張, 人工知能学会誌, Vol.10, No.5, pp.731-740(1995.9)

［ＦＴＰ］