#2-1第二章知識表示與推理

1、第二部分知識表示方法問題求解(ProblemsoIving)涉及許多研究領(lǐng)域，但知識表示是其三大基本功能之一。本章主要討論幾中基本的知識表示方法技術(shù)，如狀態(tài)空間表示法、問題歸約法、謂詞邏輯法、語義網(wǎng)絡(luò)法等方法。2-1狀態(tài)(state)空間表示法2-1-1問題Q的狀態(tài)描述State:為描述某類不同事物間差異而引入的一組變量qo,qi,.,qn之有序集合。即Q=血1,qnT,其中，qi表示狀態(tài)分量或狀態(tài)變量。Qk二q°kq1k,qnJ表示Q的每一元素都賦予一個值之后的某種狀態(tài)。(1) 操作符/算符：是問題從一種狀態(tài)變遷到另外一種狀態(tài)的過程或手段。如走步、過程、規(guī)則、算子、邏輯運算符號等。

2、問題狀態(tài)空間：表示問題全部可能狀態(tài)及其關(guān)系的圖。其構(gòu)成由三部分構(gòu)成(如圖所示)15數(shù)碼難題(15puzzleproblem)114121321011315984567114121321011315984567TargetShift412111321014315981567A需要解決的問題如下:原始問題描述：每次移Source動一步，只能移動跟空格相鄰的數(shù)字單元。是 問題的狀態(tài)描述方法 問題的初始狀態(tài)描述 問題的目標(biāo)狀態(tài)描述問題描述狀態(tài)轉(zhuǎn)換的操作算子及其對狀態(tài)描述的作用問題描述狀態(tài)轉(zhuǎn)換的操作算子及其對狀態(tài)描述的作用(1)(1)1117151211941513128862-1十五數(shù)碼難題的部分狀態(tài)

3、圖表示6119415138127156狀態(tài)問：由若干（不一定是有限）節(jié)點的集合構(gòu)成（有向圖或無向圖）。日頁的狀問題的狀路徑：節(jié)點序列5（n8,nd，nik7）中5除n外，所有節(jié)點都有一個后繼6則該序示法心、列稱為節(jié)點片到節(jié)點氐的長度為k的一條路徑。心、能夠能夠節(jié)示的問若節(jié)點口到nj之間存在一條路徑，則稱節(jié)點n到節(jié)點nj可達，節(jié)點nj 求解問題狀態(tài)圖中指定節(jié)點S（初始狀態(tài)）與另一節(jié)點t（目標(biāo)狀態(tài)）之間的一條路徑（或所有路徑）。 求節(jié)點S與節(jié)點集合t中任一個節(jié)點之間的距離（最小距離，最大距離等）求節(jié)點集合S中任一個節(jié)點與節(jié)點集合t中任一個節(jié)點之間的路徑。2-1-3狀態(tài)空間表示舉例（從要解決的五個基

4、本問題分析）例1十五數(shù)碼問題（表示如圖2-1，可用矩陣形式表示）原始問題描述：有一個4M的方格棋盤，其中的每一方格放入一1-15之間的數(shù)字值,個空格方格，每次（只能）通過交換空格方格和其（水平和垂直方向上）相鄰四個方格中的一個數(shù)進入下一狀態(tài)。問是否能從給定棋盤初始狀態(tài)，進入目標(biāo)狀態(tài)？或給定兩棋盤格局,能否從一個狀態(tài)達到另一狀態(tài)？等等。例2推銷員旅行問題（如圖2-2的形式表示，其狀態(tài)空間圖如2-3）。原始問題描述：推銷員要在n個城市之間旅行推銷產(chǎn)品，從一個城市出發(fā)，經(jīng)過每個城市一次,最后回到起點城市。問：如果按照總路程的長短為評判標(biāo)準(zhǔn)，如何設(shè)計旅行路徑，使得他能夠旅行所有城市一次，且僅一次，同時

