JPH0512017A

JPH0512017A - 非単調推論型エキスパートシステム

Info

Publication number: JPH0512017A
Application number: JP3161233A
Authority: JP
Inventors: Akihiko Koga; 明彦古賀
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1991-07-02
Filing date: 1991-07-02
Publication date: 1993-01-22

Abstract

(57)【要約】【目的】問題解決のための膨大な探索空間を持つＡＴ
ＭＳにおいて、効率良く探索範囲を絞り込み、高速に解
を得る。【構成】それぞれのワーキングメモリに、該ワーキン
グメモリの内容を表す複数の記号からなる第１のタグ
を、また、推論エンジンに、上記それぞれのワーキング
メモリの内容を表す全ての記号の内で、該推論エンジン
が処理の対象とする複数の記号からなる第２のタグを付
与し、該推論エンジンは、第２のタグに含まれる記号か
らなる第１のタグを有するワーキングメモリのみを、推
論の対象とし、また、推論対象以外のワーキングメモリ
を、ラベル伝播の対象から外す。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、多くの解構成を有する
計画問題などにおいて、大量の仮説を用いて非単調推論
を行なうエキスパートシステムに係わり、特に、探索空
間の絞り込みを効率良く行ない、結論を高速に導くのに
好適な非単調推論型エキスパートシステムに関するもの
である。

【０００２】

【従来の技術】従来、コンピュータを利用し、専門的知
識を有効に用いて種々の問題を解決するエキスパートシ
ステムにおいて、非単調推論に基づくものが提供されて
いる。この非単調推論に基づくエキスパートシステム
は、演繹的推論では対処できない、欠如した情報による
推論等のように、不完全な知識に基づく推論を進めるも
のであり、エキスパートシステムの適用分野を一層拡大
し、より実用に耐えるものとすることができる。非単調
推論に基づくエキスパートシステムには、ＴＭＳ（Trut
h MaintenanceSystem）やＡＴＭＳ（Assumption-based
Truth Maintenance System）等がある。ＴＭＳは、
推論の各ステップを保存することにより、推論の制御、
仮説（真にも、偽にもなりえるデータ）の採択や破棄、
破棄されていた仮説の復活という非単調論理、仮説推論
に必要な機能を提供し、さらに、推論に使用する知識ベ
ースを状況の変化を反映させながら一貫性を保持する知
識管理のための機能を提供する。ＴＭＳで同時に扱える
仮説の組合せは１つだけであるが、ＡＴＭＳは、複数の
仮説の組合せの取扱いを可能とした。ＡＴＭＳは、仮説
の組合せ毎に、それぞれ１つのワーキングメモリを構成
し、それぞれのワーキングメモリは、仮説の組み合わせ
の包含関係によりラティス（格子型配列）を構成する。
例えば、あるデータＤが、ある仮説の組み合わせＷ
｛Ａ，Ｂ，Ｃ｝から導かれる時、そのデータＤは、ワー
キングメモリＷで成立するという。また、ＡＴＭＳは、
全てのデータに、そのデータが成立する仮説の組み合わ
せ（ワーキングメモリ）の集合を関連付ける。このワー
キングメモリの集合をラベルと呼び、そして、ＡＴＭＳ
は、矛盾の出た仮説の組合せを記録し、それを他のワー
キングメモリが利用することにより、探索空間の絞り込
みを行い、推論の効率化を図る。

【０００３】ＡＴＭＳに関して、以下、さらに詳しく説
明を行う。従来のエキスパートシステムにおいて、例え
ば、計画問題に対するアプローチとしては、ドゥ・クレ
アによる論文「仮説に基づいた真理の管理機構（ＡＴＭ
Ｓ：An assumption-based truth maintenance syste
m）」（１９８６年、学会誌アーティフィシャルインテ
リジェンスの第２８巻の第１２７頁から第１６２頁（Jo
han de Kleer，An assumption-based truth maintenanc
e system，Artificial Intelligence Vol.28，1986,Els
evier Science Publishers B.V.,pp.127〜162）に記載
のエーティーエムエス（ＡＴＭＳ）がある。ＡＴＭＳで
問題を解く場合、真にも、偽りにもなりえるデータを仮
説としてＡＴＭＳに入力し、「ｉｆ条件ｔｈｅｎ結論」
の形のルールによる推論を行う。ＡＴＭＳは、ルールの
推論によって生成されたデータに、それがどのような仮
説の組合せのもとで成立するかという情報を記録する。
ＡＴＭＳを用いたエキスパートシステムでは、このよう
な推論を繰り返し、最終的に、望むデータが導出された
仮説の組合せを解とする。以下、計画問題を抽象化した
次の例題でＡＴＭＳの動作を説明する。次の変数ｘ，
ｙ，ｚが用意されているとする。ｘ：｛５，６｝ｙ：｛４，６，８｝ｚ：｛４，７，８｝変数の右側に書かれている集合はそれぞれの変数が取り
得る値の集合である。いま、全ての変数に値を割当て、
ｘとｙの和が１０以上、ｙとｚの和が１２以上になるよ
うにしたい。ただし、ｘ，ｙ，ｚは全て異なる数を選ぶ
ことにする。また、ｘは偶数でなければならないものと
する。この問題をＡＴＭＳで解く場合、まず、それぞれ
の変数に可能な値を割当てたことを表すデータを仮説と
してＡＴＭＳに入力する。 (x = 5) (x = 6) (y = 4) (y = 6) (y = 8) (z = 4) (z = 7) (z = 8) これらは、全て真偽の不定なデータである。

