知識表示方法23208

1、第二章 知識表示方法2.1 狀態(tài)空間法2.2 問題歸約法2.3 謂詞邏輯法2.4 語義網(wǎng)絡法2.5 其他方法2.6 小結CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU知識的定義 Feigenbaum知識是經(jīng)過削減、塑造、解釋和轉換的信息。簡單地說，知識是經(jīng)過加工的信息Bernstein知識是由特定領域的描述、關系和過程組成的 Hayes-Roth知識是事實、信念和啟發(fā)式規(guī)則。從知識庫的觀點看，知識是某領域中所涉及的各有關方面的一種符號表示。2CSUCSUCSUCSUCSUCSUC

2、SUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU知識要素3 事實事實 規(guī)則規(guī)則有關問題環(huán)境的一些事物的知識，常以有關問題環(huán)境的一些事物的知識，常以“是是”的形式出的形式出現(xiàn)?，F(xiàn)。有關問題中與事物的行動、動作相聯(lián)系的因果關系知識，有關問題中與事物的行動、動作相聯(lián)系的因果關系知識，是動態(tài)的，常以是動態(tài)的，常以“如果如果那么那么”形式出現(xiàn)。形式出現(xiàn)。 控制控制有關問題的求解步驟、技巧性知識，告訴怎么做一件事。有關問題的求解步驟、技巧性知識，告訴怎么做一件事。 元知識元知識有關知識的知識，是知識庫中的高層知識。包括怎樣使用有關

3、知識的知識，是知識庫中的高層知識。包括怎樣使用規(guī)則，解釋規(guī)則、校驗規(guī)則、解釋程序結構等知識。規(guī)則，解釋規(guī)則、校驗規(guī)則、解釋程序結構等知識。 CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU知識的表示4知識表示的分類知識表示的分類陳述性知識表示：將知識表示與知識的運用分開處理，在陳述性知識表示：將知識表示與知識的運用分開處理，在表示知識時，并不涉及如何運用知識的問題，是一種靜態(tài)表示知識時，并不涉及如何運用知識的問題，是一種靜態(tài)的描述方法。的描述方法。過程性知識表示：將知識表示與知識的

4、運用相結合，知識過程性知識表示：將知識表示與知識的運用相結合，知識寓于程序中，是一種動態(tài)的描述方法。寓于程序中，是一種動態(tài)的描述方法。知識表示的定義知識表示的定義可看成是一組事物的約定，以把人類知識表示成機器能處可看成是一組事物的約定，以把人類知識表示成機器能處理的數(shù)據(jù)結構。對知識進行表示的過程就是把知識編碼成某理的數(shù)據(jù)結構。對知識進行表示的過程就是把知識編碼成某種數(shù)據(jù)結構的過程。種數(shù)據(jù)結構的過程。CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU選取知識表示的因素5l表示知識的范圍

5、是否廣表示知識的范圍是否廣泛泛l是否適于推理是否適于推理l是否適于計算機處理是否適于計算機處理l是否有高效的求解算法是否有高效的求解算法l能否表示不精確知識能否表示不精確知識l能否在同一層次上和不同層能否在同一層次上和不同層次上模塊化次上模塊化l知識和元知識能否用統(tǒng)一的知識和元知識能否用統(tǒng)一的形式表示形式表示l是否適合于加入啟發(fā)信息是否適合于加入啟發(fā)信息l過程性表示還是說明性表示過程性表示還是說明性表示l表示方法是否自然表示方法是否自然CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCS

6、U62.1狀態(tài)空間法（State Space Representation）v問題求解技術主要是兩個方面：v問題的表示v求解的方法v狀態(tài)空間法v狀態(tài)（state）v算符（operator）v狀態(tài)空間方法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU72.1.1 問題狀態(tài)描述v定義v狀態(tài)：描述某類不同事物間的差別而引入的一組最少變量q0，q1，qn的有序集合。v算符：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。v問題的狀態(tài)空間：是一個表示該問題全部可能狀態(tài)及其關系的圖，