5、，又能旅行路徑最短?7例3猴子和香蕉冋題ACB圖2-4猴子和香蕉問題組向狗)(，一只，z)表示整個問題的各種狀態(tài)，其箱子和懸掛在天花板上的W表示猴子的水平位置；x表香蕉，猴子否在高度子頂容易香蕉，是時x=1，否則x=0;丫彳表示箱子所在的箱平位置可z表示猴子是否摘到香蕉，摘到以。如,果否將其看成機器人，問題的初始狀態(tài)描述(a,0,b,0) 問題描述狀態(tài)轉(zhuǎn)換的操作算子及其對狀態(tài)描述的作用本問題有四個算子：(1) goto(u)表示猴子走到水平位置U。用產(chǎn)生式規(guī)則表示成：(W,0,Y,z)goto(U)>(U,0,Y,z)。即猴子在水平位置W處，箱子在丫處，沒有站在箱子上,是否摘到香蕉處于z

6、值狀態(tài)，在goto(U)算子作用下，會進入下一個狀態(tài)(U,0,Y,z)。(2) pushbox(V)表示猴子把箱子推到水平位置V。用產(chǎn)生式規(guī)則表示成：(W,0,W,z)pushbox(V)>(V,0,V,z)。即猴子與箱子在同一位置，且猴子不在箱子頂上時,(W,0,W,z)climbbox>(W,1,W,z)(c,1,c,0)grasp>(c,1,c,1)它通過pushbox(V)算子將箱子推到水平位置V，進入(V10,V,z)狀態(tài)。(3) climbbox算子表示猴子爬上箱子頂去。即:(4) grasp算子表示猴子在箱子頂上摘香蕉。即: 問題的目標(biāo)狀態(tài)描述(C,1,C,1)

7、初始狀態(tài)(a,0,b,0)goto(u),goto(u)(U,0,b,0)V=c,climbbox(c,1,c,0)V，0，V，0)gotO(U)goto(U)pushbox(V)U=b,climbbox(b,1,b,0)(U,0,V,0)grasp*(c,1,c,1)目標(biāo)狀態(tài)圖2-4猴子和香蕉冋題的狀態(tài)空間圖(1)HanoiPuzzle(圖示略)問題的原始描述2-2問題歸約法(ProblemReduction)2-2-1問題歸約描述基本思想：已知問題描述，希望通過對原始問題進行變換或分解，變成難度較小的子問題，通過解三個組成部分：(1)初始問題描述；將問題變成子問題的操作符集合；(3)套原始

8、問題的歸約(將其變成三個難度較小的子問題)歸約的圖表示(2)歸約問題的描述方法 已有的問題描述方法：列表(list)、樹(tree)、字符串(string)、矢量(array)、數(shù)組(array)等。 問題歸約法利用狀態(tài)空間法中的狀態(tài)、算子和目標(biāo)等概念來描述問題，但不等同于狀態(tài)空間法。實際上是比狀態(tài)空間法更一般的問題求解方法。其目的是產(chǎn)生具有明顯解的本原問題。“與或圖”概念本原問題圖2-6“與或圖”的結(jié)構(gòu)NMBDEA原始冋題子問題集合1)每一節(jié)點代表要求解問題的一個單一子問題或者子問題集合2) 葉子節(jié)點表示本原問題帶小弧線連接的分支節(jié)點集合稱為與節(jié)點，當(dāng)左右這些子問題得解時，其父問題才可解。3

