五章節(jié)產(chǎn)生式系統(tǒng)課件_第1頁(yè)
五章節(jié)產(chǎn)生式系統(tǒng)課件_第2頁(yè)
五章節(jié)產(chǎn)生式系統(tǒng)課件_第3頁(yè)
五章節(jié)產(chǎn)生式系統(tǒng)課件_第4頁(yè)
五章節(jié)產(chǎn)生式系統(tǒng)課件_第5頁(yè)
已閱讀5頁(yè),還剩71頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、第五章 產(chǎn)生式系統(tǒng)產(chǎn)生式表示方法產(chǎn)生式系統(tǒng)基本原理產(chǎn)生式系統(tǒng)與圖搜索產(chǎn)生式系統(tǒng)應(yīng)用9/21/20221第五章 產(chǎn)生式系統(tǒng) 產(chǎn)生式系統(tǒng)的體系結(jié)構(gòu)是 實(shí)現(xiàn)圖搜索的理想程序結(jié)構(gòu),產(chǎn)生式已是人工智能系統(tǒng)的一種最典型最普遍的結(jié)構(gòu)形式。 許多專(zhuān)家系統(tǒng)和機(jī)器學(xué)習(xí)系統(tǒng)都是用產(chǎn)生式系統(tǒng)實(shí)現(xiàn)的。從結(jié)構(gòu)形式上看很多人工智能系統(tǒng)都是產(chǎn)生式系統(tǒng)。9/21/20222第五章 產(chǎn)生式系統(tǒng)產(chǎn)生式表示方法產(chǎn)生式系統(tǒng)基本原理產(chǎn)生式系統(tǒng)與圖搜索產(chǎn)生式系統(tǒng)應(yīng)用9/21/20223產(chǎn)生式表示法產(chǎn)生式產(chǎn)生式一詞是從波斯特機(jī)中借用來(lái)的。波斯特機(jī)是一種自動(dòng)機(jī),它是根據(jù)串替換規(guī)則提出的一種計(jì)算模型。其中的每一條規(guī)則就叫一個(gè)產(chǎn)生式。也稱(chēng)產(chǎn)生式規(guī)

2、則,簡(jiǎn)稱(chēng)規(guī)則。這里產(chǎn)生式就是前面討論過(guò)的操作、邏輯蘊(yùn)含式、推理規(guī)則以及各種關(guān)系(包含經(jīng)驗(yàn)性聯(lián)想)的一種邏輯抽象。 9/21/20224產(chǎn)生式表示法例:一條知識(shí)的原始形態(tài)是 R: ( (A B) (C D) (E F) G)=S 引入中間結(jié)論S1,S2,形成一些小型的產(chǎn)生式: R1: A B =S1 R2: C D =S1 R3: E F =S2 R4: S1 G =S R5: S1 S2 =S9/21/20226產(chǎn)生式表示法給定一組事實(shí)之后可用匹配技術(shù)尋找可用產(chǎn)生式,其基本思想是將已知事實(shí)代入產(chǎn)生式的前件,若前件為真,則該產(chǎn)生式是可用的。提高匹配效率的方法索引匹配。為狀態(tài)建立可用產(chǎn)生式索引表,

3、減少可用產(chǎn)生式搜索范圍。分層匹配。將產(chǎn)生式分成若干層或組,按一定特征進(jìn)行分層搜索。過(guò)濾匹配。邊匹配邊 按某些附加特征或參數(shù)對(duì)可用產(chǎn)生式進(jìn)行精選。9/21/20227產(chǎn)生式表示法在產(chǎn)生式系統(tǒng)中,從前提到結(jié)論通常也是一棵與或樹(shù)。合取,與節(jié)點(diǎn):一個(gè)產(chǎn)生式的前提包含了幾個(gè)事實(shí),那么它的結(jié)論對(duì)應(yīng)這些事實(shí)的合取。析取,或節(jié)點(diǎn):一個(gè)結(jié)論可以由多個(gè)產(chǎn)生式得到,則這個(gè)結(jié)論對(duì)應(yīng)這些產(chǎn)生式的析取。每個(gè)產(chǎn)生式系統(tǒng)都隱含著許多這樣的與或樹(shù)。9/21/20229產(chǎn)生式表示法F1P1F3F4F5F6BCDAP2P3P4P5F2事實(shí)中介事實(shí)B、C、D產(chǎn)生式規(guī)則P1、P2、P3、P4、P5結(jié)論9/21/202210產(chǎn)生式表示法

