基于產(chǎn)生式規(guī)則的機(jī)器推理.ppt

1、第6章 基于產(chǎn)生式規(guī)則的機(jī)器推理,2020/8/16,人工智能,2,第6章基于產(chǎn)生式規(guī)則的機(jī)器推理,6.1 產(chǎn)生式規(guī)則 6.2 產(chǎn)生式系統(tǒng),2020/8/16,人工智能,3,6.1 產(chǎn)生式規(guī)則,6.1.1 產(chǎn)生式規(guī)則 6.1.2 基于產(chǎn)生式規(guī)則的推理模式,2020/8/16,人工智能,4,6.1.1產(chǎn)生式規(guī)則（1）,產(chǎn)生式 產(chǎn)生式（Production）一詞從波斯特機(jī)中借用來的。波斯特機(jī)是一種自動(dòng)機(jī)，它是根據(jù)串替換規(guī)則提出的一種計(jì)算模型。其中的每一條規(guī)則就叫一個(gè)產(chǎn)生式。也稱產(chǎn)生式規(guī)則，簡(jiǎn)稱規(guī)則。 這里產(chǎn)生式就是前面討論過的操作（二階梵塔問題，猴子摘香蕉問題等）、邏輯蘊(yùn)含式、推理規(guī)則以及各種關(guān)系

2、（包含經(jīng)驗(yàn)性聯(lián)想）的一種邏輯抽象。,2020/8/16,人工智能,5,6.1.1產(chǎn)生式規(guī)則（2）,產(chǎn)生式的一般形式為： 前件后件（情況行為） 前件是前提，規(guī)則的執(zhí)行條件。 后件是結(jié)論或動(dòng)作，規(guī)則體。 產(chǎn)生式規(guī)則的語義：如果前提滿足，則可得結(jié)論或者執(zhí)行相應(yīng)的動(dòng)作，即后件由前件觸發(fā)。 一個(gè)產(chǎn)生式規(guī)則就是一條知識(shí)，用產(chǎn)生式不僅可以進(jìn)行推理，也可以實(shí)現(xiàn)操作。,2020/8/16,人工智能,6,6.1.1產(chǎn)生式規(guī)則（3）,產(chǎn)生式規(guī)則例子 如果銀行存款利率下調(diào)，那么股票價(jià)格上漲。 如果爐溫超過上限，則立即關(guān)閉風(fēng)門。 如果發(fā)燒、嘔吐并且出現(xiàn)黃疸，那么得了肝炎。（0.7） 如果鍵盤突然失靈，且屏幕上出現(xiàn)怪字符

3、，則是病毒發(fā)作。,2020/8/16,人工智能,7,6.1.1產(chǎn)生式規(guī)則（例）,例 三個(gè)聰明人問題。古代有個(gè)國王想知道他的三個(gè)大臣中誰最聰明，就在他們每個(gè)人前額上都畫了一個(gè)點(diǎn)，他們都能看到別人點(diǎn)的顏色，但看不到自己點(diǎn)的顏色。國王說，你們中間至少有一個(gè)人的點(diǎn)是白色的。于是重復(fù)地問他們：“誰知道自己點(diǎn)的顏色？”三位大臣們頭兩次都回答說不知道。題目要求證明下一次他們?nèi)紩?huì)說“知道”，并且所有的點(diǎn)都是白色。,2020/8/16,人工智能,8,6.1.1產(chǎn)生式規(guī)則（例）,分析： 這類問題的特點(diǎn)是有有限個(gè)受試者，每個(gè)人對(duì)問題都只有部分了解，無法直接求解。但在推理過程中每個(gè)人又可以從別人那里獲得新的知識(shí)，重

