西電人工智能確定性推理ar5

ArtificialIntelligence(AI)

人工智能主講：戚玉濤Email：第三章：確定性推理內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.自然演繹推理4.歸結(jié)演繹推理5.基于規(guī)則的演繹推理6.產(chǎn)生式系統(tǒng)基于規(guī)則的演繹推理規(guī)則演繹系統(tǒng)規(guī)則正向演繹系統(tǒng)規(guī)則逆向演繹系統(tǒng)規(guī)則雙向演繹系統(tǒng)規(guī)則逆向演繹系統(tǒng)規(guī)則逆向演繹推理過程：規(guī)則逆向演繹推理過程是從待證明的問題，即目標(biāo)公式的與/或樹出發(fā)，通過逆向地使用蘊含式（B規(guī)則），對目標(biāo)公式的與/或樹進行變換，直到得出包含已知事實的終止條件為止。規(guī)則逆向演繹系統(tǒng)目標(biāo)公式的表示：與/或形變換，與/或樹表示B規(guī)則的表示形式已知事實的表示形式規(guī)則逆向演繹推理過程目標(biāo)公式的與/或形變換在與/或形逆向演繹推理中，要求目標(biāo)公式采用與/或形表示，其化簡采用與正向系統(tǒng)中對事實表達式處理的對偶形式。轉(zhuǎn)化步驟要用存在量詞約束變元的Skolem函數(shù)來替換由全稱量詞約束的相應(yīng)變元，消去全稱量詞。（隱含著變量受存在量詞的約束）再消去存在量詞，并進行變元換名，使主析取元之間具有不同的變元名。目標(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)))變元換名后為

?P(f(z))∨(Q(f(y),y)∧(?R(f(y))∨?S(y)))關(guān)于為何需用對偶方式消去量詞，這里不作形式證明，僅通過與歸結(jié)反演方法作對比來加以直觀說明：在歸結(jié)反演中，需將目標(biāo)公式取反，存在量詞約束變量就成為全稱量詞約束變量。

目標(biāo)公式的與/或樹表示目標(biāo)公式的與/或形也可用與/或樹表示出來，其表示方法與正向演繹推理中事實的與或樹表示略有不同：子表達式之間的析取關(guān)系用單一連接符連接，表示稱或的關(guān)系；子表達式之間的合取關(guān)系則用k線連接符連接，表示為與的關(guān)系。例如：對上述目標(biāo)公式的與/或形，可用如下的與/或樹表示。目標(biāo)公式的與/或樹表示?P(f(z))∨Q(f(y),y)∧(?R(f(y))∨?S(y))?P(f(z))Q(f(y),y)∧(?R(f(y))∨?S(y))Q(f(y),y)?R(f(y))∨?S(y)?R(f(y))?S(y)若把葉節(jié)點用它們之間的合取及析取關(guān)系連接起來，就可得到原目標(biāo)公式的三個子目標(biāo)：

?P(f(z))；Q(f(y),y)∧?R(f(y))；Q(f(y),y)∧?S(y)子目標(biāo)是文字的合取式B規(guī)則的表示形式B規(guī)則的表示形示形式

W→L其中，前項W為任一與/或形公式，后項L為一單文字。這里要求B規(guī)則的右邊為文字，是因為推理時要用它與目標(biāo)與或樹中的葉節(jié)點進行匹配（合一），而目標(biāo)與或樹中的葉節(jié)點是文字。如果已知的B規(guī)則不是要求的形式，可用與轉(zhuǎn)化F規(guī)則類似的方法把它轉(zhuǎn)化為規(guī)定的形式。特別地，當(dāng)B規(guī)則為W→L1∧L2時，則可化件為兩條規(guī)則W→L1和W→L2進行處理。已知事實的表示形式已知事實的表示形式反向演繹系統(tǒng)的事實表達式限制為文字合取形式，如：

F1∧F2∧…∧Fn其中，每個Fi（i=1,2,…,n）都為單文字，且都可單獨起作用，因此可表示為如下集合形式

