JPH0616267B2 - 計算機システムの高速処理方法 - Google Patents

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は、経験則や自然の法則と初期事実から新事実や
仮説を推論する（プロダクション）システムの高速化処
理方法に係わり、特に、大規模で時間がかかりすぎた
り、リアルタイム性を要求される場合に好適な、高速推
論のための計算機システムの高速処理方法に関する。

〔発明の背景〕

規則と事実から推論を行なうのに、推論の各サイクル毎
に全ての規則と事実の照合をとって実行規則を決めるの
がプロダクションシステムであるが、規則と事実の増大
と共に推論時間が爆発的に増大し実用規模では有用でな
い。これを防止するため、規則や事実のコード化とその
インデキシングを行なっている。特に、弁別ネットを用
いた高速方式が効率・適用性において優れているが、規
則の各項目によっては弁別ネットのオーバヘッドは大き
く、リアルタイムシステムへの実用化上問題がある。

また、規則にカウンタを持たせ、その初期値をその条件
項の数に等しくし、事実のプールであるワーキングメモ
リに、この規則の条件項と類似の事実が加えられたらカ
ウンタの値を１減らし、削除されたらカウンタの数を１
増し、カウンタの値が０か、マイナスになったら、この
規則を実行候補規則に加え、より完全な実行チェックを
行なう方式（一種のフィルタ）が提案されているが、こ
のフィルタは、効率が悪い。なぜなら、同一条件項の変
数の値が異なる場合に相当する事実が連続して加えられ
ると上記カウンタは常に０以下になり、他の条件項の事
実属性が空の規則が実行候補規則に加えられ、変数の値
のすべての組合わせを試みた後、実行条件を満さないと
判定するロスを生じる。また、類似の条件項を見つける
だけであるから実行条件を満さない規則を実行候補規則
に加えるだけでなく、実行条件を満す規則さえ実行候補
規則から削除すること、つまり不良を発生することすら
ある。

〔発明の目的〕

本発明の目的は、高度な知的情報処理を可能にするプロ
ダクションシステムあるいは、これに類する計算機シス
テムの実行速度を、実用上充分高速に（特に、コマンド
アンドコントロール等厳しいリアルタイム性を要求され
る場合にも耐えれるように）、しかも、ルールや条件の
数，事実数，変数の数などにより性能の急激な低下に対
処するために実行候補規則を選択する効率的な方法を提
供することにある。

〔発明の概要〕

従来技術の問題点で述べたように、カウンタによる実行
候補規則のフィルタでは、実行条件を満足しない規則が
多数、実行候補に加えられるため推論効率が低下する。
特に変数の数や種類が多い場合、効率低下が著るしい。
フィルタリング機能が高く、しかもオーバヘッドの少な
いフィルタが必要となる。本発明では、この要求に応じ
るため、変数の値の矛盾は無視した場合に、条件が全て
満足される規則のみを実行候補とするフィルタに特徴が
ある。

〔発明の実施例〕

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

第１Ａ図は、本発明の方法を実現するためのシステム構
成である。

連想ネット作成プロセッサ１００は、規則ファイル１０
３から、規則を取出し、規則の起動条件やその起動が他
の規則の起動や推論に及ぼす影響を分析し、その結果を
連想ネット（但し、事実組込み前のもの）１０６として
出力する。また、初期事実を連想ネットに効率良く組込
むための連想フィルタ１０５を作成する。初期事実組込
みプロセッサ１０１は、初期事実ファイル１０４から事
実を取出し、連想ネット１０６の該当場所に組込む。推
論実行プロセッサ１０２は、連想ネット１０６をベース
に、高速推論を行ない推論結果１０７を出力する。

第１Ｂ図は、本発明の方法の計算機システム上での実現
構成図である。

連想ネット作成プロセッサ１００、初期事実組込みプロ
セッサ１０１、推論実行プロセッサ１０２、連想フィル
タ１０５は、推論プログラム１５１として、また、連想
ネット１０６は推論用知識１５２として、それぞれＣＰ
Ｕ１５０に置かれる。

コンソールディスプレー１５３（キーボード、コンソー
ルタイプライタでも良い）から、規則や初期事実を入力
する。実際のシステムでは、初期事実の入力は、センサ
ーなども用いることも可能である。推論の実行（あるい
は連想ネット１０６の作成など推論の準備）など推論制
御指令１６０もコンソールディスプレー１５３から入力
する。

推論結果は、（ライン）プリンタ１５４やＣＲＴ１５
５、あるいは、ディスクやＭ／Ｔなどの補助記憶装置１
５６に出力する。推論制御指令１６０により、推論結果
に至るまでの推論経過の出力も可能である。

補助記憶装置１５６には、規則ファイル１０３、初期事
実ファイル１０４、連想ネット１０６を保存し、エラー
回復や前処理に利用できる。

以下、具体的な事実や規則とこれを用いた連想ネットワ
ークの作成について説明する。

第１Ｃ図は上記プロダクションシステムで用いるルール
集合の具体例を示す。同図において、＞ＦはＦが変数で
あることを示し、＞のつかない文字は定数であることを
示す。Ｆは女性、Ｍは男性、またＰは人を示す。さら
に、行動項（ｔｈｅｎ項）中のａｄは追加されるべき項
目、ｒｄは除去されるべき項目をそれぞれ示す。

初期事実が第１Ｄ図に示すものであると仮定して、実行
関係を表わすネットワーク、すなわち、初期事実にもと
づく連想ネットワークが第１Ｅ図のように具体化され
る。

第１Ｅ図において、ルール番号Ｒ１〜Ｒ５で示される水
平線はその上側及び下側が、それぞれ第１Ｃ図に示され
るルール集合のうちの関連するルールのｉｆ部及びｔｈ
ｅｎ部に対応することを表わしている。水平線の下につ
けた小さい丸印はここから発する矢印で示される大きい
丸印が除去されるべき項目であることを示すものであ
る。