4、(例)例 三個(gè)聰明人問(wèn)題。古代有個(gè)國(guó)王想知道他的三個(gè)大王中誰(shuí)最聰明,就在他們每個(gè)人前額上都畫(huà)了一個(gè)點(diǎn),他們都能看到別人點(diǎn)的顏色,但看不到別人點(diǎn)的顏色。國(guó)王說(shuō),你們中間至少有一個(gè)人的點(diǎn)式白色的。于是重復(fù)地問(wèn)他們:“誰(shuí)知道自己點(diǎn)地顏色?”三位大臣們頭兩次都回答說(shuō)不知道。題目要求證明下一次他們?nèi)紩?huì)說(shuō)“知道”,并且所有的點(diǎn)都是白色。9/21/202211產(chǎn)生式表示法(例)分析: 這類(lèi)問(wèn)題的特點(diǎn)是有有限個(gè)受試者,每個(gè)人對(duì)問(wèn)題都只有部分了解,無(wú)法直接求解。但在推理過(guò)程中每個(gè)人又可以從別人那里獲得新的知識(shí),重新進(jìn)行推理??梢杂卯a(chǎn)生式來(lái)表達(dá)推理過(guò)程中所用到的各種知識(shí)。9/21/202212產(chǎn)生式表示法(例)

5、狀態(tài)集合表示: 用x1,x2,x3表示三個(gè)人點(diǎn)的顏色,1表示白色,0表示非白色。 X(x1,x2,x3)表示顏色分布狀態(tài)。 全部可能的狀態(tài)集合(可能界PW0):(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) 實(shí)際給定的狀態(tài)為現(xiàn)實(shí)界X0 (x10,x20,x30) 用排除法找到X0 。9/21/202213產(chǎn)生式表示法(例)排除過(guò)程:第一次,大臣只知道至少有一個(gè)人是白點(diǎn),排除X0(0,0,0)狀態(tài)。這時(shí)如果有人看到兩個(gè)非白點(diǎn),根據(jù)排除的狀態(tài)可推知自己是白點(diǎn)。第二次大臣根據(jù)沒(méi)有一個(gè)人知道自己點(diǎn)顏色的事實(shí)推知至少兩人為白

6、點(diǎn)。排除(0,0,1)(0,1,0)(1,0,0)狀態(tài)。這時(shí)如果有人看到一個(gè)非白點(diǎn),根據(jù)排除后得到的狀態(tài)可推知自己的點(diǎn)是白的。第三次,大臣們根據(jù)仍無(wú)人知道自己點(diǎn)顏色的新事實(shí)推知沒(méi)有一個(gè)非白點(diǎn)出現(xiàn),即X0(1,1,1)。于是三人都知道自己點(diǎn)的顏色是白的。9/21/202214產(chǎn)生式表示法(例)(1)(已知)(n=1) X0 (0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1);(2)(有人看見(jiàn)兩個(gè)非白點(diǎn))(n=1) (Si=2) =(Wi=1),(i=1,2,3,下同);(3)( i ) (Wi=1) (n=1) = (n=1) ;(4)

