ネットワーク化バブル伝播法(NBP法)に基づき以前に実現した述語版仮説推論 システム [大澤 95b] では、述語引数をネット ワークのノードとして、巧妙な方法で NBP法を適用していた。しかし、これは メカニズムが複雑でかつ動作の理解が難解になり、ネットワーク中の変数束縛 の伝播も推し量りにくいという性質があった。そこで今回はQSQR法を用いて、 あらかじめゴールの証明に必要な述語群、およびそのインスタンスを抽出し、 それに対して命題版NBP法を適用することで、見通しよく述語論理の仮説推論 を実現する。
なお、我々は以前にこの QSQR法に準拠する最適解計算の仮説推論法を作成し ているが [Kondo 96]、これは QSQR法の推 論に最良優先探索、ビーム探索、分枝限定法を組み入れたものであり、記号操 作により（最適解がビーム外に出てしまうと見逃してしまうので厳密ではない が）基本的に最適解探索を行っている。
(1)QSQR法について
まず、演繹データベースの手法である QSQR法のアルゴリズムについて説明し ておく。これはトップダウン制御のボトムアップ推論を行い、述語論理の効率 的な全解計算法として有効である。
前準備として、次のように定義する。
また、ホーン節頭部に現れる変数はすべて本体に現れている時、このホーン節 を領域制限的と言うが、ここでのルールはこの領域制限的なホーン節のみであ るとする。
QSQR法はEDB、IDBの他に、二つの状態、Q、Lを保持する。
状態Qは、それまでに評価した問い合わせのゴール、サブゴールを保持し、マッ チング時に利用する。また状態Lは、それぞれのIDB述語の求まった関係を保持 する。これは、すでに計算されたサブゴールの答え、補題(lemma)と見なせる。 この二つの状態を用いて、同じサブゴールの再計算を防ぐ。
さらにPrologによる推論などとのもう一つの違いは、下位ノードからの答を一 つずつ受けとるのではなく、下位ノードの全解をすべて受けとることである。 これにより、バックトラックなどに伴う同じサブゴールの再計算を防げる。 AND関係の兄弟述語間では変数の束縛情報を横方向に伝播させて、不要な推論 の抑制も図る。
QSQR法はゴール指向ボトムアップ推論を実現し、マジックセット法とは効率の 点で同等である。
(2)QSQR法の適用が有効なケース
述2語知識の命題への展開は、ゴールの証明に関係しない部分を省いた選択的 なエルブラン領域への展開に等しいことになる。そのため述語の持つ引数の数 に対して、一般にはノードの展開量は指数的に増大する傾向となる。
ただし単純なエルブラン展開を利用する場合と異なり、引数同士が相互に関連 していて独立性が低く、述語として成立する引数の組み合わせが少ない場合は、 展開量も制限され、十分適用可能になる。QSQR法による命題への選択的エルブ ラン展開が有効なのは、このような場合であり、実用的問題ではこのようなこ とが多い。