4、新進(jìn)行推理?？梢杂卯a(chǎn)生式來表達(dá)推理過程中所用到的各種知識(shí)。,2020/8/16,人工智能,9,6.1.1產(chǎn)生式規(guī)則（例）,狀態(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 。,2020/8/16,人工智能,10,6.1.1產(chǎn)生式規(guī)則（例）,排除過程： 第一次，大臣只知道至少有一個(gè)人是白

5、點(diǎn)，排除X0=(0,0,0)狀態(tài)。這時(shí)如果有人看到兩個(gè)非白點(diǎn)，根據(jù)排除的狀態(tài)可推知自己是白點(diǎn)。 第二次大臣根據(jù)沒有一個(gè)人知道自己點(diǎn)顏色的事實(shí)推知至少兩人為白點(diǎn)。排除(0,0,1)(0,1,0)(1,0,0)狀態(tài)。這時(shí)如果有人看到一個(gè)非白點(diǎn)，根據(jù)排除后得到的狀態(tài)可推知自己的點(diǎn)是白的。 第三次，大臣們根據(jù)仍無人知道自己點(diǎn)顏色的新事實(shí)推知沒有一個(gè)非白點(diǎn)出現(xiàn)，即X0=(1,1,1)。于是三人都知道自己點(diǎn)的顏色是白的。,2020/8/16,人工智能,11,6.1.1產(chǎn)生式規(guī)則（例）,引入中介狀態(tài)并定義下述符號(hào)： Si i大臣看到的非白點(diǎn)數(shù)； Wi i大臣猜出自己點(diǎn)的顏色否。如果他宣布已知道自己點(diǎn)的顏色，

6、為1，否則為0； nX0中白點(diǎn)的個(gè)數(shù)。,2020/8/16,人工智能,12,6.1.1產(chǎn)生式規(guī)則（例）,(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) (n=1) (Si=2) =(Wi=1),(i=1,2,3,下同)； (3)( i ) (Wi=1) (n=1) = (n=1) ； (4) (n=1) = ( i ) (Wi=1) ； (5) ( i ) (Wi=0) (n=1) = (n=2) ; (6) (n=2) X0 (0,1,1),(1,0,1),(1,1,0),(1,1,1)； (

7、7) (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).,2020/8/16,人工智能,13,6.1.1產(chǎn)生式規(guī)則（例）,上述結(jié)果可以推廣到更一般的情況：設(shè)有m個(gè)大臣，國王說至少有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=

8、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)。,2020/8/16,人工智能,14,6.1.2基于產(chǎn)生式規(guī)則的推理模式,A B A B 把有前提的操作和邏輯推理統(tǒng)稱為推理，產(chǎn)生式系統(tǒng)中的推理是更廣義的推理。,2020/8/16,人工智能,15,6.2產(chǎn)生式系統(tǒng),6.2.1系統(tǒng)結(jié)構(gòu) 6.2.2運(yùn)行過程 6.2.3控制策略常用算法 6.2.4程序?qū)崿F(xiàn)* 6.2.5產(chǎn)生式

9、系統(tǒng)與問題求解,2020/8/16,人工智能,16,6.2.1系統(tǒng)結(jié)構(gòu)（1）,產(chǎn)生式系統(tǒng)結(jié)構(gòu),產(chǎn)生式規(guī)則庫,推理機(jī),全局?jǐn)?shù)據(jù)庫,2020/8/16,人工智能,17,6.2.1系統(tǒng)結(jié)構(gòu)（2）,組成 產(chǎn)生式規(guī)則庫作用在全局?jǐn)?shù)據(jù)庫上的一些規(guī)則的集合。每條規(guī)則都有一定的條件，若全局?jǐn)?shù)據(jù)庫中內(nèi)容滿足這些條件可調(diào)用這條規(guī)則。一般可形成一個(gè)稱為推理網(wǎng)絡(luò)的結(jié)構(gòu)圖。對(duì)應(yīng)過程性知識(shí)。 推理機(jī)負(fù)責(zé)產(chǎn)生式規(guī)則的前提條件測(cè)試或匹配，規(guī)則的調(diào)度和選取，規(guī)則體的解釋和執(zhí)行。即推理機(jī)實(shí)施推理，并對(duì)推理進(jìn)行控制，它也是規(guī)則的解釋程序。對(duì)應(yīng)控制性知識(shí)。 全局?jǐn)?shù)據(jù)庫人工智能系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)中心。是一個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，用來存放初始事實(shí)數(shù)

