第二章知識表示方法

人工智能第二章：知識表示方法知識的概念知識的一般概念：知識是人們在改造客觀世界的實(shí)踐中積累起來的認(rèn)識和經(jīng)驗(yàn)認(rèn)識：包括對事物現(xiàn)象、本質(zhì)、屬性、狀態(tài)、聯(lián)系等的認(rèn)識經(jīng)驗(yàn)：包括解決問題的微觀方法和宏觀方法微觀方法：如步驟、操作、規(guī)則、過程、技巧等宏觀方法：如戰(zhàn)略、戰(zhàn)術(shù)、計謀、策略等

eg：“if

大雁向南飛，then

冬天就要來臨了?！边@樣一條知識就是人們經(jīng)過長期的觀察，將“大雁向南飛”與“冬天來臨”這兩條信息關(guān)聯(lián)在一起。“雪是白色的”反映雪與顏色的一種關(guān)系。知識表示知識表示：是研究用機(jī)器表示知識的可行性、有效性的一般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體，既考慮知識的存儲又考慮知識的使用。以知識和符號操作為基礎(chǔ)的智能系統(tǒng)，其問題的求解都需要某種對解答的搜索。在搜索過程開始之前，必須先將問題表示出來。表示問題的方法，可能涉及狀態(tài)空間、問題歸約、語義網(wǎng)絡(luò)、框架或謂詞公式，或者把問題表示為一條要證明的定理，或者采用結(jié)構(gòu)化方法等。對于傳統(tǒng)人工智能問題，任何復(fù)雜的求解技術(shù)都離不開兩方面的內(nèi)容：1.表示2.搜索

本章內(nèi)容2.1狀態(tài)空間表示2.2問題歸約表示2.3謂詞邏輯表示2.4語義網(wǎng)絡(luò)表示2.5框架表示2.6本體技術(shù)2.7過程表示2.1狀態(tài)空間表示狀態(tài)空間法（StateSpaceRepresentation）：

狀態(tài)空間法就是用來表示問題及其搜索過程的一種方法。它是人工智能中最基本的形式化方法，用“狀態(tài)（state）”和“算符（operator）”來表示問題。2.1狀態(tài)空間表示2.1.1問題狀態(tài)描述(1)狀態(tài)（state）：描述某類不同事物間的差別而引入的一組最少變量q0，q1，…，qn的有序集合，是表示問題解法中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)。有序集合中每個元素qi（i=0,1,...,n）為集合的分量，稱為狀態(tài)變量。給定每個分量的一組值就得到一個具體的狀態(tài)。

(2)算符（operator）：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。

