湘潭大學(xué)-人工智能課件-確定性推理-part-8

1、Artificial Intelligence (AI)人工智能,第二章：知識(shí)表示與推理,內(nèi)容提要,第二章：知識(shí)表示與推理,1.推理的基本概念,2.搜索策略,3.自然演繹推理,4.消解演繹推理,5.基于規(guī)則的演繹推理,基于規(guī)則的演繹推理,規(guī)則演繹系統(tǒng) 規(guī)則正向演繹系統(tǒng) 規(guī)則逆向演繹系統(tǒng) 規(guī)則雙向演繹系統(tǒng),規(guī)則逆向演繹系統(tǒng),規(guī)則逆向演繹推理過程： 規(guī)則逆向演繹推理過程是從待證明的問題，即目標(biāo)公式的與/或樹出發(fā)，通過逆向地使用蘊(yùn)含式（B規(guī)則），對(duì)目標(biāo)公式的與/或樹進(jìn)行變換，直到得出包含已知事實(shí)的終止條件為止。 規(guī)則逆向演繹系統(tǒng) 目標(biāo)公式的表示：與/或形變換，與/或樹表示 B規(guī)則的表示形式 已知事實(shí)

2、的表示形式 規(guī)則逆向演繹推理過程,目標(biāo)公式的與/或形變換,在與/或形逆向演繹推理中，要求目標(biāo)公式采用與/或形表示，其化簡(jiǎn)采用與正向系統(tǒng)中對(duì)事實(shí)表達(dá)式處理的對(duì)偶形式。 轉(zhuǎn)化步驟 要用存在量詞約束變?cè)腟kolem函數(shù)來替換由全稱量詞約束的相應(yīng)變?cè)?，消去全稱量詞。（隱含著變量受存在量詞的約束 ） 再消去存在量詞，并進(jìn)行變?cè)獡Q名，使主析取元之間具有不同的變?cè)?目標(biāo)公式的與/或形變換,例如，有如下目標(biāo)公式： (y) (x)(P(x)(Q(x)(R(x)S(y) Skolem化后為 P(f(y)(Q(f(y), y)(R(f(y)S(y) 變?cè)獡Q名后為 P(f(z)(Q(f(y), y)(R(f(y

3、)S(y) 關(guān)于為何需用對(duì)偶方式消去量詞，這里不作形式證明，僅通過與消解反演方法作對(duì)比來加以直觀說明：在消解反演中，需將目標(biāo)公式取反，存在量詞約束變量就成為全稱量詞約束變量。,目標(biāo)公式的與/或樹表示,目標(biāo)公式的與/或形也可用與/或樹表示出來，其表示方法與正向演繹推理中事實(shí)的與或樹表示略有不同： 子表達(dá)式之間的析取關(guān)系用單一連接符連接，表示為或的關(guān)系； 子表達(dá)式之間的合取關(guān)系則用k線連接符連接，表示為與的關(guān)系。 例如：對(duì)上述目標(biāo)公式的與/或形，可用如下的與/或樹表示。,目標(biāo)公式的與/或樹表示,若把葉節(jié)點(diǎn)用它們之間的合取及析取關(guān)系連接起來，就可得到原目標(biāo)公式的三個(gè)子目標(biāo)：,P(f(z)； Q(f(

4、y), y) R(f(y)； Q(f(y), y) S(y),B規(guī)則的表示形式,B規(guī)則的表示形示形式 WL 其中，前項(xiàng)W為任一與/或形公式，后項(xiàng) L為一單文字。 這里要求B規(guī)則的右邊為文字，是因?yàn)橥评頃r(shí)要用它與目標(biāo)與或樹中的葉節(jié)點(diǎn)進(jìn)行匹配（合一），而目標(biāo)與或樹中的葉節(jié)點(diǎn)是文字。 如果已知的B規(guī)則不是要求的形式，可用與轉(zhuǎn)化F規(guī)則類似的方法把它轉(zhuǎn)化為規(guī)定的形式。 特別地，當(dāng)B規(guī)則為WL1L2時(shí)，則可化件為兩條規(guī)則WL1和WL2進(jìn)行處理。,已知事實(shí)的表示形式,已知事實(shí)的表示形式 反向演繹系統(tǒng)的事實(shí)表達(dá)式限制為文字合取形式，如： F1F2 Fn 其中，每個(gè)Fi（i=1,2,n）都為單文字，且都可單獨(dú)起

5、作用，因此可表示為如下集合形式 F1，F(xiàn)2， ，F(xiàn)n ,規(guī)則逆向演繹推理過程,規(guī)則逆向演繹推理 從目標(biāo)公式的與/或樹出發(fā)，通過運(yùn)用B規(guī)則最終得到了某個(gè)終止在事實(shí)節(jié)點(diǎn)上的一致解圖，推理就可成功結(jié)束 推理過程 1）首先用與/或樹把目標(biāo)公式表示出來； 2）用B規(guī)則的右部和與/或樹的葉節(jié)點(diǎn)進(jìn)行匹配，并將匹配成功的B規(guī)則加入到與/或樹中； 3）重復(fù)進(jìn)行步驟2，直到產(chǎn)生某個(gè)終止在事實(shí)節(jié)點(diǎn)上的一致解圖為止。這里的“一致解圖”是指在推理過程中所用到的置換應(yīng)該是一致的。,規(guī)則逆向演繹推理過程,例：設(shè)有如下事實(shí)及規(guī)則 事實(shí)： f1: DOG(Fido) Fido是一只狗 f 2: BARKS(Fido) Fido

6、是不叫的 f 3: WAGS-TAIL(Fido) Fido搖尾巴 f 4: MEOWS(Myrtle) 貓咪的名字叫Myrtle,規(guī)則逆向演繹推理過程,規(guī)則： r1: (WAGS-TAIL(x1)DOG(x1) FRIENDLY(x1) 搖尾巴的狗是溫順的狗 r2: (FRIENDLY(x2) BARKS(x2) AFRAID(y2, x2) 溫順又不叫的東西是不值得害怕的 r3: DOG(x3)ANIMAL(x3) ：狗為動(dòng)物 r4: CAT(x4)ANIMAL(x4)：貓為動(dòng)物 r5: MEOWS(x5)CAT(x5)：貓咪是貓,規(guī)則逆向演繹推理過程,問題： 是否存在這樣的一只貓和一條狗

7、，使得這只貓不害怕這只狗？ 該問題的目標(biāo)公式為： (x) (y) (CAT(x)DOG(y)AFRAID(x, y) 改目標(biāo)公式經(jīng)變換后得到 CAT(x)DOG(y) AFRAID(x, y) 用逆向推理求解該問題的演繹過程如下圖所示：,規(guī)則逆向演繹推理過程,該圖有8條匹配弧，每條弧上都有一置換。其中終止在事實(shí)節(jié)點(diǎn)上的置換為Myrtle/x和Fido/y。把它們應(yīng)用到目標(biāo)公式，就得到該問題的解：,CAT(MyrtleDOG(Fido)AFRAID(Myrtle, Fido,基于規(guī)則的演繹推理,規(guī)則演繹系統(tǒng) 規(guī)則正向演繹系統(tǒng) 規(guī)則逆向演繹系統(tǒng) 規(guī)則雙向演繹系統(tǒng),規(guī)則雙向演繹系統(tǒng),規(guī)則雙向演繹系統(tǒng)

8、 與/或形正向演繹推理要求目標(biāo)公式是文字的析取（目標(biāo)公式用子句表示，每一個(gè)子句是文字的析取） 與/或形逆向演繹推理要求事實(shí)公式是文字的合取 正向和逆向的演繹推理都存在一定的局限性。為了克服這些局限，充分發(fā)揮各自的長處，可進(jìn)行雙向演繹推理。,規(guī)則雙向演繹系統(tǒng),與/或形雙向演繹推理是建立在正向演繹推理和逆向演繹推理基礎(chǔ)上的，它由表示目標(biāo)及表示已知事實(shí)的兩個(gè)與/或樹結(jié)構(gòu)組成，這些與/或樹分別由正向演繹的F規(guī)則和逆向演繹的B規(guī)則進(jìn)行操作，并且仍然限制F規(guī)則為單文字的左部，B規(guī)則為單文字的右部。 雙向演繹推理的難點(diǎn)在于終止條件，只有當(dāng)正向和逆向推理的與/或樹對(duì)應(yīng)的葉節(jié)點(diǎn)都可合一時(shí)，推理才能結(jié)束。其時(shí)機(jī)與

9、判斷都難于掌握。 更實(shí)用化的方式是將復(fù)雜的問題求解任務(wù)劃分為相對(duì)簡(jiǎn)單的若干子任務(wù)，然后根據(jù)子任務(wù)的特點(diǎn)選用正向或逆向演繹推理方式，以便充分發(fā)揮兩種方式各自的優(yōu)勢(shì)。,內(nèi)容提要,第三章：確定性推理,1.推理的基本概念,2.搜索策略,3.自然演繹推理,4.消解演繹推理,5.基于規(guī)則的演繹推理,6.產(chǎn)生式系統(tǒng),內(nèi)容提要,第二章：知識(shí)表示與推理,1.推理的基本概念,2.搜索策略,3.自然演繹推理,4.消解演繹推理,5.基于規(guī)則的演繹推理,6.產(chǎn)生式系統(tǒng)推理,產(chǎn)生式系統(tǒng),產(chǎn)生式表示法 事實(shí)的表示 確定性知識(shí)，事實(shí)可用如下三元組表示： （對(duì)象，屬性，值）或（關(guān)系，對(duì)象1，對(duì)象2） 如:（雪，顏色，白）或（熱

10、愛，王峰，祖國） 非確定性知識(shí)，事實(shí)可用如下四元組表示： （對(duì)象，屬性，值，可信度因子） 其中，“可信度因子”是指該事實(shí)為真的相信程度?？捎?,1之間的一個(gè)實(shí)數(shù)來表示。,產(chǎn)生式系統(tǒng),產(chǎn)生式表示法 規(guī)則的表示： PQ 或者 IF P THEN Q P是產(chǎn)生式的前提，也稱為前件，它給出了該產(chǎn)生式可否使用的先決條件，由事實(shí)的邏輯組合來構(gòu)成。 Q是一組結(jié)論或操作，也稱為產(chǎn)生式的后件，它指出當(dāng)前題P滿足時(shí)，應(yīng)該推出的結(jié)論或應(yīng)該執(zhí)行的動(dòng)作。 產(chǎn)生式的含義：如果前提P滿足，則可推出結(jié)論Q或執(zhí)行Q所規(guī)定的操作,產(chǎn)生式系統(tǒng),產(chǎn)生式與蘊(yùn)涵式的主要區(qū)別： (1) 蘊(yùn)涵式表示的知識(shí)只能是精確的，產(chǎn)生式表示的知識(shí)可以是

11、不確定的。 (2) 蘊(yùn)含式的匹配一定要求是精確的，而產(chǎn)生式的匹配可以是不確定的。 產(chǎn)生式與條件語句的主要區(qū)別： (1) 前件結(jié)構(gòu)不同：產(chǎn)生式的前件可以是一個(gè)復(fù)雜的結(jié)構(gòu)，而程序設(shè)計(jì)語言中條件語句的左部是布爾表達(dá)式。 (2) 控制流程不同：產(chǎn)生式系統(tǒng)中滿足前提條件的規(guī)則被激活后，不一定被立即執(zhí)行，能否執(zhí)行將取決于沖突消解策略，而條件語句嚴(yán)格執(zhí)行。,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu),總數(shù)據(jù)庫：存放求解問題的各種當(dāng)前信息，如：?jiǎn)栴}的初始狀態(tài)，輸入的事實(shí)，中間結(jié)論及最終結(jié)論等。 推理過程中，當(dāng)規(guī)則庫中某條規(guī)則的前提可以和總數(shù)據(jù)庫的已知事實(shí)匹配時(shí)，該規(guī)則被激活，由它推出的結(jié)論將被作為新的事實(shí)放入總數(shù)據(jù)庫，

12、成為后面推理的已知事實(shí)。,產(chǎn)生式規(guī)則：是一個(gè)規(guī)則庫，也稱知識(shí)庫 。用于存放與求解問題有關(guān)的所有規(guī)則的集合.,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu),控制策略：亦稱推理機(jī)，用于控制整個(gè)產(chǎn)生式系統(tǒng)的運(yùn)行，決定問題求解過程的推理線路。 控制系統(tǒng)的主要任務(wù)包括： 選擇匹配 沖突消解 執(zhí)行操作 終止推理 路徑解釋,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的推理 正向推理：從一組表示事實(shí)的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則，用以證明該謂詞公式或命題是否成立。 設(shè)有規(guī)則集合R1至R3 R1：P1 P2 R2：P2 P3 R3：P3 P4,正向推理過程,已知 P1,P2,P3,推出 P4,規(guī)則3,規(guī)則2,規(guī)則1,產(chǎn)生式系統(tǒng),產(chǎn)生式系

13、統(tǒng)的推理 逆向推理：從表示目標(biāo)的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則證明事實(shí)謂詞或命題成立，即首先提出一批假設(shè)目標(biāo)，然后逐一驗(yàn)證這些假設(shè)。,逆向推理過程,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的推理 雙向推理：雙向推理的推理策略是同時(shí)從目標(biāo)向事實(shí)推理和從事實(shí)向目標(biāo)推理，并在推理過程中的某個(gè)步驟，實(shí)現(xiàn)事實(shí)與目標(biāo)的匹配。,雙向推理過程,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的例子：動(dòng)物識(shí)別系統(tǒng) 該系統(tǒng)可以識(shí)別老虎、金錢豹、斑馬、長頸鹿、企鵝、信天翁這6種動(dòng)物。 其規(guī)則庫包含如下15條規(guī)則： r1: IF 該動(dòng)物有毛發(fā) THEN 該動(dòng)物是哺乳動(dòng)物 r2: IF 該動(dòng)物有奶 THEN 該動(dòng)物是哺乳動(dòng)物 r3: IF 該動(dòng)物有羽毛 TH

14、EN 該動(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)物,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的例子：動(dòng)物識(shí)別系統(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)物 AN

15、D 是黃褐色 AND 身上有黑色條紋 THEN 該動(dòng)物是虎 r11: IF 該動(dòng)物是有蹄類動(dòng)物 AND 有長脖子 AND 有長腿 AND 身上有暗斑點(diǎn) THEN 該動(dòng)物是長頸鹿,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的例子：動(dòng)物識(shí)別系統(tǒng) r12: IF 動(dòng)物是有蹄類動(dòng)物 AND 身上有黑色條紋 THEN 該動(dò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)物是信天翁 初始總數(shù)據(jù)庫包含的事實(shí)有： 動(dòng)物有暗斑點(diǎn)，有長脖子，有長腿，有奶，有蹄,產(chǎn)生式系統(tǒng),該例子的部分推理網(wǎng)絡(luò)如下：,圖中最上層的結(jié)點(diǎn)稱為“假設(shè)”或“結(jié)論” 中間結(jié)點(diǎn)稱為“中間假設(shè)”； 終結(jié)點(diǎn)稱為“證據(jù)”或“事實(shí)”；,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的主要優(yōu)點(diǎn) 自然性：采用“如果，則”的形式，人類的判斷性知識(shí)基本一致。 模塊性：規(guī)則是規(guī)則庫中最基本的知識(shí)單元，各規(guī)則之間只能通過總數(shù)據(jù)庫發(fā)生聯(lián)系，