ベータネットワーク

ウィキペディア小見出し辞書

ベータネットワーク

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/13 07:33 UTC 版)

「Reteアルゴリズム」の記事における「ベータネットワーク」の解説

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 をアルファメモリに格納する必要はない。