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に対する質問応答が可能であり、 与えられた質問に対して条件となる仮説(すなわち説明)を付けて解を返す 「アブダクション機能」を有する。その他の機能もかなり豊富である。 以下に機能をまとめる。

    -2pt
  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