(3)狀態(tài)空間方法：是一個表示該問題全部可能狀態(tài)及其關(guān)系的圖，它包含三種說明的集合，即三元狀態(tài)（S，F(xiàn)，G）。S：所有可能的問題初始狀態(tài)集合；F：操作符集合；G：目標(biāo)狀態(tài)集合。2.1狀態(tài)空間表示狀態(tài)空間法舉例：十五數(shù)碼難題(15puzzle)：由15個編有1至15并放在4×4方格棋盤上的可走動的棋子組成。119415131275861321014123456789101112131415初始棋局目標(biāo)棋局十五數(shù)碼難題119415131275861321014119151341275861321014119415131275861321014119415138127561321014119415131275861321014123456789101112131415初始狀態(tài)目標(biāo)狀態(tài)如何把初試棋局變成目標(biāo)棋局？首先把適用的算符用于初始狀態(tài)，以產(chǎn)生新的狀態(tài)再把另一些適用算符用于這些新的狀態(tài)；這樣繼續(xù)下去，直至產(chǎn)生目標(biāo)狀態(tài)為止2.1狀態(tài)空間表示2.1.2狀態(tài)圖示法狀態(tài)空間的圖示形式稱為狀態(tài)空間圖。狀態(tài)圖中有幾個術(shù)語。節(jié)點(diǎn)(Node)：圖形上的匯合點(diǎn)，用來表示狀態(tài)、事件和時間關(guān)系的匯合?；【€(Arc)：節(jié)點(diǎn)間的連接線，表示算符；有向圖(DirectedGraph)：一對節(jié)點(diǎn)用弧線連接起來，從一個節(jié)點(diǎn)指向另一個節(jié)點(diǎn)。后繼節(jié)點(diǎn)(Descendantnode)與父輩節(jié)點(diǎn)(Parentnode)：如果某條弧線從節(jié)點(diǎn)ni指向節(jié)點(diǎn)nj，那么節(jié)點(diǎn)nj就叫做節(jié)點(diǎn)ni的后繼節(jié)點(diǎn)或后裔，而節(jié)點(diǎn)ni叫做節(jié)點(diǎn)nj的父輩節(jié)點(diǎn)或祖先。2.1狀態(tài)空間表示路徑(Path)：某個節(jié)點(diǎn)序列(ni1,ni2,…,nik)當(dāng)j=2,3,…,k時，如果對于每一個ni,j-1都有一個后繼節(jié)點(diǎn)nij存在，那么就把這個節(jié)點(diǎn)序列叫做從節(jié)點(diǎn)ni1至節(jié)點(diǎn)nik的長度為k的路徑。代價(Cost)：用c(ni,nj)來表示從節(jié)點(diǎn)ni指向節(jié)點(diǎn)nj的那段弧線的代價。兩節(jié)點(diǎn)間路徑的代價等于連接該路徑上各節(jié)點(diǎn)的所有弧線代價之和。圖的顯示說明/隱示說明：指各節(jié)點(diǎn)及其具有代價的弧線可以/不可以由一張表明確給出。顯然，顯示說明對于大型的圖是不切實(shí)際的，而對于具有無限節(jié)點(diǎn)集合的圖則是不可能的。2.1狀態(tài)空間表示問題的表示對求解工作有很大影響。人們希望有較小的狀態(tài)空間表示。例如，對于十五數(shù)碼問題：可以規(guī)定15×4＝60條規(guī)則，即“上移棋子4，下移棋子4，左移棋子4，右移棋子4···”，如果用“上下左右移動空格”，則只需4條規(guī)則。所以，移動空格是一種較好的表示。各種問題都可用狀態(tài)空間加以表示，并用狀態(tài)空間搜索法來求解。2.2問題歸約表示問題歸約的概念問題歸約(problemreduction)是另一種基于狀態(tài)空間的問題描述與求解方法。已知問題的描述，通過一系列變換把此問題最終變?yōu)橐粋€子問題集合；這些子問題的解可以直接得到，從而解決了初始問題2.2問題歸約表示問題歸約表示的組成問題歸約表示可由下列3部分組成：

(1)一個初始問題描述；

(2)一套把問題變換為子問題的操作符；

(3)一套本原問題描述。2.2問題歸約表示問題歸約的方法從目標(biāo)（要解決的問題）出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。這就是問題歸約的實(shí)質(zhì)。2.2問題歸約表示2.2.1問題歸約描述