7、 (n=1) = ( i ) (Wi=1) ;(5) ( i ) (Wi=0) (n=1) = (n=2) ;(6) (n=2) X0 (0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1);(7) (有人看見(jiàn)一個(gè)非白點(diǎn))(n=2) (Si=1) =(Wi=1);(8) ( i ) (Wi=1) (n=2) = (n=2) ;(9) (n=2) = ( i ) (Wi=1);(10) ( i ) (Wi=0) (n=2) = (n=3);(11) (n=3) X0 (1,1,1);(12) (n=3) = ( i ) (Wi=1).9/21/202216產(chǎn)生式表示法(例

8、) 上述結(jié)果可以推廣到更一般的情況:設(shè)有m個(gè)大臣,國(guó)王說(shuō)至少有l(wèi)個(gè)人的點(diǎn)是白色的,則有下述產(chǎn)生式: (1) (n=l) X0 x|x中的白點(diǎn)數(shù)=l; (2) (n=l) (Si=2) =(Wi=1),(i=1,2,m,下同); (3)( i ) (Wi=1) (n=l) = (n=l) ; (4) (n=l) = ( i ) (Wi=l) ; (5)( i ) (Wi=0) (n=l) (l (n=l1) ; (6)( i ) (Wi=0) (n=l) (lm-1)= (nm)。 9/21/202217產(chǎn)生式系統(tǒng)基本原理組成和分類(lèi)運(yùn)行過(guò)程常用算法9/21/202219產(chǎn)生式系統(tǒng)基本原理(組成和

9、分類(lèi))產(chǎn)生式系統(tǒng)結(jié)構(gòu)產(chǎn)生式規(guī)則庫(kù)(知識(shí)庫(kù))推理機(jī)(控制)全局?jǐn)?shù)據(jù)庫(kù)9/21/202220產(chǎn)生式系統(tǒng)基本原理(組成和分類(lèi))組成全局?jǐn)?shù)據(jù)庫(kù)人工智能系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)中心。是一個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu),用來(lái)存放初始事實(shí)數(shù)據(jù)、中間結(jié)構(gòu)和最后結(jié)果。對(duì)應(yīng)敘述性知識(shí)。產(chǎn)生式規(guī)則庫(kù)作用在全局?jǐn)?shù)據(jù)庫(kù)上的一些規(guī)則的集合。每條規(guī)則都有一定的條件,若全局?jǐn)?shù)據(jù)庫(kù)中內(nèi)容滿(mǎn)足這些條件可調(diào)用這條規(guī)則。對(duì)應(yīng)過(guò)程性知識(shí)。推理機(jī)負(fù)責(zé)產(chǎn)生式規(guī)則的前提條件測(cè)試或匹配,規(guī)則的調(diào)度和選取,規(guī)則體的解釋和執(zhí)行。對(duì)應(yīng)控制性知識(shí)。9/21/202221產(chǎn)生式系統(tǒng)基本原理(組成和分類(lèi))例 旅行推銷(xiāo)員問(wèn)題。求從A城出發(fā),經(jīng)過(guò)其他城市一次且僅一次,最后回到A城的最

10、小費(fèi)用路線。城市之間的交通費(fèi)用標(biāo)在相應(yīng)的聯(lián)線上。建立產(chǎn)生式系統(tǒng)。BCADE713109656710109/21/202222產(chǎn)生式系統(tǒng)基本原理(組成和分類(lèi))(1)全局?jǐn)?shù)據(jù)庫(kù)(已訪問(wèn)過(guò)的城鎮(zhèn)名稱(chēng)序列)。約束條件是除城鎮(zhèn)A之外其他名稱(chēng)不得在序列中重復(fù)出現(xiàn);只有所有的名稱(chēng)都在序列中出現(xiàn)后,城鎮(zhèn)A才能重復(fù)出現(xiàn)。(2)規(guī)則集如下表所示。(3)推理: (A) (AB) (ABE) (4)終止條件序列始于A,終止于A,其中包含其他所有城鎮(zhèn)一次,且費(fèi)用最少。(5)各種搜索策略選擇規(guī)則,如廣度優(yōu)先搜索,最好優(yōu)先搜索等。R2R59/21/202223產(chǎn)生式系統(tǒng)基本原理(組成和分類(lèi))規(guī)則集規(guī)則動(dòng)作條件R1下一步到A

