法則式系統


什麼是Rule Based System (RBS)?

  法則式系統簡單的說是運用一組邏輯推理的法則來達到所欲結論的一種專家系統,最早使用RBS的人是 1943年的數學家E.Post,他稱他的系統為生產系統【Production System】。生產系統乃是將問題的解答表成 一組標示【某些符號字串如何轉為其它符號字串】的法則,其基本型式為【字串1 → 字串2】,舉一個簡單 的例子,請看下面這組英文文法:

(1)S → NP VP
(2)NP → Det Adj Noun
(3)NP → Det Noun
(4)NP → Noun
(5)VP → Verb
(6)VP → Verb NP
(7)Det → the
(8)Noun → cat
(9)Noun→ river
(10)Noun → south
(11)Verb → swam
(12)Verb → flew
(13)Adj → hesitant
(14)Adj → chilly
其中S表示一個句子
NP為名詞片語
VP為動詞片語
Det為定冠詞
Adj為形容詞



 

這14條法則統稱為法則庫,當我們想造一個合文法的句子時,首先我們會運用第一條法則,接著根據箭頭右邊 的元件再運用其他相關的法則,直到組成一個完整的句子為止,以下即是其中的一種步驟:


 
編號法則結果
S
(1)S → NP+VPNP VP
(2)NP → Det Adj NounDet Adj Noun VP
(7)Det → theThe Adj Noun VP
(13)Adj → hesitantThe hesitant Noun VP
(8)Noun → catThe hesitant cat VP
(6)VP → Verb NPThe hesitant cat Verb NP
(11)Verb → swamThe hesitant cat swam NP
(3)NP → Det NounThe hesitant cat swam Det Noun
(7)Det → theThe hesitant cat swam the Noun
(9)Noun → riverThe hesitant cat swam the river



  如此這般,我們可以很輕易地造出一個的句子。法則式系統就是利用這種方式來解決問題的。簡言之:

建構一個解決問題【造出合文法的句子】的法則庫【14條文法】,給定一個初始狀態【S】,尋找法則庫中與之 相關的法則並應用之,直到找出我們所要的答案,就是一套法則式系統。


 

RBS的架構

  法則式系統主要包括三個部份:法則庫工作記憶體以及推理機。 所有表示解題狀態的資料均在工作記憶體中加以處理 ,當程式開始運作時,由推理機中的法則選擇器依適當順序挑選法則庫中與這些資料相關的法則,再由法則解譯器予以轉換。 下圖即是RBS簡易的架構圖:


 

法則庫

包括法則事實兩部份:  

事實
關於物件之性質、關係、命題....等屬性的宣告,與法則命令式的型態相反,事實通 常是靜態、被動的。

法則
由【前提--動作】,【條件--結論】或【前因--結果】配對組成,例如

ifP1 & P2 .... & Pn
thenQ1 & Q2 .... & Qm

  翻譯成自然語言則是【若前提P1和P2...和Pn為真,則執行動作Q1和Q2...和Qm】,通常每條法則還附帶有其 相關的可信度【degree of confidence】。前提Pi,通常可表為此種配對:【物件 屬性 值】,其值可為數字, 文字或布林符號,或直接表為條件的形式;動作Qi,則無限制。
  法則的功能約有下列四種:

定義系統狀態改變的分解動作,包含簡化系統審核與解釋的狀態。
藉由表示邏輯關係與定義宣告的型式,模擬歸納與推理的動作。
藉由關聯訊號資料與高階類別來模擬主觀的感知。
使用條件式法則來表示經驗性知識的方式來模擬決策決定。

  法則可用來表示成推論性的知識如邏輯關係,以支援推理、證明與評估等目標。相反 的也可以表成目標導向的知識,如此,系統可以應用在找尋問題的解答並引以證明其 動作合理正確。其次,法則還可以表成偶發性的關係式,以處理特殊的問題。


 

工作記憶體

  其主要功用在保存暫時性的協定,這些協定早在系統進行法則推理以前就被記錄, 我們可以將工作記憶體中的資料描述成解決問題的狀態資訊,通常是以【物件--屬性 --值】的型式儲存,然後這些資料再為推理機使用而驅動(drive)某些法則。也就是 說,在工作記憶體中資料的存在與否,將會藉著滿足前提或結論的動作而驅動某些法 則。



   

推理機

包括法則挑選器與法則解譯器及現有事實等三部份。推理機簡單地說是一種【識別-- 動作】的循環,包括下列順序步驟:

1.核對法則前提之元件與工作記憶體中的元素
2.若有兩條以上的法則符合,則由法則挑選器決定應該使用那一條【此稱為衝突之解決
3.由法則解譯器執行該選定之法則,也許是增加或刪除工作記憶體裡的元件,然後回到步驟1

  就一般典型來說,是由工作記憶體提供步驟1中符合法則前提的資料與步驟3中所要 更動的資料結構,通常有一個"開始元件"於記算之初被置入工作記憶體中而啟動上述 的循環,而當有一循環已無法則可供應用或被驅動的法則,其動作有明顯叫停的指令 時,計算才會停止。

  步驟2中,系統裡同時包括兩組以上法則與資料的配對,這些配對稱作【instantiation】,其由【衝突解決器】 決定該驅動那一條法則,其實,也有可能設計一套法則庫,其中的資料規格恰好都只有一條法則可供驅動, 這種法則庫稱做【deterministic】,而在專家系統中,我們較感興趣的法則庫卻是【non-deterministic】

  如英文文法的例子中,若是運用相同的法則但不同的順序,也可以造出同一個句子。或是運用相同的順序但 不同的法則,則可造出不一樣的句子,而且很明顯的,我們可能造出一個無意義或不通順,像 The hesitant river swam the cat (1-2-7-13-9-6-11-3-7-8)的句子。因此,一個法則式系統除了建構一個法則庫之外,最重要的就是決定 應該挑選那些法則,以及決定該選定法則的運用順序,以得到我們想要的答案,如上例,我們想要的是一個 合文法的句子【若要造出既合法又有意義的句子,則上述的法則庫顯然不足】。

  衝突解決】的策略明顯對答案具有可觀的影響,因此要謹慎地作選擇,好的專家系統常以兩個指標判定其 好壞:敏感度與穩定性,敏感度是指對工作記憶體中的改變其反應的快慢,而穩定度是指在推理過程中 能否顯出連續性,衝突解決器隨系統而變,常見的有下列三種:

 
