JPH03286337A - 条件判定の処理構造最適化による推論の高速化方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野］ 本発明は、知識ベースシステムにおける推論方式に関し
、特に複雑、大規模な知識ベースシステムの構築に好適
な条件判定の処理構造最適化による推論の高速化方式に
関する。

［従来の技術］ 従来の知識ベースシステムの問題点の１つに推論速度の
低さがある。推論処理の非効率は、ルール条件の成立判
定処理が重いことに起因している。

そこで、現在の多くの知識工学ツールでは、推論を高速
化するため、条件成立判定処理（パターンマツチ処理）
の効率化を目指し、ＲｅＬｅアルゴリズムまたはＴＲＥ
ＡＴアルゴリズムを採用している。

これらのアルゴリズムは、何れもルール条件部の個々の
条件をノートで表わした弁別ネットを用いて、ルール条
件部の成立判定処理を行っている。

弁別ネットを用いれば、複数のルールに現われる同一の
条件を共通化し、１個のノードて表現することができる
。つまり、同一の条件判定を重複して行うことを回避す
ることができる。

さらに、この弁別ネット内で過去に行った条件成立判定
の中間結果を記憶することができる。これにより、状態
の変化していないものに対する条件判定は、弁別ネット
内に記憶された中間結果を参照することで置き換えるこ
とができるので、状態の変化したものについてだけ条件
成立判定処理を行えば、全てのルールの条件部の成立判
定が行える。

つまり、ルール条件部の成立判定は、推論実行により状
態の変化したものだけに限定できる。

以上のように、ルール条件部を弁別ネットワークに変形
し、そのネットワーク中に過去に行った条件成立判定の
中間結果を保持することにより、効率的なパターンマツ
チング処理が行えるため、多くの知識工学ツールに採用
されている。

なお、従来のＲｅｔｅアルゴリズムについては、例えば
“リートニアファスト　アルゴリズムフォーザメニーパ
ターン／メニーオブジェクトパターンマッチブロブレム
、アーティフィシャルインテリジェンス、第１９巻、第
１号、第１７頁−３７頁（＋９８２）（Ｒｅｔｅ：Ａ　
Ｆａｓｔ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　Ｍａ
ｎｙ　Ｐａｔｔｅｒｎ／Ｍａｎｙ　０ｂｊｅｃｔ　Ｐａ
ｔｔｅｒｎ　Ｍａｔｃｈ　Ｐｒｏｂｌｅｍ　、　Ａｒｔ
ｉｆｉｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ　ｖｏｌ、
１９．隘１．ｐｐ、１７−３７（１９８２））″におい
て論じられている。また、Ｔｒｅａｔアルゴリズムにつ
いては、例えば“トリート：アベターマッチアルゴリズ
ムフォーエイ　アイ　プロダクションシステム、エイ　
エイ　エイ　アイ−８７゜第４２頁〜４７頁（１９８７
）（Ｔｒｅａｔ：Ａ　Ｂｅｔｔｅｒ　Ｍａｔｃｈ　Ａｌ
ｇｏｒｉｔｈｍ　ｆｏｒ　Ａｒ　Ｐｒｏｄｕｃｔｉｏｎ
　Ｓｙｓｔｅｍｓ、ＡＡＡＩ−８７，ｐｐ、４２−４７
（１９８７））’″において論じられている。

［発明が解決しようとする課題］ 上記従来技術では、多くのフレーム間にまたがる複雑な
条件の成立判定に適用する場合、条件判定処理の中間結
果の記憶の量、範囲に起因して、大幅に処理効率が低下
するという問題があった。

ここで、その理由を述べる。

まず、前記の代表的な２個のアルゴリズム−Ｒｅ　ｔ　
ｅ、ＴＲＥＡＴ−の条件判定処理の中間結果の記憶範囲
の違いについて述べる。

一般に、ルールの条件部を４１１或する個々の条件は、
複数のフレーム間にまたがる条件と、１個のフレーム内
で成立判定できる条件の２つに分類でき、前者をインタ
ー条件、後者をイントラ条件と呼ぶ。このイントラ条件
を満足したフレームと、インター条件を満足したフレー
ムの組を条件成立判定処理の中間結果として記憶するの
がＲｅｔｅアルゴリズムであり、一方、イントラ条件を
満足したフレームだけを条件成立判定処理の中間結果と
して記憶するのがＴＲＥＡＴアルゴリズムであすなわち
、２つのアルゴリズムの違いは、インター条件を満たし
たフレームの組を記憶するかしないかにある。

このように、Ｒｅｔｅアルゴリズムはインター条件成立
までの処理履歴を記憶する。従って、中間結果が記憶さ
れているインター条件は、関係するフレームの状態量が
変化しない限り、条件成立判定は不要となる。しかし、
インター条件はフレームの組に対する条件であるので、
処理の中間結果の記憶、管理に要する計算量は大きく、
この記憶情報がうまく利用されない場合、処理性が大き
く低下することになる。

