人工智能課件-老師2014年春6知識表示方法part

1、Artificial Intelligence (AI)人工智能主講：戚玉濤Email： 第二章：知識表示方法內(nèi)容提要第二章：知識表示方法1.狀態(tài)空間法2.問題歸約法3.謂詞邏輯法4.語義網(wǎng)絡(luò)法5.其他方法語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)法（ Semantic Network Representation ）語義網(wǎng)絡(luò)是奎廉(J. R. Quillian) 1968年在研究人類聯(lián)想記憶時提出的一種心理學(xué)模型，認(rèn)為記憶是由概念間的聯(lián)系實現(xiàn)的。隨后，奎廉又把它用作知識表示。1972年，西蒙在他的自然語言理解系統(tǒng)中也采用了語義網(wǎng)絡(luò)表示法。語義網(wǎng)絡(luò)是一種表達(dá)能力強而且靈活的知識表示方法，目前已經(jīng)廣泛應(yīng)用于人工智能領(lǐng)域

2、，尤其是在自然語言處理方面。語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)語義網(wǎng)絡(luò)是通過概念及其語義關(guān)系來表達(dá)知識一種網(wǎng)絡(luò)圖。從圖論的觀點看，語義網(wǎng)絡(luò)是一個“帶標(biāo)識的有向圖”有向圖的節(jié)點代表實體，表示各種事物、概念、情況、屬性、狀態(tài)、事件、動作等；節(jié)點還可以是一個語義子網(wǎng)絡(luò)，形成嵌套結(jié)構(gòu)。有向圖的弧代表語義關(guān)系，表示它所連結(jié)的兩個實體之間的語義聯(lián)系，它必須帶有標(biāo)識。語義網(wǎng)絡(luò)法語義基元語義網(wǎng)絡(luò)中最基本的語義單元稱為語義基元，可用三元組表示為： （結(jié)點1，弧，結(jié)點2）基本網(wǎng)元指一個語義基元對應(yīng)的有向圖例如：若有語義基元（A, R, B），其中，A、B分別表示兩個結(jié)點，R表示A與B之間的某種語義聯(lián)系，則它所對應(yīng)的基本網(wǎng)元如下圖

3、所示：ABR語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的簡單例子例如：用于一網(wǎng)絡(luò)表示“鴕鳥是一種鳥”語義網(wǎng)絡(luò)的表示能力事實的表示：例如：“雪的顏色是白的”規(guī)則的表示：例如：“規(guī)則R：如果 A 則B”鴕鳥鳥是一種雪白顏色ABR語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的基本語義關(guān)系（1）類屬關(guān)系類屬關(guān)系體現(xiàn)的是“具體與抽象”的概念，通常指具有共同屬性的不同事物之間的實例關(guān)系、成員關(guān)系或分類關(guān)系。常有的類屬關(guān)系有：Is-a(是一個)、A-member-of（是一員）、A-kind-of（是一種）。例如：張寧是一個學(xué)生。張寧學(xué)生Is-a語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的基本語義關(guān)系（2）聚集關(guān)系如果一個事物是另一事物的組成部分或某個方面，則它們之間的關(guān)系就是聚

4、集關(guān)系。常用的聚集關(guān)系有：A-part-of（是一部分）。例如：手是人體的一部分。手人體A-part-of 語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的基本語義關(guān)系（3）屬性關(guān)系屬性關(guān)系表示了對象和其屬性之間的聯(lián)系。常用的屬性關(guān)系有：Have(有)、Can（能、會）、Owner（所有者）。 例如：張寧會說英語，年齡18歲，身高160cm。張寧英語18160havehavecan語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的基本語義關(guān)系（4）推論關(guān)系如果一個概念可由另一個概念推出，兩個概念間存在因果關(guān)系，則稱它們之間是推論關(guān)系，可以用Fetch(推出)表示。 例如：饑餓推出需要進食饑餓需要進食Fetch語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的基本語義關(guān)系（5）相近

