JPH02181228A - 推論処理装置 - Google Patents

Abstract

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

Description

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

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

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

しかしながら、これらの方式では、単にルール間の適用
可能関係のみを記述したものであるため、次に適用可能
なルールを選択する処理しか高速化することはできない
。従って、例えばある状態から他の状態へ導くことが可
能であるか、或はある結論を導くまでにはどのルールを
適用したら良いたルール間に冗長性があってもそれを判
断する手段がなかったため、不必要に多くのルールを用
いて推論を行なうことによって推論処理に要する時間が
長くなってしまうという問題もあった。

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

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

［発明の構成］ （課題を解決するための手段） 本発明に係る推論処理方式は、条件部と実行部の対から
なる複数のプロダクションルールを記憶するメタ知識記
憶部と、このメタ知識記憶部に記憶されたメタ知識に基
づいてプロダクションルールを抽出し、推論処理を実行
する推論部と、ルール記憶部へのルールの登録に際し、
そのルールを追加するかどうかを決定するルール登録判
定部を具備している。

ここで強連結成分分解部は、ルール記憶部に格納された
プロダクションルール中で扱われている各変数のとり得
る全ての状態間の遷移条件を満たすプロダクションルー
ルを有向グラフ行列として求め、更に上記有向グラフ行
列を強連結成分分解して各強連結成分の変数条件及び各
強連結成分間の遷移条件を満たすプロダクションルール
をメタ知識として求める。

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

更にルール登録判定部は、ルール記憶部へのルある。

また、このルール登録判定部に代えて、ルール記憶部に
登録されたルールの中で、そのルールを削除した場合の
強連結成分が変化するかどうかを判定し、もし変化しな
い場合にはそのルールを削除するルール削除判定部を備
えるようにしても良い。

（作用） 本発明によれば、メタ知識によって推論の大局的な方向
付けを行なうことができる。そして、このメタ知識に基
づいて最終結論を導くまでのプロダクションルールの適
用順序を決定し、該順序に基づいて前記ルール記憶部に
記憶されたプロダクションルールを抽出し、推論処理を
実行することが可能であるため、無駄なプロダクション
ルールの実行を防止して推論処理の高速化を図ることが
できる。

また、本発明ではルールの登録に際してルール登録判定
部がそのルールの追加前後の強連結成分の変化の有無を
調べる。そして、強連結成分に変」と判定しそのルール
の追加を行なわない。このため、冗長なルールが登録さ
れることがなく、結局、無駄なルールの適用が事前に防
止されるので、推論処理の高速化を図ることができる。

また、ルール登録判定部に代えてルール削除判定部が備
えられた場合においてはルール削除判定部が既に登録さ
れているルールのうち、そのルールを削除した場合でも
強連結成分が変化しないルールを削除するので、上記と
同様に無駄なルールの適用が事前に防止され、推論処理
の高速化を図ることができる。

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

第１図は本実施例に係る推論処理装置の構成を示すブロ
ック図である。即ち、この推論処理装置は、ルール入力
部１１、ルール登録判定部１２、ルール記憶部１３、強
連結成分分解部１４、メタ知識記憶部１５、推論部１６
及び状態記憶部１７にて構成されている。

ルール入力部１１は、ルール記憶部１３にプロ変化する
かどうかを判定し、もし変化しない場合にはそのルール
の登録は行なわず、変化する場合にはそのルールをルー
ル記憶部１３に格納する。

ルール記憶部１３は、上記ルール登録判定部１２で登録
の必要ありと判定されたプロダクションルールを複数記
憶する。なお、これらのプロダクションルールは、条件
部と実行部の対からなる。

強連結成分分解部１４は、ルール記憶部１３に記憶され
たプロダクションルールを、推論部１６での推論処理に
先立って抽出してメタ知識を生成する。ここでは、ルー
ル記憶部１３に格納されたプロダクションルール中で扱
われている各変数のとり得る全ての状態間の遷移条件を
満たすプロダクションルールを、有向グラフ行列として
求め、更に上記有向グラフ行列を強連結成分分解して各
強連結成分の変数条件及び各強連結成分間の遷移条件を
満たすプロダクションルールをメタ知識として得るよう
にしている。このメタ知識の算出アルゴリズムについて
は後で簡単に述べる。

メタ知識記憶部１５は、強連結成分分解部１４目標とす
る他の状態に至る推論過程を、メタ知識記憶部１３に格
納されたメタ知識に基づいて大局的に判断し、効率良く
プロダクションルールを実行していく。

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

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

