經(jīng)典人工智能技術(shù)-知識(shí)表示、推理與搜索課件

本講授課要點(diǎn)講授基于符號(hào)主義的經(jīng)典人工智能技術(shù)。符號(hào)主義的研究以知識(shí)為核心。知識(shí)的表示是問題求解的基礎(chǔ)，但單純介紹知識(shí)表示容易讓學(xué)生感覺枯燥，且無法直觀理解其作用，可考慮將表示與求解放在一起講授，例如：謂詞邏輯表示與推理技術(shù)狀態(tài)空間表示與搜索技術(shù)宜用問題帶出內(nèi)容，通過問題引發(fā)學(xué)生思考：“這樣的問題機(jī)器能解決嗎？可以怎么做？”以增加興趣。引言——經(jīng)典人工智能出色的老式人工智能（GoodOldFashionedAI，GOFAI）——哲學(xué)家約翰.豪格蘭德一個(gè)用規(guī)則和事實(shí)來程序化的高速數(shù)字計(jì)算機(jī)可能表現(xiàn)出智力行為

——圖靈人類是借助事實(shí)與規(guī)則來產(chǎn)生智力行為的經(jīng)典人工智能技術(shù)主要以符號(hào)表示、符號(hào)處理為實(shí)現(xiàn)智能的主要手段，推理和搜索是其中的核心技術(shù)5.1自動(dòng)推理證明機(jī)器真的能夠自動(dòng)推理嗎？自動(dòng)推理證明的發(fā)展史謂詞邏輯消解原理5.1.1機(jī)器真的能夠自動(dòng)推理嗎？5個(gè)房間問題有5間不同顏色的房間，每間住個(gè)不同國(guó)籍的人，每人有自己喜歡的飲料、香煙和寵物。已知信息：英國(guó)人在紅房間中西班牙人有一條狗挪威人住在左邊第一間房里黃房間中的人在抽庫(kù)爾斯牌香煙抽切斯菲爾德牌香煙的人是養(yǎng)了一只狐貍的人的鄰居挪威人住在藍(lán)房間隔壁抽溫斯頓牌香煙的人有一只蝸牛抽幸運(yùn)牌香煙的人喝橘子汁烏克蘭人喝茶日本人抽國(guó)會(huì)牌香煙抽庫(kù)爾斯牌煙的房間在有匹馬的房間隔壁綠房間中的人喝咖啡綠房間在白房間的左邊中間房間的人喝牛奶問題：斑馬在哪個(gè)房間中？哪個(gè)房間中的人喝水？自動(dòng)推理示例：5個(gè)房間問題房間號(hào)12345顏色國(guó)籍香煙飲料寵物挪威人牛奶咖啡庫(kù)爾斯馬英國(guó)人水橘子汁西班牙幸運(yùn)狗茶烏克蘭日本人國(guó)會(huì)溫斯頓切斯菲爾德蝸牛狐貍斑馬3.挪威人住在左邊第一間房里6.挪威人住在藍(lán)房間旁邊14.中間房間的人喝牛奶12.綠房間中的人喝咖啡14.綠房間在白房間的左邊1.英國(guó)人在紅房間中4.黃房間中的人在抽庫(kù)爾斯牌香煙11.抽庫(kù)爾斯牌煙的房間在有匹馬的房間隔壁8.抽幸運(yùn)香煙的人喝橘子汁9.烏克蘭人喝茶2.西班牙人有一條狗8.抽幸運(yùn)牌香煙的人喝橘子汁9.烏克蘭人喝茶10.日本人抽國(guó)會(huì)牌香煙7.抽溫斯頓牌香煙的人有一只蝸牛5.抽切斯菲爾德牌香煙的人的是養(yǎng)了一只狐貍的人的鄰居機(jī)器真的能自動(dòng)完成這樣的推理嗎？自動(dòng)推理示例求解如何實(shí)現(xiàn)自動(dòng)推理證明？邏輯方法是自動(dòng)證明中常用的方法如何進(jìn)行邏輯推理？推理的過程怎樣？怎么實(shí)現(xiàn)自動(dòng)推理？推理示例—馬普爾小姐探案阿加莎.克里斯蒂偵探小說改編的電視劇“馬普爾小姐探案”馬克和約爾是孿生兄弟誰是作案者：馬克或約爾？馬普爾小姐的結(jié)論誰是馬克誰是約爾？馬普爾小姐的推理過程觀察結(jié)果馬克是右撇子，手表戴在左手約爾是左撇子，手表戴在右手推理規(guī)則如果手表戴在左手，那么他是馬克如果手表戴在右手，那么他是約爾事實(shí)規(guī)則人類的推理可以理解語義機(jī)器如何進(jìn)行這樣類似的推理？需要將推理的過程與理解分割開，將其形式化結(jié)論只是穿著不同衣服的同一個(gè)人——約爾推理的一般形式 已知：事實(shí)1，事實(shí)2，…