11、系列中包含所有城鎮(zhèn)時(shí)可用R2下一步到B每條規(guī)則只能使用一次,即序列中已有某城鎮(zhèn)時(shí),不能再使用相應(yīng)規(guī)則R3下一步到CR4下一步到DR5下一步到E9/21/202224產(chǎn)生式系統(tǒng)基本原理(組成和分類(lèi))分類(lèi)體系(尼爾遜)按搜索策略分不可挽回(irreversible)的產(chǎn)生式系統(tǒng)試探性的(Tentative)產(chǎn)生式系統(tǒng)回溯式(Backing)產(chǎn)生式系統(tǒng)圖搜索式(Graph Search)產(chǎn)生式系統(tǒng)按搜索方向分向前產(chǎn)生式系統(tǒng)(Forward Production System)向后產(chǎn)生式系統(tǒng)(Backward Production System)雙向產(chǎn)生式系統(tǒng)(Bidirectional Produc

12、tion System)兩種特殊的產(chǎn)生式系統(tǒng)可交換的(Commutative)產(chǎn)生式系統(tǒng)可分解的(Decomposable)產(chǎn)生式系統(tǒng)9/21/202226產(chǎn)生式系統(tǒng)基本原理組成和分類(lèi)運(yùn)行過(guò)程控制策略與常用算法9/21/202227產(chǎn)生式系統(tǒng)基本原理(運(yùn)行過(guò)程)產(chǎn)生式系統(tǒng)運(yùn)行過(guò)程實(shí)際的產(chǎn)生式系統(tǒng),目標(biāo)條件往往要經(jīng)過(guò)多步推理才能滿(mǎn)足或者證明問(wèn)題無(wú)解。產(chǎn)生式系統(tǒng)的運(yùn)行過(guò)程就是推理機(jī)不斷的運(yùn)用規(guī)則庫(kù)中的規(guī)則,作用于動(dòng)態(tài)數(shù)據(jù)庫(kù),不斷進(jìn)行推理并不斷檢測(cè)目標(biāo)條件是否被滿(mǎn)足的過(guò)程。產(chǎn)生式系統(tǒng)運(yùn)行過(guò)程是從初始事實(shí)出發(fā),尋求到達(dá)目標(biāo)條件的通路的過(guò)程。所以也是一個(gè)搜索的過(guò)程。9/21/202229產(chǎn)生式系統(tǒng)基本原

13、理組成和分類(lèi)運(yùn)行過(guò)程常用算法9/21/202230產(chǎn)生式系統(tǒng)基本原理(常用算法)推理方式正向推理 從初始事實(shí)數(shù)據(jù)出發(fā),正向使用規(guī)則進(jìn)行推理,朝目標(biāo)方向前進(jìn)。又稱(chēng)為前向推理、正向鏈、數(shù)據(jù)驅(qū)動(dòng)的推理。反向推理 從目標(biāo)出發(fā),反向使用規(guī)則進(jìn)行推理,朝初始事實(shí)或數(shù)據(jù)方向前進(jìn)。又稱(chēng)反向推理、反向鏈、目標(biāo)驅(qū)動(dòng)的推理。9/21/202231產(chǎn)生式系統(tǒng)基本原理(常用算法)正向推理算法步1 將初始事實(shí)/數(shù)據(jù)置入動(dòng)態(tài)數(shù)據(jù)庫(kù);步2 用動(dòng)態(tài)數(shù)據(jù)庫(kù)中的事實(shí)匹配目標(biāo)條件,若目標(biāo)條件滿(mǎn)足,推理成功,結(jié)束。步3 用規(guī)則庫(kù)中各規(guī)則的前提匹配動(dòng)態(tài)數(shù)據(jù)庫(kù)中的事實(shí),將匹配成功的規(guī)則組成待用規(guī)則集。步4 若待用規(guī)則集為空,則運(yùn)行失敗,退

14、出。步5 將待用規(guī)則集中各規(guī)則的結(jié)論加入動(dòng)態(tài)數(shù)據(jù)庫(kù),或者執(zhí)行其動(dòng)作,轉(zhuǎn)步2。9/21/202232產(chǎn)生式系統(tǒng)基本原理(常用算法)反向推理算法步1 將初始事實(shí)/數(shù)據(jù)置入動(dòng)態(tài)數(shù)據(jù)庫(kù),將目標(biāo)條件置入目標(biāo)鏈;步2 若目標(biāo)鏈為空,則推理成功,結(jié)束。步3 取出目標(biāo)鏈中第一個(gè)目標(biāo),用動(dòng)態(tài)數(shù)據(jù)庫(kù)中的事實(shí)同其匹配,若匹配成功,轉(zhuǎn)步2。步4 用規(guī)則集中的各規(guī)則的結(jié)論同該目標(biāo)匹配,若匹配成功,則33將第一個(gè)匹配成功且未用過(guò)的規(guī)則的前提作為新的目標(biāo),并取代原來(lái)的父目標(biāo)加入目標(biāo)鏈,轉(zhuǎn)步3。步5 若該目標(biāo)是初始目標(biāo),則推理失敗,退出。步6 將該目標(biāo)的父目標(biāo)移回目標(biāo)鏈,取代該目標(biāo)及其兄弟目標(biāo),轉(zhuǎn)步3。9/21/202233