9、) 沒有小弧線連接的分支節(jié)點稱為或節(jié)點，只要其中任一個得解，其父問題即可解。(3)問題歸約機理關(guān)鍵算符：對問題求解具有決定作用的算符差別：三元狀態(tài)(S,F,G)中，用S中的元對集合G中的目標(biāo)進行測試，其中，不能滿足的原因列表。 歸約方法：將狀態(tài)空間中的算符或者算符集合與求得的差別中之每一個原因進行比較，如果可以消去該差別，則結(jié)合成功，該算符成為關(guān)鍵算符。直到遇到本原問題為止。 可解節(jié)點、不可解節(jié)點和與或圖的構(gòu)成規(guī)則：(參見教材P31-33)猴子的初始狀態(tài)為(a,O,b,O)；2-2-2例子注：因為，算符集合本身在問題描述中不會發(fā)生該問題的算符集合為：f1:(W,0,Y,z)goto(U)>

10、;(U,0,Y,z)f2:(W,0,Y,z)pushboV)>(V,0,V,z)f3:(W,0,W,z)climbbox，(W,1,W,z)f4:(c,1,c,0)grasp>(c,1,c,1)第一步：計算初始冋題的差別。最后一個兀素為0，而與之相關(guān)的關(guān)鍵操作是grasp，所以用f4對初始問題進行歸約，得到兩個子問題，即：S=(a,0,b,0),Gf4)和(f4(S),G)。第二步：對Gf4計算和初始問題的差別，然后獲取關(guān)鍵算符pushbox(c),goto(c),climbbox，并依次進行歸約。第N步：繪制歸約過程的“與或圖”2-3謂詞邏輯法2-3-1謂詞演算2-3-2謂詞公式