この問題点に対し、ＴＲＥＡＴは、インター条件成立の
処理履歴を記憶しないことで対応しているが、一方では
、インター条件の成立判定は毎回行う必要がある。従っ
て、ＴＲＥＡＴアルゴリズムの対応では、Ｒｅｔｅで処
理性が大きく低下したような部分に対しては問題解決と
なるが、一方で、Ｒｅｔｅアルゴリズムが効率よく処理
してぃた問題に対しては、逆に処理性を大きく落として
しまう。

これらのアルゴリズムの違いは、どのくらい過去の処理
結果を記憶して利用するかにある。従って、履歴情報を
２己憶するよりも条件成立判定をやり直した方が効率的
であるか、あるいは逆に、条件成立判定をやり直すより
も過去の処理結果を利用した方が速いかにより、どちら
のアルゴリズムが効率的であるかが決まる。

ところが、条件成立判定処理の中間結果をどの程度記憶
して利用すべきかは、問題の性質による。

つまり、ある種の問題に対しては、中間結果を記憶した
方がよいし、逆に、ある種の問題に対しては、記憶しな
いほうがよい。

さらに、１つのルール条件記述内でも、その条件部のあ
る部分（サブパターン）に対しては、処理の中間結果を
記憶することが有効であり、別の部分は再計算の方がよ
いということも充分考えられる。

従って、条件成立判定処理の中間結果の記憶の範囲が固
定されていた従来方式では、中間結果の記憶範囲が適切
なルール記述に対しては効率よく処理できるが、不適切
な場合には、逆に処理性を悪くしてしまう。

本発明の目的は、このような問題点を改善し、条件成立
判定処理の中間結果の記憶、利用のレベルを、対象とす
る問題に対応して最適にする機能を実現することにより
、複雑かつ大規模な知識ベースシステムを用いた推論が
可能な条件判定の処理構造最適化による推論の高速化方
式を提供することにある。

〔課題を解決するための手段〕

上記目的を達成するため、本発明の条件判定の処理構造
最適化による推論の高速化方式は、以下に示す４つの機
能を設ける。

（１）処理構造のユーザ指定機能 これは、条件の成立判定の順序の指定、および条件成立
判定処理において得た中間結果の記憶指定、および記憶
する中間結果の範囲の指定をユーザ自身が行う機能であ
る。

また、この処理構造の指定をルール内に記述し、さらに
、ルールを条件部、結論部、処理構造記述部の３部に分
割して、条件の成立判定の順序の指定、条件成立判定処
理で得た中間結果の記憶指定、および記憶する中間結果
の範囲の指定を処理構造指定部に記述する機能を設ける
。

また、ルール条件部を構成する各フレームに関する条件
ごとに識別名を対応づけ、その識別名を要素とするリス
ト構造を用いて、条件成立判定順序の指定を行う。

また、そのリストで同時に、条件成立判定処理の中間結
果の記憶指定、および記憶する中間結果の範囲の指定を
行うため、２種の括弧を用いて表現する。

（２）処理構造のユーザ指定を支援する機能これは、処
理構造を指定するために必要な情報を収集する条件成立
判定処理のモニタ機構（ログ収集機１１１）、および収
集した情報を表示するログ表示機構により実現される。

このモニタ機構では、各条件の成立確率、および記憶し
た中間結果の有効性等の情報を収集し、ログ表示機構で
は、条件の成立判定の順序をツリー形式で表示して、そ
のツリー内に、条件の成立確率、記載した中間結果の有
効性等を表示する。

（３）典型例から最適な処理構造を導び出す機能これは
、典型的な例題を与え、その推論過程における条件成立
判定処理の処理過程を解析して、自動的（こｓｔ適な成
立判定の順序の指定、条件成立判定処理で得た中間結果
の記憶指定、および記憶する範囲の指定を導び出す機能
である。

（４）推論実行時における動的な処理構造の変更機能 これは、推論実行中に条件成立判定処理をモニタして、
最適な処理構造を導き、その時点で用いている処理構造
と異なっている場合、最適な処理構造に自動的に置き換
えて条件成立判定を続行する機能であり、一定の時間周
期で起動される。

［作用］ 本発明においては、条件の成立判定の順序の指定、およ
び条件成立判定処理において得られた中間結果の記憶指
定と、２己憶する中間結果の範囲の指定をユーザ自身が
明示的に記述する機能を設ける二とにより、問題の性質
に合致した条件部α判定処理を行うことが可能となった
。

また、処理構造の指定は、ルールの一部分として２種類
の括弧を用いたリスト構造で簡単に記述でき、さらに、
構造指定のために必要となる情報を収集して表示する機
能を設けることにより、処理＃ｌＩ造のユーザによる指
定が容易となった。