5、關(guān)系相近關(guān)系是指不同事物在形狀、內(nèi)容等方面相似或接近。常用的相近關(guān)系有：Similar-to（相似）、Near-to（接近）例如：貓和虎相似貓虎Similar-to語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的基本語義關(guān)系（6）方位關(guān)系方位關(guān)系表示了不同事物之間在位置方面的相互關(guān)系，例如在上（Located-on），在下（Located-under），在內(nèi)（Located-inside）、在外（Located-outside）、位于（Located-at）等都可以表示不同事物間的方位關(guān)系。例如：書在桌子上。書桌子Located-on 語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的基本語義關(guān)系（7）時間關(guān)系時間關(guān)系表示了不同事件在發(fā)生時間方面的先

6、后次序關(guān)系。常見的時間關(guān)系有Before（在前）、After（在后）等。例如：閱覽室開放后才能供讀者閱覽就是表示了開放和閱覽兩事件之間的先后時間關(guān)系。 閱覽開放After語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的基本語義關(guān)系（8）構(gòu)成關(guān)系用于表示構(gòu)成聯(lián)系，是一種一對多的聯(lián)系，它的聯(lián)系的節(jié)點間不具有屬性繼承性。例如： 整數(shù)由正整數(shù)、負(fù)整數(shù)和零組成。整數(shù)正整數(shù)零負(fù)整數(shù)與Composed of 語義網(wǎng)絡(luò)法謂詞邏輯與語義網(wǎng)絡(luò)等效例如：用”Liming is a man”的語義網(wǎng)絡(luò)和謂詞邏輯表示說明謂詞邏輯與語義網(wǎng)絡(luò)的等效性。方法 初始問題 算符目標(biāo)結(jié)果謂詞邏輯法合式公式置換合一消解反演根結(jié)點 nil語義網(wǎng)絡(luò)法節(jié)點鏈目標(biāo)網(wǎng)絡(luò)

7、語義網(wǎng)絡(luò)LIMINGMAN ISA語義網(wǎng)絡(luò)ISA(LIMING,MAN)或MAN(LIMING)謂詞邏輯語義網(wǎng)絡(luò)法一元關(guān)系指可以用一元謂詞P(x)表示的關(guān)系。謂詞P說明實體的性質(zhì)、屬性等。描述的是一些最簡單、最直觀的事物或概念。常用：是、有、會、能等語義關(guān)系來說明。如 雪是白的 。一元關(guān)系的描述應(yīng)該說，語義網(wǎng)絡(luò)表示的是二元關(guān)系。如何用它來描述一元關(guān)系？結(jié)點1表示實體，結(jié)點2表示實體的性質(zhì)或?qū)傩缘?，弧表示語義關(guān)系。例如：用語義網(wǎng)絡(luò)表示“動物能運動、會吃” 運動吃動物CanCan語義網(wǎng)絡(luò)法二元關(guān)系：二元語義網(wǎng)絡(luò)表示可用二元謂詞P(x,y)表示的關(guān)系。其中，x,y為實體，P為實體之間的關(guān)系。單個二元

8、關(guān)系可直接用一個基本網(wǎng)元來表示對復(fù)雜關(guān)系，可通過一些相對獨立的二元或一元關(guān)系的組合來實現(xiàn)。例如：用語義網(wǎng)絡(luò)表示動物能運動、會吃。鳥是一種動物，鳥有翅膀、會飛。魚是一種動物，魚生活在水中、會游泳。語義網(wǎng)絡(luò)法用語義網(wǎng)絡(luò)表示：1）動物能運動、會吃；2）鳥是一種動物，鳥有翅膀、會飛；3）魚是一種動物，魚生活在水中、會游泳。AKO：A kind of動物吃運動翅膀水中鳥魚飛游泳CanCanAKOLiveHaveCanAKOCan語義網(wǎng)絡(luò)法例如：用語義網(wǎng)絡(luò)表示王強是理想公司的經(jīng)理；理想公司在中關(guān)村；王強28歲。中關(guān)村理想公司王強經(jīng)理28歲Located-at-Work-forHeadshipAge語義網(wǎng)絡(luò)