10、據(jù)、中間結(jié)果和最后結(jié)果。對(duì)應(yīng)敘述性知識(shí)。,2020/8/16,人工智能,18,6.2.1系統(tǒng)結(jié)構(gòu)（3）,例 旅行推銷員問題。求從A城出發(fā)，經(jīng)過其他城市一次且僅一次，最后回到A城的最小費(fèi)用路線。城市之間的交通費(fèi)用標(biāo)在相應(yīng)的聯(lián)線上。建立產(chǎn)生式系統(tǒng)。,2020/8/16,人工智能,19,6.2.1系統(tǒng)結(jié)構(gòu)（4）,（1）全局?jǐn)?shù)據(jù)庫（已訪問過的城鎮(zhèn)名稱序列）。約束條件是除城鎮(zhèn)A之外其他名稱不得在序列中重復(fù)出現(xiàn)；只有所有的名稱都在序列中出現(xiàn)后，城鎮(zhèn)A才能重復(fù)出現(xiàn)。 （2）規(guī)則集如下表所示。 （3）推理： （A） （AB） （ABE） （4）終止條件序列始于A，終止于A，其中包含其他所有城鎮(zhèn)一次，且費(fèi)用最少

11、。 （5）各種搜索策略選擇規(guī)則，如廣度優(yōu)先搜索，最好優(yōu)先搜索等。,R2,R5,2020/8/16,人工智能,20,6.2.1系統(tǒng)結(jié)構(gòu)（5）,規(guī)則集,2020/8/16,人工智能,21,6.2.1系統(tǒng)結(jié)構(gòu)（6）,與一般分級(jí)組織的計(jì)算機(jī)軟件相比具有特點(diǎn)： 全局?jǐn)?shù)據(jù)庫的內(nèi)容可以為所有規(guī)則所訪問，沒有任何部分是專為某一規(guī)則建立的，這種特性便于模仿智能行為中的強(qiáng)數(shù)據(jù)驅(qū)動(dòng)。 規(guī)則本身不調(diào)用其他規(guī)則。規(guī)則之間的聯(lián)系必須通過全局?jǐn)?shù)據(jù)庫聯(lián)系。 全局?jǐn)?shù)據(jù)庫、規(guī)則和推理機(jī)之間相對(duì)獨(dú)立，這種積木式結(jié)構(gòu)便于整個(gè)系統(tǒng)增加和修改知識(shí)。,2020/8/16,人工智能,22,6.2.2產(chǎn)生式系統(tǒng)的運(yùn)行過程（1）,推理機(jī)一次運(yùn)行

12、過程,2020/8/16,人工智能,23,6.2.2產(chǎn)生式系統(tǒng)的運(yùn)行過程（2）,產(chǎn)生式系統(tǒng)運(yùn)行過程 實(shí)際的產(chǎn)生式系統(tǒng)，目標(biāo)條件往往要經(jīng)過多步推理才能滿足或者證明問題無解。 產(chǎn)生式系統(tǒng)的運(yùn)行過程就是推理機(jī)不斷的運(yùn)用規(guī)則庫中的規(guī)則，作用于動(dòng)態(tài)數(shù)據(jù)庫，不斷進(jìn)行推理并不斷檢測(cè)目標(biāo)條件是否被滿足的過程。 產(chǎn)生式系統(tǒng)運(yùn)行過程是從初始事實(shí)出發(fā)，尋求到達(dá)目標(biāo)條件的通路的過程。所以也是一個(gè)搜索的過程。,2020/8/16,人工智能,24,6.2.3控制策略與常用算法（1）,推理方式 正向推理 從初始事實(shí)數(shù)據(jù)出發(fā)，正向使用規(guī)則進(jìn)行推理，朝目標(biāo)方向前進(jìn)。又稱為前向推理、正向鏈、數(shù)據(jù)驅(qū)動(dòng)的推理。 反向推理從目標(biāo)出發(fā)，