いま、ルール記憶部１３には、第２図の有向グラフで示
されるプロダクションルールが格納されているとする。

ここでノードａ、ｂ、ｃ、　・・・、ｉはそれぞれ状態
を示し、各状態間を結ぶ矢印はそれが適用されることに
よってそのような状態遷移が起こるプロダクションルー
ルを示し、矢印近傍の番号はルール番号を示している。

まず推論処理に先立ち、強連結成分分解部１４は第３図
８１及びＳ２に示す処理に従ってプロダクションルール
からメタ知識を生成する。

即ち、まずルール記憶部１３に格納された全てのプロダ
クションルールに基づく各ノード間の遷満たすルールに
よって結合することによって得られる。この行列は、ノ
ード番号ｊからノード番号にへと遷移可能なルール番号
を記述している。

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

次に仔向グラフ行列を強連゛結成分へ分解する（ステッ
プＳ２）。ここで強連結成分とは、それを構成するノー
ド間が双方向に遷移可能な成分であり、第２図の例では
、ノード（ｃ　、　　ｄ　）　、ノード（ｇ、ｈ、ｉ）
がそれぞれを強連結成分となる。

有向グラフ行列に対する強連結成分分解の手法としては
行と列の同時入替え法が知られている。この手法は、行
列の例えば左下の部分が全て０になるように、行の入替
えと列の入替えとを同時に行ができる。これにより第５
図中点線で込まれた６つの強連結成分が求められる。抽
出された強連結成分にはＩから■まで順番に番号が付与
され、メタ知識記憶部１５に格納される。この強連結成
分の間の半順序関係を列挙すると第６図のようになる。

続いてルール登録判定部１２は、強連結成分分解部１４
で求められた強連結成分の有効グラフ行列Ａを求める（
ステップＳ３）。この行列Ａは、第７図に示すように、
強連結成分の数をｎとするとｎＸｎの行列で、強連結成
分ｇの状態から所定のルールの適用によって強連結成分
ｍの状態へ遷移可能である場合、行列Ａの（ｇｍ）成分
に１を登録し、それ以外の部分には０を登録するという
処理を全てのプロダクションルールについて行なうこと
により求められる。

次にルール登録判定部１２は、求められた行列Ａから、 Ａ’　　−Ａ＋ＡＩ　＋Ａ２　＋、、、＋Ａｎ　　　　
　−（１）で求められる行列Ａ′を求める。但し、ここ
でＡｎは、ｎ回のルールの適用で到達可能な関係にある
強連結成分を表示している。従って、例えばＡ２は２回
のルールの適用によって到達可能な部分を示している。

従って前記（１）式を適用することによってルールを複
数回適用して到達可能な全ての関係が求められる。但し
、この例では強連結成分の数ｎ−６であるから、 Ａ’　ｓｓＡ＋ＡＩ＋Ａ２＋・・・＋Ａ６　　　　　・
・・（２）まで計算すればよい。それ以上行なっても新
たに到達可能な関係は見付からないからである。このよ
うにして求められた行列Ａ′を第８図に示す。

ここで、ルール入力部１１によって新たに登録すべきル
ールが入力されたことを考える（ステップＳ５）。いま
、この新規登録しようとするルールが第９図に示された
ルール５であるとする。ルール登録判定部１２は、その
新たなルール５によって生じる状態６間の遷移可能性を
示す第１０図のような行列Ｂを作成する。この行列Ｂも
行列Ａ。

Ａ′と同様ｎＸｎのサイズで、その新規登録ルールによ
って強連結成分ｇから強連結成分ｍへの状態遷移が可能
になる部分に１、その他の部分に０を登録したものであ
る。第９図に示したルール５の場合、第１０図に示すよ
うに■→■、■→■の部分に１、その他の部分に０が登
録された行列Ｂが得られる。

る（ステップＳ７）。この結果、対応する行列Ａ′の成
分が非零であったならばそのルールの登録は中止しくス
テップＳ８）、また零であったならばそのルールをルー
ル記憶部１３に登録する（ステップＳ９）。

第１０図の例では、行列Ｂの非零成分に対応する行列Ａ
’　　（第８図）の成分がいずれも非零であるから、ル
ール５の登録を行なわない。これは、ルール５を登録し
ても新たに遷移可能な強連結成分の組合わせが得られな
いからであり、換言すればルール５は既に登録されてい
るルール１〜４にこれに対し、第１２図に示すようなル
ール６を新規登録する場合について考えると、行列Ｂの
非零成分に対応する行列Ａ’　　（第８図）の成分がい
ずれも零であるから、ルール６の登録を行なう。

