JPH02109131A - 推論処理装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） 本発明は、プロダクションルールの実行によって推論処
理を進めていく推論処理装置に係わり、特に推論処理の
過程で適用可能なルールを予め明らかにしておくことに
より推論処理の高速化を図る推論処理装置に関する。

（従来の技術） プロダクションルールを用いて推論処理を実行するシス
テムでは、推論処理に際して与えられる現在の状態に関
する情報及び推論途中で導かれる結論にマツチングする
条件を持つプロダクションルールを、多数のプロダクシ
ョンルールから順速に抽出できることが、推論処理の高
速化を図るうえで自゛効である。

ｔｉｔ来、プロダクションルールを速やかに抽出できる
方式として、プロダクションルールの各条件部と実行部
とを調べ、どの実行部の実行によって得られる結論か次
のどの条件を成立させるか、つまりとのルールの適用が
次にとのルールの適用を可能にするかという関係をテー
ブル若しくはネットワークのかたちで予め準備しておき
、推論時には、これらの関係を参照して次に適用可能な
ルルを順次選択していくことにより、推論処理の高速化
を図るようにした方式が提案されている（特開昭６０　
７２０３号及び特開昭６１−１．９９４０号）。

しかしなから、これらの方式では、単に個々のルール間
の適用可能関係のみを記述したものであるため、次に適
用可能なルールを選択する処理しか高速化することはで
きない。従って、例えばある状態から他の状態へ導くこ
とが可能であるが、或はある結論を導くまでにはどのル
ールを適用したら良いかといった、大局的な推論の方向
付けを示唆することができず、無駄なルールを実行する
ことによって推論処理のより一層の高速化を図ることが
困難であった。

、　　（発明が解決しようとする課題）°）　このよう
に、従来の推論処理装置では、推論の大局的な方向付け
がなされなかったため、無駄なプロダクションルールの
実行が推論処理のより一層の高速化を妨げるという問題
があった。

本発明は、かかる問題点に鑑みなされたもので推論処理
の大局的な方向付けを与えて効率良くプロダクションル
ールを実行することができ、これにより推論処理の高速
化を図ることができる推論処理装置を提供することを目
的とする。

［発明の構成］ （課題を解決するための手段） 本発明に係る推論処理装置は、条件部と実行部の対から
なる複数のプロダクションルールを記憶するルール記憶
部と、このルール記憶部に格納されたプロダクンヨンル
ールに基づいてメタ知識を求める強連結成分分解部及び
類別部と、これら強連結成分分解部及び類別部で求めら
れたメタ知識を記憶するメタ知識記憶部と、このメタ知
識記憶部に記憶されたメタ知識に基づいてプロダクショ
ンルールを抽出し、推論処理を実行する推論部変数のと
り得る全ての状態間の遷移条件を満たすプロダクション
ルールを有向グラフ行列として求め、更に上記角−向グ
ラフ行列を強連結成分分解して各強連結成分の変数条件
及び各強連結成分間の遷移条件を満たすプロダクンヨン
ルールをメタ知識として求める。

前記類別部は、前記強連結成分分解部で求められた各強
連結成分を、その周期に基づいて複数の類に分割し、こ
れらの類の変数条件及び各類間の遷移条件を満たすプロ
ダクションルールをメタ知識として求める。なお、この
類別部は、前記プロダクションルールを適宜分割するこ
とにより前記周期を増やしたうえで前記各強連結成分の
分類するようにしても良い。

また、推論実行部は、メタ知讃記憶部に記憶されたメタ
知識に基づいて推論の大局的な方向付けを行ない、これ
に基づいて前記ルール記憶部に記憶されたプロダクショ
ンルールを抽出し、推論処理を実行する。

（作用） た類間の遷移条件を満たすプロダクションルールがメタ
知識として求められる。そして、これらメり知識によっ
て推論の大局的な方向付けを行ない、このメタ知識に括
ついて最終結論を導くまでのプロダクションルールの適
用順序を決定し、該順序に基づい−Ｃ前記ルール記憶部
に記憶されたプロダクツ：］−・ルールを抽出し、推論
処理を実行すること力（ｕＪ能であるため、無駄なプロ
ダクションルールの実行を肋＋ｆして推論処理のより一
層の高速化を図ることかできる。

なお、類別部が前記プロダクションルールを適宜分割し
、て各弾速結成分の周期を増やしたうえで各弾速結成分
を分類するものであると、弾速結成分を分類できないよ
うなケースでも分類が可能になり、大局的な推論の方向
付けを行なううえで極め−Ｃ’Ｈ効なメタ知識が得られ
ることになる。

（実施例） 以■、図面を参照しなから本発明の一実施例について説
明する。

第１図は本実施例に係る推論処理装置の構成を示すブロ
ック図である。即ち、この推論処理装置は、ルール記憶
部１１、弾速結成分分解部］２、たプロダクションルー
ル中で扱われている各変数のとり得る全ての状態間の遷
移条件を満たすプロダクションルールを、有向グラフ行
列として求め、更に上記有向グラフ行列を弾速結成分分
解して各弾速結成分の変数条件及び各弾速結成分間の遷
移条件を満たすプロダクションルールをメタ知識として
得るようにしている。