また、ユーザが典型的な問題を与え、その推論における
条件成立判定処理の過程を解析して、自動的に最適な処
理構造を厚き出す機能を設けることにより、ユーザ自身
が処理構造を指定しなくても、例題を与えるだけでｉ＆
適な処理構造を得ることが可能となった。

さらに、推論実行中、条件成立判定処理の過程を解析し
て最適な処理ｍａを求め、その時点で用いている処理構
造が１＆適でない場合、最適な処理構造に置き換える機
能を設けることにより、最適な処理構造が推論中に変化
するような問題に対しても、効率のよい推論処理を実現
することができる。

〔実施例〕

以下、本発明の一実施例を図面により説明する。

第１図は、本発明の一実施例における知識ベースシステ
ムの機能構成図である。

第１図において、１は知識ベースシステムのユーザ、２
は推論機構、３はワーキングメモリエレメント（以下Ｗ
ＭＥと略す）、４はルール、５はログ収集機構、６は動
的変更機構、７はログ表示機構、８は構造導出機構、９
はユーザインタフェース管理機構である。

本実施例では、ユーザ１は、ユーザインタフェース管理
機構９を通して、推論機構２、動的変更機構６、ログ表
示機構７、構造導出機構８と対話する。

また、推論機構２は、ＷＭＥ３およびルール４からなる
知識を用い、ルール条件部が成立しているルールを順次
実行して推論を行う。なお、これらはプログラミング言
語リスプにより記述される。

次に、ＷＭＥ３、ルール４の記述方法、および各機構の
機能について述べる。

（１）ＷＭＥおよびルールの記述方法 まず、ＷＭＥ３の記述法について述べる。

第２図は、本発明の一実施例におけるＷＭＥのシンタク
スを示す説明図である。

本実施例のＷＭＥ３は、括弧２１．２５で囲まれた文字
“Ｗ”、ＷＭＥ名称２２、項目名２３と値２４の組で表
わす。

なお、値２４、ＷＭＥ名称２２、項目名２３は、リスプ
のアトムである。

第３図は、本発明の一実施例におけるＷＭＥの記述側図
である。

本実施例では、３１がＷＭＥ名称”ＷＭ　Ｅ　１　”３
２〜３４が＄項目名および値であって、３２は項目“’
ａｔｔｒ１”のイ直が”１２３”であることを表わす。

同様に、３３は項目”ａＴ、ｔｒ２″の値が”　ａ　ｂ
　ｃ　”であり、３４は項目”ａ　ｔ　ｔ　ｒ　３”の
値がｔｅＸＬ　　ｄａｔａ’″であることを示す。

次に、ルール４の記述法について述べる。

第４図〜第７図は、本発明の一実施例におけるルールの
シンタクスを示す説明図である。

本実施例のルールの基本的な構造は、第４図に示すよう
に、ルール名称部４１．条件部４２、実行部４３、およ
び処理構造記述部４４を有する。

この条件部４２は、１つのＷＭＥに関する条件を表わす
条件節の並びで構成される。

また、実行部４３は、ＷＭＥの生成、削除、更新および
リスプ関数の呼び出しから構成される。

また、処理構造記述部４４は、条件成立判定の順序、条
件成立判定の中間結果の記憶指定、および記憶範囲指定
を記述する処理構造記述部４４から構成される。

すなわち、本実施例では、一般のプロダクションシステ
ムと同様のルール名称部４１、条件部４２、実行部４３
に加えて、処理構造記述部４４を設ける。

この条件部４２に記述する条件節のシンタクスは第５図
に示される。

本実施例では、１つの条件節は、１つのフレームに関す
る条件を記述するものであり、対象とするＷ〜１Ｅ名あ
るいは変数５１と、項目値か満たすべき条件を「項目名
５２、比較語５３、値あるいは項目名あるいは変数５４
」の３つ組で表現した条件記述から構成される。

なお、変数は、＋４　Ｑ　Ｉ＋を先頭文字とするアトム
で表現し、同一変数は同一値とする。また、比較語は、
　＝　　、　　”＜＞”、”　＞　”、＋　＜　４１、
°゛〉＝　　、　　”＜＝”である。

また、実行部４′３のシンタクスは第６図にポされる。

本実施例では、（ａ）のように、Ｗ＼１Ｅの生成のため
のＣＲＥ　Ａ　ＴＬ二６１、更新のためのＵＰＤＡＴＥ
６２．７肖去のためのＤＥＬＥＴＥ６３、リスプ関数の
ためのＥＸＥ（：ＵＴＥ６４の４種のコマンドが記述で
きる。

このＣＲＥＡＴＥコマンド６１では、ＷＭＥ記述６８に
沿ってＷＭＥが生成される。ＷＭＥ記述６８は、第２図
に示したＷ〜１Ｅとほぼ等しいシンタクスで表現され、
（ｂ）のように、Ｖｖ’ＭＥ名称か変数でＷＭＥを指定
し６５、項目名６６と、その値６７を繰返し記述する。

