平成7年度 委託研究ソフトウェアの提案

(7) KL1 による PROGOL の並列化に関する研究

研究代表者:古川 康一 教授
      慶應義塾大学 大学院 政策・メディア研究科




[目次]

  1. 研究の背景
  2. 研究の目的
  3. 研究の内容
  4. ソフトウェア成果


[研究の背景]

帰納論理プログラミングは、帰納推論と論理プログラミングを統合した新たな 学問領域であり、帰納推論を一階述語論理の上で展開する強力なアプローチで ある。従来、経験学習の主流は、ID3や、C4.5などに見られる決定木の自動作 成を行なうものであった。これらの帰納推論システムの特徴は、属性および属 性値の対の並び、およびその所属クラスからなる例の集合を与えて、各例がど のクラスに属するかを属性に対する条件比較を繰り返して判定する決定木を自 動作成する点である。その判定は、命題論理式で表されることが知られている。 また、各例も命題論理式で表せる。すなわち、決定木自動作成システムは、命 題論理に基づく帰納推論システムである。

その言語を命題論理から一階述語論理に拡張することによって、表現力が大 幅に拡張されることが予想される。これまでは、それに伴う処理効率の低下が あまりにも著しいため、この拡張は実用の観点から日の目を見なかったが、最 近の研究の著しい発展によって、それが実用になりつつある。

一階述語論理への拡張は、背景知識の利用を可能にする点で、画期的なもの である。この機能により、知識の連続的な獲得が可能となり、システムに成長 機能を持たせることが出来る。また、十分な背景知識を準備することによって、 これまで処理できなかった問題に対処できるようになり、かなり困難な学習問 題を扱えるようになった。即ち、帰納論理プログラミングが、今後、論理プロ グラミングのアプリケーションとして、大変重要になると予想される。

ところが、表現力の強化は、実行効率の犠牲を伴う。そのため、その実用化 のための条件として、システムの高速化が強く望まれている。例えば、データ ベースからの知識発見などへの応用を考えると、たちまち計算量の壁が問題と なってくる。それが帰納論理プログラミングの並列化の要請が生まれてくる理 由である。


[研究の目的]

本研究の目的は、KL1によって、帰納論理プログラミングシステムを実装し、 その並列化を図ることである。

帰納論理プログラミングシステムは、FOIL (Quinlan), CIGOL (Muggleton and Buntine), GOLEM (Muggleton), PROGOL (Muggleton and Srinivasan)などが知 られているが、この中で、機能的にも、効率面でも、PROGOLが最も優れている。 機能的には、PROGOLは、背景知識として、基底単位節以外にも、任意のホーン 節を用いることが出来る。これによって、背景知識の記述力が大幅に向上した。 また、PROGOLは、最特殊仮説をボトムとした概念ラティス上での、A*アルゴリ ズムを用いたトップダウン探索を用いており、効率面でも大変優れている。

以上のような理由により、本研究では、並列化の対象として、PROGOLを取り 上げる。

さらに、その並列PROGOLを用いて、機械学習の各種のベンチマーク問題を初 め、データベースからの知識発見や、プログラムの自動合成、技能獲得などの 問題の解決を試み、その有用性の実証を行なう。


[研究の内容]

本研究は、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 による実装は、実験的観点からも、あるいは、実用的観点からも、大変意義の ある研究開発であると思われる。


[ソフトウェア成果]

(1)作成されるソフトウェア名称
PARALLEL-PROGOL

(2)そのソフトウェアの機能/役割/特徴
本ソフトウエアは、機能および特徴は、PROGOLとほぼ同じである。その機能は、 事例からの帰納推論機能である。帰納推論は、例からの一般化を行なう推論で あるが、本ソフトウエアの大きな特徴は、一階述語論理を表現言語として使用 している点である。このため、他の決定木を自動作成する帰納推論システムと 異なり、機械学習にドメインに関連した背景知識を利用することが出来る。こ の能力により、これまで手の付けられなかった多くの問題を機械学習の問題と して形式化し、実際に解を得ることが可能となった。いわば、第2世代の帰納 推論システムであると考えられる。その、応用領域は、プログラムの合成、文 法学習などの、古典的な機械学習問題から始まって、より規模の大きい問題と して、遺伝子のSecondary Structureの推定問題、新薬の合成問題、発ガン性 物質の同定問題などが、これまでに研究され、かなりの成果を挙げている。さ らに、今後は、自然言語理解、定性物理モデルの推定問題、技能などの暗黙知 の解明問題などへの応用が期待されている。第2世代の帰納推論システムの特 徴は、ある一つの対象物に関する属性値ばかりでなく、複数の対象物間の関係 をも考慮に入れることが出来る点である。このことから、例えば、構造体にお ける部品間の関連が問題となる有限要素法でのメッシュの最適な切り方を例か ら学習する試みなどもなされている。

本研究で開発されるPARALLEL-PROGOLは、PROGOLの並列化、高速化を目指し ている。即ち、本ソフトウエアの役割は、大規模な帰納推論問題の解決を行な うことである。このシステムに実現によって、これまで計算量の壁によって解 決できなかった、あるいは解決が困難であった帰納推論問題のうち、あるクラ スの問題は、解決が可能となるであろう。それによって、たとえば、データベー スからの知識発見への帰納論理プログラミングの応用が可能となり、データベー スから自動的に発見できる知識の質の大幅な向上が期待できる。従来は、関数 従属性などが発見されたに過ぎないが、より意味に立ち入った、データベース の要約なども可能となるであろう。



www-admin@icot.or.jp