9、法二元關(guān)系：二元語義網(wǎng)絡(luò)表示通常，把有關(guān)一個物體或概念，或一組有關(guān)的物體或概念的知識用一個語義網(wǎng)絡(luò)來表示。用一組基元來表示知識，可以簡化表示，用簡單的知識來表示更復(fù)雜的知識。 與此相關(guān)的是尋找基本概念和某些基本弧的問題，稱為“選擇語義基元”問題。語義網(wǎng)絡(luò)法二元關(guān)系：二元語義網(wǎng)絡(luò)表示例如：我椅子的顏色是咖啡色的；椅子包套是皮革；椅子是一種家具；座位是椅子的一部分；椅子的所有者是XX是個人語義網(wǎng)絡(luò)法我椅子的顏色是咖啡色的；椅子包套是皮革；椅子是一種家具；座位是椅子的一部分；椅子的所有者是X；X是個人定義一個語義網(wǎng)絡(luò)來表示椅子的概念在椅子的基礎(chǔ)上進一步具體描述：我的椅子FURNITURECHAIRP

10、ERSONSEATMY CHAIRBROWNXLEATHER ISAOWNERCOLOR ISAISAISA PARTCOVERING椅子的概念語義網(wǎng)絡(luò)法例如：用語義網(wǎng)絡(luò)表示李新的汽車的款式是“捷達(dá)”、銀灰色。王紅的汽車的款式是“凱越”、紅色。李新和王紅的汽車均屬于具體概念,可增加“汽車” 這個抽象概念。捷達(dá)李新汽車1銀灰色人汽車交通工具王紅汽車2紅色凱越BrandOwnerColorISAISAAKOColorOwnerBrandISAISA語義網(wǎng)絡(luò)法多元關(guān)系：多元語義網(wǎng)絡(luò)表示可用多元謂詞P(x1，x2， ， xn)表示的關(guān)系。其中，個體x1，x2， ， xn為n個實體，謂詞P說明這些實體之

11、間的關(guān)系。本質(zhì)上講，語義網(wǎng)絡(luò)中節(jié)點之間的連接是二元關(guān)系，如何用二元關(guān)系表示多個實體之間的多元關(guān)系？把多元關(guān)系它轉(zhuǎn)化為一組二元關(guān)系的組合，或二元關(guān)系的合取語義網(wǎng)絡(luò)法多元關(guān)系表示方法把多元關(guān)系它轉(zhuǎn)化為一組二元關(guān)系的組合，或二元關(guān)系的合取R(X1，X2，Xn)R12(X1，X2)R13(X1，X3) R1n(X1，Xn). Rn-1 n(Xn-1，Xn)可轉(zhuǎn)換為語義網(wǎng)絡(luò)法多元關(guān)系表示方法例如： 用語義網(wǎng)絡(luò)表示 “三個點 a，b，c 圍成一個三角形”三元關(guān)系：Triangle（ a，b，c ）可轉(zhuǎn)換為一組二元關(guān)系的合取：CAT（a,b） CAT（b,c） CAT（c,a）CAT表示兩點的連線語義網(wǎng)絡(luò)法

12、多元關(guān)系表示方法西蒙斯（Simmons）和斯洛克姆（Slocum）提出增加情況和動作節(jié)點的描述方法用語義網(wǎng)絡(luò)表示事件時，需要增加一個事件節(jié)點例如： 用語義網(wǎng)絡(luò)表示 “小燕子從春天到秋天占有一個巢”四元關(guān)系需要設(shè)立一個“占有權(quán)”的情況節(jié)點，表示占有物和占有時間等。語義網(wǎng)絡(luò)法多元關(guān)系表示方法：增加情況和動作節(jié)點例如： 用語義網(wǎng)絡(luò)表示 “小燕子從春天到秋天占有一個巢”小燕子燕子鳥巢鳥窩春天時間秋天情況占有權(quán)占有資格ISAAKOOwnStartAKOAKOEndAKOAKOOwnerAKO語義網(wǎng)絡(luò)法多元關(guān)系表示方法：增加情況和動作節(jié)點例如： 用語義網(wǎng)絡(luò)表示 “小王給小林一本書”三元關(guān)系需要設(shè)立一個“給

