next up previous
Next: 参考文献 Up: 「高度問題解決のための推論プログ ラムの開発」に関する成果概要 Previous: 研究の内容

研究の成果

研究上の成果

ALP処理系の性質

今回開発した「ALP処理系(Prolog 版)」の特徴としては以下の点が挙げられる。 扱うプログラムのクラスの広さ一つの処理系で扱えるプログラムのクラスが過 去に提案されたいかなる手続きよりも広い。最も一般的なクラスである、「ア ブダクティブ選言付き拡張プログラム(abductive extended disjunctive program)」においては、失敗による否定(NAF)とアブダクションのための仮定 可能リテラルを扱えること以外に、従来の論理プログラムにはない、論理否定 (classical negation)とヘッドの選言(disjunction)が記述可能である。すな わち各ルールは、

と表すことができる( は正または負 のリテラルであり仮定可能リテラルであってもよい)。さらに各ルールは値域 限定性の条件の下で変数を含んでいてもよい。不動点意味論に基づくボトムアッ プ計算MGTPにおける分岐計算のためのプログラム変換の正当性(健全性と完全 性)は、Inoue and Sakamaによる不動点意味論 [1]により保証されている。

モジュラ変換ALP処理系の「一階述語コンパイラ」では、ALPの各ルールに対し て、一つずつMGTP節に変換する。すなわち、変換方式はモジュラ(modular)で ある。これより、プログラムサイズの線形オーダーの時間で変換が可能であり、 変換によるオーバーヘッドが極めて少ない。

ALP処理系の性能評価

まずALP処理系を、アブダクションの例題である論理回路設計問題で評価した ところ、これに関しては所望の結果を得ることができた。次に、NAFの処理速 度を評価するために、最近提案されたベンチマーク問題やグラフ理論のNP完全 問題に適用した。また処理系に最適化を加える前後の結果と、海外で提案され ている他の方式を比較した。

この結果の一部を表１に示す。このプログ ラムは安定モデルを持たない例であり、時間は安定モデルを持たないことがわ かるまでの時間である。表中のConstantsはエルブラン領域の要素の数である。 

          s(X) <- p(X), q(X).      s(X) <- p(X), r(X).
          s(X) <- q(X), r(X).      p(X) <- not q(X).
          q(X) <- not r(X).        r(X) <- not p(X).
  

表１： benchmark program 2, no stable model
Constants
ALP改良前
ALP改良後
DeReS
Smodels
SLG
Dislog
10
*
0.03
*
0.10
0.21
*
20
*
0.04
*
0.16
0.40
*
30
*
0.06
*
0.17
0.59
*
40
*
0.08
*
0.22
0.81
*
50
*
0.10
*
0.27
1.01
*
100
*
0.20
*
0.43
2.12
*

比較対象システムは以下の通りである。いずれもアブダクション機能は持たな い。NLPとDLではヘッドの選言も扱えない。DLはReiterのデフォルト論理が扱 える。

DeRes Cholewinski, Marek,Mikitiuk, and Truszczynski, 1995 命題ＤＬ
Smodels Niemela and Simons, 1995 命題ＮＬＰ
SLG Chen and Thone, 1994 一階ＮＬＰ
Dislog Seipel and Thone, 1994 一階ＮＤＰ

ALP(改良前と改良後)の実行時間は、MGTPの戦略IIを用いた時間であり、これ は３つの戦略の中でもっとも高速であった時間である。改良前ではMGTPでの分 岐数が爆発し計算が１時間以内に終了しない(*印)のに対し、改良後では安定 モデルを持つかどうかを判定するのに時間がほとんどかかっていない。これは、 最適化においてNAFについて導入した負節が有効であったためである。また、 他のシステムと比較してもまったく遜色が見られない。

ソフトウェアとしての成果

ソフトウェア構成の概要