7、它包含三種說明的集合，即三元狀態(tài)（S，F(xiàn)，G）。vS:所有可能的初始狀態(tài)集合。F:操作符集合。G:目標狀態(tài)集合。2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU82. 狀態(tài)空間表示概念詳釋v例如下棋、迷宮及各種游戲。OriginalStateMiddleStateGoalState2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU9狀態(tài)

8、空間問題求解狀態(tài)空間法狀態(tài)空間法: : 從初始狀態(tài)開始從初始狀態(tài)開始, , 每次加一個操作符每次加一個操作符, , 遞增地建立起操遞增地建立起操作符的試驗序列作符的試驗序列, , 直到達到目標狀態(tài)為止直到達到目標狀態(tài)為止. .基本過程基本過程: :1. 1. 為問題選擇適當?shù)臑閱栴}選擇適當?shù)摹睜顟B(tài)狀態(tài)”及及”操作符操作符”的形式化描述方的形式化描述方法法, , 定義初始狀態(tài)集合定義初始狀態(tài)集合, , 目標狀態(tài)集合及操作符集合目標狀態(tài)集合及操作符集合; ;2. 2. 將操作符作用在初始狀態(tài)將操作符作用在初始狀態(tài)( (新狀態(tài)新狀態(tài)) )上生成新狀態(tài)逐步構造上生成新狀態(tài)逐步構造狀態(tài)空間狀態(tài)空間, ,

9、 判斷新狀態(tài)是否為目標狀態(tài)判斷新狀態(tài)是否為目標狀態(tài), , 如果是轉如果是轉3.3.否則否則轉轉2.2.3. 3. 尋找從初始狀態(tài)到目標狀態(tài)的一個尋找從初始狀態(tài)到目標狀態(tài)的一個( (最佳最佳) )路徑。路徑邊上路徑。路徑邊上所使用的操作符序列就是該問題的一個解所使用的操作符序列就是該問題的一個解. .CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU10例:三數(shù)碼難題（3 puzzle problem）123123123312312312初始棋局目標棋局2.1 狀態(tài)空間法CSUCSUC

10、SUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU11v有向圖v路徑v代價v圖的顯示說明v圖的隱示說明2.1.2 狀態(tài)圖示法AB2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU狀態(tài)空間圖狀態(tài)空間圖 把初始狀態(tài)可達到的各狀態(tài)所組成的空間用有向把初始狀態(tài)可達到的各狀態(tài)所組成的空間用有向圖表示。用圖表示。用”狀態(tài)狀態(tài)”標識節(jié)點標識節(jié)點, , 用用”操作操作”標識有向邊標識有

11、向邊, , 有向邊方向由被施加操作有向邊方向由被施加操作的對象狀態(tài)指向操作的結果狀態(tài)。的對象狀態(tài)指向操作的結果狀態(tài)。12CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU132.1.3 狀態(tài)空間表示舉例v產(chǎn)生式系統(tǒng)（production system）v一個總數(shù)據(jù)庫：它含有與具體任務有關的信息隨著應用情況的不同，這些數(shù)據(jù)庫可能簡單，或許復雜。v一套規(guī)則：它對數(shù)據(jù)庫進行操作運算。每條規(guī)則由左部鑒別規(guī)則的適用性或先決條件以及右部描述規(guī)則應用時所完成的動作。v一個控制策略：它確定應該采用哪

12、一條適用規(guī)則，而且當數(shù)據(jù)庫的終止條件滿足時，就停止計算。2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU14 狀態(tài)空間表示舉例狀態(tài)空間表示舉例v例：猴子和香蕉問題2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU15解題過程v 用一個四元表列（W，x，Y，z）來表示這個問題狀態(tài).v這個問題的操作（算符）如下：v2 goto（U）表示猴子

