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

(9) 高速仮説推論システム

研究代表者:石塚 満 教授
      東京大学 工学部 電子情報工学科




[目次]

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


[研究の背景]

 仮説推論はアブダクション(発想的推論)の一種であり、宣言的表現下での 求解のメカニズムに立脚しているという基盤性、診断や解釈、設計という問題 に適用できるという実用性の両面で、今後の知識処理の重要な枠組みである。
宣言的知識表現による仮説推論は、推論の筋道をガイドする役割を果たす個別 的なヒューリスティックな知識を特に必要としないことから、現状の知識処理 の大きな課題である知識獲得の負担は大幅に軽減されることになる。
しかしながら、他の知識と矛盾する可能性を有する不完全な知識の使用に起因する非単 調推論系が必要になるため、低い推論速度が最大の問題となっていた。この問 題を克服し仮説推論を真に実用的知識処理手法とするために、我々は1988年か ら研究を推進し、これまでに
  1. 推論パスネットワークによる高速仮説推論法、
  2. 演繹データベース手法を利用した変数を含む述語論理表現に適用できる仮説推論法、
  3. 類推の利用による高速仮説推論法、
  4. 経験に基づく学習機能を備えた仮説推論法、
  5. 知識ベース・コンパイルによる高速仮説推論法、
  6. 0-1整数計画の近似解法を用いる準最適解計算の多項式時間仮説推論法、
  7. ネットワーク化バブル伝播法による準最適解計算の仮説推論法、
を創案、開発 してきた。仮説推論を含む非単調推論系の計算複雑度は1988年にNP 完全と証 明され、通常の推論法の範囲に滞っていたのでは問題規模に対して指数的に増 大する推論時間の壁を克服できないが、上記3)、4)は人工知能的アプロー チにより、また5)、6)、7)はより計算科学的アプローチにより、この問 題を克服する方途を示したものと位置づけられる。

[研究の目的]

仮説推論の枠組みは非常に有用であるにもかかわらず広く使用されるに至っ ていない主要な要因は、速度の問題が克服されていなかったことによるといえ る。
本研究では、上記の高速仮説推論法の成果を広く使用できる形態のソフト ウェアツール化し、新しい知識処理の枠組みの利用拡大を可能にすることを目 的とする。特に、可能な要素仮説に数値的な重みを付し、この重みの和(コス ト)の最小な解仮説を求める重み付き(あるいはコストに基づく)仮説推論に 焦点を当て、我々が開発してきた準最適解を多項式時間で求める仮説推論法の ツール化を図る。
命題論理表現版だけでなく、より豊かな表現能力を提供する 述語論理版(領域限定の述語ホーン節)の重み付き仮説推論に対して、準最適 解計算の多項式時間推論システムを作成する。

[研究の内容]

 知識処理の問題に限らず、NP完全、NP困難な問題に対して効率的 (tractable)な近似解法を明らかにすることは、計算アルゴリズム研究一般に ついて極めて重要な方向である。我々が最初に開発した重み付き仮説推論に対 する準最適解計算の多項式時間推論法は、0-1整数計画の非常に良い近似解 法である E.Balas による掃出し補数法(pivot and complement method)を利用 したものであった。これは仮説推論の問題を、ゴールの証明に関連する知識部 分のみを切り出してまず数理計画の問題に変換し(制約知識の不等式表現)、 実数領域での最適解を効率的な単体法(simplex method)で求める。そして、こ の最適実数解の近傍を巧妙な方法で局所探索して(準)最適な0-1整数解を 見い出す。インプリメントしたシステムによる実験的評価では、可能な要素仮 説数をNとすると、Nの約4乗のオーダの多項式時間で準最適解を求めることが でき、かつ得られる準最適解も非常に良いものである。ここで準最適解とは、 解仮説に含まれる要素仮説の重みの和が必ずしも最適(最小)でないという意 味であり、ゴールを証明するのに十分な無矛盾な仮説の組という論理的制約を 満たす解である。