13、”的動作節(jié)點。動作節(jié)點由一些向外引出的弧來指出動作的主體與客體。一本書小王給小林GiftReceiverGiver語義網(wǎng)絡(luò)法多元關(guān)系表示方法：增加事件節(jié)點例如： 用語義網(wǎng)絡(luò)表示 “ 北京大學(xué)和清華大學(xué)兩校籃球隊在北大進行一場比賽的比分是85：89”。三元關(guān)系需要設(shè)立一個“球賽”的事件節(jié)點引入事件節(jié)點G25來表示這場特點的球賽清華大學(xué) 籃球比賽G2585:89北京大學(xué)VISITING TEAMHOME TEAMSCOREISA語義網(wǎng)絡(luò)法連接詞和量詞的表示合取和析取的表示：可通過增加合取節(jié)點和析取節(jié)點來實現(xiàn)例如：用語義網(wǎng)絡(luò)表示：“參賽者有教師有學(xué)生，參賽者的身高有高有低”分析參賽者的不同情況，可得

14、到以下四種情況：A 教師、高； B 教師、低；C 學(xué)生、高；D 學(xué)生、低人參賽者ABCD或或教師學(xué)生高低與ISAPartPartPartPartStateStateStateState語義網(wǎng)絡(luò)法連接詞和量詞的表示否定的表示：基本語義關(guān)系的否定：可通過在有向弧上直接標(biāo)注該基本語義關(guān)系的否定的方法來解決。例如：用語義網(wǎng)絡(luò)表示“書不在桌子上”書桌子Located-on語義網(wǎng)絡(luò)法連接詞和量詞的表示否定的表示：一般語義關(guān)系的否定：可通過引進“非”節(jié)點來表例如： 用語義網(wǎng)絡(luò)表示 “小王沒有給小林一本書”一本書小王給小林GiftReceiverGiver非語義網(wǎng)絡(luò)法連接詞和量詞的表示蘊含的表示：通過增加蘊含

15、關(guān)系節(jié)點來實現(xiàn)。在蘊含關(guān)系中，有兩條指向蘊含節(jié)點的弧，一條代表前提條件(Antecedent) ，標(biāo)記為ANTE；另一條代表結(jié)論(Consequence) ，標(biāo)記為CONSE例如：用語義網(wǎng)絡(luò)表示：“如果學(xué)校組織大學(xué)生機器人競賽活動，那么李強就參加比賽”CONSEANTE學(xué)校比賽活動機器人機器人競賽蘊含參加比賽學(xué)生智能機器李強人RacerAKOConstitutionManipulatorISAAKOAKOJoiner語義網(wǎng)絡(luò)法連接詞和量詞的表示存在量詞的表示：可直接用“ISA”、“AKO”等這樣的語義關(guān)系來表示全稱量詞的表示：把一個復(fù)雜命題劃分為若干個子命題，每個子命題用一個較簡單的語義網(wǎng)絡(luò)表

16、示，稱為一個子空間，多個子空間構(gòu)成一個大空間。每個子空間看作是大空間中的一個結(jié)點，稱作超結(jié)點?？臻g可逐層嵌套，子空間之間用弧互相連結(jié)。例如： 用語義網(wǎng)絡(luò)表示：“每個學(xué)生都學(xué)習(xí)了一門程序設(shè)計語言”“每個學(xué)生都學(xué)習(xí)了所有的程序設(shè)計課程”“每個學(xué)生都學(xué)習(xí)了C+語言”語義網(wǎng)絡(luò)法“每個學(xué)生都學(xué)習(xí)了一門程序設(shè)計語言” GS：是一個概念結(jié)點，它表示具有全稱量化的一般事件。 g：是一個實例結(jié)點，代表GS中的一個具體例子，如上所提到的事實。 s：是一個全稱變量，表示任意一個學(xué)生。 r：是一個存在變量，表示某一次學(xué)習(xí)。 p：是一個存在變量，表示某一門程序設(shè)計語言。 F：弧“F”說明它所代表的子空間及其具體形式 ：