これは、ルール６を登録することによって、した新たな
強連結成分Ｉ′が得られるからであり、登録され、強運
結成分間の半順序関係も第１４図に示すように変更され
る。

以上のように強連結成分が変更されたら、これはメタ知
識記憶部１５に格納される。

推論の過程では、推論部１６は、メタ知識によって推論
の大局的な方向付けを行ない、これに基づき、推論の途
中結果を状態記憶部１７に格納しながらルール記憶部１
３のプロダクションルールを順次実行していく。例えば
、いま、推論の初期状態がｅであるとし、この状態から
状態ｉが推論結果として導き得るかどうかを知りたいと
すると、初期状態は強連結成分■に含まれ、推論の結論
は強連結成分■に含まれる。従って、推論部１６は強連
結成分■から強連結成分■に達するパスがあるかどうか
を探索する。その結果、■→Ｖ→■のパスと、■→■の
パスとが探索されるので、初期に対する大局的な方向付
けを行なうことができるとともに、新たにルールを登録
する際にそのルールの冗長性を判定して登録の可否を決
定しているので、無駄なルールが登録されることがなく
、この結果、推論処理の高速化を図ることができる。

なお、上記実施例ではルール登録判定部１２でルールを
新たに登録する際の登録可否を判定したが、このルール
登録判定部に代えてルール削除判定部を設け、既に登録
されているルールのうち冗長なルールを削除するように
しても良い。この場合には、ルール記憶部１３に登録さ
れたルールの中で、そのルールを削除した場合の強連結
成分が変化するかどうかを判定し、もし変化しない場合
にはそのルールを削除するようにすれば良い。

［発明の効果］ 以上のように、本発明によればメタ知識を利用して大局
的な推論の方向を決定することができるとともに、無駄
なルールの登録が防止できるので、無駄なルールが実行
されることがなく、推論処理の高速化を図ることができ
る。

れたルールと各状態間の関係をグラフで示す図、第３図
は強連結成分分解部及びルール登録判定部の処理手順を
示す流れ図、第４図は強連結成分を求める様子を示す図
、第５図は得られた強連結成分とその半順序関係とをグ
ラフで示した図、第６図は得られた強連結成分の半順序
関係を示す図、第７図はルール登録判定部で求められる
行列Ａを示す図、第８図はルール登録判定部で求められ
る行列Ａ′を示す図、第９図〜第１１図は冗長なルール
を追加した場合のルール登録判定部の処理を説明するた
めの図、第１２図〜第１４図は冗長でないルールを追加
した場合のルール登録判定部の処理を説明するための図
である。

１１・・・ルール入力部、１２・・・ルール登録判定部
、１３・・・ルール記憶部、１４・・・強連結成分分解
部、１５・・・メタ知識記憶部、１６・・・推論部、１
７・・・状態記憶部。

出願人　工業技術院長　飯塚幸三 第２図 ｋ（ｔｏ） 第４図 第５図 −ｍ（ｔｏ） 第 図 −ｍ（ｔｏ） 第８ 図

Claims (2)

【特許請求の範囲】
1. （１）条件部と実行部の対からなる複数のプロダクショ
   ンルールを記憶するルール記憶部と、このルール記憶部
   に格納されたプロダクションルール中で扱われている各
   変数のとり得る全ての状態間の遷移条件を満たすプロダ
   クションルールを有向グラフ行列として求め、更に上記
   有向グラフ行列を強連結成分分解して各強連結成分の変
   数条件及び各強連結成分間の遷移条件を満たすプロダク
   ションルールをメタ知識として求める強連結成分分解部
   と、 この強連結成分分解部で求められた前記メタ知識を記憶
   するメタ知識記憶部と、 このメタ知識記憶部に記憶されたメタ知識に基づいて大
   局的な推論の方向付けを行ない、これに基づいて前記ル
   ール記憶部に記憶されたプロダクションルールを抽出し
   、推論処理を実行する推論部と、 前記ルール記憶部へのルールの登録に際し、そのルール
   の追加によって強連結成分が変化するかどうかを判定し
   、もし変化しない場合にはそのルールの登録を中止する
   ルール登録判定部とを具備したことを特徴とする推論処
   理装置。
2. （２）前記ルール登録判定部に代えて、前記ルール記憶
   部に登録されたルールの中で、そのルールを削除した場
   合の強連結成分が変化するかどうかを判定し、もし変化
   しない場合にはそのルールを削除するルール削除判定部
   を備えたことを特徴とする請求項１記載の推論処理方式
   。