Reteアルゴリズム
Reteアルゴリズムに関する最適化手法がいくつか提案されている。ただし、適用可能なシナリオが非常に限定されていて、汎用の推論エンジンには使えないものもある。また、Reteの代替アルゴリズムとして TREAT や LEAPS といったものも提案されており、性能的にも向上している。そのような代替アルゴリズムを採用した商用/オープンソースのプロダクションシステムはまだ少ない。
Reteアルゴリズムは、前向き連鎖を使った推論を行うもので、既存の事実から新たな事実を生成したり、何らかの結論によって事実を打ち消したりする。また、事実群を組合せ的に評価する効率的機構でもある。類似の手法として決定木を使った方法もあるが、こちらはより単純なシナリオ向きである。
Reteアルゴリズムの定義には含まれないが、一部の推論エンジンは拡張機能として真理性維持制御を行う。例えば、あるプロダクションのマッチングが生じた場合、それによって新たな WME が追加され、別のプロダクションの条件にマッチングすることがある。そして、その結果としてワーキングメモリが更新されて最初のプロダクションのマッチングが否定される結果となった場合、2番目のマッチングも否定されることを意味する(つまり矛盾が生じる)。Reteアルゴリズムはこのような論理的真理値依存問題に自動的に対応する機構を備えていない。しかし、一部の推論エンジンは真理値依存関係を自動的に保守する機能をサポートしている。
Reteアルゴリズムは「弁明; justification」の手法を定義していない。「弁明」とは、エキスパートシステムや意思決定支援システムで一般に必要とされる機構であり、簡単に言えば、ある結論に至った際の内部の判断過程を報告する機能である。例えば、エキスパートシステムがある動物を象であると判断した際の「弁明」として、それが大きく、灰色で、大きな耳と鼻と牙を持っているから、などと報告する。推論エンジンによっては、Reteアルゴリズムを実装しつつ「弁明」機能を組み込んでいるものもある。
(現在はフェア・アイザックに買収された)RulesPower にいたころ、フォーギーは Rete II の後継である Rete IIIを開発した。Rete III は大規模なルール群や大量の事実群を扱う場合でも Rete II よりさらに高性能を発揮している。
否定の実装方法は様々である。例えば、右側入力のWMEと左側入力のWMEリストのマッチングした回数をカウントし、カウントがゼロの場合にWMEリストを次に送る。また、内部にベータメモリ形式のメモリ領域を持ち、マッチングしたWMEをそこに格納していき、その領域に何も存在しないときだけWMEリストを送る方式もある。この方式では否定ノードはベータメモリを介さずに直接後続のベータノードを活性化する。否定ノードは一種の「失敗による否定; negation as failure」を提供する。
ワーキングメモリが更新されると、それまでマッチングしなかった WME リストが新たな WME とマッチングする場合がある。この場合、ベータメモリなどにあるWMEリストの全コピーを回収する必要がある。この処理を否定ノードを使って効率的に行うことが多い。WMEリストが削除されると、対応するプロダクション・インスタンスが非活性化され、アジェンダから削除される。
存在量化は2つの否定ベータノードを組み合わせることで実現できる。つまり、二重否定である。この手法はいくつかのプロダクションシステムで採用されている。