第１Ｆ図は第１Ｄ図の初期事実を第１Ｅ図上にはめ込ん
だ状態を示す。第１Ｆ図において、大きい丸印中の実線
の長円は入力済の事実を示し、点線の長円は新しい初期
事実（例：Kate comes from Paris）がそこに加えられ
る時の状態を示す。さらに、長円を囲む円はルールの項
目を示し、点線で結ばれた項目は関連する項目（連想
項）であることを示す。

第２図は高速に推論を実行するための連想ネット１０６
の構成を示す。

２００は、規則のリストであり、その要素２０１はコー
ド化された規則２１０であり、条件部２１１と行動部２
１２から成る。条件部，行動部の各項２２０もコード化
されており、それぞれ条件項２１３、行動項２１５〜２
１７から構成される。行動項は、さらに、削除項２１
５、追加項２１６、停止項２１７などに分れる。

上記の各項２２０は、項コード２２１、項を条件部に持
つ規則（連想規則２５１）のリスト２５０を値として持
つ規則連想属性２２２、共通の型の項（連想項２４５）
のリスト（連想項リスト２４４）を、値として持つ項連
想属性２２３、連想項間の共通部２３０を値として持つ
共通部属性２２４、個別な部分（個別構造２４０その要
素は個別要素２４３）を値として持つ個別部属性２２
５、項が既知事実かどうかを示す事実属性２２６項を含
む変数（関数でも良い。以後同様）２４２を順番に並べ
た変数列２４１を値に持つ変数属性２２７、項の内容２
４６（その要素を２４７に示す。）を値として持つ内容
属性２２８、から構成される。

具体値（列）リスト２４８は、項の変数の具体値の列
（具体値列２４９）のリストであり、項が変数２４２を
含む時の事実属性２２６の値である。

共通部２３０は、そのコード２３５と、その内容である
共通構造（その要素である共通要素２３４は、項の要素
のうちの個別要素２４３に対応するものを“−”（アン
ダーライン）に変換し、他の項の要素はそのままにした
もの）２３３を値として持つ構造属性２３１と、この共
通部を持つすべての項（共通部連想項２３６）のリスト
である共通部連想項リスト２３５を値として持つ連想項
属性２３２とから成る。

候補規則リスト２６０は、実行）候補規則２６１のリス
トである。

第３図は、コードリストのデータ構造を示す。すなわ
ち、コード化した項２２０を登録するコードリスト３０
０は、項の内容２２１と対応するコード２４６から成る
コードペア３０１を要素とするリストである。項のコー
ド化（後述。ブロック６０２）に用いる。

第４図は、連想ネット共通部のデータ構造である。本デ
ータ構造は、連想ネット共通部作成（ブロック６０３。
後述）の途中段階のものである。すなわち共通部候補４
０１は、共通部の候補であり、連想ネット共通部作成処
理終了時点以降は、共通部２３０と一致する。同様に、
共通部リスト４００は、共通部作成中は共通部候補４０
１、作成後は共通部２３０を要素とするリストである。
共通部コード４０２、構造属性４０３、項連想属性４０
４、共通要素４０６、連想項リスト４０５も、共通部候
補に関するものであることを除いては、第２図で説明し
た共通部に関するそれらと同様である。

第５図は、連想フィルタ１０５の構成を示す。

連想フィルタは、初期ノード（ノード番号５０１が０の
ノード）から始まるノード５００のトリー構造体であ
る。各ノード５００は、ノード番号５０１、変数特徴属
性５０２、定数特徴属性５０３、終端属性５０４から成
る。システムは、ノード上を動きながら、初期事実の要
素（定数，変数）を読み込むが、変数特徴属性５０２は
変数を読み込んだ時にシステムが動く先のノード次ノー
ド（５０７）を、定数特徴属性５０３は、どの定数５０
８を読み込んだら次ノード５０９がどのノードであるか
のペア５０６を要素とする表（変数特徴属性値５０５）
を、それぞれ値として持つ。終端属性５０４は、ノード
５００が共通部リスト４００に登録された共通部のいず
れかをシステムが読み込んだ時、初期ノードから到達す
る先のノードである時、その共通部２３０の共通部コー
ド２３５を、そうでない時には空を値として持つ。

第６図は、連想ネット作成処理を示す。

まず、規則の項のうちその内容が記号列として互いに異
なるものにユニークを番号をつけるために、新コード番
号を１に、規則の項を取出すためのポインタを１に初期
設定する（ブロック６００）。次に、規則ファイル１０
３から規則の項を取出すとともにポインタを更新する
（ブロック６０１）。取出した項は、照合の高速化のた
めにコード化して、連想ネット１０６の規則２１０に埋
込むとともに、規則連想属性２２２を設定する（ブロッ
ク６０２）。さらに、連想ネット１０６の共通部２３０
を作成する。以上の処理を規則ファイル１０３の全ての
規則の項に対して行なった後、連想ネット１０６の個別
構造２４０を作成する（ブロック６０４）。また、連想
フィルタ１０５を作成する（ブロック６０５）。

第７図は、項をコード化した規則２１０を作成し、規則
連想属性２２２を設定するための処理である。

ブロック７０１では、ブロック６０１で取出した規則の
項が、コードリスト３００に既登録かどうかをチェック
する。既登録なら、登録されている該コードを現コード
とする（ブロック７０２）。未登録なら、項の内容２４
６と新コード番号のペア（コードペア３０１）を、コー
ドリスト３００に追加し（ブロック７０３）、現コード
番号の値を新コード番号の値に設定し、新コード番号を
更新する（ブロック７０４）。ブロック７０５では、現
コード番号にユニークに対応する項コード２２１を持つ
項２２０の変数属性２２７として、取出した項が含む変
数２４２を先頭から順にリスト結合したもの（変数リス
ト２４１）を、内容属性２２８として、項の内容２４６
を設定する。