13、走到水平位置Uv或者用產(chǎn)生式規(guī)則表示為（W，0，Y，z） goto（U） （U，0，Y，z）2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU16vpushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z） pushbox（V） （V，0，V，z）vclimbbox猴子爬上箱頂，即有（W，0，W，z） climbbox （W，1，W，z）2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU

14、CSUCSUCSUCSUCSUCSUCSUCSUCSUCSU17vgrasp猴子摘到香蕉，即有（c，1，c，0） grasp （c，1，c，1） v該初始狀態(tài)變換為目標狀態(tài)的操作序列為goto(b),pushbox(c),climbbox,grasp2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU18(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）目標狀態(tài)目標狀態(tài)goto（U）goto（

15、U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉問題的狀態(tài)空間圖猴子和香蕉問題的狀態(tài)空間圖goto（U）U=V2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU19猴子和香蕉問題自動演示： 猴子猴子香蕉香蕉箱子箱子 猴子猴子香蕉香蕉箱子箱子 Ha!Ha!2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU狀態(tài)空

16、間表示舉例v傳教士和野人問題v狀態(tài)表示：(在河的左岸的傳教士人數(shù)、野人人數(shù)和船的情況)v初始狀態(tài):（3，3，1）v結束狀態(tài):（0，0，0v中間狀態(tài)則:（2，2，0）、（3，2，1）、（3，0，0）20CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU狀態(tài)空間表示舉例v狀態(tài)表示：(在河的左岸的傳教士人數(shù)、野人人數(shù)和船的情況)v初始狀態(tài):（3，3，1）v結束狀態(tài):（0，0，0v中間狀態(tài)則:（2，2，0）、（3，2，1）v每個三元組對應了三維空間上的一個點v問題的解，則是一個合法狀態(tài)的序列

17、：(初始狀態(tài)，結束狀態(tài))v中間狀態(tài)：介于初始狀態(tài)和結束狀態(tài)之間v除了初始狀態(tài)外，該序列中任何一個狀態(tài)，都可以通過一條規(guī)則，由與他相鄰的前一個狀態(tài)轉換得到21CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU222.2 問題歸約法（Problem Reduction Representation）子問題子問題1子問題子問題n原始問題原始問題子問題集本本原原問問題題CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCS

18、UCSUCSUCSUCSUCSUCSU23v 問題歸約表示的組成部分：v一個初始問題描述；v一套把問題變換為子問題的操作符；v一套本原問題描述。v問題歸約的實質：v從目標(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。2.2 問題規(guī)約法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU242.2.1 問題歸約描述 （Problem Reduction Description）v梵塔難題123CBA2.2 問題規(guī)約法CSUCS

19、UCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU25解題過程（3個圓盤問題）1231231231231231231231232.2 問題規(guī)約法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU26多圓盤梵塔難題演示2.2 問題規(guī)約法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUC

20、SUCSU272.2.2與或圖表示v1.與圖、或圖、與或圖2.2 問題規(guī)約法ABCD與圖ABC或圖CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU282.2 問題規(guī)約法BCDEFGAHMBCDEFGANCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU292.一些關于與或圖的術語2.2 問題規(guī)約法HMBCDEFGAN父節(jié)點與節(jié)點弧線或節(jié)點子節(jié)點終葉節(jié)點CSUCSUCSUC

21、SUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU303.定義2.2 問題規(guī)約法與或圖例子與或圖例子ttttttttt（a）（b）有解節(jié)點無解節(jié)點終葉節(jié)點CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU31v不可解節(jié)點的一般定義v沒有后裔的非終葉節(jié)點為不可解節(jié)點。v全部后裔為不可解的非終葉節(jié)點且含有或后繼節(jié)點，此非終葉節(jié)點才是不可解的。v后裔至少有一個為不可解的非終葉節(jié)點且含有與后繼節(jié)點，此

22、非終葉節(jié)點才是不可解的。v與或圖構成規(guī)則2.2 問題規(guī)約法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU32梵塔問題歸約圖（113） （123） （111） （113） （123） （122） （111） （333） （122） （322） （111） （122） （322） （333） （321） （331） （322） （321） （331） （333） 2.2 問題規(guī)約法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUC

23、SUCSUCSUCSUCSUCSUCSUCSUCSUCSU332.3 謂詞邏輯法v邏輯語句v形式語言2.3.1 謂詞演算v 1. 語法和語義v基本符號v謂詞符號、變量符號、函數(shù)符號、 常量符號、括號和逗號v原子公式CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU34v連詞和量詞(Connective &Quantifiers)v連詞v與及合?。╟onjunction)v或及析?。╠isjunction）v蘊涵（Implication）v非（Not）v量詞v全稱量詞（Universa

24、l Quantifiers)v存在量詞 (Existential Quantifiers)2.3 謂詞邏輯法CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU一階謂詞邏輯v一階謂詞邏輯表示法，是一階謂詞邏輯表示法，是一種重要的知識表示一種重要的知識表示方法，它以數(shù)理邏輯為基礎，是到目前為止能方法，它以數(shù)理邏輯為基礎，是到目前為止能夠表達人類思維和推理的一種最精確的形式語夠表達人類思維和推理的一種最精確的形式語言。它的表現(xiàn)方式和人類自然語言非常接近，言。它的表現(xiàn)方式和人類自然語言非常接