【０００４】次に、制約や目的を表す「ｉｆ条件ｔｈｅ
ｎ結論」の形のルールを入力する。まず、制約として、
以下の三つを入力する。（１）ｘが偶数でなければならないという制約 if (x = ?v) & ?v は偶数でない then 矛盾（２）変数が複数の値を取ってはならないという制約 if (x = ?v1) & (x = ?v2) & ?v1=/=?v2 then 矛盾 if (y = ?v1) & (y = ?v2) & ?v1=/=?v2 then 矛盾 if (z = ?v1) & (z = ?v2) & ?v1=/=?v2 then 矛盾（３）異なる変数が同じ値を取ってはならないという制
約 if (x = ?v) & (y = ?v) then 矛盾 if (x = ?v) & (z = ?v) then 矛盾 if (y = ?v) & (z = ?v) then 矛盾これらのルールで「?v」など「?」が先頭に付いた文字
はどのようなデータにもマッチするものとする。ＡＴＭ
Ｓでは「結論」部の記述に、特に「矛盾」を表す記号を
導入し、推論において「矛盾」を導いた時、制約を犯し
たと解釈する。次に、目的として、次のものを入力す
る。 if (x = ?v1) & (y = ?v2) & ?v1+?v2 >= 10 then 目的
１を達成したif (y = ?v1) & (z = ?v2) & ?v1+?v2 >=
12 then 目的２を達成した if 目的１を達成した＆目的２を達成した then 最
終目的を達成したそして、制約のルールを実行すると、「矛盾」というデ
ータが、以下のようにして得られる。ｘが偶数でなければならないという制約に矛盾するもの｛(x = 5)} １つの変数が２つの異なる値を取ってはならないという
制約に矛盾するもの {(x = 5), (x = 6)} {(y = 4), (y = 6)} {(y = 4), (y = 8)} {(y = 6), (y = 8)} {(z = 4), (z = 7)} {(z = 4), (z = 8)} {(z = 7), (z = 8)} ２つの異なる変数が同じ値をとってはならないという制
約に矛盾するもの {(x = 6), (y = 6)} {(y = 4), (z = 4)} {(y = 8), (z = 8)} ＡＴＭＳは、このような「矛盾」が成立するということ
を記録し、そして、これらの仮説の組合せを含むような
組合せを推論から除外する。すなわち、目的のルールを
実行すると、「目的１を達成した」というデータが {(x = 5), (y = 6)} {(x = 5), (y = 8)} {(x = 6), (y = 4)} {(x = 6), (y = 6)} {(x = 6), (y = 8)} で、成立するという事実が得られるが、この内{(x =
5)}を含むもの、および、{(x = 6), (y = 6)}を含むも
のは、「矛盾」を導出するので除外され、 {(x = 6), (y = 4)} {(x = 6), (y = 8)} だけが記録される。同様に「目的２を達成した」という
データは、 {(y = 4), (z = 8)} {(y = 6), (z = 7)} {(y = 6), (z = 8)} {(y = 8), (z = 4)} {(y = 8), (z = 7)} で成立することが記録される。そして、データ「最終目
的を達成した」には、「目的１を達成した」に対応付け
られている仮説の組合せと「目的２を達成した」に対応
付けられている仮説の組合せの内矛盾を導出しない組合
せ、 {(x = 6), (y = 4), (z = 8)} {(x = 6), (y = 8), (z = 7)} {(x = 6), (y = 8), (z = 4)} が対応付けられる。これらの仮説の組合せ(ワーキング
メモリ)の集合がラベルである。

【０００５】このように、ＡＴＭＳは、導出した全ての
データに、それがどのような「仮説」の組合せで成立す
るかを記録していく。この時、「仮説」の組合せを、そ
の組合せを構成する仮説の個数が少ない順に生成し、
「矛盾」を導出する「仮説」の組合せを集合として含む
ような「仮説」の組合せを、ルールの条件部の成立判定
から除去する。そのために、仮説の組合せの内、構成す
る仮説の個数の少ない組合せが矛盾すると結論された場
合は、探索空間から、解の存在範囲を大きく絞ることが
できる。このことにより、ＡＴＭＳは、少ない個数の
「仮説」の組合せが矛盾を起こすような問題では、探索
すべき空間を大幅に縮小することができ、効率的な推論
を行なうことができる。また、基本的には全解探索であ
り、全ての解が請求される時に有効である。

【０００６】また、ＡＴＭＳは、１度実行したルールか
らデータ間の依存関係を抽出し、それを記録する。そし
て、推論の途中で、あるデータが、新たな仮説の組合せ
で成立することが分かった場合には、その仮説の組合せ
を、依存関係に従って伝播させ、全てのデータに対して
正しいラベルを計算する。例えば、 if 目的１を
達成した＆目的２を達成した then 最終目的を達成
したというルールを実行した後、「目的１を達成
した」「目的２を達成した」の二つのデータがあれ
ば「最終目的を達成した」というデータを導出して良い
というデータ間の依存関係を抽出して記録する。この依
存関係を目的１を達成した目的２を達成した −＞最終目的
を達成したと書き、「−＞」より左側に書いてあるデータの集合を、
この依存関係の条件部、また、右側に書いてあるデータ
を結論部と呼ぶ。データＤに対するラベルをＬ（Ｄ）と
書くと、推論の途中で、例えば、「目的１を達成した」
というデータが、新たに仮説の組合せＣで成立すること
が分かった場合には、「最終目的を達成した」とのデータ
に対する新しいラベルＬ（最終目的を達成した）は、古
いラベルＬ（最終目的を達成した）を用いて、次の式に
従い、自動的に再計算される。Ｌ（最終目的を達成した）＋｛Ｃ｝＊Ｌ（目的２を達成
した）ここで、「＋」は、集合の和を意味し、「＊」は、集合の直
積を表す。もし、「最終目的を達成した」とのデータ
が、別の依存関係の条件部になっていれば、この再計算
は、さらに、その依存関係の結論部のラベルを更新する
ために続けられる。そして、このような再計算は、全て
のデータのラベルが正しく計算されるまで続けられる。
この過程を、「ラベルの伝播処理」と言う。ＡＴＭＳは、
この「ラベルの伝播処理」により、データに変更があっ
た時にも、ルールの再実行を行わずに、変更から引き起
こされるラベルの更新を、効率よく行うことができる。

