1、1,第二章 知識(shí)表示方法,2.1 狀態(tài)空間法 2.2 問(wèn)題歸約法 2.3 謂詞邏輯法 2.4 語(yǔ)義網(wǎng)絡(luò)法 2.5 其他方法 2.6 小結(jié),2,2.1狀態(tài)空間法（State Space Representation）,問(wèn)題求解技術(shù)主要是兩個(gè)方面： 問(wèn)題的表示 求解的方法 狀態(tài)空間法 狀態(tài)（state）:表示問(wèn)題解法中每一步問(wèn)題狀況的數(shù)據(jù)結(jié)構(gòu) 算符（operator):把問(wèn)題從一種狀態(tài)變換為另一種狀態(tài)的手段 狀態(tài)空間方法:基于解答空間的問(wèn)題表示和求解方法，它是以狀態(tài)和算符為基礎(chǔ)來(lái)表示和求解問(wèn)題的,3,2.1.1 問(wèn)題狀態(tài)描述,定義 狀態(tài)(State)：描述某類(lèi)不同事物間的差別而引入的一組最少變量q

2、0，q1，qn的有序集合。 算符(Operate)：使問(wèn)題從一種狀態(tài)變化為另一種狀態(tài)的手段稱(chēng)為操作符或算符。 問(wèn)題的狀態(tài)空間(State Space)：是一個(gè)表示該問(wèn)題全部可能狀態(tài)及其關(guān)系的圖，它包含三種說(shuō)明的集合，即三元狀態(tài)（S，F(xiàn)，G）。,2.1 狀態(tài)空間法,4,狀態(tài)空間表示概念詳釋,狀態(tài)空間法：從某個(gè)初始狀態(tài)開(kāi)始，每次加一個(gè)操作符，遞增的建立起操作符的實(shí)驗(yàn)序列，直到達(dá)到目標(biāo)狀態(tài)止。 例如下棋、迷宮及各種游戲。,Middle State,Goal State,2.1 狀態(tài)空間法,5,例:三數(shù)碼難題（3 puzzle problem）,初始棋局,目標(biāo)棋局,2.1 狀態(tài)空間法,6,有向圖 一對(duì)

3、節(jié)點(diǎn)用弧線(xiàn)連接起來(lái)，從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)這種圖叫做有向圖。 路徑 某個(gè)節(jié)點(diǎn)序列（ni1，ni2，nik）當(dāng) j = 2，3，k時(shí)，如果對(duì)于每一個(gè)ni，j-1都有一個(gè)后繼節(jié)點(diǎn)ni，j存在，那么就把這個(gè)節(jié)點(diǎn)序列叫做從節(jié)點(diǎn)ni1至節(jié)點(diǎn)nik的長(zhǎng)度為k的路徑 代價(jià) 用c（ni，nj）來(lái)表示從節(jié)點(diǎn)ni指向節(jié)點(diǎn)nj的那段弧線(xiàn)的代價(jià)。兩點(diǎn)間路徑的代價(jià)等于連接該路徑上各節(jié)點(diǎn)的所有弧線(xiàn)代價(jià)之和.,2.1.2 狀態(tài)圖示法,2.1 狀態(tài)空間法,7,圖的顯示說(shuō)明 對(duì)于顯式說(shuō)明，各節(jié)點(diǎn)及其具有代價(jià)的弧線(xiàn)由一張表明確給出。此表可能列出該圖中的每一節(jié)點(diǎn)、它的后繼節(jié)點(diǎn)以及連接弧線(xiàn)的代價(jià) (舉例：鄰接表，鄰接矩陣) 圖的隱

4、示說(shuō)明 說(shuō)明節(jié)點(diǎn)的無(wú)限集合si作為起始節(jié)點(diǎn)是已知的。后繼節(jié)點(diǎn)算符（gamma）也是已知的，它能作用于任一節(jié)點(diǎn)以產(chǎn)生該節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)和各連接弧線(xiàn)的代價(jià)。（舉例：棋局） 表示方法的多樣性 如十五數(shù)碼難題中 規(guī)則1：移動(dòng)數(shù)碼（15X4條規(guī)則） 規(guī)則2：移動(dòng)空格（4條規(guī)則）,8,產(chǎn)生式系統(tǒng)搜索過(guò)程描述,產(chǎn)生式系統(tǒng)（production system） 一個(gè)總數(shù)據(jù)庫(kù)：它含有與具體任務(wù)有關(guān)的信息隨著應(yīng)用情況的不同，這些數(shù)據(jù)庫(kù)可能簡(jiǎn)單，或許復(fù)雜。 一套規(guī)則：它對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算。每條規(guī)則由左部鑒別規(guī)則的適用性或先決條件以及右部描述規(guī)則應(yīng)用時(shí)所完成的動(dòng)作。 一個(gè)控制策略：它確定應(yīng)該采用哪一條適用規(guī)則，而

