Reteアルゴリズム

ノードグラフの「左側」（アルファ側）は、WME属性を定数値と照合する単純な条件テストに基づいて個々のWMEを選択する識別ネットワークを形成します。識別ネットワーク内のノードは、同じWMEの2つ以上の属性を比較するテストも実行できます。WMEが1つのノードで表される条件に正しく一致した場合、次のノードに渡されます。ほとんどのエンジンでは、ルートノードの直下の子ノードを使用して、各WMEのエンティティ識別子またはファクトタイプをテストします。したがって、同じエンティティタイプを表すすべてのWMEは、通常、識別ネットワーク内の特定のノードブランチをたどります。

識別ネットワーク内では、アルファノード（1入力ノードとも呼ばれる）の各ブランチは、アルファメモリと呼ばれるメモリで終端します。これらのメモリには、特定のノードブランチ内の各ノードの各条件に一致するWMEのコレクションが格納されます。ブランチ内の少なくとも1つの条件に一致しないWMEは、対応するアルファメモリ内には具体化されません。アルファノードのブランチは、条件の冗長性を最小限に抑えるために分岐する場合があります。

グラフの「右側」（ベータ側）は、主に異なる WME 間の結合を実行します。これはオプションであり、必要な場合にのみ含まれます。ベータ側は 2 つの入力ノードで構成され、各ノードは「左」と「右」の入力を持ちます。各ベータノードは、その出力をベータメモリに送信します。

Reteの説明では、ベータネットワーク内でのトークンの受け渡しについて言及するのが一般的です。しかし、本稿では、実装オプションの違いやトークンの本来の目的と用途を考慮し、トークンではなくWMEリストを用いてデータ伝播について説明します。WMEリストがベータネットワークを通過する際、新しいWMEが追加され、リストはベータメモリに格納されます。ベータメモリ内のWMEリストは、特定の生成条件に対する部分一致を表します。

ベータノードのブランチの末尾に到達した WME リストは、単一のプロダクションに対する完全な一致を表し、ターミナルノードに渡されます。これらのノードは、 p ノードと呼ばれることもあり、「p」はプロダクションを表します。各ターミナルノードは単一のプロダクションを表し、ターミナルノードに到着する各 WME リストは、そのプロダクションの条件に一致する WME の完全なセットを表します。プロダクションノードは、受信した各 WME リストに対して、「アジェンダ」上の新しいプロダクションインスタンスを「アクティブ化」します。アジェンダは通常、優先順位付きキューとして実装されます。

ベータノードは通常、ベータメモリに格納されているWMEリストとアルファメモリに格納されている個々のWMEとの間で結合を実行します。各ベータノードは2つの入力メモリに関連付けられています。アルファメモリはWMを保持し、新しいWMEを格納するたびにベータノードに対して「右」アクティベーションを実行します。ベータメモリはWMEリストを保持し、新しいWMEリストを格納するたびにベータノードに対して「左」アクティベーションを実行します。結合ノードが右アクティベートされると、入力アルファメモリから新しく格納されたWMEの1つ以上の属性を、入力ベータメモリに含まれる各WMEリスト内の特定のWMEの指定された属性と比較します。結合ノードが左アクティベートされると、ベータメモリ内の新しく格納された単一のWMEリストを走査し、指定されたWMEの特定の属性値を取得します。これらの値をアルファメモリ内の各WMEの属性値と比較します。

各ベータノードは、ベータメモリに格納されるか、またはターミナルノードに直接送信されるWMEリストを出力します。WMEリストは、エンジンが後続のベータノードで追加の左活性化を実行する場合に、ベータメモリに格納されます。

論理的に、ベータノードのブランチの先頭にあるベータノードは、ネットワークの上位にあるベータメモリから入力を受け取らないため、特殊なケースです。この問題は、エンジンによって異なる方法で処理されます。一部のエンジンでは、専用のアダプタノードを使用してアルファメモリをベータノードの左入力に接続します。他のエンジンでは、ベータノードが2つのアルファメモリから直接入力を受け取ることを可能にし、一方を「左」入力、もう一方を「右」入力として扱います。どちらの場合も、「先頭」のベータノードは2つのアルファメモリから入力を受け取ります。

