專家系統/Rete 演算法

專家系統

一位華夏公益教科書使用者已提名此頁面進行清理，因為

關於 Rete 演算法

Rete 演算法是一種用於實現產生式規則系統的有效模式匹配演算法。Rete 演算法由卡內基梅隆大學的查爾斯·L·福吉博士設計，首次在 1974 年的工作論文中發表，並在其 1979 年的博士論文和 1982 年的論文中進行了詳細闡述（見參考文獻）。Rete 已成為許多流行專家系統的基礎，包括CLIPS、Jess、JBoss Rules 和 Soar。

對專家系統的一種樸素實現可能會檢查每個規則與知識庫中已知的事實是否匹配，並在必要時觸發該規則，然後繼續處理下一條規則（並在處理完所有規則後迴圈回第一條規則）。對於規則和事實數量中等規模的知識庫，這種樸素方法執行速度過慢。

Rete 演算法（通常讀作“REET”、“REE-tee”或在歐洲讀作“re-tay”，來自拉丁語“rete”的網狀結構，或網路）為專家系統的更高效實現提供了基礎。基於 Rete 的專家系統構建了一個節點網路，其中每個節點（根節點除外）對應於規則左側出現的模式。從根節點到葉節點的路徑定義了完整規則的左側。每個節點都儲存了滿足該模式的事實的記憶。這種結構本質上是廣義的Trie。

當斷言或修改新事即時，它們會沿著網路傳播，導致節點在事實匹配該模式時被標記。當事實或事實組合導致給定規則的所有模式都得到滿足時，會到達葉節點，並觸發相應的規則。

Rete 演算法旨在犧牲記憶體以提高速度。在大多數情況下，與樸素實現相比，速度提升了幾個數量級（因為 Rete 效能在理論上獨立於系統中規則的數量）。但是，在非常大的專家系統中，原始 Rete 演算法往往會遇到記憶體消耗問題。此後，已經設計了其他演算法，包括新演算法和基於 Rete 的演算法，這些演算法需要更少的記憶體。

描述

Rete 演算法提供了一種通用的邏輯描述，用於實現功能，該功能負責在模式匹配產生式系統（一種規則引擎類別）中，將資料元組（“事實”）與產生式（“規則”）進行匹配。一個產生式包含一個或多個條件和一組操作，這些操作可以針對匹配這些條件的每一組完整事實進行。條件測試事實屬性，包括事實型別說明符/識別符號。Rete 演算法具有以下主要特徵

它透過使用節點共享來減少或消除某些型別的冗餘。
它在執行不同事實型別之間的連線時儲存部分匹配項。這反過來又允許產生式系統在對產生式系統的活動記憶體進行更改時，避免對所有事實進行完全重新評估。相反，產生式系統只需要評估活動記憶體的更改（增量）。
它允許在從活動記憶體中撤回事即時有效地刪除記憶體元素。

Rete 演算法被廣泛用於實現模式匹配引擎中的匹配功能，這些引擎利用匹配-解決-操作迴圈來支援正向連結和推理。

Rete 是有向無環圖，表示更高級別的規則集。它們通常在執行時使用記憶體中物件的網路來表示。這些網路將規則條件（模式）與事實（關係資料元組）進行匹配。Rete 網路充當一種關係查詢處理器，有條件地對任意數量的資料元組執行投影、選擇和連線。

產生式（規則）通常由分析師和開發人員使用某種高階規則語言來捕獲和定義。它們被收集到規則集中，然後在執行時（通常在執行時）被翻譯成可執行的 Rete。

當事實被“斷言”到活動記憶體時，引擎會為每個事實建立“活動記憶體元素”（WME）。事實是n 元組，因此可能包含任意數量的資料項。每個 WME 可能會儲存整個n 元組，或者，每個事實也可以由一組 WME 來表示，其中每個 WME 都包含一個固定長度的元組。在這種情況下，元組通常是三元組 (3 元組)。

每個 WME 都會在單個根節點進入 Rete 網路。根節點將每個 WME 傳遞給它的子節點，每個 WME 可能會在網路中傳播，可能儲存在中間記憶體中，直到它到達終端節點。

Alpha 網路

節點圖的“左側”（alpha）形成一個判別網路，負責根據簡單的條件測試來選擇單個 WME，這些條件測試將 WME 屬性與常數值進行匹配。判別網路中的節點也可以執行比較同一個 WME 的兩個或多個屬性的測試。如果一個 WME 成功地與一個節點所代表的條件匹配，它將被傳遞到下一個節點。在大多數引擎中，根節點的直接子節點用於測試每個 WME 的實體識別符號或事實型別。因此，所有代表相同實體型別的 WME 通常會遍歷判別網路中給定分支的節點。