5、且當(dāng)數(shù)據(jù)庫(kù)的終止條件滿(mǎn)足時(shí)，就停止計(jì)算。,2.1 狀態(tài)空間法,9,狀態(tài)空間表示實(shí)例（1）,例：猴子和香蕉問(wèn)題,2.1 狀態(tài)空間法,10,解題過(guò)程,用一個(gè)四元表列（W，x，Y，z）來(lái)表示這個(gè)問(wèn)題狀態(tài). W 猴子的水平位置 x 當(dāng)猴子在箱子頂上時(shí)取 x = 1；否則取 x = 0 Y 箱子的水平位置 z 當(dāng)猴子摘到香蕉時(shí)取 z=1；否則取 z=0,這個(gè)問(wèn)題的操作（算符）如下： goto（U）表示猴子走到水平位置U 或者用產(chǎn)生式規(guī)則表示為 （W，0，Y，z） goto（U） （U，0，Y，z）,2.1 狀態(tài)空間法,11,pushbox（V）猴子把箱子推到水平位置V，即有 （W，0，W，z） push

6、box（V） （V，0，V，z） 應(yīng)當(dāng)注意的是，要應(yīng)用算符pushbox（V），就要求產(chǎn)生式規(guī)則的左邊，猴子與箱子必須在同一位置上，并且，猴子不是箱子頂上。這種強(qiáng)加于操作的適用性條件，叫做產(chǎn)生式規(guī)則的先決條件,climbbox猴子爬上箱頂，即有 （W，0，W，z） climbbox （W，1，W，z） 提問(wèn)：應(yīng)用算符climbbox的先決條件是什么？,2.1 狀態(tài)空間法,12,grasp猴子摘到香蕉，即有 （c，1，c，0） grasp （c，1，c，1）,令初始狀態(tài)為(a，0，b，0)。這時(shí)，goto(U)是唯一適用的操作，并導(dǎo)致下一狀態(tài)(U，0，b,0)。現(xiàn)在有3個(gè)適用的操作，即goto(

7、U)，pushbox(V)和climbbox(若U=b)。把所有適用的操作繼續(xù)應(yīng)用于每個(gè)狀態(tài)，我們就能夠得到狀態(tài)空間圖，如下圖所示。從圖不難看出，把該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為 goto(b),push box(c),climbbox,grasp,2.1 狀態(tài)空間法,13,目標(biāo)狀態(tài),goto（U）,goto（U）,U=b，climbbox,goto（U）,U=b,pushbox（V）,猴子和香蕉問(wèn)題的狀態(tài)空間圖,goto（U）,U=V,2.1 狀態(tài)空間法,14,猴子和香蕉問(wèn)題自動(dòng)演示：,2.1 狀態(tài)空間法,15,狀態(tài)空間表示實(shí)例（2）,推銷(xiāo)員旅行問(wèn)題 一個(gè)推銷(xiāo)員計(jì)劃出訪(fǎng)推銷(xiāo)產(chǎn)品。他從一

8、個(gè)城市( 如 A) 出發(fā) , 訪(fǎng)問(wèn)每個(gè)城市一次 , 且最多一次 , 然后 A返回城市 A 。要求尋找最短路線(xiàn) , 如圖 2.3 所示。為了確定這個(gè)問(wèn)題 , 作如下規(guī)定 : (1) 總數(shù)據(jù)庫(kù)是到目前為止所訪(fǎng)問(wèn)過(guò)的城市表 .初始數(shù)據(jù)庫(kù)被描述為表 (A) 。不允許目錄表中任一城市出現(xiàn)多于一次 , 只有城市 A 例外 , 但也只有當(dāng)所有其他城市均已出現(xiàn)之后 , 才能 再次出現(xiàn) A 。 (2) 規(guī)則對(duì)應(yīng)于決策 : 即下一步走向城市 A; 下一步走向城市 B; ; 下一步走向城市E 。一條規(guī)則除非能夠把某個(gè)數(shù)據(jù)庫(kù)變?yōu)橐粋€(gè)合法數(shù)據(jù)庫(kù) , 否則就不適用于這個(gè)數(shù)據(jù) 庫(kù)。例如 , 應(yīng)用 下一步走向城市 A 這條規(guī)

9、則就不適用于尚未出現(xiàn)所有其他城市的任一 數(shù)據(jù)庫(kù)。 (3) 任一以 A 為起點(diǎn)和終點(diǎn),并出現(xiàn)所有其他城市的總數(shù)據(jù)庫(kù),都滿(mǎn)足終止條件?？梢允褂孟聢D的距離圖表來(lái)計(jì)算任一旅程的總距離。提出作為解答的任一旅程,必須是具有最短距離的旅程。,2.1 狀態(tài)空間法,16,2.1 狀態(tài)空間法,17,2.2 問(wèn)題歸約法（Problem Reduction Representation）問(wèn)題歸約法思想 先把問(wèn)題分解為子問(wèn)題及子-子問(wèn)題，然后解決較小的問(wèn)題。對(duì)該問(wèn)題的某個(gè)具體子集的解答就意味著對(duì)原始問(wèn)題的一個(gè)解答,18,問(wèn)題歸約表示的組成部分： （1）一個(gè)初始問(wèn)題描述； （2）一套把問(wèn)題變換為子問(wèn)題的操作符； （3）一