また、ＵＰＤＡＴＥコマンド６２では、ＷＭＥ番号６９
で指定されたＷＭＥを更新する。ＷＭＥ番号とは、ルー
ル条件部に記述された条件節に対し、１から順に番号付
けた値であり、例えば、”ＵＰＤＡＴＥ２・・・”のよ
うにＷＭＥ番号６９が”　２　”である場合、２番目の
条件節を満足したＷＭＥを更新するという意味になる。

また、ＤＥＬＥＴＥコマンド６３は、ＷＭＥ番号で指定
されたＷＭＥを消去する。例えば、”ＤＥＬＥＴＥ　　
２”の場合は、２番目の条件節を満足したＷＭＥを消去
するという意味になる。

また、ＥＸＥＣＵＴＥコマンド６４は、リスプ式を評価
する。

さらに、処理構造記述部４４のシンタクスは第７図に示
される。

本実施例の処理構造記述部４４における構造指定は、（
ａ）のように構造定義からなり、その構造定義は、（ｂ
）のように、上記のＷＭＥ番号を要素とする”（”、”
）”と”［”、”］”の２種類の括弧７１゜７２を用い
て表現される１種のリストにより示される。なお、構造
指定については詳細に後述する。

第８図は、本発明の一実施例におけるルール記述側面で
ある。

本実施例のルール”ｒｕｌｅｌ″８１は、２つの条件節
８５．８６からなる条件部８２と、４つのコマンドから
なる結論部８３、およびリスト８７を指定する処理構造
記述部８４より構成される。

この条件部８２の第１条件節８５では、”　Ｗ　ＭＥ１
″という名称のＷＭＥが存在し、その項目”ａｔｔｒｌ
″は２０と等しく、項目”ａｔｔｒ２ｎは項目”ａｔｔ
ｒ４”と異なり、項目″’ａｎｔｒ３’は変数“？ｖａ
　１１”以上であるという条件を示している。なお、変
数”’：）ｖａｌｌ’″の値は、第２条件節８６で決ま
る値である。

一方、第２条件節８６では、”　？　Ｗ　Ｍ　Ｅ　”と
いう名称のＷＭＥが存在し、その項目”ａｔｔ、ｒｌ”
は変数“７ｖａ　ｌ　１″′と等しく、項目゛″ａｔｔ
ｒ２ｎは項目“ａｔｔｒ３”と等しいという条件を示し
ている。

この場合、第２条件節８６では、ＷＭＥ名称が変数”　
？　Ｗ　Ｍ　Ｅ　”であるので、全てのＷＭＥに対して
条件成立判定を行うことになる。

なお、８３は実行部、８４は処理＃ｌ造記述部、８７は
構造定義である。

（２）推論機構の実現方法 第９図は、本発明の一実施例における推論機構の処理フ
ローチャートである。

本実施例の推論機構２は、プロダクションシステムと同
様のフローにより推論を行う。

す３わち、第９図のように、条件部が成立しているルー
ルを全て捜しく９０１）、その中から実行するルールを
１個選択して（９０２）、そのルールの結論部のコマン
ドを実行する（９０３）。そして、このサイクルを実行
可能なルールが無くなるまで繰り返す。

この処理の中で最も処理量を要するのは、条件部が成立
しているルールを全て捜す処理９０１である。本実施例
では、このマツチング処理を高速化するため、ルール条
件部を弁別ネットに変形し、そのネットと、その中に保
持された条件成立判定処理の中間結果を用いて条件成立
判定処理を行う。

本実施例のマツチング処理における基本的な条件判定方
法は、第】０図および第１１図の例Ｉこずされる。

第１０図は、本発明の一実施例におけるルールの条件部
側面、第１１図は本発明の一実施例における弁別ネット
側面である。

第１０図において、ｌｏｔはルールｌの条件部、１０２
はルール２の条件部である。

本実施例では、第１０図に示す条件部の条件成立判定処
理を行う場合、第１１図に示す弁別ネットに変換する。

第１ｊ図において、“○”はイントラノードと呼び、同
−ＷＭＥ内の条件を示す。例えば、「ＷＭＥ名がポンプ
であるか？」、「＄型式がＰＯ６であるか９」といった
条件がこれに当たる。

また、′◎″はインターノードと呼び、異なるＷＭＥ間
の条件を表わす。例えば、変数９ｘによリ表わされる条
件「ポンプの＄出力光がタービンの＄入力光と等しいか
？」は、インターノードで表現される。

また、△”および“◇”で示したα−ｍｅｎノードおよ
びβ−ｍｅｎノード（メモリノードと総称する）では、
成立判定処理の中間結果として、そこに到達したＷＭＥ
を記憶する。なお、α−ｍｅｎノードでは、１つのＷＭ
Ｅの組からなるリスト、β−ｍｌＢｎノードでは、２つ
以上のＷＭＥの組からなるリストを記憶する。