如果

事實(shí)1那么

結(jié)論1

如果

事實(shí)2那么

結(jié)論2

…. 得到：結(jié)論1，結(jié)論2，…將事實(shí)與規(guī)則等抽象出來，不涉及具體內(nèi)容，借助一些符號(hào)來表示，推理過程可以被形式化

P：某已知事實(shí) P→Q：如果P那么Q

結(jié)論： Q

這個(gè)過程不需要直覺和解釋符號(hào)與形式語言自然語言不適合計(jì)算機(jī)處理例：小王不方便接電話，他方便去了需要一種無歧義，方便存儲(chǔ)和表達(dá)的形式化符號(hào)表征體系數(shù)理邏輯命題邏輯謂詞邏輯5.1.3謂詞邏輯什么是謂詞？原子命題中刻畫個(gè)體的性質(zhì)或個(gè)體間關(guān)系的成分謂詞邏輯是一種形式語言是目前為止能夠表達(dá)人類思維活動(dòng)規(guī)律的一種最精確的語言接近自然語言，又方便存入計(jì)算機(jī)處理最早應(yīng)用于人工智能中表示知識(shí)適合于表示事物的狀態(tài)、屬性、概念等，也可用來表示事物間確定的因果關(guān)系Terms（項(xiàng)）一個(gè)常量是項(xiàng)一個(gè)變量是項(xiàng)如果f是一個(gè)n元函數(shù)符號(hào)，t1,t2,...,tn是項(xiàng)，則f(t1,t2,...,tn)也是項(xiàng)所有項(xiàng)都是由規(guī)則(a)(b)(c)產(chǎn)生的Atoms（原子公式）

如果P是一個(gè)n元謂詞符號(hào)，t1,t2,...,tn是項(xiàng)，則P(t1,t2,...,tn)是一個(gè)原子公式，其他任何表達(dá)式都不是原子公式

WFF（合適公式）AnatomisWFF如果F和G是WFF，則~F，F(xiàn)∧G，F(xiàn)∨G，F(xiàn)→G，F(xiàn)≡G都是WFF如果F是WFF，x是自由變量則(x)F，(x)F都是WFFWFF僅由有限次使用規(guī)則(a)(b)(c)產(chǎn)生。[例]man(smith)smith是人between(albert,susan,david) albert在susan與david之間

(x)(man(x)→mortal(x))人都會(huì)死

(x)(man(x)∧clever(x))有的人聰明推理是如何進(jìn)行的？推理過程多種多樣例1：如果今天不下雨，我就去你家今天沒有下雨例2：小王說他下午或者去圖書館或者在家休息小王沒去圖書館計(jì)算機(jī)如何選擇？5.1.4消解原理（歸結(jié)原理）魯濱遜美國(guó)數(shù)學(xué)家魯濱遜