梵塔難題問題描述2.2問題歸約表示2.2問題歸約表示2.2問題歸約表示2.問題歸約描述問題歸約方法應(yīng)用算符來把問題描述變換為子問題描述。問題描述可以有各種數(shù)據(jù)結(jié)構(gòu)形式，表列、樹、字符串、矢量、數(shù)組和其他形式都曾被采用過。對于梵塔難題，其子問題可用一個包含兩個數(shù)列的表列來描述。于是，問題描述[（113），（333）]就意味著“把配置（113)變換為配置（333)”。2.2問題歸約表示可以用狀態(tài)空間表示的三元組合(S,F.G)來規(guī)定與描述問題。有關(guān)子問題可當(dāng)作狀態(tài)空間中兩個一定的“腳踏石”之間尋找路徑的問題來辨別。對于梵塔問題，子問題[(111)?(122)]，[(122)?(322)]以及[(322)?(333)]規(guī)定了最后解答路徑將要通過的腳踏石狀態(tài)（122）和（322）。問題歸約方法可以應(yīng)用狀態(tài)、算符和目標(biāo)這些表示法來描述問題，這并不意味著問題歸約法和狀態(tài)空間法是一樣的。2.2問題歸約表示2.2.2與或圖表示與或圖表示能夠方便地用一個類似于圖的結(jié)構(gòu)來表示把問題歸約為后繼問題的替換集合，畫出歸約問題圖。例如，設(shè)想問題A既可由求解問題B和C,也可由求解問題D,E和F，或者由單獨(dú)求解問題H來解決。2.2問題歸約表示2.2問題歸約表示終葉節(jié)點(diǎn)模擬問題歸約方法的相關(guān)結(jié)構(gòu)是一個與或圖。與或圖中的節(jié)點(diǎn)之一—起始節(jié)點(diǎn)對應(yīng)于原始問題描述，而對應(yīng)于本原問題的節(jié)點(diǎn)叫做終葉節(jié)點(diǎn)。2.2問題歸約表示在與或圖上執(zhí)行的搜索過程，其目的在于表明起始節(jié)點(diǎn)是有解的。與或圖中一個可解節(jié)點(diǎn)的一般定義可以歸納如下：(1)終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)。

(2)如果某個非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼節(jié)點(diǎn)至少有一個是可解的，此非終葉節(jié)點(diǎn)才是可解的。

