JPH0616266B2

JPH0616266B2 - 計算機システムの高速処理方法

Info

Publication number: JPH0616266B2
Application number: JP58177955A
Authority: JP
Inventors: 節夫鶴田; 捷二宮本; 誠能見
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1983-09-28
Filing date: 1983-09-28
Publication date: 1994-03-02
Anticipated expiration: 2009-03-02
Also published as: JPS6072031A

Description

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

〔発明の背景〕

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

〔発明の目的〕

経験則や自然法則などのルールをプロダクションメモリ
に、事実や仮説をワーキングメモリに持ち、条件部の内
容がワーキングメモリに存在するルールを順次適用する
ことにより計算機に推論を行わすプロダクションシステ
ムが存在する。本発明の目的はプロダクションシステム
の推論速度を、実用上充分高速に、しかも、従来のよう
にルールや条件の数、事実数に依存しない処理方法を提
供することにある。

〔発明の概要〕

規則の条件部と結論部を調べて、どの条件が成立すると
どの規則が起動され、結論部の実行により、どの規則の
条件が新たに成立したり不成立になったりするのかの関
係をネットワーク構造にして登録しておく。ただし、規
則に変数を含む場合の処理を行うために、変数の具体値
により照合する可能性のある条件項と結論項をグループ
化し、その代表を連想項とし、連想項の個別部により事
実を貯えるようにし、連想項を核に上記ネットワークを
構成した。

〔発明の実施例〕

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

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

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

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

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

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

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

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

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

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

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

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

第１Ｆ図は第１Ｄ図の事実を第１Ｅ図上にはめ込んだ状
態を示す。第１Ｆ図において、大きい丸印中の実線の長
円は入力済の事実を示し、点線の長円は新しい初期事実
（例：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 likes
＞Ｆ）のコードだけを要素とするリスト）をつなぐ。次
に照合した（John like⁻）を共通部リスト（４００）
から削除し、８０３に戻り、新しい候補項（⁻like
s⁻）が共通部リスト（４００）にないことをチェック
し、これを共通部リスト（４００）に加える（８０
７）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

まず、追加値２１６の事実属性２２６の値をチェックす
る（ブロック1900）。ｔ（追加項は変数を含まず、かつ
既知事実である。）なら、直ちに追加処理を終了する。
空なら、追加項の変数属性２２７が空かどうかをチェッ
クし（ブロック1903）、Ｙｅｓなら追加項の事実属性２
２６にｔをセットし（ブロック1904）、Ｎｏなら追加項
の事実属性２２６に、変数属性２２７の値、つまり変数
列２４１の各要素２４２を具体化させたもの（以下、変
数の具体値と呼ぶ）を追加する（ブロック1902）。ブロ
ック1900の結果が、ｔあるいは空以外なら、追加項の変
数の具体値が、具体値リスト２４８の要素のどれかと一
致するかをチェットし（ブロック1901）、一致すれば追
加項目は既知事実であるから追加処理を終了し、不一致
なら、上述のブロック1902の処理を行う。ブロック190
2、ブロック1904の処理の後、行動部実行結果を“変
化”にセットし（ブロック1905）、追加項の規則連想属
性２２２の値、つまり連想規則リスト２５０を候補規則
リスト２６０に結合する（ブロック1906）。

次に、追加項の項連想属性２２３をとり出す（ブロック
1907）。項連想属性２２３が空なら追加処理を終了し、
空でないなら、その値の要素（連想項２４５）を順次取
出す（ブロック1908）。連想項２４５の処理が全て終了
すれば、追加処理を終了する。そうでなければ、連想項
の個別構造２４０と、追加項の個別構造（ただし変数は
具体化されている。）との照合をとる（ブロック190
9）。照合が不成功ならブロック1908に戻り次の連想項
を取出す。照合が成功すれば、連想項の変数の具体値
（ブロック1902で説明したもの。）が連想項の具体値リ
スト２４８の要素２４９のどれかと一致するかチェック
し、（ブロック1910）、どれかと一致すれば、直ちに、
どれとも一致しなければ、連想項２４５の規則連想属性
２２２の値、すなわち連想規則リスト２５０を候補規則
２６０に結合した（ブロック1911）後、ブロック1908に
戻り、次の連想項の処理を行なう。

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

まず、削除項２１５の事実属性２２６の値をチェックす
る（ブロック2001）。空なら削除処理を終了する。ｔ
（削除項は変数を含まず、しかも既知事実である。）な
ら、削除項２１５の事実属性２２６を空にし（2004）、
さらに、候補規則リスト２６０から削除項２１５の規則
連想属性２２２の値、つまり連想規則リストの要素２５
１を全て削除する（ブロック2005）。ブロック2001の結
果が、ｔや空以外なら、削除項２１５の変数属性２２７
の値（変数列２４１）の各要素（変数２４２）を具体化
させたもの（変数の具体値。ブロック1902で定義したも
のと同じ。）が、同じ削除項２１５の具体値リスト２４
８の要素２４９のどれかと一致するかをチェックし（ブ
ロック2002）、一致しなければ、削除処理を終了し、一
致すれば、上記の変数の具体値を、削除項２１５の事実
属性２２６の値、すなわち具体値列リストから削除する
（ブロック2003）。ブロック2003、ブロック2005の終了
後、行動部実行結果を、“変化”に設定する（ブロック
2006）。