さて、ブロック７０２あるいは、ブロック７０５の処理
が終了したら規則２１０の項２２０の項コード２２１を
現コードとし、条件部２１１、もしくは行動部２１２か
らネットワークを張って、連想ネット１０６の一部とす
る（ブロック７０６）。さらに、処理の項が、条件項２
１３なら、その規則連想属性２２２の値、つまり連想規
則リスト２５０の要素２５１として自項が属する規則の
規則コード２１４を追加する。

第８図は、連想ネット１０６の項の共通部２３０を抽
出，作成するための処理フローである。

ブロック８０１では、ブロック６０１で取出した規則の
項の変数（関数を含む、以後同様）を−に変えたものを
（共通部）候補項４０１とする。この候補項のコード
（将来の共通部コード）４０２は、たとえば、取出した
項のコードがｆ_ｉのときａ_ｉとする。次に、ブロック８
０２では、候補項４０１の項連想属性４０４として、上
記の候補項のコード４０２を設定する。

さて、ブロック８０３では、（共通部）候補項４０１
と、共通部リスト４００に登録ずみの各候補項との照合
をとり、既登録かどうかのチェックを行なう。ただし、
この照合では、₋はどの要素（定数，変数）とも照合が
成功するものとする。

既登録なら、まず、候補項と照合した共通部リスト内の
候補項の₋以外の要素４０６のうち、候補項の₋と照合
した要素を₋に置替えたものを、改めて候補項とする。
この候補項のコードは、上記の照合した共通部リスト内
の候補項のコード４０２とする（ブロック８０４）。次
に、この新しい候補項の連想項リストに、もとの候補項
の連想項リストを結合する（ブロック８０６）。さら
に、もとの候補項と照合した共通部リスト内の候補項を
共通部リスト４００から削除する。ブロック８０３から
ブロック８０６までの処理を、ブロック８０３の処理結
果が既登録である間中くり返し、結果が未登録になれ
ば、連想ネット１０６の共通部リスト４００に候補項４
０１を追加して（ブロック８０７）、ブロック６０１で
取出した項に対する共通部作成処理を終了する。

第９図は、連想ネット１０６のうち各項に個別な部分
（個別構造２４０）を作成するための処理方式を示す。

共通部リスト４００の要素、つまり共通部２３０（以後
の処理では、共通部リストが確定しているので、（共通
部）候補項４０１は、すべて共通部２３０になる。）を
順次取出し（ブロック９０１）、その項連想属性２２３
の値、つまり連想項リスト２４４をとり出す（ブロック
９０２）。次に、その要素、つまり、共通部を共有する
連想項のグループ（連想グループ）のメンバーとなる項
（連想項２４５）を順次取出す（ブロック９０３）。連
想項リストの要素の取出しが全て終了すれば、ブロック
９０１に戻って、共通部リスト４００から次の要素を取
出し、共通部リストの要素を全て取り出すまで繰返し同
じ処理を行う。

さて、ブロック９０４では、取出した連想項９０４に対
して、共通部２３０の共通構造２３３の要素２３４の値
が₋である要素の共通構造内の相対位置にある連想項の
要素２４７を取出してリストにしたものを同連想項の個
別部属性２２６の値として、個別構造２４０に設定す
る。次に、連想項の共通部属性２２４として、ブロック
９０１で取出した共通部２３０のコード２３５を設定し
（ブロック９０５）、ブロック９０３の処理に戻る。

以上、第６〜９図に連想ネット作成法のうち事実や仮説
を取込む前の部分を述べたが、これを第１Ｃ図と第１Ｅ
と図いた具体例で説明する。

第６図のブロック６００で初期化後、６０１で規則Ｒ１
の項（＞Ｆ likes wine）を取出し、ブロック６０２つ
まり第７図の処理を行なう。上記の項をコード化し、コ
ードリスト（３００）に設定し（７０３）、コード化さ
れた項の変数属性２２７にその変数のリスト（上例では
＞Ｆだけ）を、内部属性２２８には項の内容、つまり＞
Ｆ，likes,wineを要素とするリストを設定する（ブロッ
ク７０５）。ブロック７０６で規則Ｒ１に対応する条件
項２１３に上記の項のコードを設定し、上記の項が条件
項か判定し（７０７）、条件項なので、この項の規則連
想属性２２２に規則Ｒ１の識別コードを設定する（７０
８）。以上でブロック６０２の処理を終り、次に６０３
の処理、つまり第８図の処理を行う。まず項（＞Ｆ li
ke wine）の変数＞Ｆを特別コード（特殊記号）⁻で置
換えた（⁻likes wine）を候補項とし（８０１），連想
項リスト（２３６，最初は空）に項のコードを加える
（８０２）。上記候補項は共通部リスト（４００，最初
はこれも空）に未登録なので⁻（８０３），共通部リス
トに上記候補項（のコード）を加える（８０７）。

以上でブロック６０３の処理を終り、６０１に戻り、規
則Ｒ１の次の項（＞Ｆ is female）を取出す。以下，
上記と同様の処理を行ない共通部リスト（４００）の値
は（⁻likes wine）と（⁻is female）から構成される
リストとなる。また規則Ｒ１の条件部には（＞Ｆ is f
emale）のコードも追加される。

次に、規則Ｒ１の項（John likes＞Ｆ）が６０１で取出
されるが、この場合、規則Ｒ１の行動部２１２にそのコ
ードが設定される（ブロック７０６）。項の内容を対応
コードに入れ替えるだけなのでａｄ（追加），ｒｍ（削
除）などの情報は保存される。さて、第８図のブロック
８０１でこの項は（John likes⁻）と変形され候補項と
なるが、共通部リスト（４００）には（likes wine）が
存在する。そこで８０３でJohnとwineのいずれも⁻に照
合するため、８０４で（⁻likes⁻）が改めて候補項と
なり、８０５でその連想項リスト（＞Ｆ like wine）
のコードに８０７で作成した連想項リスト（（John lik
es＞Ｆ）のコードだけを要素とするリスト）とつなぐ。
次に照合した（Johe like⁻）を共通部リスト（４０
０）から削除し、８０３に戻り、新しい候補項（⁻like
s⁻）が共通部リスト（４００）にないことをチェック
し、これを共通部リスト（４００）に加える（８０
７）。