【０００７】

【発明が解決しようとする課題】従来技術は、仮説の組
合せの内、構成する仮説の個数の少ない組合せが矛盾を
生じ、また、全ての解が必要な問題に対しては効率的に
働くが、計画型問題など、多くの弱い制約（仮説の組合
せの内、ごく少数を制約違反として除外する制約）から
なる場合には、全ての可能な仮説の組合せを推論して、
記録する方法では効率が悪くなってしまう。例えば、デ
ータ「目標１」を成立させる仮説の組合せが「ｎ」個あ
り、また、データ「目標２」を成立させる仮説の組合せ
が「ｍ」個あり、最終的な解に、この二つのデータ「目
標１」と「目標２」の成立が必要な場合には、例えば、
ルール if 目標１＆目標２ then 解の構成要素１で、これらが同時に成立する仮説の組合せを、データ
「解の構成要素１」に結び付ける必要がある。しかし、
弱い制約の場合には、殆ど「ｍ＊ｎ」通りの仮説の組合
せが生成される。そして、最終的な解を得るためには、
このような組合せのためのルールを何段階も実行しなけ
ればならないので、生成される仮説の組合せは、膨大な
数になる。一般に、最終的に必要な解は数個であり、効
率良く推論を行なうためには、膨大な数の仮説の組合せ
から、推論および伝播の対象を、ごく少数に限る必要が
ある。また、仮説の組合せを限定し過ぎて、最終的な解
が得られない状況が生じた場合には、一度除外した仮説
の組合せを、再度推論の対象に戻すことも必要である。
解決しようとする問題点は、従来の技術では、推論途中
での新事実に基づく推論の変更に柔軟に対応することが
できず、弱い制約の場合には、推論の対象となる仮説の
組み合わせを十分に絞り込むことができない点である。
本発明の目的は、利用者の指示に基づき、推論およびラ
ベル伝播の対象の限定に柔軟に対応し、これら従来技術
の課題を解決し、膨大な数の仮説の組合せから、効率良
く解を導くことを可能とする非単調推論型エキスパート
システムを提供することである。

【０００８】

【課題を解決するための手段】上記目的を達成するた
め、本発明の非単調推論型エキスパートシステムは、
（１）問題の解決に利用するルール群を備え、操作者が
入力した真偽が不定なデータである仮説に基づき、ルー
ルを用いて推論を行なう推論エンジンを有し、推論で得
られるデータを成立させる仮説の組合せを記録したワー
キングメモリの内で、矛盾を導出した仮説の組合せを利
用して探索空間の絞り込みを行ない、かつ、推論で得た
全てのデータに、それぞれのデータを成立させるワーキ
ングメモリの集合であるラベルを対応付け、データ相互
の依存関係を記録し、データの変更に対応して、この依
存関係に基づき、ラベルの更新を伝播する非単調推論型
エキスパートシステムにおいて、利用者の指示に基づ
き、ワーキングメモリのそれぞれに、このワーキングメ
モリの内容を表す複数の記号からなる第１のタグを、お
よび、推論エンジンに、推論の対象となる内容を表す複
数の記号からなる第２のタグを設け、推論エンジンは、
この第２のタグに含まれる記号のみからなる第１のタグ
を有するワーキングメモリのみを対象として、推論を行
なうことを特徴とする。また、（２）上記（１）に記載
の非単調推論型エキスパートシステムにおいて、推論の
途中で、利用者の指示によるワーキングメモリの第１の
タグの変更、もしくは、推論エンジンの第２のタグの変
更のいずれかに基づき、推論エンジンによる推論の範囲
を変更することを特徴とする。また、（３）上記（１）
もしくは（２）のいずれかに記載の非単調推論型エキス
パートシステムにおいて、推論エンジンは、この推論エ
ンジンの第２のタグに含まれる記号のみからなる第１の
タグを持つワーキングメモリの集合である表ラベルと、
第２のタグに含まれない記号を有する第１のタグを持つ
ワーキングメモリの集合である裏ラベルとを、それぞれ
区分けして記憶するラベル区分テーブルを備え、ラベル
の伝播は、このラベル区分テーブルの表ラベルに対して
のみ行なうことを特徴とする。

【０００９】

