《湘潭大學(xué)人工智能課件確定性推理part8》由會員分享，可在線閱讀，更多相關(guān)《湘潭大學(xué)人工智能課件確定性推理part8（35頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、,,,,Click to edit Master text styles,,Second level,,Third level,,Fourth level,,Fifth level,,Click to edit Master title style,,,,,,Artificial Intelligence (AI),人工智能,第二章：知識表示與推理,內(nèi)容提要,,第二章：知識表示與推理,,1.,推理的基本概念,,2.,搜索策略,,3.,自然演繹推理,,4.,消解演繹推理,,5.,基于規(guī)則的演繹推理,,二、確定性推理,基于規(guī)則的演繹推理,規(guī)則演繹系統(tǒng),,規(guī)則正向演繹系統(tǒng),,規(guī)則逆向演繹系統(tǒng),,規(guī)則

2、雙向演繹系統(tǒng),,規(guī)則逆向演繹系統(tǒng),規(guī)則逆向演繹推理過程：,,規(guī)則逆向演繹推理過程是從待證明的問題，即目標(biāo)公式的與,/,或樹出發(fā)，通過逆向地使用蘊含式（,B,規(guī)則），對目標(biāo)公式的與,/,或樹進(jìn)行變換，直到得出包含已知事實的終止條件為止。,,規(guī)則逆向演繹系統(tǒng),,目標(biāo)公式的表示：與,/,或形變換，與,/,或樹表示,,B,規(guī)則的表示形式,,已知事實的表示形式,,規(guī)則逆向演繹推理過程,目標(biāo)公式的與,/,或形變換,在與,/,或形逆向演繹推理中，要求,目標(biāo)公式采用與,/,或形表示,，其化簡采用與正向系統(tǒng)中對事實表達(dá)式處理的,對偶形式。,,轉(zhuǎn)化步驟,,要用,存在量詞,約束變元的,Skolem,函數(shù)來替換由,全

3、稱量詞,約束的相應(yīng)變元，消去全稱量詞。,（隱含著變量受存在量詞的約束 ）,,再消去,存在量詞,，并進(jìn)行變元換名，,使主析取元之間具有不同的變元名,。,目標(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)于為何需用對偶方式消去量詞，這里不作形式證明，僅通過與消解反演方法作對比來加以直觀