以上でブロック６０１に再び戻り、 （Adam likes＞Ｆ）を取出し、上記と同様の処理を行な
い、共通部リスト（４００）は（⁻is female）のコー
ドと（⁻likes⁻）のコードを要素とするリストとな
る。また後者の要素に対する（共通部）連想項リスト２
３６は（Adam likes＞Ｆ），（John likes＞Ｆ），（＞
Ｆ likes wine）のそれぞれのコードを要素とするリス
トとなる。

以上を第１Ｃ図の全規則（Ｒ１〜Ｒ５）の全項に対して
繰返し、処理終了後、ブロック６０４つまり、第９図の
処理を行ない。連想ネット個別部を作成することによ
り、第１Ｅ図の連想ネット（事実や仮説の取込まれてい
ないもの）が作成できる。詳細には共通部リスト（４０
０）の要素、例えば（₋like₋）に対応するコードを取
出し（９０１）、その連想項リスト（２３５）を取出し
（９０２）その要素つまり連想項２２０（Adam likes＞
Ｆ），（John…），（＞Ｆ likes wine））を取出し
（９０３），共通部（₋likes₋）の₋の位置にある例
えば⁻Adam，＞Ｆのリストを個別部属性（２２５）の値
（２４０）として設定し（９０４）、共通部属性２２４
に共通部（₋likes₋）のコードを設定する（９０５）
を全連想項に対して繰返す。

第１０図は、初期事実１０４を連想ネット１０６に取込
むための連想フィルタ１０５を作成するための処理方法
を示す。

ブロック１００１では連想フィルタ１０５のノードに与
える番号（新ノード番号）を１に設定する。次に、共通
部リスト４００から順次、その要素２３５を取出す（ブ
ロック１００２）。取出す要素がなくなれば処理を終了
する。取出す要素があれば、まず、現在のノードを出発
ノード（例えば、番号０のノード）とする（ブロック１
００４）。次に、共通部２３０の要素２３４を順次取出
す（ブロック１００４）。ブロック１００６では、取出
した要素２３４が、₋（変数に対応）かどうかをチェッ
クし（ブロック１００６）、Yesなら、現在のノード５
００の変数特徴属性５０２の値が空かどうか調らべ（ブ
ロック１００７）、空なら、新ノード番号を現ノードの
変数特徴属性５０２として設定する（ブロック１００
８）。空でなければ、変数特徴属性５０２の値を現ノー
ドとする（ブロック１０１０）。ブロック１００６の処
理結果がＮｏなら、ブロック１００４で取出した要素２
３４が、現在のノード５００の変数特徴属性５０２に含
まれるかどうかをチェックし（ブロック１０１１）、含
まれなければ、取出した要素２３４と新ノード番号の対
を現在のノードの定数特徴属性５０３に追加し（ブロッ
ク１０１２）、含まれれば、マッチした定数時特徴属性
値５０５の要素５０６に対応するノード５０７を現在の
ノードとする。また、ブロック１００８，１０１２の処
理が終了すれば、ブロック１００９において、新ノード
番号のノードを現ノードにし、新ノード番号を更新す
る。ブロック１００９，１０１０，１０１３の処理の後
１００４に戻り、共通部２３０の要素２３４がなくなる
まで、ブロック１００６以下の処理を繰返す。取出す要
素がなくなると、現在のノード５００の終端属性５０４
に、ブロック１００２で取出した共通部２３０のコード
２３５を設定する（ブロック１００５）。

以下が連想フィルタ１０５の作成法であるが、第１Ｃ図
の規則に対して、連想フィルタを構成した具体例が第１
Ｇ図である。この具体例で連想フィルタの作成法を述べ
る。

先ず、第１Ｃ図の規則から第８図に従って共通部リスト
を作成する。第８図によると、変数やそれに対応する位
置にある定数は全て特別コード₋によって置き換えられ
共通部リストに設定される。従って共通部リストは（（
₋likes₋）（₋loves₋）（₋lies）（₋is female）
（₋is beautiful）（₋is young）（₋comes from Par
is））となる。

第１０図のブロック１００２で上記共通部リストの各要
素（共通項）、例えば（₋likes₋）を取り出す。１０
０４でこの要素の要素である₋やlikesを順次取出す。
₋なら変数特徴属性）第５図の５０２）に次ノード番号
を、⁻likesなど⁻以外なら定数特徴属性（第５図の５
０３に定数値（この場合likes）と次ノード番号の対
（第５図の５０６）を追加する。これを繰返してネット
ワークのパスを構成する。共通項の要素を全て取出した
ら、現ノードの終端属性（第５図の５０４）に共通項の
識別コード（共通部コード）をセットする（第１０図の
ブロック１００５）。上記の共通部リストの全要素に対
し以上の処理を終了すると第１Ｇ図の連想フィルタが構
成できる。

第１１図は、初期事実１０４を連想ネット１０６に組込
むための処理を示す。

まず、初期事実ファイル１０４から事実を先頭から順に
取り出し（ブロック１１００）、取出す事実がある間、
以下の処理を行う。つまり、ブロック１１０１では、事
実を連想フィルタ１０５に通して、対応する共通部２３
０と個別具体値を取出す（事実のフィルタリング処理
（第１２図））。つぎに、この共通部２３０の連想項リ
スト２３５の中から、上で取出した個別具体値に、その
個別構造２４０が照合する連想項２３６を選択し、その
事実属性２２６に具体値列２４９を追加する（ブロック
１１０２）。

第１２図は、事実のフィルタリング処理を示す。

まず、個別具体値（リスト）を空に設定し、さらに、現
在のノード５００を出発ノード（ノード番号０）とし
（ブロック１２０１）、ブロック１１００で取出した事
実に対して、その要素（すなわち事実の文を構成する定
数や変数）を、前から順次取出す（ブロック１２０
２）。