【作用】本発明において、推論エンジンは、第２のタグ
に含まれる記号と一致する第１のタグを有するワーキン
グメモリのデータだけを推論の対象とする。従って、利
用者は、推論途中で、解を構成する可能性のあるワーキ
ングメモリを限定可能な情報を得た時は、解となる可能
性の薄いワーキングメモリのタグに、推論エンジンのタ
グに含まれていない記号を、新たに加えれることによ
り、新たな記号が加えられたワーキングメモリおよびそ
のワーキングメモリを継承しているワーキングメモリ全
てを、推論およびラベル伝播の対象から外すことがで
き、探索範囲の絞り込みを行なうことができる。また、
推論範囲を限定し過ぎたために解がなくなってしまった
場合には、利用者は、推論の対象にしたいワーキングメ
モリの第１のタグを構成する記号を、推論エンジンのタ
グに新たに加え、推論範囲から外れていたワーキングメ
モリを推論対象にすることができる。また、データが、
どのワーキングメモリで成立するかという情報であるラ
ベルを、現在、推論対象になっている第１のタグを持つ
ワーキングメモリを蓄積する表ラベルと、推論対象にな
っていない第１のタグを持つワーキングメモリを蓄積す
る裏ラベルの二つに分けてラベル区分テーブルに記憶
し、ラベルの伝播処理を表ラベルだけに限定する。この
ことにより、ラベルの伝播を効率良く行なうことができ
る。尚、タグの切り替えに伴い、ラベル区分テーブルに
対して次のような処理を行う。（１）タグの切り替えにより、ワーキングメモリが推論
の対象から外れた時、ワーキングメモリ内部のデータに
対して、ワーキングメモリを表ラベルから裏ラベルに移
動させる。（２）タグの切り替えにより、ワーキングメモリが推論
の対象に入った時ワーキングメモリ内部のデータに対し
て、ワーキングメモリを裏ラベルから表ラベルに移して
伝播処理を行う。

【００１０】

【実施例】以下、本発明の実施例を、図面により詳細に
説明する。図１は、本発明を施したエキスパートシステ
ム構築ツールの本発明に係わる構成の一実施例を示すブ
ロック図である。本実施例のエキスパートシステム構築
ツール１は、それぞれの仮説の組合せに対応してデータ
を格納する複数のワーキングメモリ１０〜１６と、各々
のワーキングメモリ１０〜１６に付随する第１のタグ２
０〜２６と、ワーキングメモリ１０〜１６に含まれるデ
ータの参照や、ワーキングメモリ１０〜１６へのデータ
の書き出し、および、複数のワーキングメモリ１０〜１
６を統合するルールなどからなるルール群２と、このル
ール群２の各ルールの解釈実行を行う推論エンジン３
と、この推論エンジン３の状態を決定するための第２の
タグ４により構成されている。ワーキングメモリ１０〜
１６のそれぞれは、仮説の組合せの包含関係に基づきリ
ンクされ、格子型の配列となっている。第１のタグ２０
〜２６は、付随するそれぞれのワーキングメモリ１０〜
１６の内容を示す記号の集合からなり、また、第２のタ
グ４は、推論エンジン３の推論対象とされる記号の集合
からなる。ルール群２には、「ｉｆ条件ｔｈｅｎ結論」
の形のルールが格納され、推論エンジン３は、利用者が
入力した仮説を「条件」部に有するルールを、このルー
ル群２から選択して実行する。さらに、推論エンジン３
は、その実行結果を「条件」部に有するルールの選択と
実行を繰り返して、推論を進め、ワーキングメモリ１０
〜１６のそれぞれを生成して行く。そして、推論の過程
において、ワーキングメモリ１０〜１６の内、矛盾する
ものは除外し、最終的に残ったワーキングメモリ内の仮
説の組合せを解とする。さらに、本実施例においては、
推論エンジン３は、第２のタグ４の内容に基づき、推論
の対象となるワーキングメモリ１０〜１６を選択する。
すなわち、推論エンジン３は、第２のタグ４に含まれる
第１のタグを持つワーキングメモリ内部にあるデータだ
けを推論の対象とする。このことにより、利用者は、推
論途中で、解を構成する可能性のあるワーキングメモリ
を限定可能な情報が得られた時は、可能性の薄いワーキ
ングメモリのタグに、新たに推論エンジンのタグに含ま
れない記号を加え、新たな記号が加えられたワーキング
メモリおよびそのワーキングメモリを継承しているワー
キングメモリ全てを、推論およびラベル伝播の対象から
外すことができ、最終的に解に貢献できるワーキングメ
モリ内部のデータのみを推論対象とすることができる。
すなわち、探索範囲を絞り込むことができる。また、推
論範囲を限定し過ぎたために解がなくなってしまった場
合には、利用者は、新たに推論の対象にしたいワーキン
グメモリのタグが、推論エンジン３の第２のタグ４に含
まれるように、推論エンジン３の第２のタグ４に、該当
する記号を加えることにより、推論範囲から外れていた
ワーキングメモリを推論対象にすることができる。