ノードの冗長性を排除するために、任意のアルファメモリまたはベータメモリを複数のベータノードでのアクティベーションに使用できます。ベータネットワークは、結合ノードに加えて、追加のノードタイプを含むことができ、その一部は以下に説明します。Reteにベータネットワークが含まれていない場合、アルファノードは、それぞれ単一のWMEを含むトークンをpノードに直接供給します。この場合、アルファメモリにWMEを保存する必要はありません。

マッチング・解決・実行のサイクル中、エンジンは現在ワーキングメモリにアサートされている事実に対して可能なすべてのマッチングを見つけます。現在のマッチングがすべて見つかり、対応するプロダクションインスタンスがアジェンダ上でアクティブ化されると、エンジンはプロダクションインスタンスが「実行される」順序を決定します。これは競合解決と呼ばれ、アクティブ化されたプロダクションインスタンスのリストは競合セットと呼ばれます。順序は、ルールの優先度（顕著性）、ルールの順序、各インスタンスに含まれる事実がワーキングメモリにアサートされた時間、各プロダクションの複雑さ、またはその他の基準に基づいて決定されます。多くのエンジンでは、ルール開発者が異なる競合解決戦略を選択したり、複数の戦略を連鎖させたりすることができます。

競合解決はReteアルゴリズムの一部として定義されていませんが、アルゴリズムと併用して使用されます。一部の特殊な生産システムでは、競合解決は実行されません。

競合解決が完了すると、エンジンは最初のプロダクションインスタンスを起動し、そのインスタンスに関連付けられた一連のアクションを実行します。これらのアクションは、プロダクションインスタンスのWMEリストで表されるデータに対して作用します。

デフォルトでは、エンジンはすべてのプロダクションインスタンスが起動されるまで、各プロダクションインスタンスを順番に起動し続けます。各プロダクションインスタンスは、1 つのマッチ-解決-実行サイクル中に最大で 1 回のみ起動します。この特性は屈折と呼ばれます。ただし、プロダクションインスタンスの起動シーケンスは、ワーキングメモリに変更を加えることで、どの段階でも中断される可能性があります。ルールアクションには、エンジンのワーキングメモリから WME をアサートまたはリトラクトする命令を含めることができます。いずれかのプロダクションインスタンスが 1 つ以上の変更を実行するたびに、エンジンは直ちに新しいマッチ-解決-実行サイクルに入ります。これには、ワーキングメモリに現在ある WME の「更新」が含まれます。更新は、WME をリトラクトしてから再度アサートすることで表されます。エンジンは変更されたデータのマッチングを実行し、その結果、アジェンダ上のプロダクションインスタンスのリストが変更される可能性があります。したがって、特定のプロダクションインスタンスのアクションが実行された後、以前にアクティブ化されていたインスタンスが非アクティブ化されてアジェンダから削除され、新しいインスタンスがアクティブ化されている可能性があります。

新しいマッチング・解決・実行サイクルの一環として、エンジンはアジェンダ上の競合解決を行い、現在実行中の最初のインスタンスを実行します。アジェンダ上に本番インスタンスがなくなるまで、エンジンは本番インスタンスを起動し続け、新しいマッチング・解決・実行サイクルに入ります。この時点で、ルールエンジンは処理を完了したとみなされ、停止します。

一部のエンジンは高度な屈折戦略をサポートしており、前のサイクルで実行された特定のプロダクションインスタンスは、たとえ議題上に存在していても、新しいサイクルでは再実行されません。

エンジンが無限ループに陥り、アジェンダが空の状態にならない場合があります。そのため、ほとんどのエンジンは、本番環境のアクションリストから呼び出せる明示的な「停止」コマンドをサポートしています。また、無限ループが一定回数繰り返された後に自動的に停止する自動ループ検出機能を提供するエンジンもあります。一部のエンジンは、アジェンダが空になったときに停止するのではなく、外部から新しい事実が提示されるまで待機状態に入るモデルをサポートしています。