15、產(chǎn)生式系統(tǒng)基本原理(常用算法)例:動(dòng)物識(shí)別系統(tǒng)的產(chǎn)生是系統(tǒng)描述及求解。規(guī)則:r1: IF 該動(dòng)物有毛發(fā) THEN 該動(dòng)物是哺乳動(dòng)物r2: IF 該動(dòng)物有奶 THEN 該動(dòng)物是哺乳動(dòng)物r3: IF 該動(dòng)物有羽毛 THEN 該動(dòng)物是鳥(niǎo)r4: IF 該動(dòng)物會(huì)飛 AND 會(huì)下蛋 THEN 該動(dòng)物是鳥(niǎo)r5: IF 該動(dòng)物吃肉 THEN 該動(dòng)物是食肉動(dòng)物r6: IF 該動(dòng)物有犬齒 AND 有爪 AND 眼盯前方 THEN 該動(dòng)物是食肉動(dòng)物動(dòng)物9/21/202234產(chǎn)生式系統(tǒng)基本原理(常用算法)r7: IF 該動(dòng)物是哺乳動(dòng)物 AND 有蹄 THEN 該動(dòng)物是有蹄類(lèi)動(dòng)物r8: IF 該動(dòng)物是哺乳動(dòng)物 AND

16、是嚼反芻動(dòng)物 THEN 該動(dòng)物是有蹄動(dòng)物r9: IF 該動(dòng)物是哺乳動(dòng)物 AND 是食肉動(dòng)物 AND 是黃褐色 AND 身上有暗斑點(diǎn) THEN 該動(dòng)物是金錢(qián)豹 r10:IF 該動(dòng)物是哺乳動(dòng)物 AND 是食肉動(dòng)物 AND 是黃褐色 AND 身上有黑色條紋 THEN 該動(dòng)物是虎r11:IF 該動(dòng)物是有蹄類(lèi)動(dòng)物 AND 有長(zhǎng)脖子 AND 有長(zhǎng)腿 AND 身上有暗斑點(diǎn) THEN 該動(dòng)物是長(zhǎng)頸鹿 r12:IF 該動(dòng)物有蹄類(lèi)動(dòng)物 AND 身上有黑色條紋 THEN 該動(dòng)物是斑馬9/21/202235產(chǎn)生式系統(tǒng)基本原理(常用算法)r13: IF 該動(dòng)物是鳥(niǎo) AND 有長(zhǎng)脖子 AND 有長(zhǎng)腿 AND 不會(huì)飛 AN

17、D 有黑白二色 THEN 該動(dòng)物是鴕鳥(niǎo)r14: IF 該動(dòng)物是鳥(niǎo) AND 會(huì)游泳 AND 不會(huì)飛 AND 有黑白二色 THEN 該動(dòng)物是企鵝r15:IF 該動(dòng)物是鳥(niǎo) AND 善飛 THEN 該動(dòng)物是信天翁9/21/202236產(chǎn)生式系統(tǒng)基本原理(常用算法)初始事實(shí): f1:某動(dòng)物有毛發(fā)。 f2:吃肉。 f3:黃褐色。 f4:有黑色條紋目標(biāo)條件為:該動(dòng)物為什么?9/21/202237產(chǎn)生式系統(tǒng)基本原理(常用算法)9/21/202238產(chǎn)生式系統(tǒng)基本原理(常用算法)9/21/202239第五章 產(chǎn)生式系統(tǒng)產(chǎn)生式表示方法產(chǎn)生式系統(tǒng)基本原理產(chǎn)生式系統(tǒng)與圖搜索產(chǎn)生式系統(tǒng)應(yīng)用9/21/202240產(chǎn)生式系

18、統(tǒng)與圖搜索產(chǎn)生式系統(tǒng)圖搜索初始事實(shí)數(shù)據(jù)初始節(jié)點(diǎn)目標(biāo)條件目標(biāo)節(jié)點(diǎn)產(chǎn)生式規(guī)則狀態(tài)轉(zhuǎn)換規(guī)則、問(wèn)題變換規(guī)則規(guī)則庫(kù)操作集動(dòng)態(tài)數(shù)據(jù)庫(kù)節(jié)點(diǎn)(狀態(tài)/問(wèn)題)控制策略搜索策略產(chǎn)生式系統(tǒng)與圖搜索對(duì)比9/21/202241第五章 產(chǎn)生式系統(tǒng)產(chǎn)生式表示方法產(chǎn)生式系統(tǒng)基本原理產(chǎn)生式系統(tǒng)與圖搜索產(chǎn)生式系統(tǒng)應(yīng)用9/21/202242產(chǎn)生式系統(tǒng)的應(yīng)用實(shí)例基于消解原理的產(chǎn)生式系統(tǒng)基于自然演繹法的產(chǎn)生式系統(tǒng)基于專(zhuān)用知識(shí)的產(chǎn)生式系統(tǒng)9/21/202243基于消解原理的產(chǎn)生式系統(tǒng)消解原理的產(chǎn)生式系統(tǒng)全局?jǐn)?shù)據(jù)庫(kù):子句集合S產(chǎn)生式規(guī)則集:一般形式是消解控制系統(tǒng)終止條件:NIL S搜索策略:是個(gè)可交換的系統(tǒng),使用各個(gè)具體的消解與先后順序無(wú)關(guān)

