第二章知識表示方法

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

eg：“if

大雁向南飛，then

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

本章內容2.1狀態(tài)空間表示2.2問題歸約表示2.3謂詞邏輯表示2.4語義網(wǎng)絡表示2.5框架表示2.6本體技術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ù)結構。有序集合中每個元素qi（i=0,1,...,n）為集合的分量，稱為狀態(tài)變量。給定每個分量的一組值就得到一個具體的狀態(tài)。

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

(3)狀態(tài)空間方法：是一個表示該問題全部可能狀態(tài)及其關系的圖，它包含三種說明的集合，即三元狀態(tài)（S，F(xiàn)，G）。S：所有可能的問題初始狀態(tài)集合；F：操作符集合；G：目標狀態(tài)集合。2.1狀態(tài)空間表示狀態(tài)空間法舉例：十五數(shù)碼難題(15puzzle)：由15個編有1至15并放在4×4方格棋盤上的可走動的棋子組成。119415131275861321014123456789101112131415初始棋局目標棋局十五數(shù)碼難題119415131275861321014119151341275861321014119415131275861321014119415138127561321014119415131275861321014123456789101112131415初始狀態(tài)目標狀態(tài)如何把初試棋局變成目標棋局？首先把適用的算符用于初始狀態(tài)，以產生新的狀態(tài)再把另一些適用算符用于這些新的狀態(tài)；這樣繼續(xù)下去，直至產生目標狀態(tài)為止2.1狀態(tài)空間表示2.1.2狀態(tài)圖示法狀態(tài)空間的圖示形式稱為狀態(tài)空間圖。狀態(tài)圖中有幾個術語。節(jié)點(Node)：圖形上的匯合點，用來表示狀態(tài)、事件和時間關系的匯合。弧線(Arc)：節(jié)點間的連接線，表示算符；有向圖(DirectedGraph)：一對節(jié)點用弧線連接起來，從一個節(jié)點指向另一個節(jié)點。后繼節(jié)點(Descendantnode)與父輩節(jié)點(Parentnode)：如果某條弧線從節(jié)點ni指向節(jié)點nj，那么節(jié)點nj就叫做節(jié)點ni的后繼節(jié)點或后裔，而節(jié)點ni叫做節(jié)點nj的父輩節(jié)點或祖先。2.1狀態(tài)空間表示路徑(Path)：某個節(jié)點序列(ni1,ni2,…,nik)當j=2,3,…,k時，如果對于每一個ni,j-1都有一個后繼節(jié)點nij存在，那么就把這個節(jié)點序列叫做從節(jié)點ni1至節(jié)點nik的長度為k的路徑。代價(Cost)：用c(ni,nj)來表示從節(jié)點ni指向節(jié)點nj的那段弧線的代價。兩節(jié)點間路徑的代價等于連接該路徑上各節(jié)點的所有弧線代價之和。圖的顯示說明/隱示說明：指各節(jié)點及其具有代價的弧線可以/不可以由一張表明確給出。顯然，顯示說明對于大型的圖是不切實際的，而對于具有無限節(jié)點集合的圖則是不可能的。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問題歸約表示問題歸約的方法從目標（要解決的問題）出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。這就是問題歸約的實質。2.2問題歸約表示2.2.1問題歸約描述

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

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

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

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

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

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

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

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

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

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

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

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

1.謂詞公式的定義定義2.1用P（x1,x2,...,xn）表示一個n元謂詞公式，其中P為n元謂詞,x1,x2，…，xn為客體變量或變元。通常把P(x1,x2，…，xn）叫做謂詞演算的原子公式，或原子謂詞公式?？梢杂眠B詞把原子謂詞公式組成復合謂詞公式，并把它叫做分子謂詞公式。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ù)或者為正或者為負。解把上述命題意譯如下：對于所有的x，如果x是整數(shù)，則x或為正的或者為負的。用I（x）表示“x是整數(shù)”，P（x）表示“x是正數(shù)”，N（x）表示"x是負數(shù)”。于是，可把給定命題用下列謂詞公式來表示：

(?x)（I（x）→（P（x）∨N（x）））2.3謂詞邏輯表示2.合式公式的性質如果P和Q是兩個合式公式，則由這兩個合式公式所組成的復合表達式可由下列真值表給出。2.3謂詞邏輯表示等價關系：（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）結合律（P∧Q）∧R等價于P∧(Q∧R)

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

（7）逆否律

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

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

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

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

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

(2)結構部分敘述符號排列的約束條件，指定各弧線連接的節(jié)點對。

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

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

語義網(wǎng)絡的特點：

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

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

(3)表現(xiàn)問題更加直觀，更易于理解，適于知識工程師與領域專家溝通。語義網(wǎng)絡中的繼承方式也符合人類的思維習慣。

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

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

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

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

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

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

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

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

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

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

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

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

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