この弁別ネットの基本処理は、ｒＷＭＥをルートノード
からすべての枝に流し、各ノードに記憶されている条件
を満たした場合はさらに下流に流し、満たさない場合は
処理を停止し、ターミナルノードに到達した場合、その
ルール条件部が満たされていると判定する」というもの
である。

従って、例えば弁別ネットが初期状態（メモリノードに
何も記憶されていない状態）であるとし、ＷＭＥＩ（ポ
ンプ　＄型式　ＰＯ２＄出刃先Ｔ１）がルートノード１
１１より流されたとする。

この場合、ＷＭＥＩは、まずノードｌに到着し、ｒＷＭ
Ｅ名＝ポンプ」の条件判定が行われる。その結果、条件
が成立して次のノード２へ流れ、ここでも条件成立判定
が成功して、次のノード３へ進み、ＷＭＥＩが記憶され
る。

一方、ノード４では、現在処理中のＷＭＥＩと、本イン
ターノード４の右の枝に結合しているメモリノード７内
に記憶されているＷＭＥとの間で、「ポンプの＄出力先
＝タービンの＄入力光Ｊの判定を行う。現時点では、メ
モリノード７は空であるので処理できず、別の経路であ
るノード５から処理を再開する。

ノード５では、ｒＷＭＥ名＝タービン」の条件判定を行
うが、偽であるので、さらに別の経路であるノード１０
より処理を再開するが、条件判定は失敗する。他に処理
すべき経路がなくなり、ＷＭＥ“ポンプをネットワーク
に流す処理は、この時点で終了する。

次に、ＷＭＥ２（タービン　＄型式　Ｚ　＄出力光　Ｐ
ｌ　＄機器名　タービンＬＸ）が生成され、ネットワー
クへ流されたとする。

この場合、ＷＭＥＩと同様に、ノードｌで条件不成立、
ノード５，６で条件成立、ノード７でＷＭＥ２を記憶、
の過程で処理され、ノード４に到達する。

ノード４では、現在処理中のＷＭＥ２と１本インターノ
ードの左の枝に結合しているメモリノード３内に記憶さ
れているＷＭＥとの間で、「ポンプの＄出力先＝タービ
ンの＄入力」の判定を行う。

前サイクルで、メモリノード３には、ＷＭＥＩが記憶さ
れており、ＷＭＥＩとＷＭＥ２との間での上記条件成立
判定を行う。その結果、条件が成立して、（ＷＭＥ　１
　、ＷＭＥ　２）のリストを生成し、次のノード８へ渡
す。

ノード８では、このリストをコンフルク］・セットに追
加する。つまり、（ＷＭＥ　１　、ＷＭＥ２）がルール
ｌのインスタンシェーションであることが判明したこと
になる。

さらに、このリストは、ノード９へも流れ、β−ｍｅｎ
ノードに記憶される。ノード１１には、何も記憶されて
いないので、ノード１２での処理は失敗し、ＷＭＥ２の
処理を終了する。

さらに、ＷＭＥ３（故障　＄機器名　タービンＬＸ）生
成された場合、ノード１，５，１０．ＩＩの順に処理さ
れ、ノード１１では、Ｗ　Ｍ　Ｅ　３が記憶される。ま
た、ノード１２ては、メモリノード９に（ＷＭ　Ｅ　ｌ
　、　Ｗ〜１Ｅ２）が記憶されており、このリストと、
「タービシの＄機器名＝故障の＄機器名ｊの判定が行わ
れ、（ＷＭ　Ｅ　ｌ　、〜Ｍ　Ｅ　２　。

ＷＭＥ３）のリストが生成されて、ノード１３てコンフ
リクトセットに追加される。

つまり、この時点で、ルール２も実行可能となったこと
になる。

このような弁別ネットの処理手順は、第１２図のように
まとめられる。

第１２図は、本発明の一実施例における弁別ネットの処
理フローチャートである。

本実施例では、ルートノードに続く全てのノードにＷＭ
Ｅを流しく１２０１．１２０２）、到達したノードの種
類を判定して（１２０３）、イントラノードである場合
は、条件成立判定を行い（１，２０４）、成立すれば、
下位のノードにＷＭＥを流す（１２０５）。

また、インターノードの場合には、流れてきた他方の入
力枝のメモリノードに記憶されているＷＭＥの組と、条
件成立判定を行い（１２０８）、成立すれば、新たにＷ
ＭＥの組を生成して下位のノードに流す（１２０９）。

また、ターミナルノードの場合は、流れてきたＷＭＥ（
組）をコンフリクトセットに追加する（１２１０）。

また、メモリノードの場合は、流れてきたＷＭＥ（組）
をそのノード内に記憶し、下位の全てのノードにＷＭＥ
（組）を流す（１２１１）。

