平成7年度 委託研究ソフトウェアの提案 |
その言語を命題論理から一階述語論理に拡張することによって、表現力が大 幅に拡張されることが予想される。これまでは、それに伴う処理効率の低下が あまりにも著しいため、この拡張は実用の観点から日の目を見なかったが、最 近の研究の著しい発展によって、それが実用になりつつある。
一階述語論理への拡張は、背景知識の利用を可能にする点で、画期的なもの である。この機能により、知識の連続的な獲得が可能となり、システムに成長 機能を持たせることが出来る。また、十分な背景知識を準備することによって、 これまで処理できなかった問題に対処できるようになり、かなり困難な学習問 題を扱えるようになった。即ち、帰納論理プログラミングが、今後、論理プロ グラミングのアプリケーションとして、大変重要になると予想される。
ところが、表現力の強化は、実行効率の犠牲を伴う。そのため、その実用化 のための条件として、システムの高速化が強く望まれている。例えば、データ ベースからの知識発見などへの応用を考えると、たちまち計算量の壁が問題と なってくる。それが帰納論理プログラミングの並列化の要請が生まれてくる理 由である。
帰納論理プログラミングシステムは、FOIL (Quinlan), CIGOL (Muggleton and Buntine), GOLEM (Muggleton), PROGOL (Muggleton and Srinivasan)などが知 られているが、この中で、機能的にも、効率面でも、PROGOLが最も優れている。 機能的には、PROGOLは、背景知識として、基底単位節以外にも、任意のホーン 節を用いることが出来る。これによって、背景知識の記述力が大幅に向上した。 また、PROGOLは、最特殊仮説をボトムとした概念ラティス上での、A*アルゴリ ズムを用いたトップダウン探索を用いており、効率面でも大変優れている。
以上のような理由により、本研究では、並列化の対象として、PROGOLを取り 上げる。
さらに、その並列PROGOLを用いて、機械学習の各種のベンチマーク問題を初 め、データベースからの知識発見や、プログラムの自動合成、技能獲得などの 問題の解決を試み、その有用性の実証を行なう。
PROGOLは、モード宣言、タイプ宣言、正事例、負事例、背景知識を入力とし、 背景知識と共に正事例を説明し、負事例を含まない仮説のうち最も簡潔なもの を生成する。PROGOLシステムは、大きく分けて二つの部分から成っている。第 一は、正事例の一つからその最特殊仮説を生成する部分である。この計算は、 GentzenのReduction Theoremにより、実は、Consequence Finding Problemに 帰着することが知られている。そして、この問題は、MGTPを拡張して、演繹さ れる負の基底単位節をも計算することにより、容易に解決できることが知られ ている。また、ICOTで開発されたMGTPの一つの版であるCMGTPには、すでにこ の機能が備わっており、これを直接利用することが可能である。そのようにし て得られたすべての正負の基底単位節から最特殊仮説を生成するには、それら のand結合の否定を取って、さらに、変数の導入による一般化、および冗長な リテラルの除去を行なえばよい。ただし、冗長なリテラルの除去については、 定理証明問題として考えると決定不能な問題に直面するので、発見的な手法に よらざるを得ない。
第二の部分は、第一の部分で得られた最特殊仮説をボトムとした概念ラティス 上での、A*アルゴリズムを用いたトップダウン探索である。この部分では、 Kolmogorov Complexityを用いたコスト関数を用意し、それにしたがって、A* アルゴリズムによる探索を行なう。概念ラティスは、包摂による順序づけがな されている。そのラティスをトップダウンに探索するためには、一般的な節を 特化するためのrefinement operatorが必要となる。このようなrefinement operatorとしては、ShapiroによるModel Inference Systemで用いられた、変 数の代入、ボディ部へのリテラルの付加などが知られているが、ここでは、最 特殊仮説をボトムとしていることを積極的に利用して、このrefinementを行な う。即ち、すべての仮説は、このボトムを包摂しなければならないので、仮説 の取り得るリテラルは、結局この最特殊仮説中のリテラルを一般化したものと なる。この方法により、概念ラティスの探索は、その選択肢が大幅に縮小され、 その上に、A*アルゴリズムを採用することによって、この探索は、大変高速に 行なわれる。
この段階での重要な処理の一つに、負事例による制約条件のチェックがある。 即ち、負事例を満足するような仮説を排除する必要がある。このためには、負 事例を含めた論理式の無矛盾性を調べる必要がある。もし無矛盾であれば良い が、矛盾した場合には、その仮説は(誤りを許さないという仮定の下で)除去 されなければならない。このためには、Prologと同じ能力の定理証明器が必要 となる。それは、Non-Ground MGTPの利用が考えられる。
PROGOLのアルゴリズムの解明のために、現在我々は、P-PROGOLと呼ばれてい るPROGOLのPrologによる実装について、検討を開始している。
並列度に関しては、今のところ目論みがあるわけではない。アルゴリズム全体 は、前述した通り二つの部分からなっており、これらは、並列化は出来ない。 各部分毎の並列化を達成する必要がある。前者は、CMGTPをそのまま利用でき るので、すでに並列化は、確認済みである。後者については、A*アルゴリズム の並列化が問題となるが、可能な枝分かれについての計算は、並列化が可能で ある。また、各枝についての負事例の非包含チェックは、各負事例毎に並列に 実行して差し支えない(厳密にいえばこのことは成り立たないかも知れないが、 ここでは、そのような病的な状況は考えない)。
PROGOLは機能的にも機構的にも大変興味のあるプログラムであり、そのKL1 による実装は、実験的観点からも、あるいは、実用的観点からも、大変意義の ある研究開発であると思われる。
本研究で開発されるPARALLEL-PROGOLは、PROGOLの並列化、高速化を目指し ている。即ち、本ソフトウエアの役割は、大規模な帰納推論問題の解決を行な うことである。このシステムに実現によって、これまで計算量の壁によって解 決できなかった、あるいは解決が困難であった帰納推論問題のうち、あるクラ スの問題は、解決が可能となるであろう。それによって、たとえば、データベー スからの知識発見への帰納論理プログラミングの応用が可能となり、データベー スから自動的に発見できる知識の質の大幅な向上が期待できる。従来は、関数 従属性などが発見されたに過ぎないが、より意味に立ち入った、データベース の要約なども可能となるであろう。
www-admin@icot.or.jp