在判別網路中，每個 alpha 節點分支（也稱為 1 輸入節點）都終止於一個名為“alpha”記憶體的記憶體。這些記憶體儲存與給定節點分支中每個節點的每個條件匹配的 WME 集合。未能與分支中的至少一個條件匹配的 WME 不會在相應的 alpha 記憶體中物化。alpha 節點分支可以分叉，以最大程度地減少條件冗餘。

一種可能的變體是在判別網路中的每個中間節點引入額外的記憶體。這會增加 Rete 的開銷，但在規則動態新增到或從 Rete 中刪除的情況下可能具有優勢，從而更容易動態地改變判別網路的拓撲結構。

Doorenbos 描述了另一種實現。在這種情況下，判別網路被一組記憶體和一個索引代替。該索引可以使用雜湊表實現。每個記憶體都儲存與單個條件模式匹配的 WME，而該索引用於透過其模式引用記憶體。這種方法僅在 WME 代表固定長度的元組，並且每個元組的長度很短（例如，3 元組）時才實用。此外，這種方法僅適用於執行相等性測試以匹配常量值的條件模式。當 WME 進入 Rete 時，該索引用於定位一組其條件模式與 WME屬性匹配的記憶體，然後 WME 直接新增到這些記憶體中的每一個。本身，這種實現不包含任何 1 輸入節點。但是，為了實現非相等性測試，Rete 可能包含額外的 1 輸入節點網路，WME 在放置到記憶體中之前會透過這些網路。或者，可以在下面描述的 beta 網路中執行非相等性測試。

Beta 網路

圖的“右側”（beta）主要執行不同 WME 之間的連線。它是可選的，僅在需要時才包含。它由 2 輸入節點組成，每個節點都有一個“左側”和一個“右側”輸入。每個 beta 節點將其輸出傳送到一個“beta”記憶體。

Beta 節點處理標記。標記是記憶體內的儲存單元，也是記憶體和節點之間交換的單元。在許多實現中，標記是在 alpha 記憶體中引入的，在那裡它們用於儲存單個 WME。然後，這些標記被傳遞到 beta 網路。

每個 beta 節點都執行其工作，並且作為結果，可能會建立新的標記來儲存代表部分匹配的 WME 列表。然後，這些擴充套件的標記儲存在 beta 記憶體中，並傳遞到後續的 beta 節點。在這種情況下，beta 節點通常透過從每個接收到的標記中複製現有的 WME 列表到新的標記中，然後透過執行連線或其他操作將更多 WME 新增到列表中，從而將 WME 列表傳遞到 beta 網路中。然後，新標記儲存在輸出記憶體中。

一個常見的變體是構建連結串列，其中每個標記儲存一個單個 WME。在這種情況下，部分匹配的 WME 列表由標記的連結串列表示。這種方法可能更最佳化，因為它消除了從一個標記複製 WME 列表到另一個標記的需要。相反，beta 節點只需要建立一個新的標記來儲存它希望與部分匹配列表連線的 WME，然後將新標記連結到儲存在輸入 beta 記憶體中的父標記。新標記現在形成了標記列表的頭部，並存儲在輸出 beta 記憶體中。

在 Rete 的描述中，通常會提到 beta 網路中的標記傳遞。但是，在本文中，我們將根據 WME 列表而不是標記來描述資料傳播，以認識到不同的實現選項以及標記的根本目的和用途。當任何一個 WME 列表透過 beta 網路時，可能會向其中新增新的 WME，並且該列表可能會儲存在 beta 記憶體中。beta 記憶體中的 WME 列表表示對給定產生式中條件的部分匹配。

到達 beta 節點分支末端的 WME 列表表示對單個產生式的完全匹配，並將傳遞到終端節點。這些節點有時稱為“p 節點”，其中“p”代表“產生式”。每個終端節點都代表單個產生式，並且到達終端節點的每個 WME 列表都代表對該產生式中條件的完全匹配的 WME 集。對於它接收到的每個 WME 列表，產生式節點都會在“議程”上“啟用”一個新的產生式例項。議程通常以優先佇列的形式實現。