次に、削除項２１５の項連想属性２２３をチェックする
（ブロック2007）。空なら、削除処理を終了する。空で
なければ、項連想属性の値、すなわち、連想項リスト２
４４の要素（連想項２４５）を順次取出す（ブロック20
08）。全ての連想項を取出せば、削除処理を終了する。
連想項に対しては、その個別構造２４０が、削除項の個
別構造（ただし変数要素を具体化したもの）と照合する
か（具体化してない変数は全ての定数と照合することを
前提とする。）をチェックし（ブロック2009）、照合が
不成功なら、次の連想項の処理をするためにブロック20
08に戻る。照合が成功した場合、連想項の変数属性２２
７が空かどうかをチェックし（ブロック2010）、空でな
ければ、連想項の変数の具体値（ブロック2002で定義し
たもの）が、同じ連想項の具体値リスト２４８の要素２
４９のいずれかと一致すればこれを削除して、いずれと
も一致しなければ何もしないで、ブロック2008に戻る。
ブロック2010の結果が空なら、連想項は定義しか含まな
いなら、まず、連想項の事実属性２２６を空にし（ブロ
ック2012）、次に、候補規則リスト２６０から連想項の
規則連想属性２２２の値、つまり連想規則リスト２５０
の要素２５１を全て削除し（ブロック2013）、ブロック
2008に戻る。

〔発明の効果〕

(1)ある規則の実行後、次に起動される可能性のある規
則群が事前に連想ネットに保存されているので、次に実
行する規則を探す時間が全体の規則数に依存しない。

(2)条件項が事実かどうかを事実属性として保持してい
るため、従来のように事実空間内の全事実と照合をとる
必要がない。つまり、条件項が事実かどうかのチェック
に要する時間が事実の数に依存することがない。このこ
とと(1)とから、推論時間が規則×事実の数に独立にな
る。規則数か数１００事実数が５０以上の実用的な推論
システムでは、このための効率向上は基本的なオーバヘ
ッドを考慮しても数百倍以上となる。

(3)マルチプロセッサや連想メモリ等の特殊なアーキテ
クチャーの計算機、素子を用いていないので安価に高速
化が実現できる。また、ソフトウエアの移行性も高い。

(4)規則の実行によって追加されたり削除されたりする
事実に対しては、その定数要素などの共通要素の関連は
事前に分析し連想ネットに組み込んであるので、変数要
素の具体値（実行時に変数のとる値）だけ既存の事実と
照合すればよく、オーバヘッドの大半を占める照合時間
が短縮される。通常、事実を表わす文の変数要素は、文
の要素の１〜２割程度であるから照合時間は、５〜１０
倍に向上すると考える。

(5)定数要素や変数要素を文の任意の位置に書いた規
則、つまり、自然語的に表現された規則や事実を入力
し、推論結果もこの形式（自然語的な表現形式）で出力
するので、マンマシンインタフェース、操作性が性能向
上と引き換えに損われることがない。

(6)条件項で、その一部の変数要素が特別な定数値と指
定してあるものとないものを統合し、連想項グループと
して効率良く処理できるため、知識の記述・表現などシ
ステムの操作性を損わずに効率の向上が可能である。

(7)初期事実の連想ネットへの組込みは、連想フィルタ
を用いたため、組込み時間は、（全規則の項の総数）×
（事実数）に比例する時間かかるはずのものが、その対
数時間に減少する。

(8)事実を削除した時、連想項のうち定数型のものを条
件部に持つ規則だけを候補規則集合から削除することに
より、少ないオーバヘッドで無駄な規則の条件チェック
数を減らせるので全体の処理速度が向上する。

(9)実行した結果、新事実の追加や削除などにより環境
を変化させることのなかった規則に不変属性を設定して
実行を抑止することにより、無駄な条件チェック時間、
実行時間が減り、全体の処理速度が向上する。

(10)実行の結果、新事実の追加や削除などにより環境変
化が生じた場合は、他の変数具体値に対して同じ規則の
実行を行うのでなく、候補規則集合をチェックして環境
の変化により先に実行すべき規則ができたらそれを実行
するので自然な競合解消処理が行える。

(11)候補規則集合（リスト）に、追加あるいは削除すべ
き規則が、項を構成する変数の照合だけで決定できるた
め、不要となった定数部の照合時間だけ、全体の処理効
率が増す。

(12)事実は変数に対応する部分のみ、その変数の具体値
として記憶するため、項ごとに事実を記憶しても所要メ
モリは少なくて済む。

(13)連想フィルタにおいて終端ノード（最終状態）を特
に作成せず、ノードが終端と非終端の両属性を持てる方
式であるため、処理が簡単な上、メモリ効率も良い。

(14)不変属性（(9)参照）を、他の規則が実行されて環
境が変化したらクリアすることは、その環境の変化が不
変属性を持つ規則の処理結果が、新環境を変化させるか
という複雑な処理を行うことなく、不変属性を持つ規則
の新環境での実行の機会を与える。

