我的雲端生活網 - Life+

Monday, April 6, 2009

規則式系統的系統描述

本篇來講一些規則系統(production system, rule-based sytem, or expert sytem)的系統描述(formulation)。規則系統是由工作空間(包含事實)、知識庫(包含規則)、以及推論引擎(包含推論及控制流程)等三樣東西構成。一般大學教科書中,很少明確說明規則系統的設計。而相關論文則都使用 Lisp 語言介紹系統架構,較近年代的程式人員根本看不懂。

1. 程序代數

所以,用一些形式語言說明規則系統的架構。推論引擎包含三個分開的程序,所以我們用到基本程序代數(Pi Calculus):令 p, q 是二個程序,二個程序的結構可能是下列其中一種樣子。

p, q ::=   a(c) . p                           (輸入)
           |   a! c . p                            (輸出)
           |     P  |  q                            (平行處理)
           |   if x = y then p else q   (條件控制)
           |   rec z . p                          (遞迴)
           |   stop                                (終止)

上述項目的意義是:
  1. a(c) . p 是程序 p 要從 a 通訊管道取得一些資料 c ;
  2. a! c . p 是程序 p 要對 a 通訊管道送出一些資料 p ;
  3. p | q 是二個程序 p, q 平行地執行;
  4. if x = y then p else q 是先比較二項資料 x 和 y ,如果 x = y 就執行程序 p ,否則執行程序 q ;
  5. rec z . p 是將程序 p 定義為一個遞迴程序,以 z 標示。在 p 中存在 z 符號,表示遞迴呼叫;
  6. stop 是一個終止程序。
我們說, P <= a(b) . p 是定義一個程序 P 的內容是, p 知道一 通訊管道 a 並 管道 a 取出資料
b 。為了方便,用 P(a) 表示此式,即程序 P 一開始就知道通訊管道 a ,並可以隨意使用。

2. 基本詞彙

另外,我們需要一些基本符號,列舉如下:

單元詞彙:要表示一個資料單位或一項物件,用小寫字母 a, b, ..., z 表示任何一個單元。

集合詞彙:用大寫字母 A, B, ..., Z 表示任何一個集合。每一個集合中包含了許多單元。所以,x < X 表示一個單元詞彙 x 屬於另一個集合 X 。

邏輯式敘述:用一些單元詞彙和一些邏輯運算符號 & , | , ~ ,  ->  等等,組合成另一些字串,這些字串稱為邏輯式、或稱為敘述:例如,有單元詞彙 x, y ,則 x & y 是一則敘述、 ~x 是一則敘述、並 (x & y -> x) | (x & y -> y) 也是一則敘述。在本篇文章,我們要用到許多  ->  運算符號。

隱含( -> ):是一種邏輯運算符號,用來表示符號的左項和右項之間有因果關係:例如,對單元詞彙 x, y 來說, x -> y 是一則敘述,其意義是

                  x           y                  x -> y
               true      true                true
               true      false               false
               false     true                true
               fase      false                true

只有當 x 有效但 y 無效時, x -> y 不能成立。這稱為「 x 隱含 y 」、「 x 代表 y 」。

例外詞彙:任何其他用途的詞彙,都用粗體大寫字母 A, B, ..., Z 表示:例如,用 M 表示一則程序。

Lambda函數:是一種匿名函數的表示法,以格式為「 入 a b c ...  .  p(a, b, c, ...) 」的字串表示一則函數。其中,「入」是希臘文字母,唸 lambda ;「入」之後是一些參數、之後是一點、之後是函數內容:例如, 入x y . x + y 是一則匿名函數,接受二項參數而計算總和。

3. 定義

事實:用一個單元詞彙表達一項事實:例如,用 x 表達「今天下雨」。

規則:用一則格式為「 a & b & ... -> a & b & ... 」的邏輯式,表示一條規則:例如 a & b -> c & d 。其中, ->  符號左邊稱為左手側,常用英文 LHS 表示;右邊稱為右手側,常用英文 RHS 表示。左手側就是規則條件,而右手側就是規則的結論。

規則系統:是一組結構 <F, R, M, C, A ,其中組成單元有:
  1. F :一些事實的集合。
  2. R :一些規則的集合。
  3. M :規則比對程序,負責將一些事實和一些規則彼此比對,然後選出符合比對的規則,當做結果。
  4. C :協調程序,負責將 M 的結果做衝突協議(Conflict Resolution)。衝突協議是在一些規則中,只挑選一些必須啟動的規則,當做結果;並排除彼此衝突或互相重覆的規則:例如,規則 A & B -> C 和規則 A -> C 重覆,因為前者的規則條件是後者的子集合。 Rete 演算法規定,對這二條規則,要選擇 A & B -> C ,因為規則條件比較嚴格。
  5. A :行動程序,負責將 C 的結果── 一些確定要啟動的規則 ──確實執行。 A 要將 C 結果的右手側取出並執行。
Rete 結構Rete 演算法是討論一些規則的集合應該如何組織、並組織一種有效的結構,使事實和規則彼此比對變的比較有效。令有一些規則為 R = { A & B -> C ,  B & C -> D } ,根據最初的 Rete 演算法論文, R 有一組對應的 rete 結構,令為 R(R) 。 R(R) 包含一些流程控制,定義為

        入 f  .   R(R)   ::=
                    入 f  .  if type(f) = A then assert(C(_^B)) ;
                               if type(f) = B then assert(C(A^_)); assert(D(_^C)) ;
                               if type(f) = C then assert(D(B^_)) ;
                               if assert(C(_^B)) and assert(C(A^_)) then match(A & B -> C) ;
                               if assert(D(_^C)) and assert(C(B^_)) then match(B & C -> D)

R(R) 中由三種節點構成,包括 type(f) = A 檢查輸入事實的 type 屬性、 assert(C(A^B)) 表示結果 C 是由 A & B 決定、以及 match(r) 指明條件 r 已經符合比對。而 C(_^B) 表示 C 的一則決定項已經接受、並等待另一則決定項 B 。

4. 推論引擎

推論引擎包含 M, C, A 三項程序,依序循環使用。我們用程序代數和上述符號標記法定義三項程序。

取比對程序 M

    M(a, b) <= rec z  .  a(f1, (f2, f*)) . ((入 f . R(R))  f1  |  a! f2, f*  .  z )

其中 (f1, (f2, f*)) = F = (f1, f2, ..., fn) ,並且 (入 f . R(R))  f1 是一則匿名函數代入參數而生效,計算方式是 R(R)[f1/f] 、即把函數主體 R(R) 中存在的 f 替換為 f1 。在 R(R) 中的 match 定義為

    match(b) <= b! r  .  stop

又取協調程序 C

    C(b, c) <= rec z . b(r1, (r2, r*))  .  ( if r1 = empty then stop
                                                                 else
                                                                     if forall r < R . r1 >= r then fire(r1)
                                                               | b! r2, r*  .  z )

其中, r1 > r 是一條規則對另一條規則的大於關係,定義為 LHS(r1) < LHS(r) 則 r1 > r ,並且 fire(LHS -> RHS) <= c! RHS  .  stop 。

又取行動程序 A

    A(c, d) <= rec z . c(rhs1, (rhs2, rhs*))  .  d! rhs1 . c! rhs2, rhs* .  z

於是,推論引擎取為

INF(a) <= rec z . a(F, R) . (M(a, b) | C(b, c) | A(c, d) | d(F') . a! (F+F'), R . z)

嗯?有點錯誤,管它的,只是個思考過程。

Blog Archive