(3)如果某個非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后繼節(jié)點(diǎn)全部為可解的，此非終葉節(jié)點(diǎn)才是可解的。2.2問題歸約表示與或圖的一些例子。圖中，終葉節(jié)點(diǎn)用字母t標(biāo)示，有解節(jié)點(diǎn)用小圓點(diǎn)表示，不可解節(jié)點(diǎn)用小圓圈表示。2.3謂詞邏輯表示命題邏輯的局限性雖然命題邏輯(propositionallogic)能夠把客觀世界的各種事實(shí)表示為邏輯命題，但是它具有較大的局限性，不適合于表示比較復(fù)雜的問題Eg:10是一個整數(shù)T；雪是黑色的F謂詞邏輯相對于命題邏輯的優(yōu)勢謂詞邏輯(predicatelogic)允許表達(dá)那些無法用命題邏輯表達(dá)的事情。Eg:RUNS（LIUHUA，F(xiàn)ASTEST）→WINS(LIUHUA，CHAMPION）2.3謂詞邏輯表示邏輯語句，邏輯語句，更具體地說，一階謂詞演算(firstorderpredicatecalculus)是一種形式語言，其根本目的在于把數(shù)學(xué)中的邏輯論證符號化。如果能夠采用數(shù)學(xué)演繹的方式證明一個新語句是從那些已知正確的語句導(dǎo)出的，那么也就能斷定這個新語句也是正確的。2.3謂詞邏輯表示2.3.1謂詞演算1.語法和語義謂詞邏輯的基本組成部分是謂詞符號、變量符號、函數(shù)符號和常量符號，并用圓括弧、方括弧、花括弧和逗號隔開，以表示論域內(nèi)的關(guān)系。例如，要表示“機(jī)器人(ROBOT)在1號房間(ROOM1)內(nèi)”，可應(yīng)用簡單的原子公式：

INROOM（ROBOT，r1）上式中，ROBOT和r1為常量符號INROOM為謂詞符號。

2.3謂詞邏輯表示例如，函數(shù)符號mother可用來表示某人與他（或她）的母親之間的一個映射。用下列原子公式表示“李（LI）的母親與他的父親結(jié)婚”這個關(guān)系：

MARRIED[father（LI），mother（LI）]2.3謂詞邏輯表示計算方法：

對于已定義了的某個解釋的一個原子公式，只有當(dāng)其對應(yīng)的語句在定義域內(nèi)為真時，才具有值T(真）；而當(dāng)其對應(yīng)的語句在定義域內(nèi)為假時，該原子公式才具有值F(假）。因此，INROOM(ROBOT,r1)具有值T.而INROOM(ROBOT,r2)則具有值F。當(dāng)一個原子公式含有變量符號時，對定義域內(nèi)實(shí)體的變量可能有幾個設(shè)定。對某幾個設(shè)定的變量，原子公式取值T;而對另外幾個設(shè)定的變量．原子公式則取值F。2.3謂詞邏輯表示2.連詞和量詞原子公式是謂詞演算的基本積木塊，應(yīng)用連詞∧（與）∨（或）以及?(蘊(yùn)涵或隱含)等（在某些文獻(xiàn)中，也用→來表示隱含關(guān)系），能夠組合多個原子公式以構(gòu)成比較復(fù)雜的合式公式。2.3謂詞邏輯表示連詞∧用來表示復(fù)合句子。例如，句子“我喜愛音樂和繪畫”可寫成：

LIKE（I，MUSIC）∧LIKE（I，PAINTING）此外，某些較簡單的句子也可寫成復(fù)合形式。例如．“李住在一幢黃色的房子里”即可用

LIVES（LI，HOUSE-1）∧COLOR（HOUSE-1，YELLOW）

用連詞∧把幾個公式連接起來而構(gòu)成的公式叫做合?。ㄊ剑?，而此合取式的每個組成部分叫做合取項(xiàng)。2.3謂詞邏輯表示連詞∨用來表示可兼有的“或”。例如，句子“李明打籃球或踢足球”可表示為：PLAYS（LIMING，BASKETBALL）∨PLAYS（LIMING，F(xiàn)OOTBALL）用連詞∨把幾個公式連接起來所構(gòu)成的公式叫做析?。ㄊ剑?，而此析取式的每一組成部分叫做析取項(xiàng)。由一些合式公式所構(gòu)成的任一析取也是一個合式公式。2.3謂詞邏輯表示連詞→用來表示“如果-那么”的詞句。例如，“如果該書是何平的，那么它是藍(lán)色（封面）的”可表示為：

OWNS（HEPING，BOOK-1）→COLOR（BOOK-1，BLUE）又如，“如果劉華跑得最快，那么他取得冠軍”可表示為：

RUNS（LIUHUA，F(xiàn)ASTEST）→WINS(LIUHUA，CHAMPION）用連詞→連接兩個公式所構(gòu)成的公式叫做蘊(yùn)涵。蘊(yùn)涵的左式叫做前項(xiàng)，右式叫做后項(xiàng)。2.3謂詞邏輯表示符號~（非）用來否定一個公式的真值，也就是說，把一個合式公式的取值從T變?yōu)镕,或從F變?yōu)門。如，子句“機(jī)器人不在2號房間內(nèi)”可表示為：～I(xiàn)NROOM（ROBOT，r2）前面具有符號~的公式叫做否定。2.3謂詞邏輯表示使公式中的命題帶有變量如果把句子限制為至今己介紹過的造句法所能表示的那些句子，而且也不使用變量項(xiàng)，那么可以把這個謂詞演算的子集叫做命題演算。命題演算對于許多簡化了的定義域來說，是一種有效的表示，但它缺乏用有效的方法來表達(dá)多個命題（如“所有的機(jī)器人都是灰色的”）的能力。要擴(kuò)大命題演算的能力，需要使公式中的命題帶有變量。2.3謂詞邏輯表示使公式中的命題帶有變量的例子一個原子公式如P（x),對于所有可能的變量x都具有值T。這個特性可由在P（x)前面加上全稱量詞（?x來表示。如果至少有一個x值可使P(x)具有值T，那么這一特性可由在P(x)前面加上存在量詞（?x)來表示。例如，句子“所有的機(jī)器人都是灰色的”可表示為（?x）［ROBOT（x）→COLOR（x，GRAY）]而句子“1號房間內(nèi)有個物體”可表示為（?x）INROOM（x，r1）這里，x是被量化了的變量，即x是經(jīng)過量化的。2.3謂詞邏輯表示2.3.2謂詞公式