競合解決に関して言えば、アクティブ化された本番インスタンスの起動はReteアルゴリズムの機能ではありません。しかし、Reteネットワークを使用するエンジンでは、競合解決は中心的な機能となっています。Reteネットワークが提供する最適化の中には、エンジンが複数のマッチング・解決・実行サイクルを実行するシナリオでのみ有効なものもあります。

条件付きテストは、個々のタプルに対して選択や結合を実行するために最も一般的に使用されます。しかし、追加のベータノードタイプを実装することで、Reteネットワークで量化を実行することが可能になります。 存在量化は、ワーキングメモリ内に一致するWMEのセットが少なくとも1つ存在するかどうかをテストします。 全称量化は、ワーキングメモリ内のWMEのセット全体が特定の条件を満たすかどうかをテストします。全称量化の変形として、WMEのセットから抽出された特定の数のWMEが特定の基準を満たすかどうかをテストする場合があります。これは、一致する正確な数または最小数のどちらかをテストする形で行われる可能性があります。

量化は Rete エンジンで普遍的に実装されているわけではなく、サポートされている場合でもいくつかのバリエーションが存在します。否定と呼ばれる存在量化のバリエーションは広くサポートされていますが、普遍的ではなく、主要なドキュメントに記載されています。存在否定条件と論理積では、一致する WME または WME のセットが存在しないことをテストする特殊なベータ ノードを使用します。これらのノードは、一致が見つからない場合にのみ WME リストを伝播します。否定の正確な実装は様々です。あるアプローチでは、ノードは左入力から受け取った各 WME リストに対して単純なカウントを保持します。このカウントは、右入力から受け取った WME との一致の数を示します。ノードは、カウントがゼロの WME リストのみを伝播します。別のアプローチでは、ノードは左入力から受け取った各 WME リストに対して追加のメモリを保持します。これらのメモリはベータ メモリの一種であり、右入力で受け取った WME との一致ごとに WME リストを格納します。 WMEリストのメモリにWMEリストが全く含まれていない場合、そのリストはネットワーク全体に伝播されます。この方式では、否定ノードは通常、出力を別のベータメモリに格納するのではなく、直接他のベータノードをアクティブ化します。否定ノードは「失敗としての否定」という形式を提供します。

ワーキングメモリに変更が加えられると、以前はどのWMEにも一致しなかったWMEリストが、新たに主張されたWMEに一致するようになる場合があります。この場合、伝播されたWMEリストとその拡張コピーはすべて、ネットワークのさらに下流にあるベータメモリから削除する必要があります。上記で説明した2番目のアプローチは、WMEリストを効率的に削除するメカニズムをサポートするためによく使用されます。WMEリストが削除されると、対応するプロダクションインスタンスはすべて非アクティブ化され、アジェンダから削除されます。

存在量化は、2つの否定ベータノードを組み合わせることで実行できます。これは二重否定の意味論（例：「一致するWMEが存在しないならば、…」）を表します。これは、いくつかのプロダクションシステムで採用されている一般的なアプローチです。

Reteアルゴリズムは、ワーキングメモリのインデックス付けに特定の方法を義務付けていません。しかし、最新のプロダクションシステムのほとんどはインデックス付けメカニズムを提供しています。場合によってはベータメモリのみがインデックス付けされ、また別の場合はアルファメモリとベータメモリの両方がインデックス付けされます。適切なインデックス付け戦略は、プロダクションシステムの全体的なパフォーマンスを決定する重要な要素であり、特に高度に組み合わせ的なパターンマッチング（つまり、ベータ結合ノードの集中的な使用）をもたらすルールセットを実行する場合、あるいは一部のエンジンでは、複数のマッチ・解決・実行サイクル中に多数のWMEリトラクションを実行するルールセットを実行する場合に重要です。メモリはハッシュテーブルの組み合わせを使用して実装されることが多く、ハッシュ値はメモリの内容全体ではなく、WMEリストとWMEのサブセットに対して条件付き結合を実行するために使用されます。これにより、Reteネットワークによって実行される評価の数が大幅に削減されることがよくあります。