提出消解原理（1965年） 基本的出發(fā)點(diǎn)：要證明一個(gè)命題為真都可以通過證明其否命題為假來得到 將多樣的推理規(guī)則簡(jiǎn)化為一個(gè)—消解什么叫消解PQ﹁PRQR消解式親本子句消解式是親本子句的邏輯結(jié)論消解只能在僅含否定和析取聯(lián)接詞的公式（子句）間進(jìn)行必須先把公式化成規(guī)范的形式（范式，子句集）析取聯(lián)接詞，類似“或”什么叫消解例1：小王說他下午或者去圖書館或者在家休息小王沒去圖書館R—小王下午去圖書館S—小王下午在家休息RS﹁RS例2：如果今天不下雨，我就去你家﹁

P→Q今天沒有下雨 ﹁

PPQ含變量的消解例：蘇格拉底論斷凡人都會(huì)死. x(Man

(x)Mortal(x))蘇格拉底是人. Man

(Socrates)如何得到結(jié)論：蘇格拉底會(huì)死. Mortal(Socrates)要完成消解還面臨幾個(gè)問題“”和“”必須消去Man

(x)Mortal(x)Man

(x)

Mortal“”怎么辦？化為子句集置換與合一如果能消去“”，Man

(x)

和Man

(Socrates)也不能構(gòu)成互補(bǔ)對(duì)，形式不一樣，怎么辦？置換與合一要把消解推理規(guī)則推廣到含有變量的子句，必須找到一個(gè)作用于親本子句的置換，使親本子句含有互補(bǔ)文字置換（Substitution）置換是形為{t1/x1,t2/x2,...,tn/xn}的一個(gè)有限集xi是互不相同的變?cè)?，ti是項(xiàng)用ti代換xi，不允許ti與xi相同，也不允許變?cè)獂i循環(huán)出現(xiàn)在另一個(gè)tj中{a/x,f(b)/y,w/z}{f(a)/x,b/y,t/x} {g(y)/x,f(x)/y}s={z/x,w/y}ω=P(x,f(y),B)ωs=P(z,f(w),B)置換與合一合一（Unification)尋找項(xiàng)對(duì)變量的置換，以使兩表達(dá)式一致的過程。如果一個(gè)置換s作用于表達(dá)式集{Ei}的每個(gè)元素，則我們用{Ei}s來表示置換例的集。我們稱表達(dá)式集{Ei}是可合一的（unifiable）,s為合一者（unifier）mgu(mostgeneralunifier,最一般合一者)若s為{Fi}的任一合一者，又存在某個(gè)置換s'，使得

s=gs'則稱g為{Fi}的最一般(最簡(jiǎn)單的)合一者，記作mgu。mguisuniqueF={P(x,f(y),B)}s={A/x,B/y} g={B/y}s’={A/x} gs’=s相關(guān)概念文字：原子公式及其否定統(tǒng)稱為文字子句集(1)子句定義 任何文字的析取式稱為子句 不包含任何文字的子句稱為空子句（空子句是永假的） 由子句構(gòu)成的集合稱為子句集例：{P（x）∨Q(x),~P（x，f(x)）∨Q(x,g(x))}化子句集(2)謂詞演算公式化為子句式任何一個(gè)謂詞演算公式可以化為一個(gè)子句集合步驟：

1)消去蘊(yùn)涵符號(hào)用~A∨B代換A→B2)把非號(hào)~移入內(nèi)層

P~x)

(=

x)P(~P~x)

(=

x)P(~Q~P~

Q)(P~Q~P~

Q)(P~"$$"ù=úú=ù3)對(duì)變量標(biāo)準(zhǔn)化改變變量名，使不同的變量不同名4)消去存在量詞(具體化Skolemnizing)，兩種情況：存在量詞不在全稱量詞的轄域內(nèi)——用新的個(gè)體常量替換受存在量詞約束的變?cè)嬖诹吭~在全稱量詞的轄域內(nèi)