25、近，它能夠被計算機作精確推理。它能夠被計算機作精確推理。35CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU一階謂詞邏輯v用謂詞公式既可表示事物的狀態(tài)、屬性和概念等事實性的知識，也可表示事物間具有因果關系的規(guī)則性知識。36CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU用謂詞公式表示知識的一般步驟用謂詞公式表示知識的一般步驟1.定義謂詞及個體，確定每個謂詞及個體的確定義

26、謂詞及個體，確定每個謂詞及個體的確切含義。切含義。2.根據(jù)所要表達的事物或概念，為每個謂詞中根據(jù)所要表達的事物或概念，為每個謂詞中的變元賦以特定的值。的變元賦以特定的值。3.根據(jù)所要表達的知識的語義，用適當?shù)倪B接根據(jù)所要表達的知識的語義，用適當?shù)倪B接符將各個謂詞連接起來形成謂詞公式。符將各個謂詞連接起來形成謂詞公式。37CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU謂詞邏輯表示知識舉例1v用謂詞邏輯表示下列知識：v武漢是一個美麗的城市，但她不是一個沿海城市。1.定義謂詞如下：BC

27、ity(x)：x是一個美麗的城市 HCity(x)：x是一個沿海城市2.將個體代入謂詞中，得到： BCity(wuhan), HCity(wuhan)3.根據(jù)語義，用邏輯連接符連接vBCity(wuhan)HCity(wuhan)38CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU謂詞邏輯表示知識舉例2v用謂詞邏輯表示下列知識：v如果馬亮是男孩，張紅是女孩，則馬亮比張紅長得高。1.定義謂詞如下：Boy(x): x是男孩 Girl(x): x是女孩 High(x,y): x比y長得高

28、2.將個體代入謂詞中，得到:Boy(mal), Girl(zhangh), High(mal,zhangh)3.根據(jù)語義，用邏輯連接符連接(Boy(mal)Girl(zhangh)High(mal,zhangh)39CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU402.3.2 謂詞公式v原子公式的的定義：v用P(x1，x2，xn)表示一個n元謂詞公式，其中P為n元謂詞，x1,x2,，xn為客體變量或變元。通常把P(x1,x2,xn)叫做謂詞演算的原子公式，或原子謂詞公式。v分子謂詞公式v可以用連詞把原子謂詞公式組成復合謂詞公式，并把它叫做分子謂詞公式。2.3 謂詞邏輯法CSUCSUCSUCSUC