【００１１】以下、具体的な例を用いて、エキスパート
システム構築ツール１の処理動作を説明する。利用者
は、それぞれのワーキングメモリ１０〜１６が、どのよ
うな問題解決に関係しているかを表す記号を、第１のタ
グ２０〜２６として与える。例えば、利用者に最適なワ
ークステーション構成を決定するエキスパートシステム
を構築する場合、二次記憶装置の選択として、１００Ｍ（メガバイト）ハードディスク２００Ｍハードディスク５００Ｍハードディスク６００Ｍ光磁気ディスク１Ｇ（ギガバイト）光磁気ディスクなどがあるものとする。そして、これらを一度に考察す
ると、他の選択との組合せで、いわゆる組合せ爆発を起
こすものとする。また、現状では、ほとんどの場合、ハ
ードディスクを選択すれば、問題なくワークステーショ
ンを構成できるものとする。このような場合、上述の５
つをそれぞれの仮説とし、それぞれに対してワーキング
メモリ（Ｗ）を設け、それぞれのワーキングメモリに第
１のタグを次のように付与する。ワーキングメモリの内容第１のタグＷ₁ １００Ｍハードディスク｛ハードディスク選択、二次記憶選択｝Ｗ₂ ２００Ｍハードディスク｛ハードディスク選択、二次記憶選択｝Ｗ₃ ５００Ｍハードディスク｛ハードディスク選択、二次記憶選択｝Ｗ₄ ６００Ｍ光磁気ディスク｛光磁気ディスク選択、二次記憶選択｝Ｗ₅ １Ｇ光磁気ディスク｛光磁気ディスク選択、二次記憶選択｝これは、「ワーキングメモリＷ₁は、「１００Ｍのハー
ドディスク」を内容として持ち、「ハードディスク
選択」と「二次記憶選択」を要素とするタグを持つ」こ
とを表す。また、推論の段階では、推論エンジン３の第
２のタグ４は、以下のように設定されているものとす
る。推論エンジンの第２のタグ｛ワークステーション構成、二次記憶選択、ハードディ
スク選択｝この場合、ワーキングメモリＷ₄とＷ₅のタグ「光磁気デ
ィスク選択」は、推論エンジン３の第２のタグ４に含ま
れていないので、推論の対象から外す。このようにし
て、ハードディスクを選択した場合だけが考察されるた
め、組合せ爆発の発生を回避することができる。推論を
続け、ハードディスクだけを考察範囲にするのでは、解
となるワークステーション構成が存在しないという結論
が出た場合には、利用者は、推論エンジン３の第２のタ
グ４を、以下のように変更する。推論エンジンの第２のタグ｛ワークステーション構成、二次記憶選択、ハードディ
スク選択、光磁気ディスクの選択｝このようにして、光磁気ディスクを用いたワークステー
ション構成まで、解の範囲を広げることができる。ま
た、この時、ハードディスクは全く用いないという方針
で、ワークステーション構成を行なう場合は、以下のよ
うにして、推論エンジン３のタグ４を設定すれば良い。推論エンジンの第２のタグ｛ワークステーション構成、二次記憶選択、光磁気ディ
スクの選択｝また、推論のある時点で、数値演算コプロセッサの決定
を行ない、その際に、二次記憶の選択に関する推論を同
時に行なうと、組合せ爆発を起こすことが予めわかって
いる場合は、利用者は、推論エンジン３の第２のタグ４
を、推論エンジンの第２のタグ｛ワークステーション構成、数値演算コプロセッサの決
定｝とすることにより、ワーキングメモリＷ₁〜Ｗ₅を全て推
論の対象から外し、爆発を抑えることができる。

【００１２】以上、推論エンジン３の第２のタグ４を変
更することによる推論範囲の変更に関して述べたが、次
に、ワーキングメモリのタグを変更する場合に関して説
明を行なう。例えば、推論中に、代替案Ａ、Ｂ、Ｃ、
Ｄ、Ｅがあり、また、データＺが導かれたならば、最終
的な解を構成するのにほとんど寄与しないということ
が、予めわかっている場合、利用者は、もし、Ｚが導か
れたならば、それを導いたワーキングメモリの第１のタ
グとして、「｛解にあまり寄与しない｝」という記号か
らなるタグを付与しておき、かつ、推論エンジン３の第
２のタグ４としては、「解にあまり寄与しない」という
記号を含まないようにしておく。このようにしてタグを
設定しておくことにより、最初、Ｚが導かれたワーキン
グメモリは、推論の対象にならない。また、推論が終わ
って解が構成できなかった時は、ワーキングメモリのタ
グから、「解にあまり寄与しない」を取外して行けば、
だんだんと推論範囲が広がり、もし、解があるならば、
いつかは見つかることになる。このように、第１および
第２のタグを用いることにより、潜在的な解を失わず、
かつ、一時的に、推論範囲を限定することができる。
尚、第１および第２のタグは、本実施例で述べたものに
限るものではなく、推論範囲を限定するものであれば良
い。尚、推論エンジン３に第２のタグ４を付与するの
は、利用者が任意に行なうことができる。例えば、ルー
ルの行動部で、推論エンジン３の第２のタグ４に記号を
付け加えたり、または、取り去ったりする実行文を書く
ことにより行なう。従って、推論の途中で、推論結果な
どを参照しながら、利用者は、必要に応じて、推論エン
ジン３の第２のタグ４を変化させて行くことができる。
また、ワーキングメモリ１０〜１６のタグ２０〜２６
も、同様に変更する実行文があり、ルールの行動部から
それを発行することができる。