13、反向使用規(guī)則進(jìn)行推理，朝初始事實(shí)或數(shù)據(jù)方向前進(jìn)。又稱反向推理、反向鏈、目標(biāo)驅(qū)動(dòng)的推理。,2020/8/16,人工智能,25,6.2.3控制策略與常用算法（2）,正向推理算法一 步1 將初始事實(shí)/數(shù)據(jù)置入動(dòng)態(tài)數(shù)據(jù)庫； 步2 用動(dòng)態(tài)數(shù)據(jù)庫中的事實(shí)匹配目標(biāo)條件，若目標(biāo)條件滿足，推理成功，結(jié)束。 步3 用規(guī)則庫中各規(guī)則的前提匹配動(dòng)態(tài)數(shù)據(jù)庫中的事實(shí)，將匹配成功的規(guī)則組成待用規(guī)則集。 步4 若待用規(guī)則集為空，則運(yùn)行失敗，退出。 步5 將待用規(guī)則集中各規(guī)則的結(jié)論加入動(dòng)態(tài)數(shù)據(jù)庫，或者執(zhí)行其動(dòng)作，轉(zhuǎn)步2。,2020/8/16,人工智能,26,6.2.3控制策略與常用算法（3）,若把動(dòng)態(tài)數(shù)據(jù)庫的每一個(gè)狀態(tài)作為一個(gè)

14、節(jié)點(diǎn)的話，則上述推理過程就是一個(gè)從初始狀態(tài)到目標(biāo)狀態(tài)的狀態(tài)圖搜索過程。 如果把動(dòng)態(tài)數(shù)據(jù)庫中的每一個(gè)事實(shí)/數(shù)據(jù)作為一個(gè)節(jié)點(diǎn)的話，則上述推理過程就是一個(gè)自底向上的與或樹搜索過程。,2020/8/16,人工智能,27,6.2.3控制策略與常用算法（4）,反向推理算法 步1 將初始事實(shí)/數(shù)據(jù)置入動(dòng)態(tài)數(shù)據(jù)庫，將目標(biāo)條件置入目標(biāo)鏈； 步2 若目標(biāo)鏈為空，則推理成功，結(jié)束。 步3 取出目標(biāo)鏈中第一個(gè)目標(biāo)，用動(dòng)態(tài)數(shù)據(jù)庫中的事實(shí)同其匹配，若匹配成功，轉(zhuǎn)步2。 步4 用規(guī)則集中的各規(guī)則的結(jié)論同該目標(biāo)匹配，若匹配成功，則將第一個(gè)匹配成功且未用過的規(guī)則的前提作為新的目標(biāo)，并取代原來的父目標(biāo)加入目標(biāo)鏈，轉(zhuǎn)步3。 步5

15、若該目標(biāo)是初始目標(biāo)，則推理失敗，退出。 步6 將該目標(biāo)的父目標(biāo)移回目標(biāo)鏈，取代該目標(biāo)及其兄弟目標(biāo)，轉(zhuǎn)步3。,2020/8/16,人工智能,28,6.2.3控制策略與常用算法（5）,在產(chǎn)生式系統(tǒng)中，從前提到結(jié)論的產(chǎn)生式規(guī)則通常也是一棵與或樹。 合取，與節(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)都隱含著許多這樣的與或樹。,2020/8/16,人工智能,29,6.2.3控制策略與常用算法（6）,事實(shí),中介事實(shí) B、C、D,產(chǎn)生式規(guī)則 P1、P2、P3、P4、P5,結(jié)論,2020/

16、8/16,人工智能,30,6.2.3控制策略與常用算法（7）,例6.1：動(dò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)物是鳥 r4： IF 該動(dòng)物會(huì)飛 AND 會(huì)下蛋 THEN 該動(dòng)物是鳥 r5： IF 該動(dòng)物吃肉 THEN 該動(dòng)物是食肉動(dòng)物 r6： IF 該動(dòng)物有犬齒 AND 有爪 AND 眼盯前方 THEN 該動(dòng)物是食肉動(dòng)物動(dòng)物,2020/8/16,人工智能,31,6.2.3控制策略與常用算法（8）,r7： IF 該動(dòng)物是哺乳動(dòng)物 AND