11、2-3謂詞邏輯法2-3-1謂詞演算2-3-2謂詞公式組成：謂詞符號、變量符號、函數(shù)符號、常量符號，并用圓括號、花括號和逗號分隔的符號體系。如：Married(father(L),mother(L)符號體式定義:符號體式定義:等。(1) 原子謂詞公式是合式公式(2) 若A和B都是合式公式，則AB,AB,A=B,AB都是合式公式(3) 若A是合式公式，則A也是合適公式若A是合式公式，x是A中的自由變量，貝U(-x)A,(x)A都是合適公式(5) 只有按照上述(1)(4)的原則求得的公式，才是合式公式?；具\算定律及推論：否定律：一(P)：=PPQ=P；Q狄.摩根定律：(PQ)二PQ-(PQ)二-P

12、-Q分配律：P(QR)二(PQ)(PR)P(QR)=(PQ)(PR)交換律：PQ=QPPQ=QP結(jié)合律：(PQ)R=P(QR)(PQ)R=P(QR)逆否律：PrQuQ、P其它等價關(guān)系：(x)P(x)=(-x)(P(x)(-x)P(x)二(x)(P(x)(-x)(P(x)Q(x)=(-x)P(x)(-x)Q(x)(x)(P(x)Q(x)u(x)P(x)(x)Q(x)(-x)P(x)=(-y)P(y)(x)P(x)=(y)P(y)其它相關(guān)概念：約束變量、自由變量、析取式、合取式、真值表等。2-3-3置換與合一(1)置換(Substitution):表達式的項可為變量符號、常量符號和函數(shù)表達式。在謂

13、詞邏輯中,利用假元推理(即Wi,WiTW2二W2)和全稱化推理(即(Vx)W(x)nW(A)，用置換項A對變量x進行置換，使得W(A)與W(x)保持一致的變換過程。例2-3對表達式Px,f(y),B可以有以下4個置換：si=4/x,w/y:s2=、A/y；s3="q(z)/x,A/y:s4=/x,A/y假定用Es表示對表達式E用置換s所得到的表達式的置換，則對以上表達式進行的置換結(jié)果分別為：Px,f(y),Bs1=Pz,f(w),BPx,f(y),Bs2=Px,f(A),BPx,f(y),Bs3二Pq(z),f(A),BPx,f(y),Bs4二Pc,f(A),B置換是可結(jié)合的，但是，

14、一般是不可交換的。例如：(Ls1)s2=L(s1s2);(s1s2)s3=s1(s2s3);但一般來說s1s2=S2s1。(2) 合一(Unification):尋找項對變量的置換，以使兩個表達式一致的過程。表達式集合的置換表示：EJs表示置換s作用于其中的每個元素。表達式集合是可合一的：如果存在一個置換s，使得二E?s二二Ejs=，則稱此s為表達式集合Ei的合一者。顯然，s使得表達式集合Ei成為單一形式。例2-4表達式集合Px,f(y),B,Px,f(B),B的合一者為：s=A/x,B/y。因為，經(jīng)過置換后，集合中的表達式為單一形式PA,f(B),B。表達式集合EJ的最通用/最一般合一者(m

15、gu):如果置換s是巳的任一合一者，又存在一個s'，使得Ejs=Ejgs'，則稱g為巳的最通用/最一般合一者。例如，上例中的最簡單的最一般合一者為：g二B/y。(3) 合一算法(略)2-4語義網(wǎng)絡(luò)法1概念：(最早由Quillian1966年在博士論文中提出)有關(guān)一個物體/一組物體或概念知識的圖解表示。它由節(jié)點和弧線組成。節(jié)點表示實體、概念或情況等，弧線則表示節(jié)點之間關(guān)系。2. 組成：(1) 詞法：指語義網(wǎng)絡(luò)表示中涉及的符號、節(jié)點和弧線。(2) 結(jié)構(gòu)：敘述符號排列的約束條件，指定各弧線連接的節(jié)點對。過程：說明訪問過程，以便修改、建立和回答相關(guān)問題。(4) 語義：確定與描述相關(guān)的(

16、聯(lián)想)意義。3. 語義網(wǎng)絡(luò)的特點：(1) 能夠把實體的結(jié)構(gòu)、屬性與實體間的因果關(guān)系顯式地表達出來。而與實體相關(guān)的屬性、事實、特征、關(guān)系等可通過相應(yīng)節(jié)點的弧線推導(dǎo)出來。以便以聯(lián)想的方式解釋系統(tǒng)。(2) 表達的概念容易理解和學(xué)習(xí)。(3) 表達問題直觀，符合人的思維習(xí)慣，便于與領(lǐng)域?qū)＜覝贤?。?）對網(wǎng)絡(luò)結(jié)構(gòu)的語義解釋依賴于對結(jié)構(gòu)的推理過程（沒有結(jié)構(gòu)約定），因此，推理的有效性不如謂詞邏輯。節(jié)點間的聯(lián)系可以是線狀、樹狀、網(wǎng)狀或遞歸形式。知識的檢索和存儲比較復(fù)雜二元語義網(wǎng)絡(luò)的表示XWOYAOwSAISAISA:a)*圖BIRD簡單F例是XIAOYANXIAOYANISA；甲OWNEE=ISANEST-1“

17、OWNEROWN-1匸BIRD個巢的事實圖（b）HAS-PART圖（c）ISAISANESTSTARTTIME#SPRINGENDTIMEFALLISAISATIMEWINGS圖（b）表示小燕子從春天到秋天占有一個巢的事實（從謂詞演算的角度表達時，它需要用一個四元謂詞表示）OWNERSHIPISASITUATION圖2-8具有多元關(guān)系的概念之二元語義網(wǎng)絡(luò)示例概念節(jié)點：表示一種通用概念的語義節(jié)點實例節(jié)點：表示某一具體物體和事實的節(jié)點語義基元：基本概念和基本關(guān)系。以之能夠表達更一般的概念及其關(guān)系如圖2-9中的CAR概念和MYCAR、LIUHUA'CAR實例；圖2-7中的BIRD概念等。其中

18、,圖2-9中的CAR概念是語義基元。4. 多元語義網(wǎng)絡(luò)的表示圖2-9概念節(jié)點和實例節(jié)點因為語義網(wǎng)絡(luò)本質(zhì)上只能表達二元關(guān)系，所以，對多元關(guān)系的語義表示，應(yīng)當(dāng)首先劃分成相應(yīng)的二元關(guān)系組合表達形式，或者合取。例如：“北京大學(xué)和清華大學(xué)兩?；@球隊在北京大學(xué)進行的一場比分為85比89的比賽”用謂詞邏輯可表示為：SCORE(BU,TU,(8589)表示，但用語義網(wǎng)絡(luò)時，需要將其分解為，如圖2-10所示的四個二元關(guān)系來描述。5. 謂詞邏輯中的量詞和連接關(guān)系在語義網(wǎng)絡(luò)中的表示方法(1)合取如圖2-10所表示的方法。又如：對“JohngaveMarythebook'的謂詞邏輯表示為GIVE(JOHN,M

19、ARY,BOOK)，但用語義網(wǎng)絡(luò)表示為圖2-11所示。其中G1表示“一個特定的給某人東西的事件”，B23表示給出去的東西。圖2-10多元關(guān)系的語義網(wǎng)絡(luò)表示GIVEJOHNGIVERG1ISAISA一|OBJECTrB23析取在析取關(guān)系的語義網(wǎng)絡(luò)RECIPIENT*MARY表達中，其析取連接上用加標(biāo)注的方式加以界定(如圖2-12圖2-11用語義網(wǎng)絡(luò)表示的合取中的DIS框)。對析取中的合取，需要用合取標(biāo)注界限CON界定(如BOOK圖2-12所示)(3) 否定用ISA，PART-OF或NEG界限進行標(biāo)注(圖2-13)圖2-12合取、析取及析取中嵌套合取結(jié)構(gòu)時的語義網(wǎng)絡(luò)表示蘊涵用ANTE(antece

20、dent和CONSE(consequenc©分別標(biāo)注蘊涵的先決條件和結(jié)果界限(用虛線標(biāo)注)(圖2-14)量化對存在量詞的表示，可用ISA鏈完成對全稱量詞的表示，需要采取分割的方法，將語義網(wǎng)絡(luò)分割成空間分層的集合，其中的每一個空間對應(yīng)于一個或幾個變量的范圍。如圖2-15所示。其中，對圖2-15(b),其謂詞形式為：(-x)DOG(x)二(y)POSTMAN(y)BITE(x,y)。其中，d是全稱量化變量，DOGBITEPOSTMAN1'ISA'ISAi'ISADOGBITEPOSTMAN1'ISA'ISAi'ISAThedogbitsth

21、epostman表示。其中，的郵遞員，”的語義網(wǎng)絡(luò)D表示特定的狗，P表示特定B表示特定的咬人事件。ASSAILIANTBVICTIM2-15(a)GStISADOGBITEPOSTMANISA>DVASSAILIANTISAISAS1VICTIMEverydoghasbittenapostman”的語義網(wǎng)絡(luò)表示。其中，S1是一個特定的分割，表示斷言G“Adoghasbittenapostman”。GS是一個概念節(jié)點，表示具有全稱化的一般事件，而G只是GS的一個實例。DOGBITEPOSTMANISAISADBfa.PR丿FORM2-15(b)Everydoghasbitteneveryp

22、ostman的語義網(wǎng)絡(luò)表示。可見，斷言G不發(fā)生改變。GS概念節(jié)點和斷言G之間的關(guān)系不變，只是增加一條全稱量詞連接關(guān)系來表示H“Everypostmanhasbeenbitten”。VISAV2-15(c)圖13(c)圖2-13否定的語義網(wǎng)絡(luò)表示NOTE:分割成空間分層集合方法的運用。圖2-15量化在語義網(wǎng)絡(luò)中的表示的語義網(wǎng)絡(luò)表示。其中，Y表示地址；O(X,Y)表示一個特圖2-14蘊涵的語義網(wǎng)絡(luò)表示7.基于語義網(wǎng)的推理過程(1)幾個概念2-17中的ISA槽和COLOR槽。語義網(wǎng)絡(luò)表示下的值的繼承。B和P是存在量化變量，用于表明斷定關(guān)系，稱為斷言G由兩個部分構(gòu)成：一是斷言本身(見圖中虛線部分)FO

23、RM;是代表全稱量詞的符號-值節(jié)點：在語義網(wǎng)絡(luò)鏈的尾部處的節(jié)點。例如，圖2-17中，尾部節(jié)點BRICK和TOY為實例BRICK12之ISA槽的兩個值節(jié)點；其COLOR槽的值節(jié)點為RED值。槽(Slot)：節(jié)點之間的鏈接關(guān)系。例如圖繼承繼承：在語義網(wǎng)絡(luò)中，把對事物的描述從概念節(jié)點或類節(jié)點傳遞到實例節(jié)點的過程。例如，在圖2-18中，BRICK是概念節(jié)點，BRICK12是實例節(jié)點。BRICK在SHAPE槽中的RECTANGULAR屬性值，在對BRICK12實例節(jié)點進行描述時，雖然沒有關(guān)于BRICK12的SHAPE槽描述，但通過ISA鏈，可以將SHAPE槽的值傳遞給BRICK12實例。此即基于特點：類

24、似于人的思維習(xí)慣。對事物的屬性和特征的一般化描述可以被認(rèn)為是具體實例所具有的值。例如，鳥比較小，鯨魚比較大，飛機可以飛翔等。三種繼承過程：1) 值繼承：通過ISA和AKO(A-Kind-Of)鏈用于語義網(wǎng)絡(luò)中的描述或特性的繼承。2) “如果需要”繼承：當(dāng)不知道槽值時，可以利用當(dāng)前已知的信息計算之。3) 缺省繼承。2-5框架法(Framework)2-5-1概述概念：以一個通用數(shù)據(jù)結(jié)構(gòu)的形式存儲以往的經(jīng)驗，該結(jié)構(gòu)即稱為框架。特點：在次結(jié)構(gòu)下，新的資料可以從過去的經(jīng)驗得到的概念來進行分析和解釋。2-5-2框架的構(gòu)成（1）構(gòu)成：由描述事物的各個方面的槽（Slot）組成，每個槽有若干側(cè)面（Face）構(gòu)

25、成，每個側(cè)面又可以擁有多個值。（2）結(jié)構(gòu)（見教材P45）例如：JOHN有ISA，Profession,Height，Weight等槽，而其槽值分別為PERSON，框架結(jié)構(gòu)槽的側(cè)面或值備注JOHNFrame-NameISAPERSONSlot-1:ValueProfessionPROGRAMMERSlot-2:ValueHeight1.8mSlot-3:ValueWeight79kgSlot-4:ValuePROGRAMMER，1.8m,79kg。（如表2-2所示）表2-2簡單框架示例表（3）框架系統(tǒng)大多數(shù)問題的框架表示，往往需要由多個框架同時進行。例如，表示立方體的視圖的框架問題（見教材P45-46)。構(gòu)可以同時被幾個其它框架結(jié)構(gòu)所使用；式展現(xiàn)框架系統(tǒng)樹狀結(jié)構(gòu)的框架系統(tǒng)基本構(gòu)成如下:注：1）一個框架結(jié)構(gòu)可以包含個或多個框架槽值；2）一個框架結(jié)3）框架是一種通用的知識表示形式，常常以樹的形框架名用類名表示AKOVALUEV值>AKO槽具有VALUE側(cè)面，值可以填寫PROPDEFAULT<表1>PROP槽記錄節(jié)點的特性信息，其側(cè)面可缺省繼承SFIF-NEEDEDV算術(shù)表達式>SF槽的“如果需要”側(cè)面將進行相應(yīng)計算CONFLICTADDV表2>CONFLICT槽記錄沖突表（4）基于框架表示的推理過程（略）（見教材P47-48簡介）2-6劇本法（Scri