{F1，F(xiàn)2，…，F(xiàn)n}規(guī)則逆向演演繹推理過過程規(guī)則逆向演演繹推理從目標(biāo)公式式的與/或樹出發(fā)，，通過運用用B規(guī)則最終得得到了某個個終止在事事實節(jié)點上上的一致解解圖，推理理就可成功功結(jié)束推理過程1）首先用與與/或樹把目標(biāo)標(biāo)公式表示示出來；2）用B規(guī)則的右部部和與/或樹的葉節(jié)節(jié)點進行匹匹配，并將將匹配成功功的B規(guī)則加入到到與/或樹中；3）重復(fù)進行行步驟2，直到產(chǎn)生生某個終止止在事實節(jié)節(jié)點上的一一致解圖為為止。這里里的“一致致解圖”是是指在推理理過程中所所用到的代換應(yīng)該是是一致的。規(guī)則逆向演演繹推理過過程例：設(shè)有如如下事實及及規(guī)則事實：f1:DOG(Fido)Fido是一只狗f2:?BARKS(Fido)Fido是不叫的f3:WAGS-TAIL(Fido)Fido搖尾巴f4: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ī)則逆向演演繹推理過過程問題：是否存在這這樣的一只只貓和一條條狗，使得得這只貓不不害怕這只只狗？該問題的目目標(biāo)公式為為：(?x)(?y)(CAT(x)∧DOG(y)∧?AFRAID(x,y))改目標(biāo)公式式經(jīng)變換后后得到CAT(x)∧DOG(y)∧?AFRAID(x,y)用逆向推理理求解該問問題的演繹繹過程如下下圖所示：：規(guī)則逆向演演繹推理過過程CAT(x)∧DOG(y)∧?