この手法は知識処理の推論問題を整数計画の土俵に移して解いたも のだが、このままでは内部の動作がブラックボックス的になってしまい、知識 の構造を利用した更なる改善が難しい。そこで、次に創案、開発したのがネッ トワーク化バブル伝播法である。これは掃出し補数法と等価な動作をネットワー ク化した知識上で動作させて目に見える形にし、かつ知識構造を利用して効率 の改善も実現した手法である。インプリメントしたシステムによる実験的評価 では、Nの2乗オーダ以下の多項式時間推論を達成している。このネットワー ク化バブル伝播法は、述語論理表現(領域限定述語ホーン節)の仮説推論へも 適用できるように拡張を図っている。この拡張では推論の深さの段階的拡大と 共に、我々の先行研究の成果を活用して、演繹データベースの手法であるQSQR 法の利用による冗長な推論の排除のメカニズムを取り入れている。

 人工知能分野では確率的に準最適解を求める手法としてシミュレー テッドアニーリング(SA)法や遺伝的アルゴリズム(GA)があるが、本研 究の手法はこれらとは異なり、一定の見通しを持った準最適解の高速探索法に なっている。また最近では局所探索法の有効性が再認識されてきており、制約 充足問題(CSP)や3-SATに対してHeuristic Repair MethodやGSAT法が 開発されている。本研究の手法は、単体法により最適実数解という非常に良い 初期値(initial guess)を得ること、探索の過程で多次元多面体中の0-1整数 値の位置だけでなく、その中間的な位置も取るという点でこれらにはない特色 を有している。特に推論の初期フェーズで用いる単体法は、多くの情報を総合 して素早く妥当な解を導く人間の直観的推論のコンピュータ上での実現に相当 しているとも言えるものである。

 このように優れた効率を有する重み付き仮説推論法の原理と共に、 これまでにC言語により試作システムの作成を行なってきた。このソフトウェ アは推論速度の点では優れた性能を示しているものの、使用する仮想記憶領域 が200MBと大きすぎる点、ユーザインタフェースの点で不十分である。述語論 理表現を扱うには論理型プログラムの使用が適するので、論理型プログラムと 我々のC言語で再インプリメントするネットワーク化バブル伝播法を組み合わ せ、本研究でユーザインタフェースにも配慮して広く利用できる形態のソフト ウェアツールとしてまとめる。


[ソフトウェア成果]

(1)作成されるソフトウェア名称
KICK-NBP(仮称)
(Knowledge-base handling InComplete Knowledge -- Networked Bubble Propagation version)

(2)そのソフトウェアの機能/役割/特徴
述語論理(領域限定述語ホーン節)表現の重み付き(又はコスト付 き)仮説推論における準最適解を多項式時間で求める推論システムである。仮 説は基礎代入された単節の述語リテラルであり、数値的な重みを付すことがで きる(重みのデフォルト値は1)。ルールを仮説にすることもできるが、これ は単節の仮説述語を導入し、仮説でない背景知識となるルールと、単節の仮説 述語に変換できる。背景知識は矛盾の可能性を有しないのに対し、仮説は矛盾 の可能性を有する知識であり、矛盾は'inc'アトム(inconsistentの略でATMSの nogoodに相当)を満たす条件によって定義する。推論のゴールを与えると、こ のゴールの証明に必要な重みの和(これをコストと定義する)の最小の無矛盾 な要素仮説の集合(最適解仮説)を求める。常に厳密な最適解仮説を求めるよ うにすると、問題のNP完全性により最悪値で指数オーダの推論時間になってし まうことから、創案したネットワーク化バブル伝播法により準最適解を多項式 時間で求める。

 ネットワーク化バブル伝播法の特徴は、単体法により実数領域の最 適解である探索の初期値を非常に効率的に決定し、0-1整数計画法の大変良 い近似解法である掃出し補数法に準拠の局所探索動作をネットワーク化した知 識上で動作させるようにし、更に知識構造を利用して効率の改善を図っている ことである。豊かな表現力を提供する述語論理表現を扱う独自な拡張を実現し ていることも特徴である。

 制約充足やATMS等のツールは存在しているが、問題がNP完全である ために、いずれも問題規模の拡大につれて指数的に増大する推論時間が大きな 問題になっていた。本研究の仮説推論システムでは、重み付き仮説推論システ ムとして必ずしも最適解でない準最適解を求めるようにすることにより、問題 規模に対して多項式時間で解を得るという実用性を有する。人間も複雑な問題 に対しては必ずしも最適解を求めるのでなく、実用的時間内で準最適解を求め て対処しており、準最適解を求めることはこのような人間の行動に準拠してい るともいえる。

 更に、関係の記述を許すことで豊かな表現能力を持つ述語論理表現 の知識を扱うことができる。また通常プロダクションシステムと結合して使用 されるATMSと異なり、論理を基盤とする問題解決機構であり、推論の筋道をガ イドする役割を果たす知識の記述を要しない。



www-admin@icot.or.jp