取出した要素に対して、それが、現在のノード５００の
定数特徴属性値５０５に含まれるかどうかをチェック
（ブロック１２０３）、含まれなければ、現在のノード
の変数特徴属性５０２の値が空かどうかをチェックし
（ブロック１２０４）、空なら、事実フィルタリング処
理の結果に空を設定（ブロック１２０８）し処理を終了
する。空でなければ、ブロック１２０２で取出した要素
を個別具体値（リスト）に追加する。この後、あるい
は、ブロック１２０３の処理結果がYesの時、前者では
変数特徴属性５０２によって示される次ノードを、後者
では、取出した要素とその定数部５０８が一致する定数
特徴属性値５０５の要素の次ノード部５０９が示す次ノ
ードを現在のノード５００とし、ブロック１２０２の処
理に戻る。ブロック１２０２で取出す要素がなくなれ
ば、現在のノード５００の終端属性５０４が空かどうか
をチェックし（ブロック１２０７）、空でないことが確
認できたら、事実のフィルタリング処理の結果として、
終端属性５０４の値（つまり共通部コード２３５）と、
個別具体値（リスト）を設定する（ブロック１２０
９）。終端属性５０４が空なら、事実のフィルタリング
処理の結果を空とする。（ブロック１２０８）。

事実を連想ネットワークに組み込むための連想フィルタ
の使用法は以上の通りである。これをより具体的に第１
Ｄ図の事実を第１Ｅ図の連想ネットワークに連想フィル
タ第１Ｇ図を用いて組込む例で説明する（第１１〜１３
図参照）。第１Ｇ図において、枝上の定数（lies,isな
ど）はすぐ上側にあるノード（○印）の定数特徴属性の
要素値である。終端ノード（◎印）はそれぞれ（ ）付
文の識別コードをその終端属性として持つ。例えば第１
Ｄ図の事実の最終の(Kate comes from Paris)に対して
は、第１Ｇ図の連想フィルタのパスのうち、その構成要
素である各枝が全て上記の事実の構成要素と一致するパ
スである（＞Ｆ，＞Ｍ，＞Ｐなど＞を付加した変数に対
応する枝はどれにも一致する）第１Ｇ図の右端のパス
（＞Ｐcomes from Paris）が第１２図のブロック１２０
１〜１２０７の処理によって選ばれる。

より詳細には、まずブロック１２０１で現ノードが第１
Ｇ図の出発ノードに設定され、上例の事実である(Kate
comes from Paris)の要素Kateが第１２図の１２０２で
取出される。第１Ｇ図の出発ノードからは特別コード
（変数）に対応する枝しか出てない、つまり定数特性属
性は空なのでブロック１２０３では“No”で、ブロック
１２０４で“Yes”となり、ブロック１２０５でKateが
対応する変数（この場合＞Ｐ）の個別具体値として設定
され、ブロック１２０５で先のノードが現ノードにな
る。再びブロック１２０２に戻り、次の要素comesが取
出され、ブロック１２０３でcomesが現ノードの定数特
徴属性に含まれることが分り（第１Ｇ図の出発ノードの
すぐ下の○印ノードからcomesの枝が出ていることから
分かり）、ブロック１２０６で、対応する枝の先のコー
ド（第１Ｇ図の３段目の右端のノード）に現ノードが移
り、再び１２０２に戻り、次の要素fromを取り出す。以
下、同様の処理の反復により、第１Ｇ図右端のパスの最
下端の◎印のノードが現ノードとなり、ブロック１２０
７に入る。このノードの終端属性は（₋comes from Par
is）の識別コードであり、空でないから終端ノードであ
り、ブロック１２０９に進む。

さて、１２０９で、この終端属性、つまり（comes from
Paris）の識別コード（共通部コード７３５の値）が取
出される。同様に個別具体値（−つまり変数）に対応す
る部分の定数値も取出される。以上が、第１１図のブロ
ック１１０１つまり、事実のフィルタリングの結果とし
て取出されるものである。次に、取出した共通部コード
に対する連想項の事実属性に個別具体値を設定する（ブ
ロック１１０２）。即ち、まず、取出した共通部コード
（の値）を持つ共通部（第２図の２３０）を取出し、そ
の連想項属性（２３２）から共通部連想項リスト２３５
を取出す（１３０１）。さらに、このリストの要素（連
想項２３６）が指す全ての項（２２０）に対して、その
事実属性２２６の指す具体値リスト２４８に、上記の個
別具体値（本例ではKate）を設定する（第１３図の１３
０６）。以上を繰返すことにより、連想ネット第１Ｅ図
の中空の円内に第１Ｄ図の事実が第１Ｇ図の連想フィル
タを用いて組込まれ第１Ｆ図の様に事実を（円内に）組
込んだ連想ネットを作成できる。

第１３図は、初期事実に対応する事実属性２２６の値と
して、具体値列２４９を組込むための処理（事実属性設
定処理）である。

ブロック１３０１では、事実のフィルタリング処理の結
果が空でなければ、共通部の項連想属性２３２の値、つ
まり、（共通部）連想項リスト２３５を取出す。結果が
空なら事実属性設定処理を終了する。次に、（共通部）
連想項リスト２３５から連想項２３６を先頭から順に取
出し（ブロック１３０２）、以下の処理を行う。

まず、事実のフィルタリング処理の結果である事実の個
別具体値と上記の連想項２３６の個別構造２４０との照
合をとる。個別構造２４０の要素２４３が変数の時は、
対応する位置の個別具体値の要素が、その変数に対する
変数具体値として設定される（ブロック１３０３）。照
合が不成功ならブロック１３０２に戻り、次の連想項を
とり出す照合が成功すれば、上記の連想項２３６の変数
属性２２７の値が空かどうかをチェックし（ブロック１
３０４）、空なら、さらに事実属性２２６が空かどうか
をチェックする（ブロック１３０８）。空でなければ、
すでに、連想ネットに組込み済みの事実であるから、ブ
ロック１３０２に戻り、次の連想項の処理を行う。空で
あれば、上記の連想項の事実属性を空以外、例えばｔに
設定し（ブロック１３０９）。同じく規則連想属性２２
２の値である連想規則リスト２５０を、候補規則リスト
２６０に結合し（ブロック１３０７）、ブロック１３０
２に戻る。

