PROGOLは、モード宣言、タイプ宣言、正事例、負事例、背景知識を入力とし、 背景知識と共に正事例を説明し、負事例を含まない仮説のうち最も簡潔なもの を生成する。PROGOLシステムは、大きく分けて二つの部分から成っている。第 一は、正事例の一つからその最弱仮説を生成する部分である。この計算は、 GentzenのReduction Theoremにより、実は、Consequence Finding Problemに 帰着することが知られている。そして、この問題は、MGTPを拡張して、演繹さ れる負の基底単位節をも計算することにより、容易に解決できることが知られ ている。そのようにして得られたすべての正負の基底単位節から最弱仮説を生 成するには、それらのand結合の否定を取って、さらに、変数の導入による一 般化を行なえばよい。
第二の部分は、第一の部分で得られた最弱仮説をボトムとした概念ラティス上
での、
アルゴリズムを用いたトップダウン探索である。この部分では、
Kolmogorov Complexityを用いたコスト関数を用意し、それに従って、ア
ルゴリズムによる探索を行なう。概念ラティスは、包摂による順序づけがなさ
れている。そのラティスをトップダウンに探索するためには、一般的な節を特
化するためのrefinement operatorが必要となる。このようなrefinement
operatorとしては、ShapiroによるModel Inference Systemで用いられた、変
数の代入、ボディ部へのリテラルの付加などが知られているが、ここでは、最
弱仮説をボトムとしていることを積極的に利用して、このrefinementを行なう。
即ち、すべての仮説は、このボトムを包摂しなければならないので、仮説の取
り得るリテラルは、結局この最弱仮説中のリテラルを一般化したものとなる。
この方法により、概念ラティスの探索は、その選択肢が大幅に縮小され、その
上に、アルゴリズムを採用することによって、この探索は、大変高速に
行なわれる。
PROGOLのアルゴリズムの解明のために、現在我々は、P-PROGOLと呼ばれている 並列PROGOLのPrologによる実装を行なっている。KL1によるPPROGOLの実装は、 Prologによる実装を待って、早急に着手する予定である。
PROGOLは機能的にも機構的にも大変興味のあるプログラムであり、そのKL1 による実装は、実験的観点からも、あるいは、実用的観点からも、大変意義の ある研究開発であると思われる。