Beta 節點通常執行儲存在 beta 記憶體中的 WME 列表與儲存在 alpha 記憶體中的單個 WME 之間的連線。每個 beta 節點都與兩個輸入記憶體相關聯。alpha 記憶體儲存 WME，並在每次儲存新的 WME 時對 beta 節點執行“右側”啟用。beta 記憶體儲存 WME 列表，並在每次儲存新的 WME 列表時對 beta 節點執行“左側”啟用。當連線節點被右側啟用時，它會將輸入 alpha 記憶體中新儲存的 WME 的一個或多個屬性與輸入 beta 記憶體中包含的每個 WME 列表中特定 WME 的給定屬性進行比較。當連線節點被左側啟用時，它會遍歷 beta 記憶體中新儲存的單個 WME 列表，檢索給定 WME 的特定屬性值。它將這些值與 alpha 記憶體中每個 WME 的屬性值進行比較。

每個 beta 節點都輸出 WME 列表，這些列表要麼儲存在 beta 記憶體中，要麼直接傳送到終端節點。只要引擎將在後續 beta 節點上執行額外的左側啟用，WME 列表就會儲存在 beta 記憶體中。

從邏輯上講，beta 節點分支頭部的一個 beta 節點是一個特殊情況，因為它不會從網路中任何更高層的 beta 記憶體接收輸入。不同的引擎以不同的方式處理這個問題。一些引擎使用專門的介面卡節點將 alpha 記憶體連線到 beta 節點的左側輸入。其他引擎允許 beta 節點直接從兩個 alpha 記憶體接收輸入，將其中一個視為“左側”輸入，另一個視為“右側”輸入。在這兩種情況下，“頭部”beta 節點都從兩個 alpha 記憶體接收輸入。

為了消除節點冗餘，任何一個 alpha 或 beta 記憶體都可以用於對多個 beta 節點執行啟用。除了連線節點之外，beta 網路還可以包含其他節點型別，其中一些節點型別將在下面描述。如果 Rete 不包含 beta 網路，則 alpha 節點會將每個包含單個 WME 的標記直接饋送到 p 節點。在這種情況下，可能不需要將 WME 儲存在 alpha 記憶體中。

衝突解決

在任何一個匹配-解析-動作迴圈期間，引擎都會找到當前斷言到工作記憶體中的所有事實的所有可能匹配。一旦找到了所有當前匹配，並且相應的產生式例項在議程上被啟用，引擎就會確定產生式例項可以“觸發”的順序。這被稱為“衝突解決”，並且啟用的產生式例項列表被稱為“衝突集”。該順序可以基於規則優先順序（突出顯示）、規則順序、將每個例項中包含的事實斷言到工作記憶體的時間、每個產生式的複雜性或其他一些標準。許多引擎允許規則開發人員在不同的衝突解決策略之間進行選擇，或者將多個策略的選擇連結起來。

衝突解決不是作為 Rete 演算法的一部分定義的，而是與演算法一起使用。一些專門的產生式系統不執行衝突解決。

產生式執行

在執行了衝突解決之後，引擎現在“觸發”第一個產生式例項，執行與該產生式相關聯的動作列表。這些動作作用於產生式例項的 WME 列表所代表的資料。

預設情況下，引擎將按順序繼續觸發每個生產例項，直到所有生產例項都被觸發。在任何一次匹配-解析-執行週期中，每個生產例項最多隻觸發一次。這種特性被稱為“折射”。但是，在工作記憶體進行更改的任何階段，生產例項觸發的順序都可能被打斷。規則操作可以包含從引擎的“工作記憶體”中斷言或撤回 WME 的指令。每次任何單個生產例項執行一個或多個此類更改時，引擎都會立即進入新的匹配-解析-執行週期。這包括對當前在工作記憶體中的 WME 的“更新”。更新透過撤回然後重新斷言 WME 來表示。引擎對更改後的資料進行匹配，這反過來可能會導致議程中生產例項列表的更改。因此，在任何一個特定生產例項的操作執行完畢後，以前啟用的例項可能已被停用並從議程中刪除，而新的例項可能已被啟用。

作為新匹配-解析-執行週期的一部分，引擎對議程進行衝突解決，然後執行當前的第一個例項。引擎繼續觸發生產例項並進入新的匹配-解析-執行週期，直到議程中不再存在生產例項。此時，規則引擎被認為已完成其工作並停止。

一些引擎支援高階折射策略，其中在先前週期中執行的某些生產例項不會在新的週期中重新執行，即使它們可能仍然存在於議程中。