【００１３】次に、図２の説明図、および、図３〜図８
の問題解析図（ＰＡＤ／パド図、ＰｒｏｂｌｅｍＡｎ
ａｌｙｓｉｓＤｉａｇｒａｍ）を用いて、エキスパー
トシステム構築ツール１におけるラベルの伝播処理に関
しての説明を行なう。図２は、図１におけるエキスパー
トシステム構築ツールの本発明に係わるラベル区分テー
ブルおよびデータ依存関係テーブルの構成の一実施例を
示す説明図である。図２（ａ）は、データのラベルを記
録するラベル表であり、特に、各データ５に対して、そ
のデータが成立するワーキングメモリの集合が表ラベル
６と裏ラベル７に別けて記録したラベル区分テーブル８
の構成を示している。例えば、「Ａの収入は（１０）」
というデータに対応するラベルには、ワーキングメモリ
｛Ｗ₁、Ｗ₂、Ｗ₃、Ｗ₄、Ｗ₅｝の集合があるが、表ラベ
ル６には、付与された第１のタグが現在の推論エンジン
の第２のタグに含まれ、推論と伝播の対象となっている
ワーキングメモリ｛Ｗ₁、Ｗ₂、Ｗ₃｝の集合が記録さ
れ、また裏ラベル７には、付与された第１のタグが現在
の推論エンジンのタグに含まれないため、推論と伝播の
対象とならないワーキングメモリ｛Ｗ₄、Ｗ₅｝の集合が
記録される。図２（ｂ）は、データの依存関係を示すデ
ータ依存関係テーブル９の構成を示している。テーブル
の各行は、条件部１７と結論部１８からなり、条件部１
７のデータが全て成立するワーキングメモリでは、結論
部１８のデータが必ず成立することを表している。例え
ば、Ｄ₁、Ｄ₂、Ｄ₃のデータが成立すれば、Ｄ₄のデータ
が成立することが分かる。図１のエキスパートシステム
構築ツール１は、これらのラベル区分テーブル８とデー
タ依存関係テーブル９とを用いて、ラベルの伝播を効率
良く行なう。

【００１４】以下、図３〜図５により、図１における推
論エンジン３の、ラベル区分テーブル８とデータ依存関
係テーブル９とを用いたラベル伝播処理動作を説明す
る。図３は、図１における推論エンジンの本発明に係わ
る処理動作の一実施例を示す問題解析図である。特に、
図１の推論エンジン３によるルールの解釈実行アルゴリ
ズムを記述したものである。尚、本実施例では、図１の
推論エンジン３は、データ駆動型であり、利用者が新た
にデータを作った場合、あるいは、ルールの実行で新た
なデータができた場合、それらのデータとマッチする条
件部を持つルールが起動されるものである。まず、照合
フェイズ３０１では、図１のワーキングメモリ１０〜１
６内部のデータと、図１のルール群２内部のルールの条
件部とを照合し、マッチしたルールを集め、競合集合を
作成する。次に、依存関係登録フェイズ３０２では、照
合フェーズ３０１で作成した競合集合を、図２のデータ
依存関係テーブル９に登録する。そして、伝播処理フェ
イズ３０３では、新たに登録した依存関係から作られる
ラベルを伝播させる。図１の推論エンジン３は、これら
の三段階の動作を、新しくマッチするデータが無くなる
まで続ける。

【００１５】図４は、図３における照合フェイズのアル
ゴリズムを示す問題解析図である。処理４０１で、変数
DEPを空集合とする。変数DEPには、このアルゴリズム
で、条件部のマッチしたルールから生成されるデータ間
の依存関係が格納される。すなわち、まず、処理４０２
で、照合フェイズが始まる前に生成されたデータの集合
を、変数NEWに代入する。本実施例はデータ駆動型であ
るので、変数NEWにマッチする条件部を持たないルール
は、推論から除外される。次に、処理４０３で、変数NE
Wに含まれるデータとマッチする条件部を持つルールの
内で、残りの条件部を満たすデータがいずれかのワーキ
ングメモリに存在するルールを探す。もし、あれば、図
２に示したデータ依存関係テーブル９の条件部１７およ
び結論部１８にデータを当てはめて、データ間の依存関
係を作成し、それを変数DEPに入れる。処理４０４で
は、そのようなルールとデータの組合せ全てに関して、
依存関係を作成し、それを変数DEPに入れる。このよう
にして得られた変数DEPは、次の依存関係登録フェイズ
に渡される。