AFRAID(x,y)CAT(x)DOG(y)?AFRAID(x,y)CAT(x5)MEOWS(x)MEOWS(Myrtle)DOG(Fido)?AFRAID(y2,x2)?BARKS(y)?BARKS(Fido)FRIENDLY(y)FRIENDLY(x1)WAGS-TAIL(y)DOG(y)WAGS-TAIL(Fido)DOG(Fido){Fido/y}{x5/x}{y2/x,x2/y}r5r2r1{Myrtle/x}{Fido/y}{x1/y}{Fido/y}該圖有8條匹配弧，，每條弧上上都有一置置換。其中中終止在事實實節(jié)點上的的置換為{Myrtle/x}和{Fido/y}。把它們應(yīng)用用到目標(biāo)公公式，就得得到該問題題的解：CAT({Myrtle}∧∧DOG(Fido)∧?AFRAID({Myrtle,Fido}基于規(guī)則的的演繹推理理規(guī)則演繹系系統(tǒng)規(guī)則正向演演繹系統(tǒng)規(guī)則逆向演演繹系統(tǒng)規(guī)則雙向演演繹系統(tǒng)規(guī)則雙向演演繹系統(tǒng)規(guī)則雙向演演繹系統(tǒng)與/或形正向演演繹推理要要求目標(biāo)公式是是文字的析析取（目標(biāo)公式式用子句表表示，每一一個子句是是文字的析析?。┡c/或形逆向演演繹推理要要求事實實公公式式是是文文字字的的合合取取正向向和和逆逆向向的的演演繹繹推推理理都都存存在在一一定定的的局局限限性性。。為了了克克服服這這些些局局限限，，充充分分發(fā)發(fā)揮揮各各自自的的長長處處，，可可進進行行雙雙向向演演繹繹推推理理。。規(guī)則則雙雙向向演演繹繹系系統(tǒng)統(tǒng)與/或形形雙雙向向演演繹繹推推理理是是建建立立在在正正向向演演繹繹推推理理和和逆逆向向演演繹繹推推理理基基礎(chǔ)礎(chǔ)上上的的，，它它由由表表示示目目標(biāo)標(biāo)及及表表示示一一直直事事實實的的兩兩個個與與/或樹樹結(jié)結(jié)構(gòu)構(gòu)組組成成，，這這些些與與/或樹樹分分別別由由正正向向演演繹繹的的F規(guī)則則和和逆逆向向演演繹繹的的B規(guī)則則進進行行操操作作，，并并且且仍仍然然限限制制F規(guī)則則為為單單文文字字的的左左部部，，B規(guī)則則為為單單文文字字的的右右部部。。雙向向演演繹繹推推理理的的難點點在在于于終終止止條條件件，只只有有當(dāng)當(dāng)正正向向和和逆逆向向推推理理的的與與/或樹樹對對應(yīng)應(yīng)的的葉葉節(jié)節(jié)點點都都可可合合一一時時，，推推理理才才能能結(jié)結(jié)束束。。其其時時機機與與判判斷斷都都難難于于掌掌握握。。更實實用用化化的的方方式式是是將將復(fù)復(fù)雜雜的的問問題題求求解解任任務(wù)務(wù)劃劃分分為為相相對對簡簡單單的的若若干干子子任任務(wù)務(wù)，，然然后后根根據(jù)據(jù)子子任任務(wù)務(wù)的的特特點點選選用用正正向向或或逆逆向向演演繹繹推推理理方方式式，，以以便便充充分分發(fā)發(fā)揮揮兩兩種種方方式式各各自自的的優(yōu)優(yōu)勢勢。。內(nèi)容容提提要要第三三章章：：確確定定性性推推理理1.推理的基本概概念2.搜索策略3.自然演繹推理理4.歸結(jié)演繹推理理5.基于規(guī)則的演演繹推理6.產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)產(chǎn)生式表示法法事實的表示確定性知識，，事實可用如如下三元組表表示：（對象，屬性性，值）或（關(guān)系，對象象1，對象2）如:（雪，顏色，，白）或（熱愛，王峰峰，祖國）非確定性知識識，事實可用用如下四元組組表示：（對象，屬性性，值，可信信度因子）其中，“可信信度因子”是是指該事實為為真的相信程程度?？捎肹0,1]之間的一個實實數(shù)來表示。。產(chǎn)生式系統(tǒng)產(chǎn)生式表示法法規(guī)則的表示：：P→Q或者IFPTHENQP是產(chǎn)生式的前前提，也稱為為前件，它給給出了該產(chǎn)生生式可否使用用的先決條件件，由事實的邏輯組組合來構(gòu)成。Q是一組結(jié)論或或操作，也稱稱為產(chǎn)生式的的后件，它指指出當(dāng)前題P滿足時，應(yīng)該該推出的結(jié)論或應(yīng)該執(zhí)行的動作。產(chǎn)生式的含義義：如果前提P滿足，則可推推出結(jié)論Q或執(zhí)行Q所規(guī)定的操作作產(chǎn)生式系統(tǒng)產(chǎn)生式與蘊涵涵式的主要區(qū)區(qū)別：(1)蘊涵式表示的的知識只能是是精確的，產(chǎn)產(chǎn)生式表示的的知識可以是是不確定的。。(2)蘊含式的匹配配一定要求是是精確的，而而產(chǎn)生式的匹匹配可以是不不確定的。產(chǎn)生式與條件件語句的主要要區(qū)別：(1)前件結(jié)構(gòu)不同同：產(chǎn)生式的的前件可以是是一個復(fù)雜的的的結(jié)構(gòu)，而而程序設(shè)計語語言中條件語語句的左部是是布爾表達式式。(2)控制流程不同同：產(chǎn)生式系系統(tǒng)中滿足前前提條件的規(guī)規(guī)則被激活后后，不一定被被立即執(zhí)行，，能否執(zhí)行將將取決于沖突突消解策略，，而條件語句句嚴(yán)格執(zhí)行。。產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)的的基本結(jié)構(gòu)控制策略產(chǎn)生式規(guī)則總數(shù)據(jù)庫總數(shù)據(jù)庫：存放求解問題題的各種當(dāng)前前信息，如：：問題的初始始狀態(tài)，輸入入的事實，中中間結(jié)論及最最終結(jié)論等。。推理過程中，，當(dāng)規(guī)則庫中中某條規(guī)則的的前提可以和和總數(shù)據(jù)庫的的已知事實匹匹配時，該規(guī)規(guī)則被激活，，由它推出的的結(jié)論將被作作為新的事實實放入總數(shù)據(jù)據(jù)庫，成為后后面推理的已已知事實。產(chǎn)生式規(guī)則：：是一個規(guī)則庫庫，也稱知識識庫。用于存放與與求解問題有有關(guān)的所有規(guī)規(guī)則的集合產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)的的基本結(jié)構(gòu)控制策略產(chǎn)生式規(guī)則總數(shù)據(jù)庫控制策略：亦稱推理機，，用于控制整整個產(chǎn)生式系系統(tǒng)的運行，，決定問題求求解過程的推推理線路?？刂葡到y(tǒng)的主主要任務(wù)包括括：選擇匹配沖突消解執(zhí)行操作終止推理路徑解釋產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)的的推理正向推理：從一組表示事事實的謂詞或或命題出發(fā)，，使用一組產(chǎn)產(chǎn)生式規(guī)則，，用以證明該該謂詞公式或或命題是否成成立。設(shè)有規(guī)則集合合R1至R3R1：P1→P2R2：P2→P3R3：P3→P4正向推推理過過程產(chǎn)生式式系統(tǒng)統(tǒng)產(chǎn)生式式系統(tǒng)統(tǒng)的推推理逆向推推理：：從表示示目標(biāo)標(biāo)的謂謂詞或或命題題出發(fā)發(fā)，使使用一一組產(chǎn)產(chǎn)生式式規(guī)則則證明明事實實謂詞詞或命命題成成立，，即首首先提提出一一批假假設(shè)目目標(biāo)，，然后后逐一一驗證證這些些假設(shè)設(shè)。逆向推推理過過程產(chǎn)生式式系統(tǒng)統(tǒng)產(chǎn)生式式系統(tǒng)統(tǒng)的推推理雙向推推理：：雙向推推理的的推理理策略略是同同時從從目標(biāo)標(biāo)向事事實推推理和和從事事實向向目標(biāo)標(biāo)推理理，并并在推推理過過程中中的某某個步步驟，，實現(xiàn)現(xiàn)事實實與目目標(biāo)的的匹配配。雙向推推理過過程產(chǎn)生式式系統(tǒng)統(tǒng)產(chǎn)生式式系統(tǒng)統(tǒng)的例例子：：動物識識別系系統(tǒng)該系統(tǒng)統(tǒng)可以以識別別老虎虎、金金錢豹豹、斑斑馬、、長頸頸鹿、、企鵝鵝、信信天翁翁這6種動物物。其規(guī)則則庫包包含如如下15條規(guī)則則：r1:IF該動物物有毛毛發(fā)THEN該動物物是哺哺乳動動物r2:IF該動物物有奶奶THEN該動物物是哺哺乳動動物r3:IF該動物物有羽羽毛THEN該動物物是鳥鳥r4:IF該動物物會飛飛AND會下蛋蛋THEN該動物物是鳥鳥r5:IF該動物物吃肉肉THEN該動物物是食食肉動動物r6:IF該動物物有犬犬齒AND有爪AND眼盯前前方THEN該動物物是食食肉動動物產(chǎn)生式式系統(tǒng)統(tǒng)產(chǎn)生式式系統(tǒng)統(tǒng)的例例子：：動物識識別系系統(tǒng)r7:IF該動物物是哺哺乳動動物AND有蹄THEN該動物物是有有蹄類類動物物r8:IF該動物物是哺哺乳動動物AND是嚼反反芻動動物THEN該動物物是有有蹄類類動物物r9:IF該動物物是哺哺乳動動物AND是食肉肉動物物AND是黃褐褐AND身上有有暗斑斑點THEN該動物物是金金錢豹豹r10:IF該動物是是哺乳動動物AND是食肉動動物AND是黃褐色色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ù)數(shù)據(jù)庫包包含的事事實有：：動物有暗暗斑點，，有長脖脖子，有有長腿