1.謂詞公式的定義定義2.1用P（x1,x2,...,xn）表示一個n元謂詞公式，其中P為n元謂詞,x1,x2，…，xn為客體變量或變元。通常把P(x1,x2，…，xn）叫做謂詞演算的原子公式，或原子謂詞公式?？梢杂眠B詞把原子謂詞公式組成復(fù)合謂詞公式，并把它叫做分子謂詞公式。2.3謂詞邏輯表示用歸納法給出謂詞公式的定義。在謂詞演算中合式公式的遞歸定義如下：（1)原子謂詞公式是合式公式。

(2)若A為合式公式，則~A也是一個合式公式。

(3)若A和B都是合式公式，則(A∧B)，(A∨B)，(A→B）和(A←→B)也都是合式公式。

(4)若A是合式公式，x為A中的自由變元，則(?x)A和（?x）A都是合式公式。

(5)只有按上述規(guī)則(1)至（4）求得的那些公式，才是合式公式。2.3謂詞邏輯表示例:試把下列命題表示為謂詞公式：任何整數(shù)或者為正或者為負(fù)。解把上述命題意譯如下：對于所有的x，如果x是整數(shù)，則x或?yàn)檎幕蛘邽樨?fù)的。用I（x）表示“x是整數(shù)”，P（x）表示“x是正數(shù)”，N（x）表示"x是負(fù)數(shù)”。于是，可把給定命題用下列謂詞公式來表示：

(?x)（I（x）→（P（x）∨N（x）））2.3謂詞邏輯表示2.合式公式的性質(zhì)如果P和Q是兩個合式公式，則由這兩個合式公式所組成的復(fù)合表達(dá)式可由下列真值表給出。2.3謂詞邏輯表示等價關(guān)系：（1）否定之否定

~（~P）等價于P

（2)P∨Q等價于~P→Q(3)狄·摩根定律

~(P∨Q)等價于~P∧~Q~(P∧Q)等價于~P∨~Q

（4)分配律

P∧(Q∨R)等價于(P∧Q)∨(P∧R)P∨(Q∧R)等價于(P∨Q)∧(P∨R)2.3謂詞邏輯表示（5）交換律

P∧Q等價于Q∧PP∨Q等價于Q∨P

（6）結(jié)合律（P∧Q）∧R等價于P∧(Q∧R)

（P∨Q）∨R等價于P∨(Q∨R)

（7）逆否律

P→Q等價于~P→~Q2.3謂詞邏輯表示2.3.3置換與合一

1．置換一個表達(dá)式的項(xiàng)可為變量符號、常量符號或函數(shù)表達(dá)式。函數(shù)表達(dá)式由函數(shù)符號和項(xiàng)組成。一個表達(dá)式的置換就是在該表達(dá)式中用置換項(xiàng)置換變量。2.3謂詞邏輯表示置換實(shí)例2.3謂詞邏輯表示2.合一尋找項(xiàng)對變量的置換，以使兩表達(dá)式一致．叫做合一(unification)。合一是人工智能中很重要的過程。2.3謂詞邏輯表示2.4語義網(wǎng)絡(luò)表示

語義網(wǎng)絡(luò)語義網(wǎng)絡(luò)是知識的一種結(jié)構(gòu)化圖解表示．它由節(jié)點(diǎn)和弧線或鏈線組成。節(jié)點(diǎn)用于表示實(shí)體、概念和情況等，弧線用于表示節(jié)點(diǎn)間的關(guān)系。2.4語義網(wǎng)絡(luò)表示

語義網(wǎng)絡(luò)的組成：

(1)詞法部分決定詞匯表中允許有哪些符號，它涉及各個節(jié)點(diǎn)和弧線。

(2)結(jié)構(gòu)部分?jǐn)⑹龇柵帕械募s束條件，指定各弧線連接的節(jié)點(diǎn)對。

(3)過程部分說明訪問過程，這些過程能用來建立和修正描述，以及回答相關(guān)問題。

(4)語義部分確定與描述相關(guān)的（聯(lián)想）意義的方法，即確定有關(guān)節(jié)點(diǎn)的排列及其占有物和對應(yīng)弧線。2.4語義網(wǎng)絡(luò)表示

語義網(wǎng)絡(luò)的特點(diǎn)：