ブロック１３０４で、連想項の変数属性値が空でなけれ
ば、ブロック１３０３で設定した変数具体値（列）が連
想項の事実属性２２６の値（具体値リスト２４８）の要
素である具体値列２４９のどれかに一致するかをチェッ
クし（ブロック１３０５）、一致すれば、ブロック１３
０２に戻り、次の連想項の処理を行う。一致しなけれ
ば、変数具体値（列）を具体値リスト２４８に追加し、
ブロック１３０７の処理を行う。

第１４図は、推論実行プロセッサ１０２の処理方式を示
す。

推論の実行のためには、まず、候補規則リスト２６０が
空かどうかをチェックし（ブロック１４０１）、空なら
推論実行処理を終了する。空でなければ、候補規則リス
ト２６０の要素である候補規則２６１の中から最初に実
行する規則を選択する（ブロック１４０２……競合解消
処理）。この場合、不変属性が設定されている規則は、
推論結果が新事実の生成や削除など、環境の変化に寄与
しないので選択の対象外とする。次に、選択された規則
を実行し（ブロック１４０３）、その結果が変化（上記
の環境の変化に寄与する場合）なら、候補規則２６１で
不変属性が設定されているものは、すべてその不変属性
を解除し（ブロック１４０４）、ブロック１４０１へ戻
る。結果が不変なら、実行した規則に不変属性を設定し
（ブロック１４０５）ブロック１４０１へ戻る。結果が
不成立（規則の条件が成立しない場合）、実行した規則
２６１を、候補規則リスト２６０から削除し（ブロック
１４０６）、やはり、ブロック１４０１へ戻る。結果が
“停止”なら、本処理（推論実行処理）を終了する。

第１５図は規則実行処理（ブロック１４０３）を示した
ものである。まず、結果を“不成立”にし（ブロック１
５００）、次に実行規則の条件部２１１が満足されるか
どうかをチェックする。変数に対しては具体値が矛盾な
く決めることができるかをチェックする（以上ブロック
１５０１）。条件が不成立なら、本処理（規則実行処
理）を直ちに終了する。条件が成立すれば、行動部２１
２を実行し（ブロック１５０２）、その結果が“不変な
ら”本処理の結果を“不変”とし（ブロック１５０
５）、ブロック１５０１に戻り、条件部２１１が、異な
る具体値の組に対して成立するかをチェックする。行動
部実行結果が“停止”なら規則実行処理結果を“停止”
に設定し（ブロック１５０３）、“変化”なら本処理の
結果を“変化”にして（ブロック１５０４）、規則実行
処理を終了する。

第１６図は実行条件判定処理（ブロック１５０１）を示
す。

実行規則の条件部２１１の先頭から順に条件項２１３を
取出し（ブロック１６０１）、取出した条件項２１３の
事実属性２２６をチェックし（ブロック１６０２）、そ
の値がｔ（つまり変数を含まない項でしかも条件が成立
する）なら、次の条件項を取出すためにブロック１６０
１に戻る。事実属性の値が空なら、条件が不成立である
から、条件判定処理の結果を不成立に設定して（ブロッ
ク１６０６）、本処理、すなわち、実行条件判定処理を
終了する。事実属性の値が、ｔや空以外であれば、その
要素、つまり具体値列２４９を順次取出し（ブロック１
６０３）、取出した具体値列と変数属性２２７の値（変
数列２４１）との照合をとる（条件項変数部照合処理…
…ブロック１６０４）。照合が成功すれば、すなわち変
数の具体値が矛盾なく定まれば（詳細は第１７図）、次
の条件項を調べるためにブロック１６０１に戻り、照合
が成功しなければ、次の具体値を取出すために、ブロッ
ク１６０３に戻る。ブロック１６０３において、次に取
出すべき具体値列がなくなれば、ブロック１６０６の処
理を行う。ブロック１６０１で、次に取出すべき条件項
がなくなれば、条件判定処理の結果を“成立”に設定し
て（ブロック１６０５）、本処理を終了する。

第１７図は、条件項変数部照合処理（ブロック１６０
４）を示す。

変数列２４１から、その要素である変数２４２を順番に
取出し（ブロック１７０１）、取出した変数１７０２の
値が、同じ規則内の前の条件項との照合においてすでに
定まっているか（つまり既束縛変数かどうか）をチェッ
クし（ブロック１７０２）、未束縛なら該変数を未束縛
変数列に加え、具体値列の対応要素を束縛値とし（ブロ
ック１７０３）、次の変数を処理するためにブロック１
７０１に戻る。既束縛変数に対しては、束縛値と具体値
列２４９の対応要素が一致するかどうかをチェックし、
一致すればブロック１７０１に戻り、一致しなければ、
未束縛変数列の変数をすべて未束縛にし、未束縛変数列
をクリアし（ブロック１７０５）、本処理（条件項変数
部照合処理）の結果を“照合不成功に設定し（ブロック
１８０６）、本処理を終了する。

さて、ブロック１７０１において、変数列２４１から取
出すべき要素がなくなれば、本処理の結果を“照合成
功”に設定して（ブロック１７０７）、本処理を終了す
る。

第１８図は、行動部実行処理（第１５図のブロック１５
０２）を示す。

まず、本処理（行動部実行処理）の処理結果を、“不
変”に初期設定する（ブロック１８０１）。つぎに、実
行規則の行動部２１２の行動項２１５〜２１７を先頭か
ら順番に取出す（ブロック１８０２）。取出した行動項
が追加項２１６かどうかチェックし（ブロック１８０
３）、追加項なら、追加処理を行う（ブロック１８０
４）。次に、行動項が削除項２１５かどうかをチェック
し（ブロック１８０５）、もしそうなら削除処理を行な
い（ブロック１８０６）、そうでないなら停止項かどう
かをチェックし（ブロック１８０７）、停止項２１７な
ら行動部実行処理の結果を“停止”に設定して、（ブロ
ック１８０９）本処理を終える。行動項が以上のいずれ
の項でもなければ、該当する処理を行ない（ブロック１
８０８）、ブロック１８０２に戻り次の行動項の処理を
行う。ブロック１８０４，１８０６の処理の後も、同様
にブロック１８０２に戻る。ブロック１８０２で取出す
べき行動項がなくなれば、変数２４２の束縛値をクリア
し（ブロック１８１０）、本処理を終了する。

