研究上の成果
本研究を通して、得られた成果は、MGTPを利用したPROGOLの新実装の可能性を 明らかにしたことである。これは、PROGOLという、大変複雑で、高度な機能を 有するソフトウエアを並列化できる見通しが得られた、という意味で、重要な 成果であると考えられる。さらに、得られたアルゴリズムは、元のアルゴリズ ムに対して、その記述レベルが高く、理解も容易である。
我々は、まず、現在のPROGOLのアルゴリズムを詳細に検討し、その全貌を明ら かにした。そして、MGTPを用いたボトムアップ計算による新たなアルゴリズム を検討し、その可能性を追求した。従来、PROGOLでは、最弱仮説の生成を、モー ド宣言によって定義される可能な述語を列挙して調べる方法をとっていたが、 ここでは、それをMGTPによる帰結発見問題と定義して、ボトムアップ計算によ る解法を得た。具体的には、モード宣言の情報を利用した、不必要なモデル要 素の生成を抑制するための制御節を各モード宣言毎に導入した。この特別な制 御節の働きにより、本来ならば領域述語domを用いて生成すべきモデル要素を、 モード宣言によって必要とされるもののみに制限することに成功した。
また、最適な仮説を求めるための探索アルゴリズムについては、元々のPROGOL 同様、A*アルゴリズムを採用しているが、そこで用いられるコストの推定を行 なう新たな、より精度の良い関数を導入した。そして、この関数自身をMGTPに よって実装できることを発見した。
現在までに、既存のPROGOLシステムのアルゴリズムを解明し、その並列版であ るPPROGOLの実装を開始した。はじめに、PPROGOL全体をPrologによって実装を 行ない、次に、それをKL1によって記述する、という手順を踏むこととした。 現在までに、Prologによる実装をほぼ完了した。
解決すべき問題としては、Prologによる実装のデバッグ、および、KL1による 実装が残されている。さらに、実際に並列性を引きだし、効率の良い実装を実 現するという、大きな課題が残されている。
ソフトウェアとしての成果
まず、PROGOLの第一フェーズである、正事例の一つからその最弱仮説を生成す る部分について、MGTPを利用するための方式検討を行なった。
MGTPでは、一般に値域限定条件のために導入されたdomに関わる計算が組合せ 的爆発を起こす場合があり、これへの対処が大きな課題である。これに関して は、検討の結果、マジックセット法によりエレガントに解決できることが判明 した。
最弱仮説は、背景知識と正事例の否定から得られる全ての正負の基礎リテラル を求め、その否定を取ることによって得られるが、その計算は閉包計算の枠組 によって捉えることができ、むしろMGTPのようなボトムアップ型計算の方が馴 染みがよいと考えられる。特に全解計算についてはMGTPでは自然に実現されて いる。
以上の検討を踏まえ、Prolog版のMGTPによる実験、KL1版のMGTPによる実験、 各版のMGTPをPPROGOL用に特化/調整する作業などを進めた。その結果、基本的 にMGTPによる最弱仮説の生成が妥当に行なえることが示された。
計算ステップすなわち推論の深さの限定に関しては、MGTPのh容易性は単純に 超レゾリューションの回数として定義することとし、これによるProlog版 PROGOLとの齟齬は、ユーザレベルでの所与パラメタの調整という形で解消する ことにした。
次に、最弱仮説をボトムとした概念ラティス上でのA*サーチによるトップダウ ン探索において、現ノードからゴールまでの距離の推定値の計算に対しても MGTPが利用可能であることを示した。PROGOLではサーチ中の候補仮説の頭部リ テラルの入出力変数間の関係を完成させるために本体に加えなければならない 残りリテラルの数を、この推定値として定義しているが、新実装では、最弱仮 説の変数間の連結関係を元に、最弱仮説内のリテラル間の連結関係を AND-OR グラフで表現し、最弱仮説の頭部リテラルから、ゴール変数を含む本体リテラ ルに至る、グラフ内の、一般的に複数のパス(パス集合)を求める。最弱仮説の 各リテラル内の変数の入出力関係を、入力変数を前件、出力変数を後件にした MGTP節で表現し、頭部リテラルにある入力変数を初期モデルとしてMGTPを走ら せ、ゴール変数を表すモデルが要素が生成されるまでにどの節を適用したかを 計算することでパス集合が計算される。
以上の検討結果を元に、現在、PPROGOLのPrologバージョンをほぼ完成させ、 そのデバッギングを行なっている。ソフトウェア構成の概要図を以下に示す。
残された課題
今後は、KL1によるプログラミング、および、その並列化を行なう。KL1による プログラミングは、当初、本年度中に行なう予定であったが、スケジュールの 多少の遅れにより、来年度にずれ込む見通しである。並列化については、他大 学に設置されているPIMの利用を検討したい。また、本学に新たに設置された SP2の利用も合わせて考えている。
上記２つの成果についての自己評価
研究上の評価は、十分に満足すべきものである。とくに、MGTPを利用した PROGOLの新実装は、アイディアが独創的であり、かつ、得られた成果は、学術 的に見ても、価値のある結果となっていると考えられる。モード宣言のMGTPの 入力節への翻訳は、最も画期的で、かつエレガントな成果であると考えられる。 そこでは、マジックセットの方法も駆使しており、MGTPの応用のレベルが高度 である。今後は、この成果を論文の形にして、まとめていきたい。
ソフトウエアとしての評価は、KL1の実装が完了しなかった点で、計画通りの 成果が得られなかったが、Prologによる実装は、順調に進んでおり、そこから KL1への翻訳は、それほど大きな問題はないものと思われる。