Skolem函數(shù)，即具體化函數(shù)x)Q(x)(

x)P(x)($ú"y)Q(y)(

x)P(x)($ú")a(Q)x(P)x(ú"T)y(Q)y()x(P)x($ú")y,x,...,x,x(P)y)(x)...(x)(x(n21n21$""")x,...,x,x(f,x,...,x,x(P)x)...(x)(x()n21n21n21"""T)x,...,x,x(f,x,...,x,x(P)x)...(x)(x()n21n21n21"""T5)化為前束形式把全稱量詞提到最外層前束形:=(前綴){母式} ↑↑

全稱量詞串無量詞公式6)把母式化為合取范式7)消去全稱量詞8)消去連詞符號(hào)∧，寫成子句集9)變量分離標(biāo)準(zhǔn)化 改變變量名稱，使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中消解式的定義命題邏輯的消解式設(shè)C1與C2是子句集中的任意兩個(gè)子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么從C1和C2中分別消去L1和L2，并將兩個(gè)子句中余下的部分析取，構(gòu)成一個(gè)新子句C12，則稱這一過程為消解，稱C12為C1和C2的消解式，C1，C2為C12的親本子句例：子句C1=P∨C1'C2=~P∨C2' 消解式C12=C1'∨C2'一階謂詞邏輯的消解式設(shè)C1與C2是兩個(gè)沒有相同變?cè)淖泳?，L1和L2分別是C1和C2中的文字，若σ是L1和~L2的最一般合一者，則稱

C12=(C1σ-{L1σ})∪(C2σ-{L2σ})為C1和C2的二元消解式，L1和L2為消解式上的文字怎么利用消解原理進(jìn)行證明？消解反演通俗的說就是“反證法”要證命題A恒為真，等價(jià)于證﹁A恒為假證明過程否定結(jié)論R，得﹁R；把﹁R添加到已知前提集合F中去；把新產(chǎn)生的集合｛﹁R，F(xiàn)｝化成范式；應(yīng)用消解原理，不斷求消解式，直到得到一個(gè)表示矛盾的空子句 假設(shè)：所有不貧窮并且聰明的人都是快樂的，那些看書的人是聰明的。李明能看書且不貧窮，快樂的人過著激動(dòng)人心的生活。求證：李明過著激動(dòng)人心的生活。解：先定義謂詞：

Poor(x)x是貧窮的

Smart(x)x是聰明的

Happy(x)x是快樂的

Read(x)x能看書

Exciting(x)x過著激動(dòng)人心的生活消解反演示例—“激動(dòng)人心的生活”問題消解反演示例—“激動(dòng)人心的生活”問題問題謂詞表示：

“所有不貧窮并且聰明的人都是快樂的”

(?x)((~Poor(x)∧Smart(x))→Happy(x))“那些看書的人是聰明的”

(?y)(Read(y)→Smart(y))“李明能看書且不貧窮”

Read(Liming)∧~Poor(Liming)“快樂的人過著激動(dòng)人心的生活”

(?z)(Happy(z)→Exciting(z))目標(biāo)“李明過著激動(dòng)人心的生活”的否定

~Exciting(Liming)消解反演示例—“激動(dòng)人心的生活”問題將上述謂詞公式轉(zhuǎn)化為子句集如下：

(1)Poor(x)∨~Smart(x)∨Happy(x)(2)~Read(y)∨Smart(y)(3)Read(Liming)(4)~Poor(Liming)(5)~Happy(z)∨Exciting(z)(6)~Exciting(Liming)(結(jié)論的否定)消解反演示例—“激動(dòng)人心的生活”問題~Exciting(Liming)~Happy(z)∨Exciting(z)~Happy(Liming)Happy(x))∨~Smart(x)∨Happy(x)Poor(Liming)∨~Smart(Liming)~Read(y)∨Smart(y)Poor(Liming)∨~Read(Liming)~Poor(Liming)~Read(Liming)Read(Liming)

NIL{Liming/z}{Liming/x}{Liming/y}消解原理的局限性消解原理推進(jìn)了用邏輯方法進(jìn)行機(jī)器證明的研究，使得自動(dòng)定理證明領(lǐng)域發(fā)生了質(zhì)的變化。但是要求把邏輯公式轉(zhuǎn)化為某種范式，喪失了其固有的邏輯蘊(yùn)含語義。例如： 如果一個(gè)人發(fā)燒、肚子痛，那么很可能是感染了。x(has_fever(x)∧tummy_pain(x)→has_an_infection(x))