引擎有可能進入無限迴圈，其中議程永遠不會到達空狀態。出於這個原因，大多數引擎支援可以在生產操作列表中呼叫的顯式“停止”動詞。它們還可以提供自動迴圈檢測，其中無限迴圈在給定次數的迭代後自動停止。一些引擎支援這樣一種模型，在這種模型中，引擎不會在議程為空時停止，而是進入等待狀態，直到新的事實從外部斷言。

至於衝突解決，啟用生產例項的觸發不是 Rete 演算法的特性。但是，它是使用 Rete 網路的引擎的核心特性。Rete 網路提供的一些最佳化僅在引擎執行多個匹配-解析-執行週期的情況下才有用。

存在量詞和全稱量詞

條件測試最常用於對單個元組執行選擇和連線。但是，透過實現其他 β 節點型別，Rete 網路可以執行量化。存在量化涉及測試工作記憶體中是否存在至少一組匹配的 WME。全稱量化涉及測試工作記憶體中的一整組 WME 是否滿足給定條件。全稱量化的變體可能會測試從一組 WME 中提取的給定數量的 WME 是否滿足給定條件。這可能是根據測試確切數量或最小數量的匹配。

量化並非在所有 Rete 引擎中都得到普遍實現，並且在支援量化的引擎中，存在多種變體。存在量化的一種變體，稱為“否定”，在很大程度上（但並非普遍）得到支援，並在開創性檔案中進行了描述。存在量化否定條件和連線涉及使用專門的 β 節點，這些節點測試是否存在匹配的 WME 或 WME 集。這些節點僅在找不到匹配項時才傳播 WME 列表。否定的具體實現方式各不相同。在一種方法中，節點在它從左側輸入接收的每個 WME 列表上維護一個簡單的計數。該計數指定從右側輸入接收的 WME 中找到的匹配項數量。節點僅傳播計數為零的 WME 列表。在另一種方法中，節點在從左側輸入接收的每個 WME 列表上維護一個額外的記憶體。這些記憶體是 β 記憶體的一種形式，並且儲存從右側輸入接收的每個匹配的 WME 列表。如果 WME 列表在其記憶體中沒有 WME 列表，則它將向下傳播到網路中。在這種方法中，否定節點通常直接啟用其他 β 節點，而不是將其輸出儲存在額外的 β 記憶體中。否定節點提供了一種形式的 '否定為失敗'。

當對工作記憶體進行更改時，以前與任何 WME 不匹配的 WME 列表現在可能與新斷言的 WME 匹配。在這種情況下，傳播的 WME 列表及其所有擴充套件副本都需要從網路中更下層的 β 記憶體中撤回。上面描述的第二種方法通常用於支援有效地移除 WME 列表的機制。當移除 WME 列表時，任何相應的生產例項都會被停用並從議程中移除。

存在量化可以透過組合兩個否定 β 節點來執行。這表示雙重否定的語義（例如，“如果 NOT NOT 任何匹配的 WME，那麼...”）。這是幾種生產系統採用的常見方法。

記憶體索引

Rete 演算法沒有強制要求任何特定的工作記憶體索引方法。但是，大多數現代生產系統提供索引機制。在某些情況下，只有 β 記憶體被索引，而在其他情況下，索引被用於 α 記憶體和 β 記憶體。良好的索引策略是決定生產系統整體效能的主要因素，尤其是在執行導致高度組合模式匹配（即大量使用 β 連線節點）的規則集時，或者，對於某些引擎，在執行在多個匹配-解析-執行週期中執行大量 WME 撤回的規則集時。記憶體通常使用雜湊表的組合來實現，並且雜湊值用於對 WME 列表和 WME 的子集執行條件連線，而不是對記憶體的全部內容進行連線。這反過來通常會顯著減少 Rete 網路執行的評估次數。

移除 WME 和 WME 列表

當從工作記憶體中撤回 WME 時，必須將其從儲存它的每個 α 記憶體中移除。此外，包含 WME 的 WME 列表必須從 β 記憶體中移除，並且這些 WME 列表的啟用生產例項必須被停用並從議程中移除。存在幾種實現變體，包括基於樹的移除和基於重新匹配的移除。在某些情況下，可以使用記憶體索引來最佳化移除。

處理 OR’ed 條件

在定義規則集中的生產時，通常允許使用“OR”連線詞對條件進行分組。在許多生產系統中，這是透過將包含多個 OR’ed 模式的一個生產解釋為多個生產的等價物來處理的。生成的 Rete 網路包含一組終端節點，這些節點共同代表單個生產。這種方法不允許對 OR’ed 條件進行任何形式的短路。它還可以，在某些情況下，導致議程中啟用重複的生產例項，其中相同的 WME 集匹配多個內部生產。一些引擎提供議程去重以處理此問題。