(15)実行時に条件が成立しないことが判明した規則は、
候補規則集合から削除されるので、無駄な条件照合チェ
ックにより処理効率が低下することがない。

(16)事実が追加されることによって規則の条件項のうち
１つでも満足されれば、その規則を候補規則とし（候補
規則集合に加え）、その規則の他の条件のチェックは実
行時に行なうため、全実行条件が満足されないと候補規
則に加えない方式と比べて（この方式では、事実が削除
された時の処理が複雑になる。）簡単なチェックで候補
規則が絞れるために全体の処理効率が向上する。

(17)連想フィルタは共通項のみを識別すれば良いので、
同一状態（ノード）にある時、多種の変数を入力した場
合のような複雑な変数処理が不要であるため、処理が簡
単で処理効率が良い。特に、連想フィルタは、事実の組
込みなど多用され全体の性能に影響を与えるので、その
処理効率の向上は、システム全体の性能の向上に寄与す
る。

なお、上述した説明では推論について説明したが、上述
した方法は、一般の情報処理にも当てはまる。

【図面の簡単な説明】

第１Ａ図は本発明の方法を実現するためのシステム構成
図、第１Ｂ図は本発明の方法の計算機システム上での実
現構成図、第１Ｃ図はルール集合の１例を示す図、第１
Ｄ図は初期事実の１例を示す図、第１Ｅ図は初期事実に
もとづく連想ネットワークの１例を示す図、第１Ｆ図は
第１Ｄ図の事実を第１Ｅ図上にはめ込んだ状態を示す
図、第１Ｇ図は連想フィルタの具体例を示す図、第２図
は連想ネットの構成図、第３図および第４図は、それぞ
れコードリストおよび連想ネット共通部（作成時）のデ
ータ構造の一例を示す図、第５図は連想フィルタの構成
図、第６図は連想ネット作成処理フローを示す図、第７
〜１０図はその詳細処理フローを示す図、第１１〜１３
図は（初期）事実組込み処理フローを示す図、第１４〜
２０図は、推論実行処理フローを示す図である。１００…連想ネット作成プロセッサ、１０１…初期事実
組込みプロセッサ、１０２…推論実行プロセッサ、１０
３…規則ファイル、１０４…初期事実ファイル、１０５
…連想フィルタ、１０６…連想ネット、２００…規則リ
スト、２１０…規則、２１３…条件項、２１５…削除
項、２１６…追加項、２２１…項コード、２５１…連想
規則、２４５…連想項、２４０…個別構造、２４９…具
体値列、２４１…変数列、２３０…共通部、２３３…共
通構造、２６１…候補規則。

Claims

【特許請求の範囲】

【請求項１】その要素として定数の他に変数も含みう
る、条件項と行動項を持つ、少なくとも１個の規則と事
実が与えられた時、該規則に従って事実を変更する推論
サイクルを繰返すことにより情報処理を行う計算機シス
テムにおいて、 (イ)上記規則に対応するデータブロック（２１０）と、上記各項に対応した連想項と呼ぶデータ
ブロック（２２０）と、上記各項のうち定数の位置と値
が同じ部分を抽出し、その構造を記述した共通部と呼ぶ
データブロック（２３０）と、上記各項からそれぞれの
共通部の定数を除いた残りである個別要素を記述した個
別構造と呼ぶデータブロック（２４０）と、個別要素の
具体値を格納する具体値列リストと呼ぶデータブロック
（２４８）とをノードとして含み、連想項と共通部の
間、連想項と規則との間、および連想項から個別構造
と、連想項から具体値列リストとに枝を張ることによ
り、あるいは、更に同じ共通項を持つ連想項の間に直接
に枝を張ったり、個別構造や具体値列リストを連想項に
含めることにより、連想ネットワークをあらかじめ作成
し、 (ロ)終端ノードと非終端ノードと呼ぶ異種のノードを持
ち、終端ノードは上記共通部の識別コードを持ち、非終
端ノードは次ノードの番号を持ち、次ノードの番号は上
記事実と共通部の要素を順に比較し（１００４，１００
６）、両方の要素が共に定数である場合に定数の位置を
一致させ（１００７，１００８，１００９，１０１
０）、定数の値を一致させ（１００９，１０１１，１０
１２，１０１３）、該位置と値が一致した同じ構造の状
態で全要素を比較終了した（１００４，１００５）時
に、該同じ構造の共通部の識別コードを持つ終端ノード
に遷移する（１００９，１０１０，１０１３）様に変数
と定数の値に対応したものである、連想フィルタを作成
し、 (ハ)与えられた事実を連想フィルタに通して、同じ構造
を持つ共通部を取出し、連想ネットワークの枝をたどっ
て該共通部の構造を持つ連想項を取出し、その具体値列
リストに共通部の定数以外の事実を組込み、 (ニ)上記連想ネットワークをたどって、上記事実の要素
を変更して上記推論サイクルを繰り返すことにより推論
処理を実行する計算機システムの高速処理方法。