has_fever(x)∨

tummy_pain(x)∨

has_an_infection(x)表達(dá)能力的局限性,限制了應(yīng)用范圍后來有許多重要改進(jìn)：語義歸結(jié)（消解）、鎖歸結(jié)（消解）、線性歸結(jié)（消解）等。5.2問題求解與圖搜索策略問題求解問題表示解的搜索5.2.1問題求解—什么是問題求解問題求解是人工智能的核心問題之一問題求解的目的機(jī)器自動(dòng)找出某問題的正確解決策略更進(jìn)一步，能夠舉一反三，具有解決同類問題的能力是從人工智能初期的智力難題、棋類游戲、簡(jiǎn)單數(shù)學(xué)定理證明等問題的研究中開始形成和發(fā)展起來的一大類技術(shù)求解的手段多種多樣其中搜索技術(shù)是問題求解的主要手段之一問題表示解的搜索八數(shù)碼難題在3×3的棋盤，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字。棋盤上還有一個(gè)空格，與空格相鄰的棋子可以移到空格中。12384567初始狀態(tài)81324567目標(biāo)狀態(tài)如何將棋盤從某一初始狀態(tài)變成最后的目標(biāo)狀態(tài)？5.2.1問題求解—問題示例問題示例38怎樣找到兩點(diǎn)之間的最短路徑呢？問題有了，可怎么讓計(jì)算機(jī)知道這些問題呢？5.2.2問題表示——狀態(tài)空間圖例：真空吸塵器的世界假設(shè)：吸塵器的世界只有兩塊地毯大小，地毯或者是臟的，或者是干凈的吸塵器能做的動(dòng)作只有三個(gè)

{向左(Left)，向右(Right)，吸塵(Suck)}一共有多少種可能的情況？狀態(tài)狀態(tài)轉(zhuǎn)換狀態(tài)之間可以互相轉(zhuǎn)換狀態(tài)空間圖傳教士野人問題（Missionaries&Cannibals，MC問題）

有三個(gè)傳教士M和三個(gè)野人C過河，只有一條能裝下兩個(gè)人的船，在河的一方或者船上，如果野人的人數(shù)大于傳教士的人數(shù)，那么傳教士就會(huì)有危險(xiǎn)，你能不能提出一種安全的渡河方法呢？狀態(tài)及其表示狀態(tài)：?jiǎn)栴}在某一時(shí)刻所處的“位置”，“情況”等根據(jù)問題所關(guān)心的因素，一般用向量形式表示，每一位表示一個(gè)因素0：右岸1：左岸初始狀態(tài)：(0,0,0)目標(biāo)狀態(tài)：(3,3,1)哪些操作能導(dǎo)致狀態(tài)變化？狀態(tài)可有多種表示方法：(左岸傳教士數(shù),右岸傳教士數(shù),左岸野人數(shù),右岸野人數(shù),船的位置)或(左岸傳教士數(shù),左岸野人數(shù),船的位置)狀態(tài)的轉(zhuǎn)換算子（算符，操作符）——使?fàn)顟B(tài)發(fā)生改變的操作MC問題中的算子將傳教士或野人運(yùn)到河對(duì)岸Move-1m1c-lr：將一個(gè)傳教士(m)一個(gè)野人(c)從左岸(l)運(yùn)到右岸(r)所有可能操作Move-1m1c-lrMove-1m1c-rlMove-2c-lrMove-2c-rl Move-2m-lr Move-2m-rlMove-1c-lr Move-1c-rl Move-1m-lrMove-1m-rl

