Knowledge Validation and Verification Chapter 5 Knowledge Validation and Verification 知識驗證 Expert Systems sstseng

Expert Systems sstseng 為何要做知識驗證？ 以規則作為知識的表達方式已成為專家系統的主流。 因為規則本身提供的彈性與擴充性，對系統發展者與使用者來說，可能在規則庫的建立及使用過程中造成不易偵測的錯誤。 因此，在系統應用於商業環境之前，進行知識驗證是很重要的步驟。 Expert Systems sstseng

Expert Systems sstseng 8.1 知識驗證的範圍 冗贅的規則（Redundancy） 矛盾的規則（Contradiction or Conflict） 循環的規則（Circularity） 不完整的規則（Incompleteness） Expert Systems sstseng

Expert Systems sstseng 冗贅的規則（Redundancy） 在給定所觀察到的一組「屬性-值」下，有兩條以上的規則導致相同的結果，稱為冗贅的規則（Redundancy）。 造成冗贅的規則（Redundancy）原因 ： 存在包含關係的先決條件或最後結果的規則 存在多條規則的不同推理路徑下，從一組給定的先決條件推到相同的中間點或最後結果 Expert Systems sstseng

Expert Systems sstseng Rule 1：If 商業化成功的可能性低 Then 財務可行性低 Rule 2：If 財務可行性低 Then 舉債可行性低 Rule 3：If 商業化成功的可能性低 Then 舉債可行性低 Expert Systems sstseng

矛盾的規則（Contradiction or Conflict） 矛盾的規則將造成錯誤的決策。 在推理大量的規則時，往往牽涉到多條規則間複雜的相依關係，導致錯誤不易被偵測出來。 Expert Systems sstseng

Expert Systems sstseng Rule 1：If 商業化成功的可能性低 Then 財務可行性低 Rule 2：If 財務可行性低 Then 舉債可行性低 Rule 3：If 商業化成功的可能性低 Then 舉債可行性高 Expert Systems sstseng

Expert Systems sstseng 循環的規則（Circularity） 循環的規則（Circularity）是在先決條件下進行推理後，導致推回原來的先決條件或其中的一部份子條件。 不同的專家可能在不同的時間點加入不同的規則，而這種規則循環性將造成系統推理時的錯誤。 Expert Systems sstseng

Expert Systems sstseng Rule 1：If 主要消費群意向被刺激時 Then 商業化可行性是樂觀的 Rule 2：If 商業化可行性是樂觀的 Then 主要消費群意向被刺激 Expert Systems sstseng

不完整的規則（Incompleteness） 包括無結果的推論（Deadends）及無法到達的結果（Unreachable Goals）。 當一條規則的結果不是一個目標變數，也不是其他規則條件的一部份時，稱做無結果的推論（Deadends）。 無結果的推論（Deadends）代表這些規則不應該包含到規則庫中，或是漏失相關的規則，造成這些規則缺乏一些推理到最後目標的條件。 Expert Systems sstseng

Expert Systems sstseng 當規則結果不是一個輸入變數，也不是其他規則結果的一部份時，則該條規則構成無法到達的結果（Unreachable Goals）。 無法到達的結果（Unreachable Goals）代表該條規則與其他規則是無關的，或漏失掉其他建立關係的條件。 Expert Systems sstseng

Expert Systems sstseng 8.2 單一形式（Unitized form） 假設所有規則在用來偵測錯誤之前，必須以一致的格式呈現。 先決條件只允許conjunctions 最後結果只允許一個「屬性-值」 單一形式（Unitized form）保證一個結構性的知識庫，且不失一般性（with no loss of generality）。 Expert Systems sstseng

Expert Systems sstseng 當一條規則具有多個先決條件的disjunctions時，根據每個子條件轉換成一組有相同結果且格式一致的規則。 Expert Systems sstseng

Expert Systems sstseng Rule：If 財務可行性低 Or 商業化成功的可能性低 Then 舉債可行性低 If 財務可行性低 Then 舉債可行性低 If 商業化成功的可能性低 Then 舉債可行性低 Expert Systems sstseng

Expert Systems sstseng 當一條有多個結果的規則，則根據每個結果轉換成一條格式一致的規則，但每條規則具有相同的先決條件。 Expert Systems sstseng

Expert Systems sstseng Rule：If 商業化成功的可能性低 Then 財務可行性低 舉債可行性低 If 商業化成功的可能性低 Then 財務可行性低 If 商業化成功的可能性低 Then 舉債可行性低 Expert Systems sstseng

