逆伴意における最弱仮説の完全化

以下では、関連研究として、逆伴意における最弱仮説の完全化の成果について 述べる。

近年、Muggleton[3]は、 逆伴意 (Inverse Entailment) による帰納推論によって、帰納論理プログラミングの性能を著しく向上させる ことに(ほぼ)成功した。その鍵となるアイディアは、背景知識をBとし、 一つの正例をEとする時、仮説および正例を単一節(single clause)に限定 すれば BHE を満たすすべての仮説Hが伴意するような最も 弱い仮説(最弱仮説, Most Specific Hypothesis, MSH)が存在し、それがB とBEから、BBEのすべてのモデルで正しい基底リテラル の(無限かもしれない)連言の否定として容易に計算できる、という「事実」 である。この方法を便宜上、 Algorithm IEと呼ぶことにする。

ところが、Yamamoto[7]は、その「事実」に反例があることを示 し、MSHの存在証明が誤りであることを指摘した。

この問題を解決するために、Furukawa[1]は、 Algorithm IEが正しくMSHを計算するための十分条件を与えた。それは、「背景知識が確 定節のみから成る節形式で、背景知識の任意の節の本体部から学習対象とな る目的述語を呼ばない」という条件である。

それに対して、Yamamoto[8]は、 Algorithm IEが正しく MSHを計算する問題のクラスを、Plotkin[6]のSB-Resolutionによっ て与えた。

我々は、それに対して、背景知識は任意のプログラム節で与えられ、正例は基 底単位節として、二つの場合での完全なMSHを計算する新たなアルゴリズムを 開発した。第1は、説明すべき正例に対する述語(概念)を学習する場合で、そ のアルゴリズムは Algorithm IEの拡張になっている。第2は、説明すべ き正例と異なる述語を学習によって補う場合で、それは発想的帰納推論と呼ば れている[2]。