其他注意事項

雖然 Rete 演算法沒有定義，但一些引擎提供了擴充套件功能來支援對真值維護的更多控制。例如，當為一個產生式找到匹配項時，這可能會導致斷言新的 WME，而這些 WME 反過來又與另一個產生式的條件相匹配。如果工作記憶體的後續更改導致第一個匹配變得無效，則可能意味著第二個匹配也無效。Rete演算法沒有定義任何機制來自動定義和處理這些邏輯真值依賴項。但是，一些引擎支援附加功能，其中可以自動維護真值依賴項。在這種情況下，一個 WME 的撤回可能會導致自動撤回其他 WME 以維護邏輯真值斷言。

Rete演算法沒有定義任何理由方法。理由是指在專家和決策系統中通常需要的機制，最簡單地說，系統會報告為得出最終結論所使用的每個內部決策。例如，一個專家系統可能會透過報告動物很大、灰色、有很大的耳朵、鼻子和象牙來證明動物是大象的結論。一些引擎在其對 Rete演算法的實現中提供內建的理由系統。

本文沒有提供對 Rete 演算法所有可能的變化或擴充套件的詳盡描述。其他考慮因素和創新也存在。例如，引擎可以在 Rete 網路中提供專門支援，以將模式匹配規則處理應用於特定資料型別和來源，例如程式物件、XML 資料或關係資料表。另一個例子是許多引擎為每個進入 Rete 網路的 WME 提供的附加時間戳功能，以及在衝突解決策略中使用這些時間戳。引擎在允許以程式設計方式訪問引擎及其工作記憶體的方式上表現出顯著差異，並且可能會擴充套件基本 Rete 模型以支援並行和分散式處理形式。

最佳化和效能

已經確定並在學術文獻中描述了 Rete 的一些最佳化。然而，其中一些僅適用於非常特定的場景，因此在通用規則引擎中通常幾乎沒有或根本沒有應用。此外，已經制定了 TREAT 和 LEAPS 等替代演算法，它們可以提供額外的效能改進。目前，很少有支援這些替代演算法的商業或開源產生式系統。

Rete演算法面向從現有事實中計算新事實，或過濾和丟棄事實以得出某個結論的前向連結和“推理”場景。它也被用作一種相當有效的機制，用於執行事實的高度組合評估，其中必須在事實元組之間執行大量聯接。其他執行規則評估的方法，例如使用決策樹，或實現順序引擎，可能更適合簡單的場景，應該考慮作為可能的替代方案。

下圖說明了基本的 Rete 地形，並顯示了不同節點型別和記憶體之間的關聯。

大多數實現使用型別節點在 n 元組工作記憶體元素上執行第一級選擇。型別節點可以被視為專門的選擇節點。它們區分不同的元組關係型別。
該圖沒有說明專門節點型別（例如否定連線節點）的使用。一些引擎實現了幾種不同的節點專門化，以擴充套件功能並最大限度地最佳化。
該圖提供了 Rete 的邏輯檢視。實現可能在物理細節方面有所不同。特別是，該圖顯示了在 beta 節點分支頭部提供正確啟用的“虛擬”輸入。引擎可能會實現其他方法，例如允許 alpha 記憶體直接執行正確啟用的介面卡。
該圖沒有說明所有節點共享可能性。

有關 Rete 演算法的更詳細和完整的描述，請參閱 Robert Doorenbos 編著的《大型學習系統生產匹配》第 2 章（見下方連結）。

Rete II

在 1980 年代，Charles L. Forgy 開發了 Rete 演算法的後繼者，名為Rete II[1]。與原始 Rete（它是公共領域的）不同，該演算法沒有公開。Rete II 聲稱對於更復雜的問題具有更好的效能（甚至數量級）。

參考文獻

Charles Forgy，“生產系統的網路匹配例程”。工作論文，1974 年。
Charles Forgy，“關於生產系統的高效實現”。卡內基梅隆大學博士論文，1979 年。
Charles Forgy，“Rete：一種針對多模式/多物件模式匹配問題的快速演算法”，人工智慧，19，第 17-37 頁，1982 年

外部連結

大型學習系統生產匹配 - R Doorenbos 對 Rete 的詳細和易懂的描述，還描述了針對大型系統最佳化的名為 Rete/UL 的變體（PDF）
根據規則（來自cut-the-knot的簡短介紹）