第１９図は、追加処理（第１８図のブロック１８０４）
を示す。

まず、追加項２１６の事実属性２２６の値をチェックす
る（ブロック１９００）。ｔ（追加項は変数を含まず、
かつ既知事実である。）なら、直ちに追加処理を終了す
る。ｔでなく、かつ、空でもないなら、追加項の変数の
具体値が、具体値リスト２４８の要素のどれかと一致す
るかをチェックし（ブロック１９０１）、一致すれば追
加項目は既知事実であるから追加処理を終了し、不一致
なら、またはブロック１９００の結果が空なら、追加項
の個別構造２４０でその変数や関数要素をその具体値で
置き換えたもの（個別構造具体値と呼ぶ）、および、連
想項リスト２４４を取出す（ブロック１９０２）。

次に、取出した連想項リスト２４４からその要素である
連想項２４５を順次取出す（ブロック１９０３）。取出
すべき連想項がなくなれば、直ちに追加処理を終了す
る。次のブロック１９０４では、取出した連想項は定数
からのみ構成されるかをチェックし、そうでなければ、
ブロック１９０５、そうならばブロック１９０９の処理
を行なう。ブロック１９０５では、追加項２１６の個別
構造具体値（ブロック１９０２で取出したもの）とブロ
ック１９０３で取出した連想項２４５の個別構造２４０
の照合をとる。照合が不成功なら、ブロック１９０３に
戻る。照合が成功すれば、取出した連想項２４５の事実
属性２２６の値（具体値列リスト２４８）に、連想項２
４５の変数２４２の値の列（具体値列２４９）を追加す
る（ブロック１９０６）。ブロック１９０９では、追加
項２１６の個別構造具体値（ブロック１９０２で取出し
たもの）と、連想項２４５の個別構造２４０が一致する
（照合は変数を含む場合で、ブロック１９０５で述べた
照合は、定数部が一致すれば良く、変数部はチェックし
ないもの。従って、変数を含まない“照合”の意味で、
本ブロックでは“一致”とした。）かどうかチェックす
る。不一致ならブロック（９０３に戻る。一致すれば、
連想項２４５の事実属性２２６の値２４８を、真値（例
えばｔ）とする（ブロック１９１０）。

ブロック１９０６，１９１０の処理に続いて候補規則選
択処理（ブロック１９０７）を行う。ここでは、連想項
の規則連想属性２２２の値の要素、つまり連想規則２５
１のうち、その条件部２２１のすべての条件項２１３の
事実属性２２６が（空以外の）値を持つものだけを、候
補規則リスト２６０に加える。詳細は、第２０図を用い
て、後で説明する。本ブロックの処理が終了すると、行
動部実行結果を“変化”にセットし（ブロック１９０
８）、ブロック１９０３の処理に戻る。

第２０図は、候補規則選択処理（第１９図のブロック１
９０７）を示す。

まず、連想項２４５の規則連想属性値、つまり、連想規
則リスト２５０を取出す（ブロック２００１）。つぎ
に、この連想規則リスト２５０の先頭から順に連想規則
２５１を取出す（ブロック２００２）。すべての連想規
則の処理が終了すれば、候補規則選択処理（本処理）を
終了する。取出した連想規則２５１に対しては、これが
すでに候補規則リスト２６０に含まれているかどうかを
チェックする（ブロック２００３）。含まれておれば、
ブロック２００２に戻り、次の連想規則の処理を行う。
含まれてなければ、連想規則の条件項２１３のうち、そ
の事実属性２２６の値が空のものがないかをチェックす
る（ブロック２００４）。空のものがなければ、この連
想規則を候補規則リスト２６０に追加し（ブロック２０
０５）、ブロック２００２に戻る。空のものがあれば、
何もしないでブロック２００２に戻る。

第２１図は、削除処理（第１８図のブロック１８０６）
を示す。

まず、削除項２１５の個別構造２４０で、その変数をそ
の（具体）値で置換えたもの（個別構造具体値）を取出
す（ブロック２１０１）。さらに、削除項２１５の連想
項リスト２４４も取出す（ブロック２１０２）。

次に、連想項リスト２４４から、その要素である連想項
２４５を先頭から順次取出す（ブロック１９０３）。取
出して処理すべき連想項がなくなれば削除処理を終了す
る。取出した連想項２４５に対しては、これが定数だけ
を含むかどうかをチェックし（ブロック２１０４）。
“ＮＯ”ならブロック２１０５、ＹＥＳならブロック２
１０９の処理を行う。

ブロック２１０５では、削除項２１５の個別構造具体値
（ブロック２１０１で取出したもの）と連想項２４５の
個別構造２４０の照合をとる。照合が成功しなければ、
ブロック２１０４に戻り、次の連想項の処理を行なう。
照合が成功すれば、連想項２４５の事実属性値（つまり
具体値列リスト２４８）から、この連想項の変数２４２
の値の列（具体値列２４９）を削除する（ブロック２１
０６）。その結果、この連想項２４５の事実属性値が空
になれば、ブロック２１０７、空にならなければ、ブロ
ック２１０４の処理を行なう。

ブロック２１０９では、削除項２１５の個別構造具体値
と、取出した連想項２４５の個別構造２４０が一致する
かどうかをチェックする。一致しなければ、ブロック２
１０４に戻り、次の連想項の処理を行なう。一致すれ
ば、連想項２４５の事実属性２２６の値を空にし（ブロ
ック２１１０）。ブロック２１０７の処理を行なう。

