| 平成８年度 委託研究ソフトウェアの提案 |
PROGOLは、モード宣言、タイプ宣言、正事例、負事例、背景知識を入力とし、 背景知識と共に正事例を説明し、負事例を含まない仮説のうち最も簡潔なもの を生成する。PROGOLシステムは、大きく分けて二つの部分から成っている。
第一は、正事例の一つからその最弱仮説を生成する部分である。この計算は、 GentzenのReduction Theoremにより、実は、Consequence Finding Problemに 帰着することが知られている。そして、この問題は、MGTPを拡張して、演繹さ れる負の基底単位節をも計算することにより、容易に解決できることが知られ ている。これは、負リテラルを新たなリテラルと見倣すことによって、容易に 実現できることが確かめられた。そのようにして得られたすべての正負の基底 単位節から最弱仮説を生成するには、それらのand結合の否定を取ればよい。 ただし、単純なMGTPの利用によっては、効率良い処理が望めない。無駄なリテ ラルの生成を防いで効率の良い処理を実現するために、我々はモード宣言をマ ジック法に翻訳する方法を考えて、その実験を行なった。その結果、トップダ ウン実行とほとんど変わらない効率の達成に成功した。現在は、モード宣言情 報を利用して、背景知識をマジック変換する新たな方式を検討し、その方式の 正当性をほぼ検証した。
第二の部分は、第一の部分で得られた最弱仮説をボトムとした概念ラティス 上での、A* アルゴリズムを用いたトップダウン探索である。この部分では、 Kolmogorov Complexityを用いたコスト関数を用意し、それにしたがって、 A* アルゴリズムによる探索を行なう。概念ラティスは、包摂による順序づ けがなされている。そのラティスをトップダウンに探索するためには、一般的 な節を特化するためのrefinement operatorが必要となる。このような refinement operatorとしては、ShapiroによるModel Inference Systemで用い られた、変数の代入、ボディ部へのリテラルの付加などが知られているが、こ こでは、最弱仮説をボトムとしていることを積極的に利用して、この refinementを行なう。即ち、すべての仮説は、このボトムを包摂しなければな らないので、仮説の取り得るリテラルは、結局この最弱仮説中のリテラルを一 般化したものとなる。この方法により、概念ラティスの探索は、その選択肢が 大幅に縮小され、その上に、A* アルゴリズムを採用することによって、こ の探索は、大変高速に行なわれる。
この段階での重要な処理の一つに、仮説によってカバーされる正事例の検出、 および、負事例による制約条件のチェックがある。このためには、Prologと同 じ能力の定理証明器が必要となる。それは、Non-Ground MGTPの利用が考えら れる。
今年度の主要課題は、アルゴリズム全体の並列化である。アルゴリズム全体は、 前述した通り二つの部分からなっているが、これらを並列に実行することは出 来ない。各部分毎の並列化を達成する必要がある。前者は、MGTPをそのまま利 用できるので、すでに並列化は、確認済みである。後者については、A* ア ルゴリズムの並列化が問題となるが、可能な枝分かれについての計算は、並列 化が可能である。また、各枝についての正事例の包含チェック、ならびに負事 例の非包含チェックは、各正負事例毎に並列に実行して差し支えない。
並列化の具体的作業は、現在書かれているProlog版のPROGOLをKL1に書き直す 作業から始める。そして、実際に並列実行を行ない、その有効性を確認する。 並列マシンとしては、IBMで開発された汎用並列マシンＳＰ２を用いることと する。
PROGOLは機能的にも機構的にも大変興味のあるプログラムであり、そのKL1 による実装は、実験的観点からも、あるいは、実用的観点からも、大変意義の ある研究開発であると思われる。
PARALLEL-PROGOL
本ソフトウエアは、機能および特徴は、PROGOLとほぼ同じである。その機能は、 事例からの帰納推論機能である。帰納推論は、例からの一般化を行なう推論で あるが、本ソフトウエアの大きな特徴は、一階述語論理を表現言語として使用 している点である。このため、他の決定木を自動作成する帰納推論システムと 異なり、機械学習にドメインに関連した背景知識を利用することが出来る。こ の能力により、これまで手の付けられなかった多くの問題を機械学習の問題と して形式化し、実際に解を得ることが可能となった。いわば、第２世代の帰納 推論システムであると考えられる。その、応用領域は、プログラムの合成、文 法学習などの、古典的な機械学習問題から始まって、より規模の大きい問題と して、遺伝子のSecondary Structureの推定問題、新薬の合成問題、発ガン性 物質の同定問題などが、これまでに研究され、かなりの成果を挙げている。さ らに、今後は、自然言語理解、定性物理モデルの推定問題、技能などの暗黙知 の解明問題などへの応用が期待されている。第２世代の帰納推論システムの特 徴は、ある一つの対象物に関する属性値ばかりでなく、複数の対象物間の関係 をも考慮に入れることが出来る点である。このことから、例えば、構造体にお ける部品間の関連が問題となる有限要素法でのメッシュの最適な切り方を例か ら学習する試みなどもなされている。
本研究で開発されるPARALLEL-PROGOLは、PROGOLの並列化、高速化を目指し ている。即ち、本ソフトウエアの役割は、大規模な帰納推論問題の解決を行な うことである。このシステムに実現によって、これまで計算量の壁によって解 決できなかった、あるいは解決が困難であった帰納推論問題のうち、あるクラ スの問題は、解決が可能となるであろう。それによって、たとえば、データベー スからの知識発見への帰納論理プログラミングの応用が可能となり、データベー スから自動的に発見できる知識の質の大幅な向上が期待できる。従来は、関数 従属性などが発見されたに過ぎないが、より意味に立ち入った、データベース の要約なども可能となるであろう。
ソフトウェアは前述の通り大きく2つのパートに分けられる。第一は、正事例 の一つからその最弱仮説を生成する部分である。第二の部分は、第一の部分で 得られた最弱仮説をボトムとした概念ラティス上での、A* アルゴリズムを 用いたトップダウン探索である。
まず、モード宣言、タイプ宣言、正事例、負事例、背景知識を記述したファイ ルを用意し、PARALLEL-PROGOLへの入力とする。次に正事例からランダムに1つ を取り出し背景知識と共に正事例を説明し、負事例を含まない仮説のうち最も 簡潔な最弱仮説を生成する。この計算に、制約MGTPを利用して並列化を行なう。 第二の、概念ラティス上でのトップダウン探索の部分では、並列A* アルゴ リズムを用いる予定である。
PROGOLは、ある正事例から生成された仮説で説明が可能な正事例はその仮説で 一般化する。その仮説で説明されない正事例がある場合は、その正事例の中か ら新たな仮説を生成し、一般化する操作を繰り返す。この手続きを、すべての 正事例について検査されるまで行なう。現存する逐次型PROGOLではこのような 単純な Cover-set アルゴリズムを用いているが、PARALLEL-PROGOLにおいては、 複数の仮説の生成プロセスの並列化も考えられる。
本ソフトウエアは、既に述べたように、ICOTフリーソフトウエアに登録されて いるMGTPおよびCMGTPをその一部として利用する。
プログラミング言語としては、KL1を用いる。並列版は、 IBMの汎用並列コン ピュータSP２上で走らせることを想定している。必要とされるソフトウエア・ パッケージは、特にない（MGTP を用いるが、それらは、内部に組み込んだ形 で利用する）。KL1 の処理系の存在を仮定すれば、ポータブルである。
KL1プログラムとして、3,000行程度と想定される。
- このソフトウェアがとういった形で利用されるのか
本ソフトウエアの利用形態は、PROGOLの利用形態とほぼ同じであろう。即ち、 研究開発での利用では、本システムを実際に、仮説検証の手段として用いる。 実際に、データを取った後、そのデータの解析を行なうために、本システムを 使うことになるであろう。帰納推論システムをデータ解析手法と捉えると、そ の応用範囲は、大きな広がりを見せるはずである。即ち、これまで、統計的手 法のみに頼ってきた経済や心理分析なども、新たなデータ解析ツールとして本 システムを利用できるであろう。実際、PROGOLの実習は、大学院の講義に採り 入れているが、学生は、自分の身の回りの問題を探して、PROGOLによってデー タ解析を試みている。
さらに、より進んだ形では、埋め込み型のソフトウエアとして、他のシステ ムの一部に組み込まれて利用されるような状況も想定できる。いろいろな形で の、機械学習をベースにした最適化システムが、その例である。例えば、自動 パイロットシステムや、クレーンの自動操縦システムなどの制御システムでは、 最適な制御は、経験の積み重ねによって学んでいくが、本システムのような高 度で、かつ高速な帰納推論システムを用いることによって、その学習はオンラ インで行なえるであろう。
- 利用者へのセールスポイント
本システムは、新しい科学的発見を含む、帰納推論を可能とし、特に背景知識 を利用できるので、使い方の工夫によっていろいろなことが可能となる、大き な可能性を秘めたソフトウエアシステムである。従来のデータ解析手法では、 数値データの取り扱いには適していたが、非数値データに関しては、さまざま な数量化の手法を使いこなす必要があり、また、その結果の解釈もあまり直観 に訴えるものではなかった。PROGOLでのデータ解析は、その結果が人間にも理 解の出来るルールの形で得られるので、その利用価値は大きいと思われる。特 に、大規模で複雑な構造を持った帰納推論問題を扱う場合には、 PARALLEL-PROGOLは、大きな武器になるであろう。
ソフトウェア仕様書、プログラム・ソースリスト、ユーザマニュアル
www-admin@icot.or.jp