【００１６】この照合フェイズを、具体例を使って説明
する。例えば、データとして（Ａの値は４） in ワーキングメモリ１（Ａの値は６） in ワーキングメモリ２（Ｂの値は７） in ワーキングメモリ３（Ｂの値は８） in ワーキングメモリ４があるとする。ここで、inより右に書いてあるワーキン
グメモリ名は、そのデータが存在するワーキングメモリ
名を表すとする。さらにルール群内部のルールとして if （Ａの値は？Ｘ）（Ｂの値は？Ｙ）？Ｘ＞２？Ｙは偶数 then (Ｃの値は？Ｘ＋？Ｙ）があるとする。この時、このルールからできる競合集合
は、（Ａの値は４）（Ｂの値は８） −＞（Ｃ
の値は１２）（Ａの値は６）（Ｂの値は８） −＞（Ｃ
の値は１４）となる。これは、それぞれ、「（Ａの値は４）と
（Ｂの値は８）から（Ｃの値は１２）が導出で
きる」ことと、「（Ａの値は６）と（Ｂの値は
８）から（Ｃの値は１４）が導出できる」ことを表
している。右向き矢印（−＞）の左側のデータの集まり
をルールにマッチしたデータの集合といい、右側のデー
タをルールの結論部のデータということにする。このよ
うにして、全てのルールに対応して、それぞれの競合集
合を作り、それらの和集合を、次に説明する依存関係登
録フェイズに送る。

【００１７】図５は、図３における依存関係登録フェイ
ズのアルゴリズムを示す問題解析図である。まず、処理
５０１で、変数ＲＳを空集合にする。変数ＲＳには、本
アルゴリズムの実行により、ワーキングメモリ（ｗ）の
集合とデータ（ｃ）の組み、＜＜ｗ１，．．．，ｗｎ＞，ｃ＞の集合が入り、次の伝播処理フェイズに渡される。この
組みは、「データｃは、ワーキングメモリｗ
１，．．．，ｗｎを統合したワーキングメモリで成立す
る」ことを表す。次に、処理５０２では、照合フェイズ
３０１で求めた競合集合の各要素ｒに関して、処理５０
３以下の処理を行う。まず、処理５０３で、変数ＤＳ
に、競合集合の各要素ｒの条件部にマッチしたデータの
集合を入れる。そして、処理５０４で、要素ｒ自身を、
図２のデータ依存関係テーブル９に登録する。次に、処
理５０５で、変数ＤＳに入っているデータが全て存在す
るためには、どのようなワーキングメモリを統合すれば
良いかを求める。すなわち、変数ＤＳに含まれるデータ
の集合を｛ｄ１，．．．，ｄｎ｝とし、ｄｉ（ｉ＝１，
２，．．．，ｎ）が存在するワーキングメモリの集合
を、Ｌｉ（ｉ＝１，２，．．．，ｎ）とする。ここで、
ワーキングメモリの集合（Ｌｉ）のそれぞれがラベルで
ある。次に、Ｌｉ（ｉ＝１，２，．．．，ｎ）の直積を
作成し、それをＬとする。そして、処理５０６と処理５
０７で、Ｌの中の各ワーキングメモリの組みであるｗに
対して、ｗおよびｒの帰結部（データ）ｃとのペア＜
ｗ，ｃ＞を、変数ＲＳに入れる。このようにして、変数
ＲＳに格納したワーキングメモリ（ｗ）の集合とデータ
（ｃ）の組みの集合を、次に説明する伝播処理フェイズ
に送る。

【００１８】図６は、図３における伝播処理フェイズの
アルゴリズムを示す問題解析図である。まず、処理６０
１で、変数ＲＳの各要素＜ｗ，ｃ＞に対して、処理６０
２以下の処理を行う。尚、ここで、ｗ＝＜ｗ
１，．．．，ｗｎ＞とする。処理６０２では、ワーキン
グメモリｗｉ（ｉ＝１，２，．．．，ｎ）の全てを統合
して、新しいワーキングメモリｗ’を作成し、データｃ
を新しいワーキングメモリｗ’に書き込み、このｗ’の
タグを、ｗｉ（ｉ＝１，２，．．．，ｎ）のタグの和集
合とする。次に、処理６０３で、この新しいワーキング
メモリｗ’のタグ（第１のタグ）が、現在の推論エンジ
ンのタグ（第２のタグ）に含まれているか否かをチェッ
クする。含まれていれば、処理６０４で、データｃの表
ラベルに、新しいワーキングメモリｗ’を追加し、図２
のデータ依存関係テーブル９を用いて、表ラベルの伝播
を行う。含まれていなければ、処理６０５で、データｃ
の裏ラベルに新しいワーキングメモリｗ’を加える。こ
の時、表ラベルへは変更がないので、表ラベルを伝播さ
せる必要はない。このようにして、処理６０１では、ワ
ーキングメモリｗｉ（ｉ＝１，２，．．．，ｎ）のいず
れかのタグ（第１のタグ）が、現在の推論エンジンのタ
グ（第２のタグ）に含まれていない場合は、ワーキング
メモリｗｉ（ｉ＝１，２，．．．，ｎ）を統合して、新
しく作成したワーキングメモリを、データｃの裏ラベル
に登録して処理を終る。

【００１９】次に、タグが変更された時の処理を記述す
る。図７は、図１におけるワーキングメモリの第１のタ
グへの記号追加処理アルゴリズムを示す問題解析図であ
る。処理７０１はコメントであり、この問題解析図は、
ワーキングメモリｗの第１のタグに、記号Ｓを追加した
時の処理を記述していることを示している。すなわち、
処理７０２で、推論エンジンの第２のタグが、記号Ｓを
含むかどうか調べる。もし、記号Ｓを含まない場合は、
処理７０３以下の処理で、記号Ｓが付け加えられたワー
キングメモリを、推論の対象およびラベル伝播の対象か
ら外さなければならない。また、推論エンジンのタグが
Ｓを含む場合は、推論およびラベル伝播の対象は変わら
ないので、何もしないで処理を終る。処理７０３では、
処理７０４以下の処理を繰り返して、ワーキングメモリ
ｗ自身、および、ワーキングメモリｗを継承している全
てのワーキングメモリｗ’に対して、推論およびラベル
伝播の対象から外す処理を行なう。処理７０４では、ワ
ーキングメモリｗ’に含まれる全てのデータｄに対し
て、ワーキングメモリｗをデータｄの表ラベルから裏ラ
ベルに移す処理７０５の処理を繰り返す。このようにし
て、ワーキングメモリの第１のタグに記号が追加された
場合、このワーキングメモリは、裏ラベルに移され、ラ
ベル伝播処理の対象外となる。

【００２０】図８は、図１における推論エンジンの第２
のタグへの記号追加処理アルゴリズムを示す問題解析図
である。処理８０１はコメントであり、この問題解析図
は、推論エンジンの第２のタグに、記号Ｓを追加した時
の処理を記述するものであることを示している。処理８
０２では、処理８０３以降の処理により、記号Ｓをタグ
に含む全てのワーキングメモリｗについて、新たに推論
およびラベル伝播の対象になるかどうかを判定し、も
し、新たに推論およびラベル伝播の対象になるのであれ
ば、そのワーキングメモリを表ラベルに戻す処理を行
う。すなわち、処理８０３で、ワーキングメモリｗの第
１のタグが、推論エンジンの第２のタグに含まれるかど
うか判定する。含まれない場合は、ワーキングメモリｗ
は、依然として、推論およびラベル伝播の対象にならな
いのでなにもしない。もし、ワーキングメモリｗの第１
のタグが、推論エンジンの第２のタグに含まれるなら
ば、処理８０４で、ワーキングメモリｗを、新たに推論
およびラベル伝播の対象にする。この処理８０４におい
ては、ワーキングメモリｗに含まれる全てのデータｄに
関して、まず、処理８０５により、ワーキングメモリｗ
を、データｄの裏ラベルから表ラベルに移し、次に、処
理８０６により、図２のデータ依存関係テーブル９を用
いたラベルの伝播を行う。このようにして、推論エンジ
ンの第２のタグに記号が追加された場合には、追加した
記号をタグに含むワーキングメモリを表ラベルに移し、
ラベルの伝播処理の対象とする。

【００２１】以上、図１〜図８を用いて説明したよう
に、本実施例のエキスパートシステム構築ツールでは、
ワーキングメモリ、および、推論エンジンに、問題解決
に関連する内容からなるタグを付与して、探索空間の絞
り込みを効率良く行なうことができる。また、推論の途
中で、新たに得たデータに対応して、柔軟に推論過程を
変更することができる。また、タグを記号の集合とする
ことにより、利用者は、より直感的な定式化が可能とな
り、エキスパートシステムの構築が容易となる。さら
に、表ラベルと裏ラベルの二つを設けることにより、タ
グを無視して、ラベルの伝播処理を効率良く行なうこと
ができる。

【００２２】

【発明の効果】本発明によれば、利用者の指示に基づ
き、推論対象の限定、および、ラベル伝播を効率良く行
ない、膨大な数の仮説の組合せから、容易に解を導くこ
とができ、非単調推論型エキスパートシステムの性能を
向上させることが可能である。

【００２３】

【図面の簡単な説明】

【図１】本発明を施したエキスパートシステム構築ツー
ルの本発明に係わる構成の一実施例を示すブロック図で
ある。

【図２】図１におけるエキスパートシステム構築ツール
の本発明に係わるラベル区分テーブルおよびデータ依存
関係テーブルの構成の一実施例を示す説明図である。

【図３】図１における推論エンジンの本発明に係わる処
理動作の一実施例を示す問題解析図である。

【図４】図３における照合フェイズのアルゴリズムを示
す問題解析図である。

【図５】図３における依存関係登録フェイズのアルゴリ
ズムを示す問題解析図である。

【図６】図３における伝播処理フェイズのアルゴリズム
を示す問題解析図である。

【図７】図１におけるワーキングメモリの第１のタグへ
の記号追加処理アルゴリズムを示す問題解析図である。

【図８】図１における推論エンジンの第２のタグへの記
号追加処理アルゴリズムを示す問題解析図である。

【符号の説明】

１エキスパートシステム構築ツール２ルール群３推論エンジン４第２のタグ５データ６表ラベル７裏ラベル８ラベル区分テーブル９データ依存関係テーブル１０〜１６ワーキングメモリ１７条件部１８結論部２０〜２６第１のタグ

Claims

【特許請求の範囲】

【請求項１】問題の解決に利用するルール群を備え、
操作者が入力した真偽が不定なデータである仮説に基づ
き、上記ルールを用いて推論を行なう推論エンジンを有
し、上記推論で得られるデータを成立させる上記仮説の
組合せを記録したワーキングメモリの内で、矛盾を導出
した仮説の組合せを利用して探索空間の絞り込みを行な
い、かつ、上記推論で得た全てのデータに、該それぞれ
のデータを成立させるワーキングメモリの集合であるラ
ベルを対応付け、上記データ相互の依存関係を記録し、
上記データの変更に対応して、該依存関係に基づき、上
記ラベルの更新を伝播する非単調推論型エキスパートシ
ステムにおいて、利用者の指示に基づき、上記ワーキン
グメモリのそれぞれに、該ワーキングメモリの内容を表
す複数の記号からなる第１のタグを、および、上記推論
エンジンに、推論の対象となる内容を表す複数の記号か
らなる第２のタグを設け、上記推論エンジンは、該第２
のタグに含まれる記号のみからなる上記第１のタグを有
するワーキングメモリのみを対象として、推論を行なう
ことを特徴とする非単調推論型エキスパートシステム。
【請求項２】請求項１に記載の非単調推論型エキスパ
ートシステムにおいて、推論の途中で、上記利用者の指
示による上記ワーキングメモリの第１のタグの変更、も
しくは、上記推論エンジンの第２のタグの変更のいずれ
かに基づき、上記推論エンジンによる上記推論の範囲を
変更することを特徴とする非単調推論型エキスパートシ
ステム。
【請求項３】請求項１もしくは請求項２のいずれかに
記載の非単調推論型エキスパートシステムにおいて、上
記推論エンジンは、該推論エンジンの第２のタグに含ま
れる記号のみからなる第１のタグを持つ上記ワーキング
メモリの集合である表ラベルと、上記推論エンジンの第
２のタグに含まれない記号を有する第１のタグを持つ上
記ワーキングメモリの集合である裏ラベルとを、それぞ
れ区分けして記憶するラベル区分テーブルを備え、上記
ラベルの伝播は、該ラベル区分テーブルの表ラベルに対
してのみ行なうことを特徴とする非単調推論型エキスパ
ートシステム。