ALP処理系のプログラム構成を図１に示す。 ALP処理系は、ALPからMGTPの入力節への変換器である「一階述語コンパイラ」、 推論エンジンとなるモデル生成型定理証明器MGTP、そしてMGTPの出力を処理系 の枠組に変換するモジュールから構成される。このモジュールでは、安定モデ ルや信念モデルの処理に対するものと、問合せや観測への解代入や説明計算の 処理に対するものの２つを用意した。

  
図１: ALP処理系(Prolog版)の構成概念図

ソフトウェアの特長

ALP処理系では、ALPの信念集合をボトムアップに計算するほか、 ALPに対する質問応答が可能であり、 与えられた質問に対して条件となる仮説(すなわち説明)を付けて解を返す 「アブダクション機能」を有する。その他の機能もかなり豊富である。 以下に機能をまとめる。

  1. アブダクションを行なわない場合
    安定モデルを１つ返す/安定モデルをすべて返す/あるゴール:Gを 満たすモデルが存在するか(yes,no)判定する/ あるゴール:Gを満たす モデルを１つ返す/ あるゴール:Gを満たすモデルをすべて返す/ ある ゴール:Gがすべてのモデルで満たされるか(yes,no)判定する
  2. アブダクションを行なう場合
    信念モデルを１つ返す/ 信念モデルをすべて返す/ ある観測:Oを 満たすモデルが存在するか(yes,no)判定する/ ある観測:Oを満たすモ デルを１つ返す/ ある観測:Oを満たすモデルの説明を１つ返す/ ある 観測:Oを満たすモデルをすべて返す/ ある観測:Oを満たすモデ ルの説明をすべて返す/ ある観測:Oがすべてのモデルで満たされるか (yes,no)判定する/ プログラムで観測が与えられている場合はその最小の説明 をすべて返す
  3. 共通の機能
    MGTPによりプログラムの充足可能性(sat,unsat)を判定する/ MGTPにより 出力されるモデルを１つ返す/ MGTPにより出力されるモデルの数とそれらのモ デルをすべて返す
上記の機能はいずれも、解代入を返すことも可能である。モデルを１つ返す場 合には、Prolog同様、応答の後にセミコロン(;)を入力することにより他の解 を求めることができる。

残された課題

今回実現したALP処理系では、安定モデル計算の効率化のための各種の最適化 を行っている。これにより、計算時間の短縮からもかなりの効率化が認められ た。とくにDislogやDeReSなど汎用性のあるシステムと比較すると、かなり良 好な結果が得られた。しかし、その他の専用システム、特にSmodelsやSLGでは、 いくつかの例題において本ALP処理系よりもまだかなり速い結果を出している。 よって、NAFの処理においてさらなる効率化が必要である。

またアブダクションの計算における効率化では、「太田・井上・長谷川・中島」 による、枝刈りルールによる効率化が提案されている。しかしこの方法は Abductive Horn Programに対するものであり、NAFの入ったプログラムについ ては考慮されていない。よってALPに対する枝刈りルールの整備も課題である。

また本システムの推論エンジンであるMGTPのさらなる効率化の必要性も感じら れた。

なお本研究は２年計画のものであり、２年目の計画として予定しているテーマ として、状態変化が記述・推論できるアクション言語の処理系の開発も残され ている。ALP処理系の機能をフルに発揮させるためにも、アクション言語への 応用は必須である。

成果についての自己評価

ALPに対する一階述語コンパイラの変換方式の理論的正当性については保証さ れていたので、今回それを素直にインプリメントした。そして今年度の研究目 標であった「ALPのProlog処理系」が無事実現され、豊富な機能を有し、正し く動作するものが出来た。しかし、1995年以降発表され始めた海外の他のシス テムとの比較に至って、論文通りの実現だけでは限界を感じた。そこで当初予 定よりも大幅に評価・改良に時間を費やすことになった。その結果には概ね満 足している。まだ一部の問題で本ALP処理系のサブシステムよりも速いものが ある以上、改良をさらに続ける必要があると思っている。MGTP本体もまだ改良 の余地は多い。


www-admin@icot.or.jp