19、,采用不可挽回的控制策略。9/21/202244基于消解原理的產(chǎn)生式系統(tǒng)過(guò)程RESOLUTION步1 CLAUSES S;步2 until NIL是CLAUSES中的元素為止,do;步3 begin步4 在CLAUSES中選取兩個(gè)可消解的子句Ci和Cj;步5 計(jì)算Ci和Cj的消解式Rij;步6 把Rij并入到CLAUSES中;步7 end。9/21/202245基于消解原理的產(chǎn)生式系統(tǒng)控制策略廣度優(yōu)先搜索策略 相當(dāng)于水平浸透法。完備的但效率低。支持集消解策略 反向產(chǎn)生式系統(tǒng)。完備的,但不一定得到最優(yōu)解。啟發(fā)式搜索策略 利用消解原理求解問(wèn)題的經(jīng)驗(yàn),設(shè)計(jì)啟發(fā)函數(shù)。9/21/202246補(bǔ)充:解樹(shù)代

20、換的一致性(一)設(shè)有一個(gè)代換集u1,u2,,un,其中每個(gè)ui都是一個(gè)代換ti1/ vi1, ti2/ vi2,, tim(i)/ vim(i) 又設(shè)U1v11, , vim(1),, vn1, , vnm(n)(所有下邊的變量) U2t11, , tim(1),, tn1, , tnm(n) (所有上邊的項(xiàng))定義:代換集u1,u2,,un是一致的,當(dāng)且僅當(dāng)U1和U2是可合一的。定義:u1,u2,,un的合一復(fù)合U是U1和U2的最一般合一。解樹(shù)上所有代換是一致的,則該問(wèn)題有解,最后的代換是合一復(fù)合U。9/21/202247補(bǔ)充:解樹(shù)代換的一致性(二)例設(shè)有一個(gè)代換集u1,u2,其中 u1f(g

21、(x1)/x3,f(x2)/x4U1和U2是可合一的,其最一般合一是: Uf(g(x1)/x3,f(g(x1)/x4, g(x1)/x2u2x4/x3,g(x1)/x2U1=x3, x4, x3 ,x2U2=f(g(x1) f(x2) ,x4 ,g (x1)9/21/202248產(chǎn)生式系統(tǒng)的應(yīng)用實(shí)例基于消解原理的產(chǎn)生式系統(tǒng)基于自然演繹法的產(chǎn)生式系統(tǒng)基于專(zhuān)用知識(shí)的產(chǎn)生式系統(tǒng)9/21/202249基于自然演繹法的產(chǎn)生式系統(tǒng)消解原理產(chǎn)生式系統(tǒng)特點(diǎn)優(yōu)點(diǎn):形式單一,處理規(guī)則簡(jiǎn)單。缺點(diǎn):太一般化,丟失了原公式重要語(yǔ)義信息,對(duì)應(yīng)用啟發(fā)搜索系統(tǒng)和人機(jī)交互帶來(lái)了困難;組合爆炸,難以直接使用。自然演繹法保持專(zhuān)家知

22、識(shí)原始的邏輯形態(tài),保留了控制信息。推理規(guī)則復(fù)雜,但便于設(shè)計(jì)啟發(fā)函數(shù)。推理過(guò)程直觀,便于理解。9/21/202250基于自然演繹法的產(chǎn)生式系統(tǒng)規(guī)則基產(chǎn)生式系統(tǒng)事實(shí) 用非蘊(yùn)含形式謂詞公式表示,規(guī)則 用蘊(yùn)含形式表示F規(guī)則 前向推理系統(tǒng)中應(yīng)用B規(guī)則 后向推理系統(tǒng)中應(yīng)用 9/21/2022511、基于規(guī)則的向前推理系統(tǒng)(一)基本原理 從代表初始事實(shí)的謂詞公式F0出發(fā)通過(guò)一組F規(guī)則F1,F(xiàn)2來(lái)證明目標(biāo)公式G成立。初始事實(shí)F0任意謂詞公式前束范式表示;運(yùn)用Skolem函數(shù)消去存在量詞;省去全稱(chēng)量詞;得到任意與或型事實(shí)表達(dá)式,改名,使各主要合取項(xiàng)的變量應(yīng)不相同。與或圖表示:析取部分用與節(jié)點(diǎn)表示合取部分用或節(jié)點(diǎn)

23、表示9/21/2022521、基于規(guī)則的向前推理系統(tǒng)(二)F規(guī)則形如 L=WL為單一文字W為任意與或型謂詞公式;W中用Skolem消去存在量詞,變?cè)皇苋Q(chēng)量詞約束;改名,使不同規(guī)則具有不同變?cè)?guī)則變?cè)c事實(shí)變?cè)膊煌?。?fù)雜規(guī)則化為簡(jiǎn)單規(guī)則。9/21/2022531、基于規(guī)則的向前推理系統(tǒng)(三)終止條件用目標(biāo)謂詞G表示G為文字的析取式(文字都為目標(biāo)文字);用Skolem函數(shù)消去全稱(chēng)量詞;消去存在量詞;改名,使同一變?cè)诟髂繕?biāo)文字、規(guī)則、事實(shí)中最多出現(xiàn)一次。推理基本過(guò)程不斷將規(guī)則L=W利用匹配弧連接在與或圖的L葉結(jié)點(diǎn)上;目標(biāo)文字G本身可看作G =G作用在與或圖上;一致解樹(shù)各個(gè)葉結(jié)點(diǎn)都終止在目標(biāo)