ブロック２１０７では、候補規則リスト２６０から、連
想項２４５の規則連想属性２２２の値の要素（つまり連
想規則２５１）を全て削除する。続いて、ブロック２１
０８において、行動部実行結果を“変化”に設定し、ブ
ロック２１０３の処理に戻る。

〔発明の効果〕

本発明によれば、変数の値の矛盾などを無視した条件部
のチェックをまず行なうことにより、実行候補規則を絞
ることができるので、すべての変数の組合わせに対して
条件部が成立するかどうかをチェックして条件部が満足
されないような、組合わせ論的に急増するオーバヘッド
を効率良く抑止でき推論効率・性能が向上する。

このオーバヘッドを定量的に見積ると、 Θ＝Ｉ_ｖ ^Nv・Ｔ_ｃ・Ｎ_ｒ ただし Ｎ_ｒ…実行候補規則に加えられたが、条件を満
足しないことが判明した規則の平均数 Ｎ_ｖ…上記規則内の変数の平均数 Ｉ_ｖ…上記規則内の変数の具体値の平均数 Ｔ_ｃ…変数の組合わせの一つに対して条件部を満足する
かチェックする時間の平均値 Ｔ_ｃ＝１０ミリ秒，Ｎ_ｖ＝３，Ｉ_ｖ＝３，Ｎ_ｒ＝５００
とした場合Θ＝１３５秒，これがＮ_ｖ＝５，Ｉ_ｖ＝５と
なるとΘ＝１５０００秒となり急激に増大し、実用に耐
えられない。実験したところ、従来の方式（カウント方
式）でＮ_ｒ＝５５０であったが、本発明の方式ではＮ_ｒ
＝６０となり、約１０倍、オーバヘッドが減少した。
（Ｎ_ｒを絞るための時間は、変数の値の矛盾を無視した
テストであるから充分小さいと考えられる。実験でも１
秒以下であり、充分無視できる。） 連想ネットを用いると、条件項の属性として事実が記憶
されるので上記テストの処理効率が良い。

なお、上述の説明では推論について述べたが、一般に情
報処理にも適用できることは言うまでもない。

【図面の簡単な説明】

第１Ａ図は本発明の方法を実現するためのシステム構成
図、第１Ｂ図は本発明の方法の計算機システム上での実
現構成図、第１Ｃ図はルール集合の１例を示す図、第１
Ｄ図は初期事実の１例を示す図、第１Ｅ図は初期事実に
もとづく連想ネットワークの１例を示す図、第１Ｆ図は
第１Ｄ図の事実を第１Ｅ図上にはめ込んだ状態を示す
図、第１Ｇ図は連想フィルタの具体例を示す図、第２図
は連想ネットの構成図、第３図はコードリストのデータ
構造を示す図、第４図は連想ネット共通部のデータ構造
を示す図、第５図は連想フィルタの構成図、第６〜９図
は連想ネットの作成の流れ図、第１０図は連想フィルタ
の作成を示す図、第１１〜１３図は事実組込み処理を示
す図、第１４〜２１図は推論実行処理の流れ図である。 ２５１……連想規則、２１３……条件項、２２６……事
実属性、２６０……候補規則集合又は候補規則リスト、
２３６……連想項、２４２……変数、２２２……規則連
想属性、ブロック２００４……変数の値の矛盾は無視し
て条件部の事実属性をチェックする処理、ブロック２１
０７……削除後の事実属性が空の連想項の規則連想属性
の全要素を候補規則集合から削除する処理。

Claims (4)

【特許請求の範囲】
1. 【請求項１】その要素として定数の他に変数も含みう
   る、条件項と行動項を持つ、少なくとも１個の規則と事
   実が与えられた時、該規則に従って事実を変更する推論
   サイクルを繰返すことにより情報処理を行う計算機シス
   テムにおいて、事実が追加されたら、該事実に関連する
   条件項を見つけ、該事実を該条件項の事実属性として登
   録し、該条件項を含む規則の条件部のすべての条件項に
   対して、その事実属性が空か否かをチェックし、どの条
   件項の事実属性も空でない規則だけを、さらに完全にチ
   ェックするための実行候補リストに加え、該リストに加
   えられた規則にたいしてのみすべての条件項を変数の一
   致チェックも含めてチェックする完全条件チェックをお
   こなうことを特徴とする計算機システムの高速処理方
   法。
2. 【請求項２】前記完全条件チェックをおこなう処理は、
   チェックを行なった結果、条件部が満足されないことが
   判明した規則を実行候補リストから削除する処理を含む
   特許請求の範囲第１項記載の計算機システムの高速処理
   方法。
3. 【請求項３】前記削除する処理は、削除されるべき事実
   に対応する条件項の事実属性から該事実を削除し、該条
   件項の事実属性が空か否かをチェックし、空なら、該条
   件項を条件部に含む規則を前記実行候補リストから削除
   する処理からなる特許請求の範囲第２項記載の計算機シ
   ステムの高速処理方法。
4. 【請求項４】前記登録する処理は、（イ）規則の行動部
   のうちの追加項または削除項によってそれぞれ追加又は
   削除される事実にもとづき満足されるか否かを決定する
   条件項を連想項として前記追加項または削除項の属性と
   して登録する処理と、（ロ）該条件項を条件部に含む規
   則を前記追加項または削除項の属性として登録する処理
   と、（ハ）該追加項または削除項によってそれぞれ追加
   または削除される事実がその連想項である前記条件項を
   含む条件部のすべての条件項の変数値と矛盾しないか、
   どうかを決める追加項または削除項内の要素に対応する
   前記連想項の変数名とその値を前記連想項の個別部属性
   として登録する処理とにより、事実を前記追加項または
   削除項、および条件項の各項の事実属性として分散して
   保持できるようにあらかじめ作成した情報ネットワーク
   である連想ネットワークに前記各項の属性として与えら
   れた初期事実を登録する処理からなる特許請求の範囲第
   １項記載の計算機システムの高速処理方法。