推論引擎

最近在閱讀有關規則推論引擎 (rule-based inference engine) 的書和資料。這方面的研究知識早在九零年代結束之前就成熟了，但在國內技術應用看起來像是冷門技術項目。有人說專家系統是沒落的東西。然而，放眼看過去技術應用趨勢，八零年代時 LISP 的使用也相當熱門，九零年代初期 Prolog 已取得成功應用，而專家系統 (expert system) 的規則推論引擎和框架系統 (frame-based system) 是二項成功產物。資訊領域並不是只有命令式程式 (imperative programming) 計算模型，並不是要會寫 C 或 Java ，或者要會雕刻組合語言，才佔領全局。還有其他的聰明、高產能的選項可挑選！
推論引擎的產生，來自於解決問題的需要 --- 許多問題並不只是寫一則演算法就能解決。有些問題的思考空間太龐大，而且對於那些問題，經常只有一部分的解題規則，這些規則可能來自於專家的知識或經驗。於是生成系統 (Production System) 出現，後來此系統類型稱為專家系統。規則式生成系統的構成，有一組以具體表達的規則所組成的知識庫、知識輸入介面、推論引擎、以及工作空間。系統接受一些事實作為輸入，由推論引擎將輸入事實與知識庫中的解題規則互相比對，藉由邏輯的歸納推理產生解決方案。此系統的好處是，答案是由專家知識所導出，而且導出答案的那些規則可以直接作為解釋。缺點是，系統所容納的知識庫不能太大，若規則太多則耗費計算時間，以及知識規則的建置花費工夫。
推論引擎的效能問題，在於輸入的事實與知識庫的規則比對所消耗的時間。 Markov 演算法提出順序式的比對，帶來直接的毛病是：有多少規則，就要比對多少時間以上。而且，規則的比對經常花費 O(n²) 級的成本，因為推論引擎必須做到衝突決議 (conflict-resolution) 的處理程序，意即經過眾多層次不同且可能有彼此矛盾的規則，綜合評判之後，取得一致的正確結果。為了適應規則推論引擎的特殊計算環境， Rete 演算法提出以網狀資料結構 (rete 是拉丁文，意思是 net ) 處理衝突決議。推論引擎總是進行循環工作，進行步驟有：1. 接受輸入事實並啟動； 2. 比對規則； 3. 衝突決議：若沒有比對到任何規則，則關閉，否則由比對到的規則中挑選一條規則，認定為生效； 4. 將生效的規則啟動，改變工作空間的狀態； 5. 回到步驟 (2) 。
推論引擎雖然不好寫，卻也可以用組合語言或 C 撰寫。 2003 年， Lynwood Wilson 在 Dr. Dobb's 雜誌發表的文章 ”Rule-Based Programming in C” 示範了二項注意事項： 1. 要做衝突決議； 2. 將專家系統劃分為模組使計算時間減少。因為是簡單的示範，他使用 Markov 演算法比對規則。
參考文獻
1. Joseph C. Giarratano & Gary D. Riley. Expert Systems: Principles and Programming. (4 ed.) Course Technology, Thomson Learning, 2005.
2. Charles L. Forgy. Rete: a fast match algorithm. AI Expert, vol. 2, issue 1, 1987.
3. Lynwood Wilson. Rule-Based Programming in C. Dr. Dobb's Portal. Available online: http://www.ddj.com/184405245.