WMEがワーキングメモリから削除される場合、それが格納されているすべてのアルファメモリから削除されなければなりません。さらに、WMEを含むWMEリストはベータメモリから削除され、これらのWMEリストのアクティブなプロダクションインスタンスは非アクティブ化され、アジェンダから削除されなければなりません。ツリーベースやリマッチベースなど、いくつかの実装バリエーションが存在します。場合によっては、メモリインデックスを使用して削除を最適化することができます。

ルールセットでプロダクションを定義する際、条件をOR結合子でグループ化することが一般的です。多くのプロダクションシステムでは、複数のORパターンを含む単一のプロダクションを複数のプロダクションと同等と解釈することで、この処理が行われます。結果として得られるReteネットワークには、単一のプロダクションを表す終端ノードのセットが含まれます。このアプローチでは、OR条件の短絡処理は一切許可されません。また、場合によっては、同じWMEセットが複数の内部プロダクションに一致する場合、アジェンダ上で重複したプロダクションインスタンスがアクティブ化される可能性があります。この問題に対処するため、一部のエンジンではアジェンダの重複排除機能を提供しています。

以下の図は、基本的なReteトポロジーを示し、異なるノードタイプとメモリ間の関連性を示しています。

• ほとんどの実装では、タプルのワーキングメモリ要素に対する最初の選択レベルを実行するためにタイプノードを使用します。タイプノードは、特殊な選択ノードと考えることができます。タイプノードは、異なるタプル関係タイプを区別します。
• この図は、否定結合ノードなどの特殊なノードタイプの使用例を示していません。一部のエンジンでは、機能を拡張し最適化を最大化するために、複数の異なるノード特殊化を実装しています。
• この図は、Reteの論理的な構造を示しています。実装は物理的な詳細において異なる場合があります。特に、この図では、ベータノードの分岐の先頭で右方向の活性化を行うダミー入力を示しています。エンジンによっては、アルファメモリが直接右方向の活性化を実行できるようにするアダプタなど、他のアプローチを採用する場合もあります。
• この図は、ノード共有のすべての可能性を示しているわけではありません。

Reteアルゴリズムのより詳細かつ包括的な説明については、Robert Doorenbos著『Production Matching for Large Learning Systems』の第2章を参照してください（下記のリンクを参照）。

考えられるバリエーションの一つは、識別ネットワーク内の各中間ノードに追加のメモリを導入することです。これによりReteのオーバーヘッドは増加しますが、ルールがReteに動的に追加または削除される状況では、識別ネットワークのトポロジーを動的に変更しやすくなるという利点があります。

代替実装はDoorenbosによって説明されている。^{[ 5 ]}この場合、識別ネットワークはメモリのセットとインデックスに置き換えられる。インデックスはハッシュテーブルを使用して実装できる。各メモリには単一の条件パターンに一致するWMEが保持され、インデックスはパターンによってメモリを参照するために使用される。このアプローチは、WMEが固定長のタプルを表し、各タプルの長さが短い場合（たとえば、3タプル）にのみ実用的である。さらに、このアプローチは、定数値に対して等価性テストを実行する条件パターンにのみ適用される。WMEがReteに入ると、インデックスを使用して、条件パターンがWME属性に一致するメモリのセットが特定され、WMEはこれらのメモリのそれぞれに直接追加される。この実装自体には、1入力ノードは含まれていない。ただし、非等価性テストを実装するために、Reteには、WMEがメモリに配置される前に通過する追加の1入力ノードネットワークが含まれる場合がある。あるいは、非等価性テストは、以下で説明するベータネットワークで実行できる。

一般的なバリエーションとして、各トークンが単一のWMEを保持するトークンのリンクリストを作成する方法があります。この場合、部分一致のWMEリストは、トークンのリンクリストによって表現されます。この方法は、WMEリストをあるトークンから別のトークンにコピーする必要がなくなるため、より優れている可能性があります。代わりに、ベータノードは、部分一致リストに追加したいWMEを保持する新しいトークンを作成し、その新しいトークンを入力ベータメモリに格納されている親トークンにリンクするだけで済みます。新しいトークンはトークンリストの先頭となり、出力ベータメモリに格納されます。