10、套本原問(wèn)題描述。,問(wèn)題歸約的實(shí)質(zhì)： 從目標(biāo)(要解決的問(wèn)題)出發(fā)逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集合。,2.2 問(wèn)題規(guī)約法,19,2.2.1 問(wèn)題歸約描述 （Problem Reduction Description）,梵塔難題,2.2 問(wèn)題規(guī)約法,思考：用狀態(tài)空間法有多少個(gè)節(jié)點(diǎn)？為什么？,20,解題過(guò)程,將原始問(wèn)題歸約為一個(gè)較簡(jiǎn)單問(wèn)題集合 將原始梵塔難題歸約（簡(jiǎn)化）為下列子難題 移動(dòng)圓盤(pán)A和B至柱子2的雙圓盤(pán)難題 移動(dòng)圓盤(pán)C至柱子3的單圓盤(pán)難題 移動(dòng)圓盤(pán)A和B至柱子3的雙圓盤(pán)難題 詳細(xì)過(guò)程參看下圖,21,解題過(guò)程（3個(gè)圓盤(pán)問(wèn)題）,2.2 問(wèn)題規(guī)

11、約法,22,梵塔問(wèn)題歸約圖,2.2 問(wèn)題規(guī)約法,23,多圓盤(pán)梵塔難題思考？,2.2 問(wèn)題規(guī)約法,24,問(wèn)題歸約的描述,問(wèn)題歸約方法應(yīng)用算符把問(wèn)題描述轉(zhuǎn)化為子問(wèn)題描述，可以采用各種數(shù)據(jù)結(jié)構(gòu)：表列、樹(shù)、字符串、矢量、數(shù)組等； 例如梵塔問(wèn)題的表示：包含兩個(gè)數(shù)列的表列：(113),(333) 也可以用狀態(tài)空間表示法的三元組（S，F(xiàn)，G）表示；其子問(wèn)題描述規(guī)定了最后解答路徑將要通過(guò)的中間狀態(tài)； 可以把問(wèn)題歸約發(fā)看成比狀態(tài)空間法更通用的問(wèn)題求解方法；其核心實(shí)現(xiàn)是不斷簡(jiǎn)化問(wèn)題，直至問(wèn)題成為本原問(wèn)題（已知問(wèn)題、易解問(wèn)題）；,2.2 問(wèn)題規(guī)約法,25,2.2.2與或圖表示,1.與圖、或圖、與或圖 一般，我們用一

12、個(gè)似圖結(jié)構(gòu)來(lái)表示把問(wèn)題歸約為后繼問(wèn)題的替換集合，這一似圖結(jié)構(gòu)叫做問(wèn)題歸約圖，或叫與或圖。如下所示,2.2 問(wèn)題規(guī)約法,26,2.2 問(wèn)題規(guī)約法,與或圖,增加附加節(jié)點(diǎn)后的規(guī)范化與或圖表示：,27,2.一些關(guān)于與或圖的術(shù)語(yǔ),2.2 問(wèn)題規(guī)約法,28,一些關(guān)于與或圖的術(shù)語(yǔ),父節(jié)點(diǎn)、子（后繼）節(jié)點(diǎn)、弧線(xiàn) 起始節(jié)點(diǎn) 終葉節(jié)點(diǎn)：對(duì)應(yīng)于原問(wèn)題的本原節(jié)點(diǎn) 或節(jié)點(diǎn)：只要解決某個(gè)問(wèn)題就可解決其父輩問(wèn)題的節(jié)點(diǎn)集合，如（M，N，H）。 與節(jié)點(diǎn)：只有解決所有子問(wèn)題，才能解決其父輩問(wèn)題的節(jié)點(diǎn)集合，如（B，C）和（D，E，F(xiàn)）。各個(gè)節(jié)點(diǎn)之間用一端小圓弧連接標(biāo)記。 與或圖：由與節(jié)點(diǎn)及或節(jié)點(diǎn)組成的結(jié)構(gòu)圖。,2.2 問(wèn)題規(guī)約法,

13、29,3.定義,可解節(jié)點(diǎn)的一般定義： 終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)(因?yàn)樗鼈兣c本原問(wèn)題相關(guān)連)。： 如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只要當(dāng)其后繼節(jié)點(diǎn)至少有一個(gè)是可解的時(shí)，此非終葉節(jié)點(diǎn)才是可解的。 如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼節(jié)點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)才是可解的。,2.2 問(wèn)題規(guī)約法,30,不可解節(jié)點(diǎn)的一般定義： 沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。 全部后裔為不可解的非終葉節(jié)點(diǎn)且含有或后繼節(jié)點(diǎn)，此非終葉節(jié)點(diǎn)才是不可解的。 后裔至少有一個(gè)為不可解的非終葉節(jié)點(diǎn)且含有與后繼節(jié)點(diǎn)，此非終葉節(jié)點(diǎn)才是不可解的。,2.2 問(wèn)題規(guī)約法,31,如圖所示,2.2 問(wèn)題規(guī)約法,與或圖例子,t,t