17、有蹄 THEN 該動(dòng)物是有蹄類動(dòng)物 r8： IF 該動(dòng)物是哺乳動(dòng)物 AND 是嚼反芻動(dòng)物 THEN 該動(dòng)物是有蹄動(dòng)物 r9： IF 該動(dòng)物是哺乳動(dòng)物 AND 是食肉動(dòng)物 AND 是黃褐色 AND 身上有暗斑點(diǎn) THEN 該動(dòng)物是金錢豹 r10： IF 該動(dòng)物是哺乳動(dòng)物 AND 是食肉動(dòng)物 AND 是黃褐色 AND 身上有黑色條紋 THEN 該動(dòng)物是虎,2020/8/16,人工智能,32,6.2.3控制策略與常用算法（9）,r11： IF 該動(dòng)物是有蹄類動(dòng)物 AND 有長(zhǎng)脖子 AND 有長(zhǎng)腿 AND 身上有暗斑點(diǎn) THEN 該動(dòng)物是長(zhǎng)頸鹿 r12： IF 該動(dòng)物有蹄類動(dòng)物 AND 身上有黑色條紋

18、 THEN 該動(dòng)物是斑馬 r13： IF 該動(dòng)物是鳥 AND 有長(zhǎng)脖子 AND 有長(zhǎng)腿 AND 不會(huì)飛 AND 有黑白二色 THEN 該動(dòng)物是鴕鳥,2020/8/16,人工智能,33,6.2.3控制策略與常用算法（10）,r14： IF 該動(dòng)物是鳥 AND 會(huì)游泳 AND 不會(huì)飛 AND 有黑白二色 THEN 該動(dòng)物是企鵝 r15：IF 該動(dòng)物是鳥 AND 善飛 AND 不怕風(fēng)浪 THEN 該動(dòng)物是海燕,2020/8/16,人工智能,35,6.2.3控制策略與常用算法（12）,初始事實(shí)： f1：某動(dòng)物有毛發(fā)。 f2：吃肉。 f3：黃褐色。 f4：有黑色條紋 目標(biāo)條件為：該動(dòng)物為什么？,2020

19、/8/16,人工智能,36,6.2.3控制策略與常用算法（13）,2020/8/16,人工智能,37,6.2.3控制策略與常用算法（14）,例6.2 使用反向推理算法,2020/8/16,人工智能,38,6.2.3控制策略與常用算法（15）,3 沖突消解策略 給定一組事實(shí)之后可用匹配技術(shù)尋找可用產(chǎn)生式，其基本思想是將已知事實(shí)代入產(chǎn)生式的前件，若前件為真，則該產(chǎn)生式是可用的。 提高匹配效率的方法 索引匹配。為狀態(tài)建立可用產(chǎn)生式索引表，減少可用產(chǎn)生式搜索范圍。 分層匹配。將產(chǎn)生式分成若干層或組，按一定特征進(jìn)行分層搜索。 過濾匹配。邊匹配邊 按某些附加特征或參數(shù)對(duì)可用產(chǎn)生式進(jìn)行精選。,2020/8/16,人工智能,39,6.2.3控制策略與常用算法（2）,正向推理算法二 步1 將初始事實(shí)/數(shù)據(jù)置入動(dòng)態(tài)數(shù)據(jù)庫； 步2 用動(dòng)態(tài)數(shù)據(jù)庫中的事實(shí)匹配目標(biāo)條件，若目標(biāo)條件滿足，推理成功，結(jié)束。 步3 用規(guī)則庫中各規(guī)則的前提匹配動(dòng)態(tài)數(shù)據(jù)庫中的事實(shí)，將匹配成功的規(guī)則組成待用規(guī)則集。 步4 若待用規(guī)則集為空，則運(yùn)行失敗，退出。 步5 用某種策略，從待用規(guī)則集中選取一條規(guī)則，將其結(jié)論加入動(dòng)態(tài)數(shù)據(jù)庫，或者執(zhí)行其動(dòng)作，撤消待用規(guī)則集，轉(zhuǎn)步2。,2020/8/16,人工智能,40