傳教士野人問題狀態(tài)空間圖MC5.2.3解的搜索求解過程轉(zhuǎn)化為在狀態(tài)空間圖中搜索一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑問題圖的搜索無信息搜索（盲目搜索）有信息搜索（啟發(fā)式搜索）寬度優(yōu)先搜索深度優(yōu)先搜索A算法A*算法圖的一般搜索策略圖的搜索過程狀態(tài)：(城市名)算子：常德→益陽 益陽→常德 益陽汨羅 益陽寧鄉(xiāng) 益陽婁底

…？？？？必須記住哪些點(diǎn)走過了必須記住下一步還可以走哪些點(diǎn)深度優(yōu)先搜索必須記住從目標(biāo)返回的路徑圖的搜索過程必須記住哪些點(diǎn)走過了必須記住下一步還可以走哪些點(diǎn)必須記住從目標(biāo)返回的路徑OPEN表(記錄還沒有擴(kuò)展的點(diǎn))CLOSED表(記錄已經(jīng)擴(kuò)展的點(diǎn))每個(gè)表示狀態(tài)的節(jié)點(diǎn)結(jié)構(gòu)中必須有指向父節(jié)點(diǎn)的指針圖的一般搜索策略開始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入OPEN表，提供返回節(jié)點(diǎn)n的指針修改指針方向重排OPEN表失敗成功是是否否盲目搜索不同的搜索策略其搜索的效率是不同的盲目搜索又稱無信息搜索寬度優(yōu)先搜索深度優(yōu)先搜索特點(diǎn)搜索過程中不使用與問題有關(guān)的經(jīng)驗(yàn)信息不重排OPEN表搜索效率低不適合大空間的實(shí)際問題求解是什么影響了搜索的效率？八數(shù)碼難題1238456712384567（目標(biāo)狀態(tài)）（初始狀態(tài)）操作:空格上移，空格下移，空格左移，空格右移1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345寬度優(yōu)先搜索樹12384567271345612384567123845671238456712384567232425262782212384567123845671238456712384567123845671238456712384567141516171819202112384567123845671238456712384567123845671238456712384567123845671238456741238567深度優(yōu)先搜索樹(深度約束=4)123845671238456712384567123845671238456713456278能否預(yù)先知道下一步應(yīng)選擇誰？啟發(fā)式搜索有信息搜索搜索過程中利用與問題有關(guān)的經(jīng)驗(yàn)信息（啟發(fā)式信息）引入估價(jià)函數(shù)來估計(jì)節(jié)點(diǎn)位于解路徑上的“希望”，函數(shù)值越小“希望”越大搜索過程中按照估價(jià)函數(shù)的大小對(duì)OPEN表排序每次選擇估價(jià)函數(shù)值最小的節(jié)點(diǎn)作為下一步考察的節(jié)點(diǎn)估價(jià)函數(shù)是啟發(fā)式搜索中最重要的因素啟發(fā)式搜索和盲目搜索的不同就體現(xiàn)在對(duì)OPEN表按估價(jià)函數(shù)的大小排序不同的估價(jià)函數(shù)所體現(xiàn)出來的搜索效率不同，甚至天差地遠(yuǎn)不同的估價(jià)函數(shù)也決定了不同的啟發(fā)式搜索算法A算法特征：估價(jià)函數(shù)

f(x)=g(x)+h(x)從起始狀態(tài)到當(dāng)前狀態(tài)x的代價(jià)從當(dāng)前狀態(tài)x到目標(biāo)狀態(tài)的估計(jì)代價(jià)（啟發(fā)函數(shù)）雖提高了算法效率，但不能保證找到最優(yōu)解利用A*算法求解八數(shù)碼問題估價(jià)函數(shù)的定義f(x)=g(x)+h(x)g(x)：從初始狀態(tài)到x需要進(jìn)行的移動(dòng)操作的次數(shù)h(x)：？誰更接近目標(biāo)狀態(tài)？錯(cuò)放的棋子越少越好！=x狀態(tài)下錯(cuò)放的棋子數(shù)滿足限制條件123845671238456781324567h(x)=1h(x)=2h(x)=445631238456712384567123845671+31+51+51238456712384567123845672+42+32