平成７年度　委託研究ソフトウェアの 成果ソフトウェア

(9) 高速仮説推論システム

研究代表者：石塚 満 教授
　　　　　　東京大学 工学部 電子情報工学科

ネットワーク化バブル伝播法による
高速仮説推論システム
− 命題論理版(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)

［ＦＴＰ］


www-admin@icot.or.jp