8.3 有向超連結圖的規則表示法（Directed Hypergraph Representation） 用圖形化的表示來代表規則間的關係，有助於偵測系統中各種不同的錯誤。 圖形可以把驗證問題轉變成在某種狀態中兩點是否有可相通的路徑 圖形化表示簡單易用的架構，能清楚的展示出概念間的關係 各種分析圖形連接關係的技術，也使得知識規則在更嚴謹的方法下進行驗證 Expert Systems sstseng

Expert Systems sstseng Mysore Ramaswamy、Sumit Sarkar及Ye-Sho Chen等三位學者在1997年提出使用「有向超連結圖」以清楚的表示規則中的複合條件，而不需要依賴人為的額外註釋來表示這些關係。 Expert Systems sstseng

Expert Systems sstseng 範例 Rule 1：If 政府沒有任何限制時 Then 高階管理階層會同意 Rule 2：If 技術成功的可能性高 And 商業化成功的可能性高 Then 研發專案可在3年內完成 Rule 3：If 技術成功的可能性高 And 商業化成功的可能性高 Then 可得到聯邦政府的許可 Rule 4：If 高階管理階層會同意 And 研發專案可在3年內完成 Then 繼續該專案 Rule 5：If 研發專案可在3年內完成 And 可得到聯邦政府的許可 Then 繼續該專案 Rule 6：If 可得到聯邦政府的許可 Then 分配更多的人力資源 Expert Systems sstseng

Expert Systems sstseng

符號和定義（Notation and Definitions） 規則（Rule） 超節點（Hypernode） 超路徑（Hyperpath） 路徑長度（Length of a Path） Expert Systems sstseng

Expert Systems sstseng 規則（Rule） 每對「屬性-值」以小寫的英文字母代表屬性，並搭配一個數值代表該屬性的值。 例如：若屬性P有三個合法值，則分別以p1、p2、p3來代表 。 規則（Rule）以＜b1, c1; e1＞的形式來代表。 Expert Systems sstseng

Expert Systems sstseng Rule 1：a1  d1 Rule 2：b1 + c1  e1 Rule 3：b1 + c1  f1 Rule 4：d1 + e1  g1 Rule 5：e1 + f1  g1 Rule 6：f1  h1 Expert Systems sstseng

Expert Systems sstseng

Expert Systems sstseng 超節點（Hypernode） 每一個與規則的先決條件或最後結果相關的節點，稱為超節點（Hypernode）。 當一個超節點僅由單一的「屬性-值」配對所組成，稱為簡單節點（Simple node） 若是由兩個以上的「屬性-值」配對所組成，則稱為複合節點（Compound node） Expert Systems sstseng

Expert Systems sstseng 提到一個超節點（Hypernode）可以用相關於條件的「屬性-值」來表示超節點，或是用大寫英文字母加底線來表示。 例如：Rule 2可以寫成＜U; V＞，其中U=（b1, c1），V=（e1） 為了進一步區分簡單節點和複合節點，也可以用小寫的字母來代表簡單節點。 例如： Rule 2可以寫成＜U; v＞，其中U=（b1, c1），v=（e1） Expert Systems sstseng

Expert Systems sstseng 超路徑（Hyperpath） 超路徑（Hyperpath）是由指定的開始超節點至結果結點的推論過程中找出的一條「唯一的」推論路徑。 例如：（b1, c1）與（h1）之間的推理路徑可以寫成 P{b1, c1; h1\ ＜b1, c1; f1＞, ＜f1; h1＞} Expert Systems sstseng

Expert Systems sstseng 超路徑（Hyperpath）中的複合節點（Compound node）會有不只一種的執行順序能到達同樣的目標節點。 例如：（b1, c1）與（e1, f1）之間可以有兩種的規則推理過程：P{b1, c1; e1, f1\ ＜b1, c1; e1＞, ＜b1, c1; f1＞}或是P{b1, c1; e1, f1\ ＜b1, c1; f1＞, ＜b1, c1; e1＞} Expert Systems sstseng

Expert Systems sstseng 區間（Segment） 為了使代號執行的順序避開不只一種的執行順序的影響，使用區間（Segment）記號來標記規則的超路徑執行邏輯順序。 例如：（b1, c1）與（g1）之間的區間執行順序，則寫成： P{b1, c1; g1\ <<＜b1, c1; e1＞, ＜b1, c1; f1＞>>, <<＜e1, f1; g1＞>>} Expert Systems sstseng

