《產(chǎn)生式系統(tǒng) 》PPT課件

2020/10/5,1,第五章 產(chǎn)生式系統(tǒng),產(chǎn)生式表示方法 產(chǎn)生式系統(tǒng)基本原理 產(chǎn)生式系統(tǒng)與圖搜索 產(chǎn)生式系統(tǒng)應(yīng)用,2020/10/5,2,第五章 產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的體系結(jié)構(gòu)是 實(shí)現(xiàn)圖搜索的理想程序結(jié)構(gòu)，產(chǎn)生式已是人工智能系統(tǒng)的一種最典型最普遍的結(jié)構(gòu)形式。 許多專家系統(tǒng)和機(jī)器學(xué)習(xí)系統(tǒng)都是用產(chǎn)生式系統(tǒng)實(shí)現(xiàn)的。從結(jié)構(gòu)形式上看很多人工智能系統(tǒng)都是產(chǎn)生式系統(tǒng)。,2020/10/5,3,第五章 產(chǎn)生式系統(tǒng),產(chǎn)生式表示方法 產(chǎn)生式系統(tǒng)基本原理 產(chǎn)生式系統(tǒng)與圖搜索 產(chǎn)生式系統(tǒng)應(yīng)用,2020/10/5,4,產(chǎn)生式表示法,產(chǎn)生式 產(chǎn)生式一詞是從波斯特機(jī)中借用來的。波斯特機(jī)是一種自動(dòng)機(jī)，它是根據(jù)串替換規(guī)則提出的一種計(jì)算模型。其中的每一條規(guī)則就叫一個(gè)產(chǎn)生式。也稱產(chǎn)生式規(guī)則，簡稱規(guī)則。 這里產(chǎn)生式就是前面討論過的操作、邏輯蘊(yùn)含式、推理規(guī)則以及各種關(guān)系（包含經(jīng)驗(yàn)性聯(lián)想）的一種邏輯抽象。,2020/10/5,5,產(chǎn)生式表示法,產(chǎn)生式的一般形式為： 前件后件（情況行為） 前件是前提，規(guī)則的執(zhí)行條件。 后件是結(jié)論或動(dòng)作，規(guī)則體。 產(chǎn)生式規(guī)則的語義：如果前提滿足，則可得結(jié)論或者執(zhí)行相應(yīng)的動(dòng)作，即后件由前件觸發(fā)。 從基本事實(shí)到結(jié)論之間的復(fù)雜推理可以借助中間結(jié)論形成小型簡單產(chǎn)生式。,2020/10/5,6,產(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 =S,2020/10/5,7,產(chǎn)生式表示法,給定一組事實(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/10/5,8,產(chǎn)生式表示法,如果一組事實(shí)可以同時(shí)使幾個(gè)產(chǎn)生式前提為真，常用以下方法進(jìn)行選擇（沖突消解策略）： 將所有產(chǎn)生式排序，選最早匹配成功的一個(gè)，不管其余的產(chǎn)生式； 在所有匹配成功的產(chǎn)生式中取最強(qiáng)的，即前提條件最多或情況元素最多者； 最近用過的產(chǎn)生式優(yōu)先（或反之）； 給情況元素以不同的優(yōu)先權(quán)； 使用估計(jì)函數(shù)f(x)排序； 利用上下文限制。,2020/10/5,9,產(chǎn)生式表示法,在產(chǎn)生式系統(tǒng)中，從前提到結(jié)論通常也是一棵與或樹。 合取，與節(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/10/5,10,產(chǎn)生式表示法,事實(shí),中介事實(shí) B、C、D,產(chǎn)生式規(guī)則 P1、P2、P3、P4、P5,結(jié)論,2020/10/5,11,產(chǎn)生式表示法（例）,例 三個(gè)聰明人問題。古代有個(gè)國王想知道他的三個(gè)大王中誰最聰明，就在他們每個(gè)人前額上都畫了一個(gè)點(diǎn)，他們都能看到別人點(diǎn)的顏色，但看不到別人點(diǎn)的顏色。國王說，你們中間至少有一個(gè)人的點(diǎn)式白色的。于是重復(fù)地問他們：“誰知道自己點(diǎn)地顏色？”三位大臣們頭兩次都回答說不知道。題目要求證明下一次他們?nèi)紩?huì)說“知道”，并且所有的點(diǎn)都是白色。,2020/10/5,12,產(chǎn)生式表示法（例）,分析： 這類問題的特點(diǎn)是有有限個(gè)受試者，每個(gè)人對(duì)問題都只有部分了解，無法直接求解。但在推理過程中每個(gè)人又可以從別人那里獲得新的知識(shí)，重新進(jìn)行推理。可以用產(chǎn)生式來表達(dá)推理過程中所用到的各種知識(shí)。,2020/10/5,13,產(chǎn)生式表示法（例）,狀態(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/10/5,14,產(chǎn)生式表示法（例）,排除過程： 第一次，大臣只知道至少有一個(gè)人是白點(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/10/5,15,產(chǎn)生式表示法（例）,引入中介狀態(tài)并定義下述符號(hào)： Si i大臣看到的非白點(diǎn)數(shù)； Wi i大臣猜出自己點(diǎn)的顏色否。如果他宣布已知道自己點(diǎn)的顏色，為1，否則為0； nX0中白點(diǎn)的個(gè)數(shù)。,2020/10/5,16,產(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)(有人看見兩個(gè)非白點(diǎn))(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,0),(1,0,1),(1,1,0),(1,1,1)； (7) (有人看見一個(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).,2020/10/5,17,產(chǎn)生式表示法（例）,上述結(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=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/10/5,18,第五章 產(chǎn)生式系統(tǒng),產(chǎn)生式表示方法 產(chǎn)生式系統(tǒng)基本原理 產(chǎn)生式系統(tǒng)與圖搜索 產(chǎn)生式系統(tǒng)應(yīng)用,2020/10/5,19,產(chǎn)生式系統(tǒng)基本原理,組成和分類 運(yùn)行過程 常用算法,2020/10/5,20,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,產(chǎn)生式系統(tǒng)結(jié)構(gòu),產(chǎn)生式規(guī)則庫(知識(shí)庫),推理機(jī)（控制）,全局?jǐn)?shù)據(jù)庫,2020/10/5,21,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,組成 全局?jǐn)?shù)據(jù)庫人工智能系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)中心。是一個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，用來存放初始事實(shí)數(shù)據(jù)、中間結(jié)構(gòu)和最后結(jié)果。對(duì)應(yīng)敘述性知識(shí)。 產(chǎn)生式規(guī)則庫作用在全局?jǐn)?shù)據(jù)庫上的一些規(guī)則的集合。每條規(guī)則都有一定的條件，若全局?jǐn)?shù)據(jù)庫中內(nèi)容滿足這些條件可調(diào)用這條規(guī)則。對(duì)應(yīng)過程性知識(shí)。 推理機(jī)負(fù)責(zé)產(chǎn)生式規(guī)則的前提條件測試或匹配，規(guī)則的調(diào)度和選取，規(guī)則體的解釋和執(zhí)行。對(duì)應(yīng)控制性知識(shí)。,2020/10/5,22,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,例 旅行推銷員問題。求從A城出發(fā)，經(jīng)過其他城市一次且僅一次，最后回到A城的最小費(fèi)用路線。城市之間的交通費(fèi)用標(biāo)在相應(yīng)的聯(lián)線上。建立產(chǎn)生式系統(tǒng)。,2020/10/5,23,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,（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)用最少。 （5）各種搜索策略選擇規(guī)則，如廣度優(yōu)先搜索，最好優(yōu)先搜索等。,R2,R5,2020/10/5,24,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,規(guī)則集,2020/10/5,25,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,與一般分級(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)系必須通過全部數(shù)據(jù)庫聯(lián)系。 全局?jǐn)?shù)據(jù)庫、規(guī)則和推理機(jī)之間相對(duì)獨(dú)立，這種積木式結(jié)構(gòu)便于整個(gè)系統(tǒng)增加和修改知識(shí)。,2020/10/5,26,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,分類體系（尼爾遜） 按搜索策略分 不可挽回（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 Production System） 兩種特殊的產(chǎn)生式系統(tǒng) 可交換的（Commutative）產(chǎn)生式系統(tǒng) 可分解的（Decomposable）產(chǎn)生式系統(tǒng),2020/10/5,27,產(chǎn)生式系統(tǒng)基本原理,組成和分類 運(yùn)行過程 控制策略與常用算法,2020/10/5,28,產(chǎn)生式系統(tǒng)基本原理（運(yùn)行過程）,推理機(jī)一次運(yùn)行過程,2020/10/5,29,產(chǎn)生式系統(tǒng)基本原理（運(yùn)行過程）,產(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)行推理并不斷檢測目標(biāo)條件是否被滿足的過程。 產(chǎn)生式系統(tǒng)運(yùn)行過程是從初始事實(shí)出發(fā)，尋求到達(dá)目標(biāo)條件的通路的過程。所以也是一個(gè)搜索的過程。,2020/10/5,30,產(chǎn)生式系統(tǒng)基本原理,組成和分類 運(yùn)行過程 常用算法,2020/10/5,31,產(chǎn)生式系統(tǒng)基本原理（常用算法）,推理方式 正向推理 從初始事實(shí)數(shù)據(jù)出發(fā)，正向使用規(guī)則進(jìn)行推理，朝目標(biāo)方向前進(jìn)。又稱為前向推理、正向鏈、數(shù)據(jù)驅(qū)動(dòng)的推理。 反向推理 從目標(biāo)出發(fā)，反向使用規(guī)則進(jìn)行推理，朝初始事實(shí)或數(shù)據(jù)方向前進(jìn)。又稱反向推理、反向鏈、目標(biāo)驅(qū)動(dòng)的推理。,2020/10/5,32,產(chǎn)生式系統(tǒng)基本原理（常用算法）,正向推理算法 步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/10/5,33,產(chǎn)生式系統(tǒng)基本原理（常用算法）,反向推理算法 步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)匹配，若匹配成功，則33將第一個(gè)匹配成功且未用過的規(guī)則的前提作為新的目標(biāo)，并取代原來的父目標(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。,2020/10/5,34,產(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)物是鳥 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/10/5,35,產(chǎn)生式系統(tǒng)基本原理（常用算法）,r7： IF 該動(dòng)物是哺乳動(dòng)物 AND 有蹄 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)物是虎 r11：IF 該動(dòng)物是有蹄類動(dòng)物 AND 有長脖子 AND 有長腿 AND 身上有暗斑點(diǎn) THEN 該動(dòng)物是長頸鹿 r12：IF 該動(dòng)物有蹄類動(dòng)物 AND 身上有黑色條紋 THEN 該動(dòng)物是斑馬,2020/10/5,36,產(chǎn)生式系統(tǒng)基本原理（常用算法）,r13： IF 該動(dòng)物是鳥 AND 有長脖子 AND 有長腿 AND 不會(huì)飛 AND 有黑白二色 THEN 該動(dòng)物是鴕鳥 r14： IF 該動(dòng)物是鳥 AND 會(huì)游泳 AND 不會(huì)飛 AND 有黑白二色 THEN 該動(dòng)物是企鵝 r15：IF 該動(dòng)物是鳥 AND 善飛 THEN 該動(dòng)物是信天翁,2020/10/5,37,產(chǎn)生式系統(tǒng)基本原理（常用算法）,初始事實(shí)： f1：某動(dòng)物有毛發(fā)。 f2：吃肉。 f3：黃褐色。 f4：有黑色條紋 目標(biāo)條件為：該動(dòng)物為什么？,2020/10/5,38,產(chǎn)生式系統(tǒng)基本原理（常用算法）,2020/10/5,39,產(chǎn)生式系統(tǒng)基本原理（常用算法）,2020/10/5,40,第五章 產(chǎn)生式系統(tǒng),產(chǎn)生式表示方法 產(chǎn)生式系統(tǒng)基本原理 產(chǎn)生式系統(tǒng)與圖搜索 產(chǎn)生式系統(tǒng)應(yīng)用,2020/10/5,41,產(chǎn)生式系統(tǒng)與圖搜索,產(chǎn)生式系統(tǒng)與圖搜索對(duì)比,2020/10/5,42,第五章 產(chǎn)生式系統(tǒng),產(chǎn)生式表示方法 產(chǎn)生式系統(tǒng)基本原理 產(chǎn)生式系統(tǒng)與圖搜索 產(chǎn)生式系統(tǒng)應(yīng)用,2020/10/5,43,產(chǎn)生式系統(tǒng)的應(yīng)用實(shí)例,基于消解原理的產(chǎn)生式系統(tǒng) 基于自然演繹法的產(chǎn)生式系統(tǒng) 基于專用知識(shí)的產(chǎn)生式系統(tǒng),2020/10/5,44,基于消解原理的產(chǎn)生式系統(tǒng),消解原理的產(chǎn)生式系統(tǒng) 全局?jǐn)?shù)據(jù)庫：子句集合S 產(chǎn)生式規(guī)則集：一般形式是消解 控制系統(tǒng) 終止條件：NIL S 搜索策略：是個(gè)可交換的系統(tǒng)，使用各個(gè)具體的消解與先后順序無關(guān)，采用不可挽回的控制策略。,2020/10/5,45,基于消解原理的產(chǎn)生式系統(tǒng),過程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。,2020/10/5,46,基于消解原理的產(chǎn)生式系統(tǒng),控制策略 廣度優(yōu)先搜索策略 相當(dāng)于水平浸透法。完備的但效率低。 支持集消解策略 反向產(chǎn)生式系統(tǒng)。完備的，但不一定得到最優(yōu)解。 啟發(fā)式搜索策略 利用消解原理求解問題的經(jīng)驗(yàn)，設(shè)計(jì)啟發(fā)函數(shù)。,2020/10/5,47,補(bǔ)充：解樹代換的一致性（一）,設(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的最一般合一。 解樹上所有代換是一致的，則該問題有解，最后的代換是合一復(fù)合U。,2020/10/5,48,補(bǔ)充：解樹代換的一致性（二）,例設(shè)有一個(gè)代換集u1,u2，其中 u1f(g(x1)/x3,f(x2)/x4 U1和U2是可合一的，其最一般合一是： Uf(g(x1)/x3,f(g(x1)/x4， g(x1)/x2,u2x4/x3,g(x1)/x2 U1=x3, x4, x3 ,x2 U2=f(g(x1) f(x2) ,x4 ,g (x1),2020/10/5,49,產(chǎn)生式系統(tǒng)的應(yīng)用實(shí)例,基于消解原理的產(chǎn)生式系統(tǒng) 基于自然演繹法的產(chǎn)生式系統(tǒng) 基于專用知識(shí)的產(chǎn)生式系統(tǒng),2020/10/5,50,基于自然演繹法的產(chǎn)生式系統(tǒng),消解原理產(chǎn)生式系統(tǒng)特點(diǎn) 優(yōu)點(diǎn)：形式單一，處理規(guī)則簡單。 缺點(diǎn)：太一般化，丟失了原公式重要語義信息，對(duì)應(yīng)用啟發(fā)搜索系統(tǒng)和人機(jī)交互帶來了困難；組合爆炸，難以直接使用。 自然演繹法 保持專家知識(shí)原始的邏輯形態(tài)，保留了控制信息。 推理規(guī)則復(fù)雜，但便于設(shè)計(jì)啟發(fā)函數(shù)。 推理過程直觀，便于理解。,2020/10/5,51,基于自然演繹法的產(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)用,2020/10/5,52,1、基于規(guī)則的向前推理系統(tǒng)（一）,基本原理 從代表初始事實(shí)的謂詞公式F0出發(fā)通過一組F規(guī)則F1，F(xiàn)2來證明目標(biāo)公式G成立。 初始事實(shí)F0 任意謂詞公式 前束范式表示；運(yùn)用Skolem函數(shù)消去存在量詞；省去全稱量詞；得到任意與或型事實(shí)表達(dá)式，改名，使各主要合取項(xiàng)的變量應(yīng)不相同。 與或圖表示：析取部分用與節(jié)點(diǎn)表示合取部分用或節(jié)點(diǎn)表示,2020/10/5,53,1、基于規(guī)則的向前推理系統(tǒng)（二）,F規(guī)則 形如 L=W L為單一文字 W為任意與或型謂詞公式；W中用Skolem消去存在量詞，變元只受全稱量詞約束；改名，使不同規(guī)則具有不同變元，規(guī)則變元與事實(shí)變元也不同。 復(fù)雜規(guī)則化為簡單規(guī)則。,2020/10/5,54,1、基于規(guī)則的向前推理系統(tǒng)（三）,終止條件 用目標(biāo)謂詞G表示 G為文字的析取式（文字都為目標(biāo)文字）；用Skolem函數(shù)消去全稱量詞；消去存在量詞；改名，使同一變元在各目標(biāo)文字、規(guī)則、事實(shí)中最多出現(xiàn)一次。 推理基本過程 不斷將規(guī)則L=W利用匹配弧連接在與或圖的L葉結(jié)點(diǎn)上；目標(biāo)文字G本身可看作G =G作用在與或圖上； 一致解樹各個(gè)葉結(jié)點(diǎn)都終止在目標(biāo)節(jié)點(diǎn)，成功終止。,2020/10/5,55,1、基于規(guī)則的向前推理系統(tǒng)（四）,例:命題邏輯中一個(gè)定理證明問題 構(gòu)造一個(gè)向前的規(guī)則基推理系統(tǒng)來求解。 事實(shí) F0： 規(guī)則 F1： F2 ： F3： 目標(biāo) G：,2020/10/5,56,1、基于規(guī)則的向前推理系統(tǒng)（五）,2020/10/5,57,1、基于規(guī)則的向前推理系統(tǒng)（六）,例:謂詞邏輯中一個(gè)定理證明問題 自然數(shù)都是大于0的整數(shù) 所有整數(shù)不是偶數(shù)就是奇數(shù) 偶數(shù)的一半是整數(shù) 所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。 構(gòu)造一個(gè)向前的規(guī)則基推理系統(tǒng)來求解,2020/10/5,58,1、基于規(guī)則的向前推理系統(tǒng)（六）,一、預(yù)處理F0為事實(shí)表達(dá)式方法： （1）將公式化稱任意與或型前束范式，每個(gè)否定詞僅管 轄一個(gè)謂詞； （2）用Skolem函數(shù)去掉存在量詞并改名使主合取項(xiàng)之間無相同變量； （3）隱去全稱量詞。,2020/10/5,59,1、基于規(guī)則的向前推理系統(tǒng)（七）,二、預(yù)處理F1 F2為F規(guī)則方法： （1）暫時(shí)消去； （2）將公式化為前束范式，一個(gè)否定詞管轄一個(gè)謂詞； （3）用Skolem函數(shù)消去存在量詞； （4）改變變元名稱使其與其他公式不同； （5）恢復(fù)蘊(yùn)含式。,2020/10/5,60,1、基于規(guī)則的向前推理系統(tǒng)（八）,三、處理目標(biāo)G： （1）用Skolem函數(shù)消去全稱量詞； （2）隱去存在量詞。,2020/10/5,61,1、基于規(guī)則的向前推理系統(tǒng)（九）,2020/10/5,62,2、基于規(guī)則的向后推理系統(tǒng)（一）,基本原理 從代表目標(biāo)的謂詞公式出發(fā)，通過一組B規(guī)則證明事實(shí)公式成立。 目標(biāo) 任意謂詞公式，Skolem函數(shù)消去全稱量詞；隱去存在量詞；改名，公式中主要析取項(xiàng)的變元應(yīng)不相同。 與或圖表示：與節(jié)點(diǎn)對(duì)應(yīng)合?。换蚬?jié)點(diǎn)對(duì)應(yīng)析??；根節(jié)點(diǎn)上任何后裔都為子目標(biāo)。,2020/10/5,63,2、基于規(guī)則的向后推理系統(tǒng)（二）,B規(guī)則 W=L； L為單一文字； W為任意與或型謂詞公式，變元受全稱量詞約束，變元改名。 復(fù)雜規(guī)則化為簡單規(guī)則。,2020/10/5,64,2、基于規(guī)則的向后推理系統(tǒng)（三）,推理過程 目標(biāo)謂詞公式的與或圖中有一節(jié)點(diǎn)標(biāo)為L，且可與L合一，則可將規(guī)則作用在該與或樹上。其結(jié)果使在與或樹上從L引出一條匹配弧，連接一個(gè)以L為根，表示W(wǎng)的與或圖， 為L與L的最一般合一。 終止條件 當(dāng)與或樹的一致解樹各個(gè)葉節(jié)點(diǎn)都終止在事實(shí)節(jié)點(diǎn)時(shí)，此產(chǎn)生式系統(tǒng)成功終止。,2020/10/5,65,2、基于規(guī)則的向后推理系統(tǒng)（四）,例:基于規(guī)則的向后推理系統(tǒng)。 給定事實(shí)為: Fido是狗 Fido不會(huì)吠叫 Fido會(huì)搖尾巴 Myetle會(huì)咪咪叫,2020/10/5,66,2、基于規(guī)則的向后推理系統(tǒng)（五）,已知規(guī)則為 目標(biāo)：存在貓不怕狗的現(xiàn)象，即,2020/10/5,67,2、基于規(guī)則的向后推理系統(tǒng)（六）,2020/10/5,68,3、F系統(tǒng)和B系統(tǒng)的對(duì)比（一）,2020/10/5,69,3、F系統(tǒng)和B系統(tǒng)的對(duì)比（一）,2020/10/5,70,產(chǎn)生式系統(tǒng)的應(yīng)用實(shí)例,基于消解原理的產(chǎn)生式系統(tǒng) 基于自然演繹法的產(chǎn)生式系統(tǒng) 基于專用知識(shí)的產(chǎn)生式系統(tǒng),2020/10/5,71,基于專用知識(shí)的產(chǎn)生式系統(tǒng)（一）,例機(jī)器人完成食品裝袋作業(yè)的產(chǎn)生式系統(tǒng)BAGGER。 全局?jǐn)?shù)據(jù)庫：記錄階段信息（核對(duì)訂貨/大件物品裝袋/中 件物品裝袋/小件物品裝袋/裝 袋完畢）； 物品信息； 裝袋情況。,2020/10/5,72,基于專用知識(shí)的產(chǎn)生式系統(tǒng)（二）,階段：核對(duì)訂貨 口袋1：空,2020/10/5,73,基于專用知識(shí)的產(chǎn)生式系統(tǒng)（三）,規(guī)則集 R11：IF核對(duì)核對(duì)訂貨階段，有炸土豆片，無飲料 THEN建議增訂一瓶百事可樂 R12：IF核對(duì)訂貨階段，有面包，無黃油 THEN建議增訂一塊黃油 R2：IF核對(duì)訂貨階段 THEN結(jié)束核對(duì)訂貨階段，進(jìn)入大件物品裝袋階段，并啟用口袋 為當(dāng)前袋 R3：IF大件物品裝袋階段，有瓶子待裝，當(dāng)前袋中大件物品少于6件 THEN把瓶子裝入當(dāng)前袋中 R4：IF大件物品裝袋階段，有大件物品待裝，當(dāng)前袋中大件物品少于6件 THEN把此大件武平轉(zhuǎn)入當(dāng)前袋中,2020/10/5,74,基于專用知識(shí)的產(chǎn)生式系統(tǒng)（四）,R5：IF大件物品裝袋階段，有瓶子待裝 THEN啟用新口袋I1為當(dāng)前袋 R6：IF大件物品裝袋階段 THEN進(jìn)入中件物品裝袋階段，并啟用一空口袋為當(dāng)前袋。 R7：IF中件物品裝袋階段，有冰凍物品待裝，當(dāng)前袋未滿 THEN將此冰凍物品放入冰凍融離袋，然后放入當(dāng)前袋中 R8：IF中件物品裝袋階段，有中件物品待裝，當(dāng)前袋中未滿 THEN把此中件物品放入當(dāng)前袋 R9：IF中件物品裝袋階段，有中件物品待裝 THEN啟用新口袋i1為當(dāng)前袋,2020/10/5,75,基于專用知識(shí)的產(chǎn)生式系統(tǒng)（五）,R10：IF中件物品裝袋階段 THEN結(jié)束中件物品裝袋階段，進(jìn)入小件物品裝袋階段，并選一未滿口袋為當(dāng)前袋 R11：IF小件物品裝袋階段，有小件物品待裝，當(dāng)前袋未滿 THEN把此小件物品裝入當(dāng)前袋中 R12：IF小件物品裝袋階段，有小件物品待裝 THEN選一未滿口袋或新口袋為當(dāng)前袋 R13：IF小件物品裝袋階段 THEN結(jié)束裝袋作業(yè)，裝袋完畢。 控制系統(tǒng)：正向推理系統(tǒng)，規(guī)則優(yōu)先權(quán)按自然大小排序，只有Ri規(guī)則不能使用時(shí)才考慮Ri1規(guī)則。,2020/10/5,76,基于專用知識(shí)的產(chǎn)生式系統(tǒng)（六）,上述初始狀態(tài)經(jīng)BAGGER作業(yè)后有如下終止?fàn)顟B(tài)： 階段：裝袋完畢 待裝：無 口袋1：百事可樂，點(diǎn)心（2） 口袋2：冰淇淋，炸土豆片、面包、果醬,