14、,t,t,t,t,t,t,t,（a）,（b）,有解節(jié)點(diǎn),無(wú)解節(jié)點(diǎn),終葉節(jié)點(diǎn),32,與或圖構(gòu)成規(guī)則,（1）與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問(wèn)題或問(wèn)題集合。起始節(jié)點(diǎn)對(duì)應(yīng)于原始問(wèn)題。 （2）對(duì)應(yīng)于本原問(wèn)題的節(jié)點(diǎn)，叫做終葉節(jié)點(diǎn) （3）對(duì)于把算符應(yīng)用于問(wèn)題A的每種可能情況，都把問(wèn)題變換為一個(gè)子問(wèn)題集合；有向弧線(xiàn)自A指向后繼節(jié)點(diǎn)，表示所求得的子問(wèn)題集合，只要其中任意一個(gè)有解，問(wèn)題A就可解，所有這些子問(wèn)題節(jié)點(diǎn)稱(chēng)為或節(jié)點(diǎn)； （4）一般對(duì)于代表兩個(gè)或兩個(gè)以上子問(wèn)題集合的每個(gè)節(jié)點(diǎn)，有向弧線(xiàn)從此節(jié)點(diǎn)指向此子問(wèn)題集合中的各個(gè)節(jié)點(diǎn),只有所有子問(wèn)題都有解，這個(gè)子問(wèn)題的集合才有解，所有這些子問(wèn)題節(jié)點(diǎn)叫做與節(jié)點(diǎn)。這些具

15、有共同父節(jié)點(diǎn)的與節(jié)點(diǎn)用小圓弧連接，以表示與或節(jié)點(diǎn)的區(qū)別； （5）在特殊情況下，當(dāng)只有一個(gè)算符可應(yīng)用于問(wèn)題A，而且這個(gè)算符產(chǎn)生具有一個(gè)以上子問(wèn)題的某個(gè)集合時(shí)，由上述規(guī)則3和規(guī)則4所產(chǎn)生的圖可以得到簡(jiǎn)化。（即不增加附加節(jié)點(diǎn)的情況下）,2.2 問(wèn)題規(guī)約法,33,梵塔問(wèn)題歸約圖,（322） （333）,2.2 問(wèn)題規(guī)約法,數(shù)據(jù)結(jié)構(gòu)介紹,思考題：四圓盤(pán)問(wèn)題,34,2.3 謂詞邏輯法(Predicate Logic),邏輯語(yǔ)句：一種形式語(yǔ)言，它能夠把邏輯論證符號(hào)化，并用于證明定理，求解問(wèn)題。 形式語(yǔ)言：嚴(yán)格地按照相關(guān)領(lǐng)域的特定規(guī)則，以數(shù)學(xué)符號(hào)（符號(hào)串）形式描述該領(lǐng)域有關(guān)客體的表達(dá)式,2.3.1 謂詞演算

16、語(yǔ)法與語(yǔ)義 基本符號(hào)：謂詞符號(hào)、變量符號(hào)、函數(shù)符號(hào)、 常量符號(hào)、括號(hào)和逗號(hào) 謂詞演算的解釋?zhuān)?謂詞符號(hào)對(duì)應(yīng)關(guān)系， 常量符號(hào)論域?qū)嶓w， 函數(shù)符號(hào)對(duì)應(yīng)函數(shù)；,35,原子公式：由若干謂詞符號(hào)和項(xiàng)組成的謂詞演算。原子公式是謂詞演算基本積木塊。項(xiàng)包括常量符號(hào)、變量符號(hào)、函數(shù)符號(hào)等。定義原子公式為真值或假值就表示了某種語(yǔ)義。 無(wú)變量的原子公式取值確定，包含變量的原子公式取值不定。 例如： INROOM（ROBOT，r1） 為真 INROOM（ROBOT，r2）為假 MARRIEDfather(wang),mother(wang),2.3 謂詞邏輯法,36,連詞和量詞(Connective ES2 = Px

17、,f(A),B; ES3 = Pq(z),f(A),B; ES4 = Pc,f(A),B; ES1S2 = Pz,f(w),B; ES2S1 = Pz,f(A),B 思考： (1) ES4S1，ES3S2？ (2) 置換的運(yùn)算規(guī)則？,2.3 謂詞邏輯法,45,置換的性質(zhì) 可結(jié)合律: （LS1）S2 = L（S1S2） （S1S2）S3 = S1（S2S3） 問(wèn)題：請(qǐng)舉例說(shuō)明？ 不可交換律: S1S2 = S2S1 問(wèn)題：請(qǐng)舉例說(shuō)明？ 思考：什么置換是謂詞邏輯推理所需要的？,2.3 謂詞邏輯法,/,46,合一（Unification)： 合一：尋找項(xiàng)對(duì)變量的置換，以使多個(gè)表達(dá)式一致的操作稱(chēng)為合一

