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

［特徴ある機能］

コストに基づく仮説推論の準最適解を効率的に求めるシステムの述語論理版。
（正確には関数なし領域制限述語ホーン節表現を扱う。）

　仮説推論（生成可能な仮説を定義しているアブダクション）は、知識処理の
有用な枠組であるが、厳密解の計算には問題サイズに対して指数オーダの推論
時間を要する。本ソフトウェアは、コストに基づく命題論理表現仮説推論の準
最適解（解コストは解に含まれる要素仮説の重みの和であり、最適解とは解の
コストが最小なもの）を低次多項式時間で求めるネットワーク化バブル伝播法
（NBP法: Networked Bubble Propagation method）を実装したNBP1を下部推論
メカニズムとして利用し、述語論理表現の仮説推論を実行するものである。
コストに基づく述語論理版仮説推論の準最適解を求める事ができる。 

　東大石塚研究室で考案、開発されたNBP法は、0-1整数計画の大変良い近似解
法である掃出し補数法(pivot and compliment method)の動作をネットワーク
上で実現し、かつ知識構造を利用した推論効率の向上を達成したものである。
その命題版仮説推論の速度は要素仮説数の約1.5乗の多項式オーダ時間を達成
する。
　述語論理部の処理にはここでは簡素な実現法として、演繹データベースの効率的
手法であるQSQR法を段階的深化により用いて、述語論理表現の仮説推論問題を命題
表現の仮説推論問題に変換する。これによってNBP法の適用を可能にしている。          

［必要な環境］

標準的CコンパイラとX-windowツール（nbp1b.cをコンパイルして実行プログラムnbp
    を作成する）
Sicstus Prologの実行系（qsqr.plgの実行）
Perlインタプリタ      

［ソースプログラムの分量とファイル構成］

nbp1b.c : コストに基づく命題版仮説推論を解くNBP法のC言語プログラム [73KB]
          （先に公開しているnbp1aのバージョンとは異なり、任意の
            重みの仮説を扱う機能を持つ。X-windowによるGUIの機能
　　　　　　 も持っているが、ここでの述語版仮説推論ソフトの下部
　　　　　　 機構として利用するときは使わない。）
{nbp    : nbp1b.cをCでコンパイルして作成する実行形式プログラム}

qsqr.plg: 述語論理表現仮説推論を段階的深化のQSQR法により命題論
           理仮説推論に変換するSicstus Prologプログラム [3.5KB]

runqsqr : qsqr.plgとnbp（命題版仮説推論）との間の円滑なデータ
          のやり取りを実現するPerlプログラム  [5.6KB]
       

［ＦＴＰ］

• README
• ソースプログラム、マニュアル [46.2K]