ここで、ルール記述の処理構造記述部に記憶されるリス
トの意味と、それを条件成立判定処理にどのように用い
るかを説明する。

第１３図および第１４図は、本発明の一実施例における
弁別ネットの構成側図である。

第７図に示したように、構造指定は、上記のＷＭＥ番号
を要素とする”（”、”）”と”［”、”コ”の２種の
括弧を用いて表現される１種のリストで表現される。

なお、括弧の意味は以下の通りである。

”（”、ｎ）”・・この括弧で囲まれた条件節の判定結
果は記憶されない。

”［”、”コ”・・・この括弧で囲まれた条件節の判定
結果は記憶される。

このリストによって、条件判定の順序（即ち、条件節を
どのような順序でインターノードによって結合するか）
と、判定処理の中間結果の記憶の指定（即ち、α−ｍｅ
ｎ、β−ｍｅｎを生成するかどうか）を表わすことがで
きる。

例えば、 ［［［ｌコ　［２コ　］　［３コ　コ の指定では、第１３図のような弁別ネットが生成される
。つまり、このリストは条件判定の順序として、］番目
の条件節と２番目の条件節をまずインターノード１３４
で結合し、次に、その結合されたものと第３番目の条件
節をインターノード１３６で結合することを示している
。

また、判定処理の中間結果の指定に関しては、［１］、
［２］、［３］の記述から、各条件節にはａ−ｍｅｎ１
３１，１３２，１３３が生成され、Ｃ［＋、］［２］］
の記述から、１番目の条件節と２番目の条件部間のイン
ターノードでの条件判定が成功したＷＭＥの組がβ−ｍ
ｅｎ１３５に記憶されることを示している。

また、 ［［１コ　（［２］　　［３］）］ の指定では、第１４図のような弁別ネットが生成される
。つまり、このリストは１条件判定の順序として、２番
目の条件節と３番目の条件節をインターノード１４４で
結合し、次に、その結合されたものと１番目の条件節を
インターノード１４５で結合することを示している。

また、判定処理の中間結果の指定に関しては、前例と同
様、各条件節には、α−ｍｅｎノード１４１〜）４３が
生成されるが、＋［２］　　［３］１の指定により、２
番目の条件節と３番目の条件部間のインターノード１４
４の条件判定か成功したときの中間結果は記憶されず、
インターノート１４４．１４５間にはβ−ｍｅｎノード
は生成されない。

このように、ルールの処理構造指定に従ってネットワー
クが生成され、推論機構は、このネットワークを用いて
条件成立判定を行う。

従って、過去の処理結果が記憶されていない可能性があ
り、この場合は第１２図に示した処理１２０６．１２０
７のようになる。

即ち、ネットワークに流すＷＭＥがインターノードに到
着した場合、条件判定を行う前に、ＷＭＥが流れてきた
方ではない枝の先にメモリノードがあるかをチエツクし
く１２０６）、もしなければ、他方の枝をメモリノード
に到達するまで逆に辿り、そこに記憶されているＶｖ’
　Ｍ　Ｅを下位に流し、条件判定に必要なＷＭＥの組を
生成する（１２０？）。

さらに、生成されたＷＭＥとノードに記されている条件
判定を行い（１２０８）、成立していれば、下位のノー
ドに流す（１２０９）。

例えば、第１４図で、条件節ｌからＷＭＥを流すと、イ
ンターノード１４５に到達するが、インターノード１４
４の処理結果が記憶されていないので、メモリノード１
４２，１４３に記憶されているＷＭＥを再度下位ノード
に流し、インターノード１４４の条件を満たすＷＭＥの
組を作成し、作成されたＷＭＥの組との間で、インター
ノード１４５の判定を行うという処理が第１２図の処理
１２０６．１２０７である。

（３）ログ収集機構 第１図に示したログ収集機構５は、弁別ネットを用いた
条件成立判定処理過程をモニタして、“イントラノード
、インターノードでの条件成立確率”および″メモリノ
ードに記憶されたリスト各々に対し、参照された回数”
を計測する。

（４）ログ表示機構 第１５図は、本発明の一実施例における処理構造指定と
なる情報の表示フォーマット側口である。

第１図に示したログ表示機構７は、弁別ネットを画面に
表示し、ネットワーク上に、パログ収集機構５により計
測されたイントラノート、インターノードでの条件成立
確率”および“′メモリノードに記憶されたリスト１つ
に対する平均参照回数“を表示する。

第１５図に示すように、Ｐ＝Ｏ９１の記述１５１は、そ
のメモリノードでの条件成立確率が０．１であることを
示しており、また、Ｒ＝１０．５の記述１５２は、その
メモリノードに記憶されたＷＭＥの組は、平均１０．５
回参照されたことを示す。

（５）構造導出機構 第１図に示した構造導出機構８は、ログ収集機構５が計
測したイントラノード、インターノードでの条件成立確
率、およびメモリノードに記憶されたリスト１つに対す
る平均参照回数をもとに、処理効率のよい処理構造を導
き、画面に表示する。