Expert Systems sstseng 簡單路徑（Simple path） 當U至V路徑中的每個區間只有一條規則及第一條規則是以整組U作為前置條件時（不能只是U的子集合），稱之為簡單路徑（Simple path）。 例如：SP{b1, c1; h1\ <<＜b1, c1; f1＞>>, <<＜f1; h1＞>>} Expert Systems sstseng

完整超路徑（Strict hyperpath） 滿足下面兩種情況下的任一種狀況，則稱路徑U至V為完整超路徑： 路徑中至少有一個區間包含兩條以上的規則 在規則第一個區間的前置條件有U’U的關係（就是條件式為U的子集合） 例如：HP{b1, c1; g1\ <<＜b1, c1; e1>, <b1, c1; f1＞>>, <<＜e1, f1; g1＞>>} 和 HP{e1, f1; h1\ <<＜f1; h1＞>>} Expert Systems sstseng

Expert Systems sstseng 路徑長度（Length of a Path） 路徑長度（Length of a Path）定義為構成路徑的區間數量。 例如：P{b1, c1; g1}路徑長度為2，P{b1, c1; e1, f1}路徑長度為1 Expert Systems sstseng

8.4 相鄰矩陣規則表示法（Adjacency Matrix） 除了矩陣相乘、相加、相減等標準矩陣運算外，再加上另外兩種特殊的運算稱為欄修正運算（Column Revision）與列修正運算（Row Revision）。 Expert Systems sstseng

相鄰矩陣（Adjacency Matrix） 相鄰矩陣為一方形矩陣A，其列、欄個別包含所有在超連結圖中的超節點；如果從超節點U到V存在一條路徑，則我們在矩陣A[U, V]輸入格的值標為1，而若沒有存在任何路徑，則標為0。 由於每個超節點會與一個規則的前置條件或結果相連接，所以相鄰矩陣的大小最大為 2n 2n，其中n代表資料庫中的規則數量。 Expert Systems sstseng

Expert Systems sstseng

欄修正運算（Column Revision） CR(M[U, V])=M[U, V]+M[U’, V] U’U P{f1; h1\ <<＜f1; h1＞>>}  P{e1, f1; h1\ <<＜f1; h1＞>>} Expert Systems sstseng

Expert Systems sstseng

Expert Systems sstseng 列修正運算（Row Revision） 當開始超節點與目標超節點都是複合節點，且開始超節點對目標超節點的每一個構成要素都有路徑到達時，列修正運算（Row Revision）便可建立所有的此種到達性關係。 RR(M[U, V])=M[U,V]+iM[U, vi] s.t. ivi=V P{b1, c1; e1\ <<＜b1, c1; e1＞>>} × P{b1, c1; f1\ <<＜b1, c1; f1＞>>}  P{b1, c1; e1, f1\ <<＜b1, c1; e1, f1＞>>} Expert Systems sstseng

Expert Systems sstseng

Expert Systems sstseng 8.5 知識驗證流程 檢查流程的基本概念在於正確識別出所有的簡單路徑與完整超路徑，然後再測試路徑中的漏失與錯誤。 路徑若由超過一個區間以上所組成，則以矩陣乘積來偵測相關的錯誤。 Expert Systems sstseng

Expert Systems sstseng 定義矩陣 A：超連結圖的相鄰矩陣 Ai：代表所有路徑長度為i的簡單路徑 Ei：代表所有路徑長度為i且終止於簡單節點的完整超路徑 Bi：代表所有路徑長度 i，且終止於簡單節點的簡單路徑和完整超路徑 Ci：代表所有路徑長度 i，且終止於簡單節點或複合節點的簡單路徑和完整超路徑 Di：代表所有路徑長度為i，且終止於簡單節點或複合節點的完整超路徑 Expert Systems sstseng

循環路徑表（Circular Path List） 在矩陣中，以星號＊來表示循環路徑的存在，而在進行矩陣運算時，則將該值視為0。 Expert Systems sstseng

Expert Systems sstseng 驗證演算法 Step 0：建立相鄰矩陣A，分類表和相衝突表 Step 1：初始化 i=1 B1=CR(A1) E1=B1- A1 C1=RR(B1) D1=C1- A1 Step 2：當 Ai+Ei0，即Ai或Ei都不是空矩陣時，重複 Steps 3-8 Step 3：令 i=i+1 Step 4：Ai=Ai-1A 當元素 Ai[U, V]1，且UV，則將規則P[U; V]列入循環表中，並設Ai[U, V]=0 Expert Systems sstseng