類別部１３は、弾速結成分分解部］２で求められた各弾
速結成分に対してその周期を計算し、その値に基づいて
弾速結成分を複数の類に分割する。

その後、これらの類の変数条件及び各類間の遷移条件を
病たすプロダクションルールをメタ知識として求める。

メタ知識記憶部１４は、弾速結成分分解部１２及び類別
部１３で求められた上記メタ知識を格納［１標とする他
の状態に至る推論過程を、メタ知識記憶部１４に格納さ
れたツタ知識に基づいて大局的に判断し、効率良くプロ
ダクションルールを実行していく。

状態記憶部１６は、初期状態や推論部１５における推論
処理の途中状態を格納する。

次に以上のように構成された推論処理装置の動作につい
て説明する。

いま、ルール記憶部１１には、第２図に示すような６つ
のプロダクションルールが格納されているとする。ここ
でＸ、ｙは変数、ａ、ｂ、ｃはそれぞれ状態を示してい
る。

まず、推論処理に先立って、弾速結成分分解部１２は第
３図に示すようなアルゴリズムに従ってプロダクション
ルールからメタ知識を生成する。

■ステップＳ１ まずルール記憶部］１に格納された全てのプロダクショ
ンルールの条件部と実行部とを調べ、ルル中に扱われて
いる各変数のとり得る値を全て取出し、それらの全ての
組合わせに対し、ノード−態の全ての組合わせは、第４
図に示す通り９通りである。従って、この９通りの組合
わせに１′から９′までノード番号を付与する。

１）・ 一■ステップＳ２ 次に求められた各ノードの条件から有向グラフ行列を生
成する。即ち、第４図に示した９つのノド間を、これら
ノード間の遷移条件を満たすルルによって結合すると、
第５図に示すような有向グラフ行列が得られる。この行
列は、ノード番号ｊからノード番号にへと遷移可能なル
ール番号ｉを記述している。

この行列を求めるため、ステップＳ２では、サイズがｎ
Ｘｎの行列（テーブル）Ａを用意し、ノード番号ｊの状
態が第１番目のルールの条件部を満たし、そのルールの
実行結果としてノード番号にの状態が得られるとき、行
列Ａの（ｉｊ）成分にルール番号ｉを登録し、それ以外
の部分には０を登録するという処理を全てのプロダクシ
ョンルールについて行なう。

■ステップＳ３ ■ステップＳ４ 求められた各弾速結成分について、そこに含まれるノー
ド番号に対応する変数の値の条件の論理和を止り、その
弾速結成分に対応する条件とする。

例えば、第６図に示す弾速結成分はノード２′〜８′を
含むので、弾速結成分の条件は、（ｘ＝ｂ）　Ｖ　（Ｘ
＄Ｙ） である。

■ステップＳ５ 次に弾速結成分間の遷移条件を満たすプロダクションル
ールを用いて有向グラフ行列を求める。

即ち、求められた弾速結成分の個数をｍとしてまずサイ
ズかｍＸｍのテーブルを用意し、ノードａが第Ｃ強迫結
成分に属し、ノードｂが第ｄ強運結成分に属するならば
、テーブル（ｃ　ｄ）成分のと１この手法は、行列の例
えば左下の部分が全てＯに、：なるように、行の入替え
と列の入替えとを同時にノ１ｊ・□、− 一イ）ない、行列の対角上に集まった要素を弾速結成分
とするものである。

”−ｙ−”５行列はメタ知識としてメタ知識記憶部］４
に−”格−納される。

次に、類別部１３は、求められた弾速結成分の周期を計
算する。ここで、弾速結成分の周期とは、弾速結グラフ
中の任意のノードを通る任意の閉路の長さの最大公約数
のことである。この値は、グラフ中のどのノードについ
ても同じ値をとる。この周期か２以」二の数であれば、
弾速結成分を更に分割することができる。

いま、第６図の弾速結成分についてこの周期を計算する
と、ノード３′を通る閉路３′→７′→６′→３′の長
さが“３“　閉路３′→５′−２’−，４，’　→６′
→３′の長さか“５′であるから、周期は“１“である
。従って、このままでは弾速結成分をこれ以上分解する
ことはできない。

そこで、適当ないくつかのプロダクションルールを分割
することによってその周期を大きくすることを試みる。

ここでは、例えば第７図に示すように、ルール６をルー
ル６−１とルール６−２とにＴ”””ｒ臨８図は、こう
して得られた新しいブ・ダクシ］　３ ・１・−ンルールの組からなる弾速結成分のグラフ表現
である。ルール６を分解したことにより、新たにノード
１０′が追加されている。これにより、ノド′３′を通
る閉路３′→１０′→５′→２′→４’　−６’　−３
’　の長さが“６“となり、この有向グラフの周期は“
３”になる。したがって、この弾速結成分はノード５′
、６′、８′からなる類Ｉと、ノード２′、３′からな
る類■と、ノーＦ４’　、７’　、１０’　からなる類
■とに分類することができる。これらの類とルールとの
関係を第９図に示ず。