18、。如果一個(gè)置換s作用于表達(dá)式集Ei的每個(gè)元素，則我們用Ei s來(lái)表示置換例的集。 可合一：如果存在置換s使得表達(dá)式集Ei置換后有：E1S E2S E3S,則我們稱(chēng)表達(dá)式集Ei是可合一的， s 稱(chēng)為Ei 的合一者。 例題：表達(dá)式集 Px,f(y),B, Px,f(B),B 的合一者： s A/x,B/y 說(shuō)明： Px,f(y),Bs Px,f(B),Bs PA,f(B),B 思考：還有其他合一者嗎？,2.3 謂詞邏輯法,47,最通用的合一者：如果對(duì)表達(dá)式集Ei的任一合一者s，都存在某一s，使得Eis Eigs，則稱(chēng)g為Ei的最通用合一者。 問(wèn)題：上例題中，最通用的合一者是什么？ 置換與合一的作用

19、：謂詞邏輯推理的基本方法，就是尋找簡(jiǎn)單有效置換合一，采用消解原理利用消解反演方法求解問(wèn)題，詳見(jiàn)第三章。,2.3 謂詞邏輯法,48,2.4 語(yǔ)義網(wǎng)絡(luò)法 (Semantic Network Representation),語(yǔ)義網(wǎng)絡(luò)的結(jié)構(gòu) 定義 語(yǔ)義網(wǎng)絡(luò)是知識(shí)的一種圖解表示，它由節(jié)點(diǎn)和弧線(xiàn)或鏈線(xiàn)組成。節(jié)點(diǎn)用于表示實(shí)體、概念和情況等，弧線(xiàn)用于表示節(jié)點(diǎn)間的關(guān)系。 組成部分 詞法 決定表示詞匯表中允許有哪些符號(hào)，它涉及各個(gè)節(jié)點(diǎn)和弧線(xiàn)。 結(jié)構(gòu) 敘述符號(hào)排列的約束條件，指定各弧線(xiàn)連接的節(jié)點(diǎn)對(duì) 過(guò)程 說(shuō)明訪(fǎng)問(wèn)過(guò)程，這些過(guò)程能用來(lái)建立和修正描述，以及回答相關(guān)問(wèn)題。 語(yǔ)義 確定與描述相關(guān)的(聯(lián)想)意義的方法即確定有