refractoriness每條法則不能被同樣的資料驅動超過一次,作法是將【instantiation】中先前已執行過的 部分區別開來
recency工作記憶體中的元素通常附有一個時間標籤,以致於可以辨別某項資料是在那一次循環中被加進中 作記憶體的,這種策略是將【instantiation】以參與核對資料的先後排序,因此,使用越新資料的法則將優 先被採用
specificity【instantiation】中較特殊的法則,也就是條件較多較難計算的法則要比一般性法則優先採 用



 

推理策略

  法則式系統之推理機運作時,通常會配合適當的推理策略以達到最佳的效率。 推理策略主要有三種:前向鏈結、後項鏈結與前後向混合鏈結,這裡的方向指的是 我們解題步驟的方向,我們可以從現有的狀態走向目標狀態,也可以由目標狀態走 回符合該目標的初始狀態。

  什麼是前向鏈結與後項鏈結呢?讓我們回到剛剛的例子。在前面英文文法的例子中 ,我們都是假設現有的假設剛好滿足某條法則的左邊然後再將其轉成法則右邊的元 件,但當初始值是一個句子,如The chilly bird flew south,而我們想知道他是 否何合文法時,我們運用法則的方式大概有兩種,一是由 S出發,運用法則庫中的 法則,配合所有可能的不同順序,直到造出上述句子為只止,而另一種方法則是假 想法則中的箭頭都指相反的方向,然後運用它們將句子簡化,看是否能得到 S的結 果。以下是後者的詳細步驟:

法則結果
The chilly bird flew south
Det ← the Det chilly bird flew south
Adj ← chilly Det Adj bird flew south
Noun ← bird Det Adj Noun flew south
Verb ← flew Det Adj Noun Verb south
Noun ← south Det Adj Noun Verb Noun
Np ← Det Adj Noun Np Verb Noun
VP ← Verb Noun NP VP
S ← NP VP S


  我們運用文法法則由右向左造出一個句子即是前向鏈結,而由左向右檢查句子的 正確性則是後向鏈結。很明顯的,若我們想要造一個合文法的句子時,前向鏈結 是很好的選擇;但我們只是要檢查某句子的合法性時,後向鏈結顯然更為有效率。

前向鏈結的問題通常在初始狀態時有大量的資料,然而並沒有單一或最佳的目標狀態 ,也就是說只有一組目標需要遵守束制條件而已,前向鏈結的過程中,每一步所面臨 的問題是【下一步該如何走才能更接近目標狀態】,排程問題通常可用前向鏈結法: 某排程任務可開始於要排定的事件或物件與其束制條件,最後的程序則由滿足該條件 的經驗法則產生。

  後向鏈結的問題則是始於一項假設或一個目標,然後由該項結論導演出次一層的事實 或證據,後向鏈結每一步所要問的問題是【為使現行狀態為真,什麼必定為真?】。 後向鏈結的問題常常是答案已知或現有狀態明顯可歸類於某一目標狀態,診斷型問題 即屬之。

  決定該用前向鏈結還是後向鏈結作為推理策略要看問題的初始及目標狀態,如果要加以合成 而為答案的初始狀態包含很多事實,則前向鏈結較為合適,若對於必須加以解析以在 資料庫中找到能夠支持的現行狀態存有一詳盡的描述,則後向鏈結較佳。而有些問題 則需要兩者的合併使用,即是前後向混合式鏈結,通常應用在較複雜的大型問題,較 為少見。


 

不確定性

  專家系統解決的問題通常需要大量的經驗性知識,既為經驗性知識則不可避免地會 牽涉到個人主觀的判斷,或者即使是專家也無法百分之百地確信其知識無誤。因此 對於每條法則仍須另外個別定義其可信度,以反應這個事實。

  我們將不確定性定義為:對精確知識的缺乏度,其中所謂精確知識能夠完美而正確 地解決我們的問題。其來源除了前述的根本原因外,還可能是不可靠的資料、資料 背後的模糊性以及不完全的資料等等。我們通常以條件機率來將不確定性加以量化 。條件機率表為P(A|B),表示在B確定為真的情況下A為真的機率,比如:

 
A表得麻瘋病,P(A)則為得麻瘋病的機率
B表發生全身抖動的症狀,P(B)則為全身抖動的機率
則P(A|B)表示:當發生全身抖動的症狀時,判定為麻瘋病的機率

  然而,P(A|B)通常無法直接判斷,而P(B|A),即在得麻瘋病的情況下有全身抖動的機率 則可輕易得出,如統計所有麻瘋病人有該症狀的比即可。
  然後在根據貝氏法則可知:

  P(A|B)=P(A)*P(B|A)/P(B)


   

參考資料

•Introduction to Expert Systems
Jackson , Peter,1984
•Rule-based Programming with OPS%
Thomas Cooper,Nancy Wogrin,1988
•Knowledge-based System:Fundamental and Tools
Oscar N.Garcia , Yi-Tzuu Chien , 1992
•Rule-based System
Frederick Hayes-Roth
•Expert System:Principles and Programming
Giarratano,Riley , 1989
 

          1