17、弧“”說明它所代表的全稱量詞。GSgsrp學(xué)生學(xué)習(xí)程序語言ISAISAISAFSubjectObjectISA子空間語義網(wǎng)絡(luò)法“每個學(xué)生都學(xué)習(xí)了所有的程序設(shè)計課程”學(xué)生學(xué)習(xí)程序設(shè)計課gGSsrpISAISAISASubjectObjectISAF子空間語義網(wǎng)絡(luò)法“每個學(xué)生都學(xué)習(xí)了C+語言”GSgsr學(xué)生學(xué)習(xí)C+語言程序語言ISAISASubjectObjectFISAISA子空間在這種表示方法中，要求子空間中的所有非全稱變量節(jié)點都是全稱變量的函數(shù)C+是具體的程序設(shè)計語言，不是全稱變量s的函數(shù)，應(yīng)該放在子空間外面語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的推理過程：用語義網(wǎng)絡(luò)表示知識的問題求解系統(tǒng)主要由兩大部分所組成，

18、一部分是由語義網(wǎng)絡(luò)構(gòu)成的知識庫，另一部分是用于問題求解的推理機制。語義網(wǎng)絡(luò)的推理過程主要有兩種：繼承：是指把對事物的描述從抽象結(jié)點傳遞到實例結(jié)點。通過繼承可以得到所需結(jié)點的一些屬性值，它通常是沿著ISA、AKO等繼承弧進行的。匹配：是指在知識庫的語義網(wǎng)絡(luò)中尋找與待求解問題相符的語義網(wǎng)絡(luò)模式。語義網(wǎng)絡(luò)法兩個概念：語義網(wǎng)絡(luò)的值與槽值：鏈的尾部的節(jié)點稱為值節(jié)點，如上圖中的BRICK、TOY和RED。槽：節(jié)點的槽相當(dāng)于鏈，不過取不同的名字而已。在磚塊12(BRICK12)有3個鏈，構(gòu)成兩個槽。其中一個槽只有一個值，另外一個槽有兩個值。顏色槽(COLOR)填入紅色(RED)，ISA槽填入了磚塊BRICK

19、)和玩具(TOY)。BRICKTOYBRICK12RED ISACOLOR語義網(wǎng)絡(luò)法繼承在語義網(wǎng)絡(luò)中所謂的繼承是把對事物的描述從概念節(jié)點或類節(jié)點傳遞到實例節(jié)點。例如在圖中BRICK是概念節(jié)點，BRICK12是一個實例節(jié)點。BLOCKWEDGETRIANGULERBRICKRECTANGULARWEDGE18BRICK12AKOISASHAPEISAAKOSHAPE語義網(wǎng)絡(luò)法繼承的3種過程：值繼承：除了ISA鏈以外，另外還有一種AKO(A-KIND-OF)鏈也可被用于語義網(wǎng)絡(luò)中的描述或特性的繼承。 總之，ISA和AKO鏈直接地表示類的成員關(guān)系以及子類和類之間的關(guān)系，提供了一種把知識從某一層傳遞到

20、另一層的途徑?！叭绻枰崩^承：在某些情況下，當(dāng)我們不知道槽值時，可以利用已知信息來計算。例如，我們可以根據(jù)體積和物質(zhì)的密度來計算積木的重量。進行上述計算的程序稱為if-needed(如果需要)程序。語義網(wǎng)絡(luò)法繼承的3種過程：“缺省”繼承 ：某些情況下，當(dāng)我們對事物所作的假設(shè)不是十分有把握時，最好對所作的假設(shè)加上“可能”這樣的字眼。例如，我們可以認(rèn)為法官可能是誠實的，但不一定是；或認(rèn)為寶石可能是很昂貴的，但不一定是。我們把這種具有相當(dāng)程度的真實性，但又不能十分肯定的值稱為“缺省”值。語義網(wǎng)絡(luò)法匹配：對于困難一些的問題，當(dāng)解決涉及由幾部分組成的事物時，如下圖中的玩具房(TOY-HOUSE)和玩具房-77(TOY-HOUSE77)，繼承過程將如何進行？ TOY-HOUSETOY-HOUSE77WEDGEBRICKISAPART