第１０図に、周期ｎの弾速結グラフを周期ｍ（但しｎ≧
ｍ）のグラフに拡張しながらノードの類別をも行なうア
ルゴリズムを示す。このアルゴリズムでは、グラフ中の
各ノードに対して、そのノードを始点とするノードを順
次辿りながら、類別番号を順番に付与してい＜（Ｓｉｌ
〜５１４Ｓ１６〜５２０）。そして、この過程で、同一
のノードに異なる類別番号が付与されたら、そのノード
に至る経路に形式的なノードを追加する］４ （Ｓ　１５）。そし２て、各ノートについて追加した満
〜たすプロダクションルールをメタ知識としてメタ知識
記憶部］４に記憶する。

以」二の処理の結果、求められたグラフをメタ知識とす
ることにより大局的な推論処理の方向を知ることかでき
る。

推論の過程では、推論部１５は、これらのメタ知識によ
って推論の大局的な方向付けを行ない、これに基づき、
推論の途中結果を状態記憶部１６に格納しながらルール
記憶部１１のプロダクションルールを順次実行シていく
。

例えば、いま、推論の初期状態がｘ＝ａ。

ｙ−ａであるとし、この状態からＸ＝Ｃ，ｙ＝２が推論
結果として導き得るかどうかを知りたい場合、弾速結成
分分解部１２によって得られたメタ知識を用いると、第
６図におけるルール３とルル４のいずれかを先ず始めに
適用すれば良いというような大局的な推論方針を決定す
ることができる。

また、類別部１３により求められたメタ知識を用いれば
、例えば現在の推論の状態が第９図の類−一−ｎ＝ＢＸ
ｉ＋２　　　（ｔ＝ｏ、１．・・・）ｊ斗４−゛ であること等が分る。また、例えば後ろ向き推論ノード
と終了条件を満たす状態に対応するノードが各々どの類
に属するものかが分りでいれば、終了条件のチエツクは
、周期をｎとしてルールのｎ回の適用毎に行なうだけで
済む。

なお、類別部１３として上記のようにノードを追加する
処理を行なうものを用いる場合には、追加するノードの
数をある程度制限することが望ましい。即ち、この処理
は、表現の一部を冗長にすることにより全体としては簡
潔な構成を推論過程に与えることを目指したものである
が、追加するノードの数が大きすぎるとグラフのサイズ
が大きくなり、冗長性が勝り全体の推論の効率はかえっ
て低下してしまう。例えば、追加したノード数が元のノ
ード数を」皿回るような場合はこのケースに相当すると
考えられる。従って、元のグラフのノド数の数％以下に
相当する数のノードの追加に

【図面の簡単な説明】

第１図は本発明の一実施例に係る推論処理装置のブロッ
ク図、第２図は同装置におけるルール記憶部の内容を示
す図、第３図は同装置における弾速結成分分解部の処理
手順を示す流れ図、第４図及び第５図は同分解部の処理
を説明するための図、第６図は同分解部で得られた弾速
結グラフを示す図、第７図〜第９図は類別部での処理の
内容を説明するための図、第コー０図は同類別部の処理
手順を示す流れ図である。 １１・・・ルール記憶部、１２・・弾速結成分分解部、
１３・・・類別部、１４・・・メタ知識記憶部、１５・
・・推］一部及び類別部で得られたメタ知識を利用して
大局的な推論の方向を決定することかできるので、無駄
なルールの実行を防止して推論処理の高速化を図ること
ができる。 爛４ ｈ 口 ■ 〉） 凹 φ　　°Ｏ ＩＩ　　　　１１ ×　　　× （□□−１−−）

Claims (2)

【特許請求の範囲】
1. （１）条件部と実行部の対からなる複数のプロダクショ
   ンルールを記憶するルール記憶部と、このルール記憶部
   に格納されたプロダクションルール中で扱われている各
   変数のとり得る全ての状態間の遷移条件を満たすプロダ
   クションルールを有向グラフ行列として求め、更に上記
   有向グラフ行列を強連結成分分解して各強連結成分の変
   数条件及び各強連結成分間の遷移条件を満たすプロダク
   ションルールをメタ知識として求める強連結成分分解部
   と、 この強連結成分分解部で求められた各強連結成分を、そ
   の周期に基づいて複数の類に分割し、これらの類の変数
   条件及び各類間の遷移条件を満たすプロダクションルー
   ルをメタ知識として求める類別部と、 前記強連結成分分解部及び前記類別部で求められたメタ
   知識を記憶するメタ知識記憶部と、このメタ知識記憶部
   に記憶されたメタ知識に基づいて大局的な推論の方向付
   けを行い、これに基づいて前記ルール記憶部に記憶され
   たプロダクションルールを抽出し、推論処理を実行する
   推論部とを具備したことを特徴とする推論処理装置。
2. （２）前記類別部は、前記プロダクションルールを適宜
   分割することにより前記周期を増やした上で前記各強連
   結成分を複数の類に分割するものである請求項１記載の
   推論処理装置。