この場合、処理構造を導く基準として、「イントラノー
ドの確率が高い条件節は、ターミナルノードに近いとこ
ろで他の条件節と結合する」、「平均参照回数が小さい
メモリノードは削除する」等を用いて、好ましい処理構
造を導き、画面に第１５図のように表示する。

（６）動的変更機構 第１図に示した動的変更機構６は、一定周期で、ログ収
集機構５が計測したイントラノード、インターノードで
の条件成立確率、およびメモリノードに記憶されたリス
ト１つに対する平均参照回数を得て、これをもとに、処
理効率のよい処理構造を導き、現在推論で用いられてい
る弁別ネットの処理構造と比較する。

なお、処理効率のよい処理構造は、構造導出機構と同様
に、「イントラノードの確率が高い条件節は、ターミナ
ルノードに近いところで他の条件節と結合する」、「平
均参照回数が小さいメモリノードは削除するｊ等の基準
を用いて導く。

また、導き出した処理構造と現在推論で用いている弁別
ネットの処理機構が異なる場合には、推論機構に通知し
、処理構造を入れ換える。

本実施例によれば、ユーザ自身が条件成立の処理構造を
リストの形で簡単に記述でき、また、処理構造を決める
ための情報として、確率や利用度が得られるので、簡単
に処理構造を決めることかできる。

また、典型的な問題を推論させ、そのログブタを構造導
出機構に解析させることにより、自動的に効率のよい処
理構造を表示させることができるので、ユーザ自身が確
率や有効性を解析しむくでも効率のよい処理構造を知る
ことができる。

さらに、推論に用いる処理構造を、一定周期て最適な構
造に動的に置き換える機能により、推論中に、確率や利
用度が変化する問題に対しても、常に効率のよい推論を
行う二とが可能とｌる。

〔発明の効果］ 本発明によれば、推論の高速化に最も重要な処理構造を
ユーザ自身が簡単に指定でき、推論の高速化が図れる。

また、推論実行中の条件判定処理の過程を解析し、処理
構造の決定に必要ｌ情報を表示し、あるいは、効率のよ
い処理構造を提案する機能を設けることにより、ユーザ
の処理構造決定を支援する二とが可能となり、ユーザ自
身による構造指定の負荷が軽政される。

さらに、推論実行中に、一定周期で処理構造を最適化す
る機能を設けることにより、推論実行中に、性質の変化
する問題に対しても、常に効率のよい推論を行うことが
可能である。

【図面の簡単な説明】

第１図は本発明の一実施例における知識データベースシ
ステムの機能構成図、第２図は本発明の一実施例におけ
るＷＭＥのシンタクスを示す説明図、第３図は本発明の
一実施例におけるＷＭＥの記述側面、第４図〜第７図は
本発明の一実施例におけるルールのシンタクスを示す説
明図、第８図は本発明の一実施例におけるルール記述側
面、第９図は本発明の一実施例における推論機構の処理
フローチャート、第１０図は本発明の一実施例における
ルールの条件部側口、第１１図は本発明の一実施例にお
ける弁別ネット側面、第１２図は本発明の一実施例にお
ける弁別ネットの処理フローチャート、第１３図および
第１４図は、本発明の一実施例における弁別ネットの構
成測量、第１５図は本発明の一実施例における処理構造
指定となる情報の表示フォーマット側面である６ １：ユーザ、２・推論機構７３．ワーキングメモリエレ
メント（ＷＭＥ）、　４　　ルール、５：ログ収集機構
、６：動的変更機構、７：ログ表示機構。 ８・構造導出機構、９：ユーザインタフェース管理機構
、２１，２５：括弧、２２：ＷＭＥ名称。 ２３　項目名、２４：値、３１：ＷＭＥ名称、３２〜３
４：項目名と値の組、４１：ルール名称部。 ４２・条件部、４３：実行部、４４・処理構造記述部、
５１：ＷＭＥ名あるいは変数、５２・項目名、５３：比
較語、５４：値あるいは項目名あるいは変数、６１　：
ＣＲＥＡＴＥコマンド、６２：ｔＪＰＤＡＴＥコマンド
、６３：ＤＥＬＥＴＥコマンド、６４　：　ＥＸＥＣＵ
ＴＥコｖンド、６５：ＷＭＥ名称あるいは変数、６６：
項目名、６７：値あるいは項目名あるいは変数あるいは
式、６８：ＷＭＥ記述、７１．７２・括弧、８１　ルー
ル。 ８２　条件部、８３　結論部、８４：処理構造記述部、
８５．８６　　条件節、８７　リスト、１０１．１０２
　　条件部、　　ｌ　３１−１３３　：　ａ−ｍｅｎノ
ード、１３４．１３６．インターノード、１３５β−ｍ
ｅｎノード、　１４１〜１４３　　α−ｍｅｎノード。 １４４．１４５：インターノード　１５１：Ｐ＝０、　
ｌ　ノミ己４１　Ｄ　２　：　Ｒ＝　Ｉ　０．５（１’
）ａｅ述。 区 賊 −口 の−″戸 セ 第 ９ 図 匝腰 工椙 ？　１ ≦ 、　＼ ママ　セ　１　々 ００１０口 札べ 第 １ 図 〔〔〔１〕 〔２〕〕 〔３〕〕 第 図 〔（１〕 （〔２〕 〔３：］）：］ 土４ら