24、節(jié)點(diǎn),成功終止。9/21/2022541、基于規(guī)則的向前推理系統(tǒng)(四)例:命題邏輯中一個(gè)定理證明問(wèn)題構(gòu)造一個(gè)向前的規(guī)則基推理系統(tǒng)來(lái)求解。事實(shí) F0:規(guī)則 F1: F2 : F3:目標(biāo) G:9/21/2022551、基于規(guī)則的向前推理系統(tǒng)(五)9/21/2022561、基于規(guī)則的向前推理系統(tǒng)(六)例:謂詞邏輯中一個(gè)定理證明問(wèn)題 自然數(shù)都是大于0的整數(shù) 所有整數(shù)不是偶數(shù)就是奇數(shù) 偶數(shù)的一半是整數(shù) 所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。構(gòu)造一個(gè)向前的規(guī)則基推理系統(tǒng)來(lái)求解9/21/2022571、基于規(guī)則的向前推理系統(tǒng)(六)一、預(yù)處理F0為事實(shí)表達(dá)式方法:(1)將公式化稱(chēng)任意與或型前束范式,每個(gè)否定詞

25、僅管 轄一個(gè)謂詞;(2)用Skolem函數(shù)去掉存在量詞并改名使主合取項(xiàng)之間無(wú)相同變量;(3)隱去全稱(chēng)量詞。9/21/2022581、基于規(guī)則的向前推理系統(tǒng)(七)二、預(yù)處理F1 F2為F規(guī)則方法:(1)暫時(shí)消去;(2)將公式化為前束范式,一個(gè)否定詞管轄一個(gè)謂詞;(3)用Skolem函數(shù)消去存在量詞;(4)改變變?cè)Q(chēng)使其與其他公式不同;(5)恢復(fù)蘊(yùn)含式。9/21/2022591、基于規(guī)則的向前推理系統(tǒng)(八)三、處理目標(biāo)G:(1)用Skolem函數(shù)消去全稱(chēng)量詞;(2)隱去存在量詞。9/21/2022601、基于規(guī)則的向前推理系統(tǒng)(九)9/21/2022612、基于規(guī)則的向后推理系統(tǒng)(一)基本原理從