Expert Systems sstseng Step 5：Ei=Di-1A 當元素 Ei[U, V]1，且UV，則將規則P[U; V]列入循環表中，並設Ei[U, V]=0，若 Ai+Ei=0，則跳至 Step 9。 Step 6：Bi=Ai+Ei+Bi-1 Step 7：Ci=RR(Bi) Step 8：Di=Ci-Ci-1-Ai Step 9：搜尋矩陣Bi中，所有元素> 1的，代表有多餘規則路徑的可能。 測試在矩陣Bi中每欄的屬性-值，是否有同時不為0的元素，且存在於相衝突表，代表這兩列結果是相反的。 利用循環路徑表偵測出規則庫中的循環性。 利用分類表來偵測矩陣A中，是否有整列為0的無目標節點。 利用分類表來偵測矩陣A中，是否有整欄為0的無法到達的目標節點。 Expert Systems sstseng

Expert Systems sstseng 8.6 知識驗證實例說明 Rule 1：If 技術成功的可能性高 (a1) Then 專案領導者的同意程度高 (c1) Rule 2：If 技術成功的可能性高 (a1) Then 繼續投資 (j1) Rule 3：If 超過預算成本的可能性高 (b2) Then 無法從業界得到資助 (f1) Rule 4：If超過預算成本的可能性高 (b2) Then 優先權評定等級為C (g1) Expert Systems sstseng

Expert Systems sstseng Rule 5：If 技術成功的可能性高 (a1) And 超過預算成本的可能性高 (b2) Then 預期投資報酬率低 (e1) Rule 6：If 預期投資報酬率低 (e1) Then優先權評定等級為C (g1) Rule 7：If 無法從業界得到資助 (f1) Then 專案無法在3年內完成 (d1) Rule 8：If 無法從業界得到資助 (f1) And 先權評定等級為C (g1) Then 終止投資 (j2) Rule 9：If 專案無法在3年內完成 (d1) Then 超過預算成本的可能性高 (b2) Rule 10：If 利潤低 (i2) Then 終止投資 (j2) Expert Systems sstseng

Expert Systems sstseng

Expert Systems sstseng 事實：“技術成功的可能性高” 和 “超過預算成本的可能性高”（即a1和b2） 目標：決定是否繼續投資研發專案（即j1或j2） Expert Systems sstseng

Expert Systems sstseng 矩陣A Expert Systems sstseng

Expert Systems sstseng 矩陣B3 Expert Systems sstseng

Expert Systems sstseng 偵測錯誤 經由檢查矩陣A和B3，我們可以偵測出下列各種的錯誤： 冗贅的規則（Redundancy）：矩陣B3[a1, b2; g1]=2表示從（a1, b2）到（g1）節點有兩條不同的路徑存在於規則庫中。 矛盾的規則（Contradiction or Conflict）：B3[a1, b2; j1]=1是指 (a1, b2) 到 (j1) 節點有路徑存在，而B3[a1, b2; j2]=2是指 (a1, b2) 到 (j2) 節點有2條路徑存在，這兩條規則在有相同的前置條件下，指向兩個完全相反的結果。 Expert Systems sstseng

Expert Systems sstseng 循環的規則（Circularity）：循環路徑在矩陣中以星號來表示，分別在B3[b2; b2]、B3[f1; f1]、B3[d1; d1]、B3[a1, b2; b2]、B3[f1, g1; f1]和 B3[f1, g1; g1] 無結果的推論（Deadends）：矩陣A中的節點c1那一列沒有任何的輸入值，表示該節點不會到達任何目標結果。 無法到達的結果（Unreachable Goals）：矩陣A中的節點i2那一欄沒有任何的輸入值，且i2也不是初始的輸入變數，則表示該節點為一沒有任何路徑到達的目標節點。 Expert Systems sstseng

Expert Systems sstseng Exercise 設一規則庫中有下列規則存在，其中j1、j2為所要決定的目標結果，請畫出該規則庫的 Directed Hypergraph（有向超連結圖）。 Rule 1：a1  c1 Rule 2：a1  j1 Rule 3：b2  f1 Rule 4：d1  k1 Rule 5：a1 + b2  e1 Rule 6：e1  g1 Rule 7：f1  d1 Rule 8：f1 + g1  j2 Rule 9：k1  f1 Rule 10：i2  j2 Rule 11：c1 + d1 h1 Rule 12：h1  a1 Expert Systems sstseng