ベータノードはトークンを処理します。トークンはメモリ内の記憶単位であり、メモリとノード間の交換単位でもあります。多くの実装では、トークンはアルファメモリ内に導入され、そこで単一のWME（Webメモリ要素）を保持するために使用されます。これらのトークンはその後、ベータネットワークに渡されます。

各ベータノードは処理を実行し、その結果、部分一致を表すWMEのリストを保持する新しいトークンを作成する場合があります。これらの拡張トークンはベータメモリに格納され、後続のベータノードに渡されます。この場合、ベータノードは通常、受信した各トークンから既存のWMEリストを新しいトークンにコピーし、結合などのアクションを実行した結果としてリストにさらにWMEを追加することで、ベータネットワークを介してWMEのリストを渡します。新しいトークンは出力メモリに格納されます。

1980年代に、チャールズ・フォーギーはReteアルゴリズムの後継であるRete IIを開発しました。^{[ 7 ]}オリジナルのRete（パブリックドメイン）とは異なり、このアルゴリズムは公開されていません。Rete IIは、より複雑な問題に対してより優れたパフォーマンス（桁違いに^{[ 8 ] ）を謳っており、1998年にC/++実装のCLIPS/R2とJava実装のOPSJに正式に実装されました。KnowledgeBased Systems Corporation [ 9 ]}のベンチマークによると、Rete IIはより複雑な問題に対して約100対1桁のパフォーマンス向上をもたらします。

Rete II は、2 つの改善点によって特徴付けられます。1 つは Rete ネットワークの一般的なパフォーマンスに関連する特定の最適化 (より大きなデータセットでのパフォーマンスを向上させるためにハッシュ メモリを使用することを含む)、もう 1 つはRete ネットワーク上で動作するように調整されたバックワード チェイニングアルゴリズムの組み込みです。バックワード チェイニングだけでも、Rete と Rete II のベンチマークに関する最も極端な変化を説明できます。Rete II は、以前は Fair Isaac ^{[ 10 ]}と呼ばれていた FICO の商用製品 Advisor に実装されています。

Jess（少なくともバージョン5.0以降）は、Reteネットワークの上に商用のバックワードチェイニングアルゴリズムを追加していますが、完全な仕様が公開されていないこともあり、Rete IIを完全に実装しているとは言えません。

2000年代初頭、チャールズ・フォーギーがFICOのエンジニアと協力してRete IIIエンジンを開発しました。Rete IIIアルゴリズムはRete-NTではなく、Rete IIのFICO商標であり、FICOアドバイザーエンジンの一部として実装されています。アドバイザーエンジンは他のFICO製品にアクセスできるため、アドバイザーエンジンへのアクセスを可能にするAPIを備えたRete IIエンジンです。 ^{[ 11 ]}

2010年、ForgyはReteアルゴリズムの新世代を開発しました。InfoWorldのベンチマークでは、このアルゴリズムはオリジナルのReteアルゴリズムよりも500倍、前身のRete IIよりも10倍高速であると評価されました。^{[ 12 ]} このアルゴリズムは現在、Forgyが投資家兼戦略アドバイザーとして参加したSparkling Logic社にライセンス供与されており、SMARTS製品の推論エンジンとして使用されています。^{[ 13 ] [ 14 ]}

Rete は一階述語論理(基本的にif-then-else文) をサポートすることを目的としているのに対し、Rete-OO ^{[ 15 ]}は不確実性 (意思決定に必要な情報が欠落しているか不正確な場合) をサポートするルールベースのシステムを提供することを目的としている。著者の提案によれば、「危険ならば警報」というルールは、「危険の確率が与えられた場合、警報が鳴る確率が一定である」や「危険が大きいほど警報音は大きくなるべきである」といったものに改善される。このために、 Drools言語 (既に Rete アルゴリズムを実装している)を拡張し、ファジー論理やベイジアンネットワークなどの確率的論理をサポートするようにしている。