4、說明：,在消解反演中，需將目標(biāo)公式取反，存在量詞約束變量就成為全稱量詞約束變量。,,目標(biāo)公式的與,/,或樹表示,目標(biāo)公式的與,/,或形也可用與,/,或樹表示出來，其表示方法與正向演繹推理中事實的與或樹表示略有不同：,,子表達(dá)式之間的,析取,關(guān)系用單一連接符連接，表示為,或,的關(guān)系；,,子表達(dá)式之間的,合取,關(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

5、(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),B,規(guī)則的表示形式,B,規(guī)則的表示形示形式,,,W→L,,其中，前項,W,為任一,與,/,或形公式,，后項,L,為一,單文字,。,,這里要求,B,規(guī)則的右邊為文字，是因為推理時要用它與目標(biāo)與或樹中的葉節(jié)點進(jìn)行匹配（合一），而目標(biāo)與或樹中的葉節(jié)點是文字。,,如果已知的,B,規(guī)則不是要求的形式，

6、可用與轉(zhuǎn)化,F,規(guī)則類似的方法把它轉(zhuǎn)化為規(guī)定的形式。,,特別地，當(dāng),B,規(guī)則為,W→L,1,∧L,2,時，則可化件為兩條規(guī)則,W→L,1,和,W→L,2,進(jìn)行處理。,已知事實的表示形式,已知事實的表示形式,,反向演繹系統(tǒng)的事實表達(dá)式限制為,文字,合取形式，如：,,,F,1,∧F,2,∧ …∧F,n,,其中，每個,F,i,（,i=1,2,…,n,）都為,單文字,，且都可單獨起作用，因此可表示為如下集合形式,,,{ F,1,，,F,2,，,…,，,F,n,},規(guī)則逆向演繹推理過程,規(guī)則逆向演繹推理,,從目標(biāo)公式的與,/,或樹出發(fā)，通過運用,B,規(guī)則最終得到了某個終止在事實節(jié)點上的,一致解圖,，推理

7、就可成功結(jié)束,,推理過程,,1,）首先用與,/,或樹把目標(biāo)公式表示出來；,,2,）用,B,規(guī)則的右部和與,/,或樹的葉節(jié)點進(jìn)行匹配，并將匹配成功的,B,規(guī)則加入到與,/,或樹中；,,3,）重復(fù)進(jìn)行步驟,2,，直到產(chǎn)生某個終止在事實節(jié)點上的一致解圖為止。這里的,“一致解圖”,是指在推理過程中所用到的,置換應(yīng)該是一致的,。,規(guī)則逆向演繹推理過程,例：設(shè)有如下事實及規(guī)則,,事實：,,f,1,: DOG(Fido),Fido,是一只狗,,f,2,:,?,,BARKS(Fido),Fido,是不叫的,,f,3,: WAGS-TAIL(Fido),Fido,搖尾巴,,f,4,: MEOWS(Myrt

8、le),貓咪的名字叫,Myrtle,規(guī)則逆向演繹推理過程,規(guī)則：,,r,1,: (WAGS-TAIL(x,1,)∧DOG(x,1,))→ FRIENDLY(x,1,),,,搖尾巴的狗是溫順的狗,,r,2,: (FRIENDLY(x,2,)∧,?,,BARKS(x,2,))→,?,,AFRAID(y,2,, x,2,),,溫順又不叫的東西是不值得害怕的,,r,3,: DOG(x,3,)→ANIMAL(x,3,),：,狗為動物,,r,4,: CAT(x,4,)→ANIMAL(x,4,),：,貓為動物,,r,5,: MEOWS(x,5,)→CAT(x,5,),：,貓咪是貓,,規(guī)則逆向演繹推

9、理過程,問題：,,是否存在這樣的一只貓和一條狗，使得這只貓不害怕這只狗？,,該問題的目標(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(x,5,),MEOWS(x),MEOWS(Myrtle,),DOG(Fido,),?AFRAID(y,2,,x,2,),?BA

10、RKS(y),?BARKS(Fido),FRIENDLY(y),FRIENDLY(x,1,),WAGS-TAIL(y),DOG(y),WAGS-TAIL(Fido),DOG(Fido),,,,,,,,,{,Fido/y,},{,x,5,/x,},{y,2,/x , x,2,/y},r,5,r,2,r,1,{,Myrtle/x,},{,Fido/y,},{x,1,/y},{,Fido/y,},該圖有,8,條匹配弧，每條弧上都有一置換。其中,終止在事實節(jié)點上的置換為,{Myrtle/x},和,{Fido/y},。,把它們應(yīng)用到目標(biāo)公式，就得到該問題的解：,,CAT({Myrtle}∧DOG(Fid

11、o)∧,?,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)公式用子句表示，每一個子句是文字的析?。?,與,/,或形逆向演繹推理要求,事實公式是文字的合取,,正向和逆向的演繹推理都存在一定的局限性。,為了克服這些局限，充分發(fā)揮各自的長處，可進(jìn)行雙向演繹推理。,規(guī)則雙向演繹系統(tǒng),與,/,或形雙向演繹推理是建立在正向演繹推理和逆向演繹推理基礎(chǔ)上的，它由表示,目標(biāo),及表示已知,事實,的,兩個與,/,或樹,結(jié)構(gòu)組成，

12、這些與,/,或樹分別由正向演繹的,F,規(guī)則,和逆向演繹的,B,規(guī)則,進(jìn)行操作，并且仍然限制,F,規(guī)則為單文字的左部，,B,規(guī)則為單文字的右部。,,雙向演繹推理的,難點在于終止條件,，只有當(dāng)正向和逆向推理的與,/,或樹對應(yīng)的葉節(jié)點都可合一時，推理才能結(jié)束。其時機(jī)與判斷都難于掌握。,,更實用化的方式是將復(fù)雜的問題求解任務(wù)劃分為相對簡單的若干子任務(wù)，然后根據(jù)子任務(wù)的特點選用正向或逆向演繹推理方式，以便充分發(fā)揮兩種方式各自的優(yōu)勢。,內(nèi)容提要,,第三章：確定性推理,,1.,推理的基本概念,,2.,搜索策略,,3.,自然演繹推理,,4.,消解演繹推理,,5.,基于規(guī)則的演繹推理,,6.,產(chǎn)生式系統(tǒng),內(nèi)容提

13、要,,第二章：知識表示與推理,,1.,推理的基本概念,,2.,搜索策略,,3.,自然演繹推理,,4.,消解演繹推理,,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,→

14、,Q,或者,IF P THEN Q,,P,是產(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ū)別：,,(1),蘊涵式表示的知識只能是精確的，產(chǎn)生式表示的知識可以是不確定的。,,(2),蘊含式的匹配一定要求是精確的，而產(chǎn)生式的匹配可以是不確定的。,,產(chǎn)生式與條件語句的主要區(qū)別：,,(1),前件結(jié)構(gòu)不同：產(chǎn)生式的前

15、件可以是一個復(fù)雜的結(jié)構(gòu)，而程序設(shè)計語言中條件語句的左部是布爾表達(dá)式。,,(2),控制流程不同：產(chǎn)生式系統(tǒng)中滿足前提條件的規(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ī)則被激活，由它推出的結(jié)論將被作為新的事實放入總數(shù)據(jù)庫，成為后面推理的已知事實。,產(chǎn)生式規(guī)則：,是一個規(guī)則庫，也稱知識庫,,。用于存放與求解問題有關(guān)的,所有規(guī)則的

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

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

18、 IF,該動物有毛發(fā),THEN,該動物是哺乳動物,,r,2,: IF,該動物有奶,THEN,該動物是哺乳動物,,r,3,: IF,該動物有羽毛,THEN,該動物是鳥,,r,4,: IF,該動物會飛,AND,會下蛋,THEN,該動物是鳥,,r,5,: IF,該動物吃肉,THEN,該動物是食肉動物,,r,6,: IF,該動物有犬齒,AND,有爪,AND,眼盯前方,,,THEN,該動物是食肉動物,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的例子：,動物識別系統(tǒng),,r,7,: IF,該動物是哺乳動物,AND,有蹄,THEN,該動物是有蹄類動物,,r,8,: IF,該動物是哺乳動物,AND,是嚼反芻動物,THEN,該動物是

19、有蹄類動物,,r,9,: IF,該動物是哺乳動物,AND,是食肉動物,AND,是黃褐,AND,身上有暗斑點,THEN,該動物是金錢豹,,r,10,: IF,該動物是哺乳動物,AND,是食肉動物,AND,是黃褐色,AND,身上有黑色條紋,THEN,該動物是虎,,r,11,: IF,該動物是有蹄類動物,AND,有長脖子,AND,有長腿,AND,身上有暗斑點,THEN,該動物是長頸鹿,,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的例子：,動物識別系統(tǒng),,r,12,: IF,動物是有蹄類動物,AND,身上有黑色條紋,THEN,該動物是斑馬,,r,13,: IF,該動物是鳥,AND,有長脖子,AND,有長腿,AND,不會飛

20、,AND,有黑白二色,THEN,該動物是鴕鳥,,r,14,: IF,該動物是鳥,AND,會游泳,AND,不會飛,AND,有黑白二色,THEN,該動物是企鵝,,r,15,: IF,該動物是鳥,AND,善飛,THEN,該動物是信天翁,,初始總數(shù)據(jù)庫包含的事實有：,,動物有暗斑點，有長脖子，有長腿，有奶，有蹄,產(chǎn)生式系統(tǒng),該例子的部分推理網(wǎng)絡(luò)如下：,,長頸鹿,斑馬,長脖子,長腿,暗斑點,有蹄類,黑條紋,有蹄,哺乳動物,有毛,r,2,r,7,r,11,r,12,有奶,r,1,圖中最上層的結(jié)點稱為“假設(shè)”或“結(jié)論”,,中間結(jié)點稱為“中間假設(shè)”；,,終結(jié)點稱為“證據(jù)”或“事實”；,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的

21、主要優(yōu)點,,自然性：,采用“如果,……,，則,……”,的形式，人類的判斷性知識基本一致。,,模塊性：,規(guī)則是規(guī)則庫中最基本的知識單元，各規(guī)則之間只能通過總數(shù)據(jù)庫發(fā)生聯(lián)系，而不能相互調(diào)用，從而增加了規(guī)則的模塊性。,,有效性：,產(chǎn)生式知識表示法既可以表示確定性知識，又可以表示不確定性知識，既有利于表示啟發(fā)性知識，又有利于表示過程性知識。,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的主要缺點,,效率較低：,各規(guī)則之間的聯(lián)系必須以總數(shù)據(jù)庫為媒介。并且，其求解過程是一種反復(fù)進(jìn)行的“匹配,—,沖突消解,—,執(zhí)行”過程。這樣的執(zhí)行方式將導(dǎo)致執(zhí)行的低效率。,,不便于表示結(jié)構(gòu)性知識：,由于產(chǎn)生式表示中的知識具有一致格式，且規(guī)則之間不能相互調(diào)用，因此那種具有結(jié)構(gòu)關(guān)系或?qū)哟侮P(guān)系的知識則很難以自然的方式來表示。,,問題？,