Claims (1)

1. 【特許請求の範囲】 １、推論に用いる知識として、対象世界を構成する１個
   の対象物をスロットとスロットの値の組で表現するフレ
   ームと、フレームの状態を規定する条件の記述、および
   該条件が成立したときに実行すべき動作の組から構成さ
   れるルールを持ち、該条件が成立したルールを順次実行
   することにより、推論を行う知識ベースシステムの推論
   方式において、複数のフレーム間にまたがる条件記述を
   持つルールに対し、個々のフレームに関する条件の成立
   判定の順序の指定と、条件成立判定処理において得られ
   た中間結果の記憶指定と、記憶する中間結果の範囲の指
   定とを行い、該指定に従って条件成立判定を行うことを
   特徴とする条件判定の処理構造最適化による推論の高速
   化方式。 ２、上記個々のフレームに関する条件の成立判定順序の
   指定、条件成立判定処理で得られた中間結果の記憶指定
   、および記憶する範囲の指定からなる処理構造指定を、
   ルール内に記述することを特徴とする請求項１記載の条
   件判定の処理構造最適化による推論の高速化方式。 ３、上記ルールを条件部、結論部、処理構造記述部の３
   要素で構成し、上記個々のフレームに関する条件の成立
   判定の順序の指定と、条件成立判定処理において得られ
   た中間結果の記憶指定と、記憶する中間結果の範囲の指
   定とを該処理構造記述部に記述することを特徴とする請
   求項１記載の条件判定の処理構造最適化による推論の高
   速化方式。 ４、上記個々のフレームに関する条件の成立判定順序を
   指定する場合、ルール条件部を構成するフレームに関す
   る条件節毎に識別名を対応付けて、該識別名を要素とす
   るリスト構造で判定順序を表現し、該リスト構造中には
   、条件成立判定処理で得られた中間結果の記憶指定、お
   よび記憶する範囲の指定を併記する形式で上記処理構造
   記述部に記述することを特徴とする請求項３記載の条件
   判定の処理構造最適化による推論の高速化方式。 ５、上記判定順序を表現するリスト構造には、２種類の
   括弧を有して、上記フレームに関する条件に対応する識
   別子を第１種の括弧で囲むことにより、該フレームに関
   する条件成立処理の中間結果の非記憶を指定し、識別子
   を第２種の括弧で囲むことにより、該中間結果の記憶を
   指定するという記述形態で、条件成立判定処理において
   得られた中間結果の記憶指定、および記憶する範囲の指
   定を表現することを特徴とする請求項４記載の条件判定
   の処理構造最適化による推論の高速化方式。 ６、上記個々のフレームに間する条件の成立判定の順序
   の指定と、条件成立判定処理において得られた中間結果
   の記憶指定と、記憶する中間結果の範囲の指定とを行う
   際に必要な情報を収集して、該情報を表示することによ
   り、処理構造指定を支援することを特徴とする請求項１
   記載の条件判定の処理構造最適化による推論の高速化方
   式。 ７、上記情報には、条件の成立確率、および記憶した中
   間結果の有効性を含むことを特徴とする請求項６記載の
   条件判定の処理構造最適化による推論の高速化方式。 ８、上記情報を表示する場合、条件成立判定の順序をツ
   リー形式で表示し、該ツリー内に該情報を表示すること
   を特徴とする請求項６記載の条件判定の処理構造最適化
   による推論の高速化方式。 ９、上記個々のフレームに関する条件の成立判定の順序
   の指定と、条件成立判定処理において得られた中間結果
   の記憶指定と、記憶する中間結果の範囲の指定を行う場
   合、典型的な推論過程における条件成立判定処理のログ
   情報を解析することにより、最適な判定順序および中間
   結果の記憶範囲の指定を自動的に導き出すことを特徴と
   する請求項１記載の条件判定の処理構造最適化による推
   論の高速化方式。 １０、上記推論過程における条件成立判定処理を一定周
   期でモニタして、最適な処理構造を導き出し、該最適処
   理構造がモニタ時点で用いている処理構造と異なる場合
   、動的に該処理構造を置き換え、最適な処理構造によっ
   て条件成立判定を行うことを特徴とする請求項９記載の
   条件判定の処理構造最適化による推論の高速化方式。