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

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

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

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

5、作用，因此可表示為如下集合形式 F1，F(xiàn)2， ，F(xiàn)n ,規(guī)則逆向演繹推理過程,規(guī)則逆向演繹推理 從目標公式的與/或樹出發(fā)，通過運用B規(guī)則最終得到了某個終止在事實節(jié)點上的一致解圖，推理就可成功結(jié)束 推理過程 1）首先用與/或樹把目標公式表示出來； 2）用B規(guī)則的右部和與/或樹的葉節(jié)點進行匹配，并將匹配成功的B規(guī)則加入到與/或樹中； 3）重復進行步驟2，直到產(chǎn)生某個終止在事實節(jié)點上的一致解圖為止。這里的“一致解圖”是指在推理過程中所用到的置換應該是一致的。,規(guī)則逆向演繹推理過程,例：設有如下事實及規(guī)則 事實： 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) ：狗為動物 r4: CAT(x4)ANIMAL(x4)：貓為動物 r5: MEOWS(x5)CAT(x5)：貓咪是貓,規(guī)則逆向演繹推理過程,問題： 是否存在這樣的一只貓和一條狗

7、，使得這只貓不害怕這只狗？ 該問題的目標公式為： (x) (y) (CAT(x)DOG(y)AFRAID(x, y) 改目標公式經(jīng)變換后得到 CAT(x)DOG(y) AFRAID(x, y) 用逆向推理求解該問題的演繹過程如下圖所示：,規(guī)則逆向演繹推理過程,該圖有8條匹配弧，每條弧上都有一置換。其中終止在事實節(jié)點上的置換為Myrtle/x和Fido/y。把它們應用到目標公式，就得到該問題的解：,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、 與/或形正向演繹推理要求目標公式是文字的析?。繕斯接米泳浔硎?，每一個子句是文字的析?。?與/或形逆向演繹推理要求事實公式是文字的合取 正向和逆向的演繹推理都存在一定的局限性。為了克服這些局限，充分發(fā)揮各自的長處，可進行雙向演繹推理。,規(guī)則雙向演繹系統(tǒng),與/或形雙向演繹推理是建立在正向演繹推理和逆向演繹推理基礎上的，它由表示目標及表示已知事實的兩個與/或樹結(jié)構(gòu)組成，這些與/或樹分別由正向演繹的F規(guī)則和逆向演繹的B規(guī)則進行操作，并且仍然限制F規(guī)則為單文字的左部，B規(guī)則為單文字的右部。 雙向演繹推理的難點在于終止條件，只有當正向和逆向推理的與/或樹對應的葉節(jié)點都可合一時，推理才能結(jié)束。其時機與

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

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

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

12、成為后面推理的已知事實。,產(chǎn)生式規(guī)則：是一個規(guī)則庫，也稱知識庫 。用于存放與求解問題有關(guān)的所有規(guī)則的集合.,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu),控制策略：亦稱推理機，用于控制整個產(chǎn)生式系統(tǒng)的運行，決定問題求解過程的推理線路。 控制系統(tǒng)的主要任務包括： 選擇匹配 沖突消解 執(zhí)行操作 終止推理 路徑解釋,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的推理 正向推理：從一組表示事實的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則，用以證明該謂詞公式或命題是否成立。 設有規(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)的推理 逆向推理：從表示目標的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則證明事實謂詞或命題成立，即首先提出一批假設目標，然后逐一驗證這些假設。,逆向推理過程,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的推理 雙向推理：雙向推理的推理策略是同時從目標向事實推理和從事實向目標推理，并在推理過程中的某個步驟，實現(xiàn)事實與目標的匹配。,雙向推理過程,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的例子：動物識別系統(tǒng) 該系統(tǒng)可以識別老虎、金錢豹、斑馬、長頸鹿、企鵝、信天翁這6種動物。 其規(guī)則庫包含如下15條規(guī)則： r1: IF 該動物有毛發(fā) THEN 該動物是哺乳動物 r2: IF 該動物有奶 THEN 該動物是哺乳動物 r3: IF 該動物有羽毛 TH

14、EN 該動物是鳥 r4: IF 該動物會飛 AND 會下蛋 THEN 該動物是鳥 r5: IF 該動物吃肉 THEN 該動物是食肉動物 r6: IF 該動物有犬齒 AND 有爪 AND 眼盯前方 THEN 該動物是食肉動物,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的例子：動物識別系統(tǒng) r7: IF 該動物是哺乳動物 AND 有蹄 THEN 該動物是有蹄類動物 r8: IF 該動物是哺乳動物 AND 是嚼反芻動物 THEN 該動物是有蹄類動物 r9: IF 該動物是哺乳動物 AND 是食肉動物 AND 是黃褐AND 身上有暗斑點 THEN 該動物是金錢豹 r10: IF 該動物是哺乳動物 AND 是食肉動物 AN

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