26、代表目標(biāo)的謂詞公式出發(fā),通過(guò)一組B規(guī)則證明事實(shí)公式成立。目標(biāo)任意謂詞公式,Skolem函數(shù)消去全稱(chēng)量詞;隱去存在量詞;改名,公式中主要析取項(xiàng)的變?cè)獞?yīng)不相同。與或圖表示:與節(jié)點(diǎn)對(duì)應(yīng)合取;或節(jié)點(diǎn)對(duì)應(yīng)析取;根節(jié)點(diǎn)上任何后裔都為子目標(biāo)。9/21/2022622、基于規(guī)則的向后推理系統(tǒng)(二)B規(guī)則W=L;L為單一文字;W為任意與或型謂詞公式,變?cè)苋Q(chēng)量詞約束,變?cè)拿?fù)雜規(guī)則化為簡(jiǎn)單規(guī)則。9/21/2022632、基于規(guī)則的向后推理系統(tǒng)(三)推理過(guò)程目標(biāo)謂詞公式的與或圖中有一節(jié)點(diǎn)標(biāo)為L(zhǎng),且可與L合一,則可將規(guī)則作用在該與或樹(shù)上。其結(jié)果使在與或樹(shù)上從L引出一條匹配弧,連接一個(gè)以L為根,表示W(wǎng)的與或圖,

27、 為L(zhǎng)與L的最一般合一。終止條件當(dāng)與或樹(shù)的一致解樹(shù)各個(gè)葉節(jié)點(diǎn)都終止在事實(shí)節(jié)點(diǎn)時(shí),此產(chǎn)生式系統(tǒng)成功終止。9/21/2022642、基于規(guī)則的向后推理系統(tǒng)(四)例:基于規(guī)則的向后推理系統(tǒng)。給定事實(shí)為: Fido是狗 Fido不會(huì)吠叫 Fido會(huì)搖尾巴 Myetle會(huì)咪咪叫9/21/2022652、基于規(guī)則的向后推理系統(tǒng)(五)已知規(guī)則為目標(biāo):存在貓不怕狗的現(xiàn)象,即9/21/2022662、基于規(guī)則的向后推理系統(tǒng)(六)9/21/2022673、F系統(tǒng)和B系統(tǒng)的對(duì)比(一)對(duì)比項(xiàng)目F系統(tǒng)B系統(tǒng)使用條件1、事實(shí)謂詞可為任意形式;2、規(guī)則的形式L=W;3、目標(biāo)謂詞公式是文字的析取。1、事實(shí)謂詞公式是文字的合取

28、式;2、規(guī)則的形式是W=L;3、目標(biāo)謂詞公式是任意形式。預(yù)處理用Skolem函數(shù)消去事實(shí)和規(guī)則謂詞公式中的存在謂詞;略去全稱(chēng)量詞。用Skolem函數(shù)消去目標(biāo)謂詞公式中的全稱(chēng)量詞;略去存在量詞。用Skolem函數(shù)消去目標(biāo)謂詞公式中的全稱(chēng)量詞;略去存在量詞。用Skolem函數(shù)消去事實(shí)和規(guī)則謂詞公式中的存在謂詞;略去全稱(chēng)量詞。9/21/2022683、F系統(tǒng)和B系統(tǒng)的對(duì)比(一)對(duì)比項(xiàng)目F系統(tǒng)B系統(tǒng)初始數(shù)據(jù)庫(kù)事實(shí)謂詞公式,用與或樹(shù)表示目標(biāo)謂詞公式,用與或樹(shù)表示推理過(guò)程事實(shí)目標(biāo)匹配時(shí)注意:變量代換, 以W代替L目標(biāo)事實(shí)匹配時(shí)注意:變量代換, 以W代替L終止條件得到目標(biāo)的一致解樹(shù)得到事實(shí)的一致解樹(shù)子句文字的析取文字的合取子句集子句的合取子句的析取9/21/202269產(chǎn)生式系統(tǒng)的應(yīng)用實(shí)例基于消解原理的產(chǎn)生式系統(tǒng)基于自然演繹法的產(chǎn)生式系統(tǒng)基于專(zhuān)用知識(shí)的產(chǎn)生式系統(tǒng)9/21/202270基于專(zhuān)用知識(shí)的產(chǎn)生式系統(tǒng)(一)例機(jī)器人完成食品裝袋作業(yè)的產(chǎn)生式系統(tǒng)BAGGER。全局?jǐn)?shù)據(jù)庫(kù):記錄階段信息(核對(duì)訂貨/大件物品裝袋/中 件物品裝袋/小件物品裝袋/裝

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論