20、關(guān)節(jié)點(diǎn)的排列及其占有物和對(duì)應(yīng)弧線(xiàn)。,49,語(yǔ)義網(wǎng)絡(luò)的特點(diǎn): (1) 能把實(shí)體的結(jié)構(gòu)、屬性與實(shí)體間的因果關(guān)系顯式并簡(jiǎn)明地表達(dá)出來(lái) , 與實(shí)體相關(guān)的事實(shí)、特征和關(guān)系可以通過(guò)相應(yīng)的節(jié)點(diǎn)弧線(xiàn)推導(dǎo)出來(lái)。這樣便以聯(lián)想方式實(shí)現(xiàn)對(duì)系統(tǒng) 的解釋。 (2) 由于與概念相關(guān)的屬性和聯(lián)系被組織在一個(gè)相應(yīng)的節(jié)點(diǎn)中 , 因而使概念易于受訪(fǎng)和學(xué)習(xí)。 (3 ）表現(xiàn)問(wèn)題更加直觀 , 更易于理解 , 適于知識(shí)工程師與領(lǐng)域?qū)＜业臏贤?。語(yǔ)義網(wǎng)絡(luò)中的繼承方式也符合人類(lèi)的思維習(xí)慣。 (4) 語(yǔ)義網(wǎng)絡(luò)結(jié)構(gòu)的語(yǔ)義解釋依賴(lài)于該結(jié)構(gòu)的推理過(guò)程而沒(méi)有結(jié)構(gòu)的約定 , 因而得到的推理不能保證像謂詞邏輯法那樣有效。 (5 ）節(jié)點(diǎn)間的聯(lián)系可能是線(xiàn)狀、樹(shù)狀

21、或網(wǎng)狀的 , 甚至是遞歸狀的結(jié)構(gòu) , 使相應(yīng)的知識(shí)存儲(chǔ)和檢索可能需要比較復(fù)雜的過(guò)程。,2.4 語(yǔ)義網(wǎng)絡(luò)法,50,表示一些簡(jiǎn)單事實(shí)，如占有關(guān)系和其它情況：以節(jié)點(diǎn)表示實(shí)體與概念，節(jié)點(diǎn)間關(guān)系以有向鏈關(guān)聯(lián)。 例： 小燕是一只燕子，燕子是一種鳥(niǎo)，鳥(niǎo)有翅膀；巢-1是小燕的巢，巢-1是巢中的一個(gè)。 問(wèn)題： 上述的語(yǔ)義網(wǎng)絡(luò)為二元關(guān)系，無(wú)法表示復(fù)雜事實(shí)，如：小燕從春天到秋天占有巢1。 如果采用謂詞邏輯表示為一個(gè)四元謂詞演算： Owns（XIAOYAN,NET-1,SPRING,FALL） 思考：用語(yǔ)義網(wǎng)絡(luò)如何表示上述四元謂詞公式？,2.4 語(yǔ)義網(wǎng)絡(luò)法,2.4. 1 二元語(yǔ)義網(wǎng)絡(luò)的表示,SWALLOW,BIRD,

22、XIAOYAN,NEST-1,NEST,ISA,ISA,ISA,OWNS,HAS-PART,WINGS,51,Simmons與Slocum擴(kuò)展了該基本方法： 允許節(jié)點(diǎn)既可以表示一個(gè)物體或一組物體，也可以表示情況與動(dòng)作。每一情況節(jié)點(diǎn)成為事例框，有一組向外的弧，用以說(shuō)明與該事例有關(guān)的各種變量。,2.4 語(yǔ)義網(wǎng)絡(luò)法,SWALLOW,BIRD,XIAOYAN,NEST-1,NEST,ISA,ISA,ISA,OWNEE,OWN-1,OWNER,SPRING,FALL,SITUATION,TIME,OWNERSHIP,ISA,ISA,ISA,ISA,STARTTIME,ENDTIME,52,選擇語(yǔ)義基元：

23、 問(wèn)題：如果語(yǔ)義網(wǎng)絡(luò)只表示一個(gè)特定的物體或概念，那么當(dāng)有更多不直接相關(guān)的同類(lèi)實(shí)體與概念時(shí)，需要很多獨(dú)立的語(yǔ)義網(wǎng)絡(luò)，使得語(yǔ)義網(wǎng)絡(luò)圖復(fù)雜化。 Solution：通常需要把有關(guān)的一組物體或概念的知識(shí)用一個(gè)語(yǔ)義網(wǎng)絡(luò)表示出來(lái)，否則會(huì)造成網(wǎng)絡(luò)過(guò)多，使問(wèn)題復(fù)雜化。試圖用一組基元來(lái)表示知識(shí)，以便簡(jiǎn)化表示，并可用簡(jiǎn)單的知識(shí)來(lái)表示更復(fù)雜的知識(shí)，稱(chēng)為選擇語(yǔ)義基元。,2.4 語(yǔ)義網(wǎng)絡(luò)法,RED,MYCAR,COLOR,GREEN,LIHUACAR,COLOR,53,2.4 語(yǔ)義網(wǎng)絡(luò)法,RED,MYCAR,COLOR,GREEN,LIHUACAR,COLOR,CAR,ISA,ISA,概念節(jié)點(diǎn)與實(shí)例節(jié)點(diǎn),FURNITUR

24、E,CHAIR,MYCAR,LEATHER,SEAT,BROWN,PERSON,X,ISA,OWNER,ISA,ISA,ISA PART,COLOR,COVERING,椅子的語(yǔ)義網(wǎng)絡(luò),54,2.4.2 多元語(yǔ)義網(wǎng)絡(luò)的表示,謂詞邏輯與語(yǔ)義網(wǎng)絡(luò)等效,容易實(shí)現(xiàn)一元關(guān)系與二元關(guān)系表示。,LIMING,MAN,ISA,ISA（LIMING，MAN）或 MAN（LIMING）,（語(yǔ)義網(wǎng)絡(luò)）,（謂詞邏輯）,2.4 語(yǔ)義網(wǎng)絡(luò)法,55,多元語(yǔ)義網(wǎng)絡(luò)表示的實(shí)質(zhì) 把多元關(guān)系轉(zhuǎn)化為一組二元關(guān)系的組合，或二元關(guān)系的合取。,R(X1，X2，Xn),R12(X1，X2)R13(X1，X3) R1n(X1，Xn) . Rn-

25、1 n(Xn-1，Xn),可轉(zhuǎn)換為,2.4 語(yǔ)義網(wǎng)絡(luò)法,56,多元語(yǔ)義網(wǎng)絡(luò)的表示實(shí)例1,SCORE(BU,TU,(8589),2.4 語(yǔ)義網(wǎng)絡(luò)法,GAME,G25,BU,85-89,TU,VISITING TEAM,ISA,HOME TEAM,SCORE,57,三元變?yōu)槎M合,2.4 語(yǔ)義網(wǎng)絡(luò)法,例 John gave Mary the book.,（2）用語(yǔ)義網(wǎng)絡(luò)法表示時(shí)引入附加節(jié)點(diǎn)G1：,G1,B23,JOHN,GIVER,OBJECT,MARY,GIVE,ISA,RECIPIENT,BOOK,ISA,多元語(yǔ)義網(wǎng)絡(luò)的表示實(shí)例2,58,2.4.3 語(yǔ)義網(wǎng)絡(luò)的推理過(guò)程,語(yǔ)義網(wǎng)絡(luò)表示知識(shí)，沒(méi)有

26、形式語(yǔ)義，沒(méi)有統(tǒng)一的語(yǔ)義表示法。 為了便于下面的敘述 , 對(duì)所用符號(hào)作進(jìn)一步的規(guī)定。區(qū)分在鏈的頭部和在鏈的尾部的節(jié)點(diǎn) , 把在鏈的尾部的節(jié)點(diǎn)稱(chēng)為值節(jié)點(diǎn)。另外 , 還規(guī)定節(jié)點(diǎn)的槽相當(dāng)于鏈 , 不過(guò)取不同的名字而已。如磚塊12(BRICK12)有3個(gè)鏈,構(gòu)成兩個(gè)槽。其中一個(gè)槽只有一個(gè)值,另外一個(gè)槽有兩個(gè)值。顏色槽(COLOR)填入紅色(RED) ISA槽填入了磚塊 (BRICK)和玩具(TOY) 。,2.4 語(yǔ)義網(wǎng)絡(luò)法,59,繼承推理 定義：所謂繼承就是對(duì)事物的描述從概念節(jié)點(diǎn)或類(lèi)節(jié)點(diǎn)傳遞到實(shí)例節(jié)點(diǎn)，例如下圖。,2.4 語(yǔ)義網(wǎng)絡(luò)法,60,三種繼承模式 值繼承：ISA鏈與 AKO（A Kind Of）

27、鏈，常用知識(shí)傳遞方法；放入值側(cè)面中。 “如果需要”（Ifneeded）鏈：有時(shí)對(duì)不知道的槽值，可以計(jì)算得到，通過(guò)此計(jì)算程序得到知識(shí)的模式稱(chēng)為ifneeded鏈，如通過(guò)體積與密度在需要時(shí)可以計(jì)算其質(zhì)量。 ifneeded程序放入IFNEEDED側(cè)面中。 “缺省”繼承：在對(duì)事務(wù)所作假設(shè)無(wú)十分把握時(shí)，可以加上“可能”字樣，這種不肯定的值稱(chēng)為“缺省”值，放入槽的DEFAULT側(cè)面中。,2.4 語(yǔ)義網(wǎng)絡(luò)法,61,匹配推理 當(dāng)解決涉及由幾部分組成的事物時(shí) ,必須制定把值從類(lèi)部件傳遞到實(shí)例部件的路徑，稱(chēng)為匹配推理。 例如, 由于 TOY-HOUSE77 是 TOY-HOUSE 的一個(gè)實(shí)例 , 所以它必須有兩

28、個(gè)部件 , 一個(gè)是磚塊 , 另一個(gè)是模塊 (wedge) 。另外 , 作為玩具房的一個(gè)部件的磚塊必須 支撐模塊。在圖 2.19 中 , 玩具房 -77 部件以及它們之間的鏈 , 都用虛線(xiàn)畫(huà)的節(jié)點(diǎn)和箭頭 來(lái)表示。因?yàn)檫@些知識(shí)是通過(guò)繼承而間接知道的 , 并不是通過(guò)實(shí)際的節(jié)點(diǎn)和鏈直接知道 的。因此 , 虛線(xiàn)所表示的節(jié)點(diǎn)以及箭頭所表示的鏈?zhǔn)翘摴?jié)點(diǎn)和虛鏈。,2.4 語(yǔ)義網(wǎng)絡(luò)法,62,現(xiàn)在來(lái)研究圖 2.20中的結(jié)構(gòu) 35(STRUCTURE35)。已知這個(gè)結(jié)構(gòu)有兩個(gè)部件,一 個(gè)磚塊BRICK12和一個(gè)楔塊WEDGE18。一旦在STRUCTURE35和TOY-HOUSE之間放上ISA鏈,就知道BRICK12