(1)能把實(shí)體的結(jié)構(gòu)、屬性與實(shí)體間的因果關(guān)系顯式和簡明地表達(dá)出來，與實(shí)體相關(guān)的事實(shí)、特征和關(guān)系可以通過相應(yīng)的節(jié)點(diǎn)弧線推導(dǎo)出來。這樣便于以聯(lián)想方式實(shí)現(xiàn)對系統(tǒng)的解釋。

(2)由于與概念相關(guān)的屬性和聯(lián)系被組織在一個相應(yīng)的節(jié)點(diǎn)中，因而使概念易于受訪和學(xué)習(xí)。

(3)表現(xiàn)問題更加直觀，更易于理解，適于知識工程師與領(lǐng)域?qū)＜覝贤?。語義網(wǎng)絡(luò)中的繼承方式也符合人類的思維習(xí)慣。

(4)語義網(wǎng)絡(luò)結(jié)構(gòu)的語義解釋依賴于該結(jié)構(gòu)的推理過程而沒有結(jié)構(gòu)的約定，因而得到的推理不能保證像謂詞邏輯法那樣有效。

(5)節(jié)點(diǎn)間的聯(lián)系可能是線狀、樹狀或網(wǎng)狀的，甚至是遞歸狀的結(jié)構(gòu)，使相應(yīng)的知識存儲和檢索可能需要比較復(fù)雜的過程。

2.4語義網(wǎng)絡(luò)表示

2.4.1二元語義網(wǎng)絡(luò)的表示

首先用語義網(wǎng)絡(luò)來表示一些簡單的事實(shí)。例如，所有的燕子（swallow）都是鳥(bird)小燕(xiaoyan)是一只燕子。用語義網(wǎng)絡(luò)表示鳥有翅膀2.4語義網(wǎng)絡(luò)表示

2.4語義網(wǎng)絡(luò)表示

Eg1:表示小燕有一個巢(nest)2.4語義網(wǎng)絡(luò)表示

Eg2:小燕從春天到秋天占有一個巢的信息加到語義網(wǎng)絡(luò)中。使用現(xiàn)有的語義網(wǎng)絡(luò)不能實(shí)現(xiàn)這一點(diǎn)。因?yàn)檎加嘘P(guān)系在語義網(wǎng)絡(luò)中表示為一根鏈，它只能表示二元關(guān)系。如果用謂詞運(yùn)算來表示所討論的例子，則要用一個四元的謂詞演算?，F(xiàn)在所需要的是一個和這樣的四元謂詞演算等價的，能夠表示占有關(guān)系的起始時間、終止時間、占有者和所有物的語義網(wǎng)絡(luò)2.4語義網(wǎng)絡(luò)表示

由西蒙斯（Simmons）和斯洛克姆（Slocum）提出來的方法允許節(jié)點(diǎn)既可以表示一個物體或一組物體，也可以表示情況和動作。每一情況節(jié)點(diǎn)可以有一組向外的?。ㄊ吕。?，稱為事例框，用以說明與該事例有關(guān)的各種變量。2.4語義網(wǎng)絡(luò)表示

2.4語義網(wǎng)絡(luò)表示

語義網(wǎng)絡(luò)結(jié)點(diǎn)的選擇在選擇節(jié)點(diǎn)時，首先要弄清節(jié)點(diǎn)是用于表示基本的物體或概念的，或是用于多種自的的。否則，如果語義網(wǎng)絡(luò)只用來表示一個特定的物體或概念，那么當(dāng)有更多的實(shí)例時就需要更多的語義網(wǎng)絡(luò)，這樣就使問題復(fù)雜化。2.4語義網(wǎng)絡(luò)表示

2.4語義網(wǎng)絡(luò)表示

通常把有關(guān)一個物體或概念，或一組有關(guān)的物體或概念的知識用一個語義網(wǎng)絡(luò)來表示。不然的話，會造成過多的網(wǎng)絡(luò)，使間題復(fù)雜化。與此相關(guān)的是尋找基本概念和某些基本弧