29、必須支撐WEDGE18。在圖2.20中用虛線(xiàn)箭頭表示BRICK12和WEDGE18 之間的SUPPORT虛鏈。因?yàn)楹苋菀鬃霾考ヅ?所以虛線(xiàn)箭頭的位置和方向很容易被確定。WEDGE18肯定與作為T(mén)OY-HOUSE的一個(gè)部件的楔塊相匹配,而 BRICK12 肯定與磚塊相匹配。,2.4 語(yǔ)義網(wǎng)絡(luò)法,63,2.5 框架（Frame）表示,提問(wèn)：語(yǔ)義網(wǎng)絡(luò)中個(gè)案知識(shí)與通用知識(shí)的關(guān)系問(wèn)題？ Solution：用通用框架存儲(chǔ)類(lèi)似的個(gè)案知識(shí)。 框架：框架是一種結(jié)構(gòu)化表示法，通常采用語(yǔ)義網(wǎng)絡(luò)中的節(jié)點(diǎn)-槽-值表示結(jié)構(gòu)，以通用數(shù)據(jù)結(jié)構(gòu)的形式存儲(chǔ)以往的經(jīng)驗(yàn)知識(shí)。 框架與語(yǔ)義網(wǎng)絡(luò)的關(guān)系： 框架可以定義為一組語(yǔ)義網(wǎng)絡(luò)的節(jié)

30、點(diǎn)與槽，這組節(jié)點(diǎn)與槽可以描述格式固定的事務(wù)、行為和事件； 語(yǔ)義網(wǎng)絡(luò)是節(jié)點(diǎn)和弧線(xiàn)的集合，也可以看作框架的集合。 思考：框架與語(yǔ)義網(wǎng)絡(luò)的區(qū)別？,64,2.5.1 框架的構(gòu)成,框架通常由描述事務(wù)的各個(gè)方面的槽組成，每個(gè)槽可以擁有若干個(gè)側(cè)面，而每個(gè)側(cè)面可以擁有若干個(gè)值。 框架的一般結(jié)構(gòu)： ,2.5 框架表示法,65,一個(gè)簡(jiǎn)單框架的例子 對(duì)于復(fù)雜的問(wèn)題，必須同時(shí)使用許多框架，構(gòu)成框架系統(tǒng)，例如： 思考：框架與框架的關(guān)系？,2.5 框架表示法,66,框架的關(guān)系：一個(gè)框架可以是另一個(gè)框架的槽值，并且一個(gè)框架結(jié)構(gòu)可以作為幾個(gè)不同框架的槽值。這樣相同的信息不必重復(fù)存儲(chǔ)，節(jié)約空間。,2.5 框架表示法,67,框架

31、系統(tǒng)的繼承關(guān)系與樹(shù)型結(jié)構(gòu) 框架的一個(gè)重要屬性是繼承。為此，框架常表示成一種樹(shù)型結(jié)構(gòu)，樹(shù)的每一節(jié)點(diǎn)就是一個(gè)框架結(jié)構(gòu)，子節(jié)點(diǎn)與父節(jié)點(diǎn)之間用ISA或AKO槽連接。 框架的繼承方法：當(dāng)子節(jié)點(diǎn)的某些槽值或側(cè)面沒(méi)有被直接記錄時(shí)，可以從其父節(jié)點(diǎn)繼承這些值。 樹(shù)狀框架系統(tǒng)的形式： AKO/ISA VALUE PROP DEFAULT SF IF-NEEDED CONFLICT ADD,2.5 框架表示法,68,框架系統(tǒng)的基本推理方法 特性繼承（ISA/AKO鏈），例如：燕子鳥(niǎo) 部分匹配，例如TOYHOUSE 從描述中直接引用，例如：ROOM的例子 各槽值的相關(guān)信息可以指導(dǎo)進(jìn)行該槽值的描述，如：圖2.22的D面

32、 解答子節(jié)點(diǎn)與父節(jié)點(diǎn)差異的原因，例如：三條腿的椅子 思考：框架是一種規(guī)定格式描述的事務(wù)、行為與事件。那么對(duì)于具體的應(yīng)用，當(dāng)直接套用框架知識(shí)推理不順利時(shí)，框架推理的策略？,2.5.1 框架的推理,2.5 框架表示法,69,推理框架的選擇方法： 選擇與當(dāng)前情況對(duì)應(yīng)的框架片斷，與其他候選框架相匹配，選擇最佳匹配；（知識(shí)的合成、交叉） 允許部分不相匹配的信息，如漏失某項(xiàng)特性比多了某項(xiàng)特性更合理，比如只有一條腿的人比有三條腿的人更合理；（合理推斷） 查詢(xún)框架之間保存有關(guān)的連接，指出應(yīng)用此框架不合理的情況下，可以下一步試探的建議框架；如下圖： （啟發(fā)匹配） 沿著框架系統(tǒng)的層次向上搜索，知道找到足夠通用、與

33、事實(shí)不矛盾的框架，或直接使用，或者建立新的下一層框架。（類(lèi)型匹配與新類(lèi)生成）,2.5 框架表示法,70,2.6 劇本（Script）表示,提問(wèn)：框架中對(duì)事件的描述有什么不足？ 定義：劇本是框架的特殊形式，它用一組槽值描述事件發(fā)生的序列。 劇本的構(gòu)成： （1）開(kāi)場(chǎng)條件 （事件發(fā)生的前提條件） （2）角色 （有關(guān)人物的槽值） （3）道具 （有關(guān)物體的槽值） （4）場(chǎng)景 （事件的順序，場(chǎng)景可以是其他劇本） （5）結(jié)果 （事件發(fā)生后的結(jié)果）,71,劇本的例子 (1) 開(kāi)場(chǎng)條件 (a) 顧客餓了 , 需要進(jìn)餐。 (b) 顧客有足夠的錢(qián)。 (2) 角色 顧客 , 服務(wù)員 , 廚師 , 老板。 (3) 道具 食品 , 桌子 , 菜單 , 錢(qián)。 (4) 場(chǎng)景 場(chǎng)景 l 進(jìn)入餐廳 (a) 顧客走入餐廳 (b) 尋找桌子 (c) 在桌子旁坐下。