,,,,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ī)則雙向演繹系統(tǒng),,規(guī)則逆向演繹系統(tǒng),規(guī)則逆向演繹推理過程：,,規(guī)則逆向演繹推理過程是從待證明的問題，即目標公式的與,/,或樹出發(fā)，通過逆向地使用蘊含式（,B,規(guī)則），對目標公式的與,/,或樹進行變換，直到得出包含已知事實的終止條件為止。,,規(guī)則逆向演繹系統(tǒng),,目標公式的表示：與,/,或形變換，與,/,或樹表示,,B,規(guī)則的表示形式,,已知事實的表示形式,,規(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))∨¬S(y))),,,關于為何需用對偶方式消去量詞，這里不作形式證明，僅通過與消解反演方法作對比來加以直觀說明：,在消解反演中，需將目標公式取反，存在量詞約束變量就成為全稱量詞約束變量。,,目標公式的與,/,或樹表示,目標公式的與,/,或形也可用與,/,或樹表示出來，其表示方法與正向演繹推理中事實的與或樹表示略有不同：,,子表達式之間的,析取,關系用單一連接符連接，表示為,或,的關系；,,子表達式之間的,合取,關系則用,k,線連接符連接，表示為,與,的關系。,,例如：,對上述目標公式的與,/,或形，可用如下的與,/,或樹表示。,目標公式的與,/,或樹表示,¬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é)點用它們之間的合取及析取關系連接起來，就可得到原目標公式的三個子目標：,,¬,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ī)則的右邊為文字，是因為推理時要用它與目標與或樹中的葉節(jié)點進行匹配（合一），而目標與或樹中的葉節(jié)點是文字。,,如果已知的,B,規(guī)則不是要求的形式，可用與轉(zhuǎn)化,F,規(guī)則類似的方法把它轉(zhuǎn)化為規(guī)定的形式。,,特別地，當,B,規(guī)則為,W→L,1,∧L,2,時，則可化件為兩條規(guī)則,W→L,1,和,W→L,2,進行處理。,已知事實的表示形式,已知事實的表示形式,,反向演繹系統(tǒng)的事實表達式限制為,文字,合取形式，如：,,,F,1,∧F,2,∧ …∧F,n,,其中，每個,F,i,（,i=1,2,…,n,）都為,單文字,，且都可單獨起作用，因此可表示為如下集合形式,,,{ F,1,，,F,2,，,…,，,F,n,},規(guī)則逆向演繹推理過程,規(guī)則逆向演繹推理,,從目標公式的與,/,或樹出發(fā)，通過運用,B,規(guī)則最終得到了某個終止在事實節(jié)點上的,一致解圖,，推理就可成功結(jié)束,,推理過程,,1,）首先用與,/,或樹把目標公式表示出來；,,2,）用,B,規(guī)則的右部和與,/,或樹的葉節(jié)點進行匹配，并將匹配成功的,B,規(guī)則加入到與,/,或樹中；,,3,）重復進行步驟,2,，直到產(chǎn)生某個終止在事實節(jié)點上的一致解圖為止。這里的,“一致解圖”,是指在推理過程中所用到的,置換應該是一致的,。,規(guī)則逆向演繹推理過程,例：設有如下事實及規(guī)則,,事實：,,f,1,: DOG(Fido),Fido,是一只狗,,f,2,:,¬,,BARKS(Fido),Fido,是不叫的,,f,3,: WAGS-TAIL(Fido),Fido,搖尾巴,,f,4,: MEOWS(Myrtle),貓咪的名字叫,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ī)則逆向演繹推理過程,問題：,,是否存在這樣的一只貓和一條狗，使得這只貓不害怕這只狗？,,該問題的目標公式為：,,(,?,x) (,?,y) (CAT(x)∧DOG(y)∧,¬,AFRAID(x, y)),,改目標公式經(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,),¬BARKS(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},。,把它們應用到目標公式，就得到該問題的解：,,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),,與,/,或形正向演繹推理要求,目標公式是文字的析取,（目標公式用子句表示，每一個子句是文字的析?。?,與,/,或形逆向演繹推理要求,事實公式是文字的合取,,正向和逆向的演繹推理都存在一定的局限性。,為了克服這些局限，充分發(fā)揮各自的長處，可進行雙向演繹推理。,規(guī)則雙向演繹系統(tǒng),與,/,或形雙向演繹推理是建立在正向演繹推理和逆向演繹推理基礎上的，它由表示,目標,及表示已知,事實,的,兩個與,/,或樹,結(jié)構(gòu)組成，這些與,/,或樹分別由正向演繹的,F,規(guī)則,和逆向演繹的,B,規(guī)則,進行操作，并且仍然限制,F,規(guī)則為單文字的左部，,B,規(guī)則為單文字的右部。,,雙向演繹推理的,難點在于終止條件,，只有當正向和逆向推理的與,/,或樹對應的葉節(jié)點都可合一時，推理才能結(jié)束。其時機與判斷都難于掌握。,,更實用化的方式是將復雜的問題求解任務劃分為相對簡單的若干子任務，然后根據(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)生式表示法,,事實的表示,,確定性知識，事實可用如下三元組表示：,,（對象，屬性，值）,或,（關系，對象,1,，對象,2,）,,如,:,（雪，顏色，白）,或,（熱愛，王峰，祖國）,,非確定性知識，事實可用如下四元組表示：,,（對象，屬性，值，可信度因子）,,其中，“可信度因子”是指該事實為真的相信程度?？捎?[0,1],之間的一個實數(shù)來表示。,,,,產(chǎn)生式系統(tǒng),產(chǎn)生式表示法,,規(guī)則的表示：,P,→,Q,或者,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)生式表示的知識可以是不確定的。,,(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),控制策略,產(chǎn)生式規(guī)則,總數(shù)據(jù)庫,總數(shù)據(jù)庫：,存放求解問題的各種當前信息，如：問題的初始狀態(tài)，輸入的事實，中間結(jié)論及最終結(jié)論等。,,推理過程中，當規(guī)則庫中某條規(guī)則的前提可以和總數(shù)據(jù)庫的已知事實匹配時，該規(guī)則被激活，由它推出的結(jié)論將被作為新的事實放入總數(shù)據(jù)庫，成為后面推理的已知事實。,產(chǎn)生式規(guī)則：,是一個規(guī)則庫，也稱知識庫,,。用于存放與求解問題有關的,所有規(guī)則的集合,.,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu),控制策略,產(chǎn)生式規(guī)則,總數(shù)據(jù)庫,控制策略：,亦稱推理機，用于控制整個產(chǎn)生式系統(tǒng)的運行，,決定,問題求解過程的,推理線路,。,,控制系統(tǒng)的主要任務包括：,,選擇匹配,,沖突消解,,執(zhí)行操作,,終止推理,,路徑解釋,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的推理,,正向推理：,從一組表示事實的謂詞或命題出發(fā)，使用一組,產(chǎn)生式規(guī)則,，用以證明該謂詞公式或命題是否成立。,,設有規(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,推出,,,P,4,規(guī)則,3,規(guī)則,2,規(guī)則,1,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(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ī)則：,,r,1,: 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,該動物是有蹄類動物,,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,不會飛,AND,有黑白二色,THEN,該動物是鴕鳥,,r,14,: IF,該動物是鳥,AND,會游泳,AND,不會飛,AND,有黑白二色,THEN,該動物是企鵝,,r,15,: IF,該動物是鳥,AND,善飛,THEN,該動物是信天翁,,初始總數(shù)據(jù)庫包含的事實有：,,動物有暗斑點，有長脖子，有長腿，有奶，有蹄,產(chǎn)生式系統(tǒng),該例子的部分推理網(wǎng)絡如下：,,長頸鹿,斑馬,長脖子,長腿,暗斑點,有蹄類,黑條紋,有蹄,哺乳動物,有毛,r,2,r,7,r,11,r,12,有奶,r,1,圖中最上層的結(jié)點稱為“假設”或“結(jié)論”,,中間結(jié)點稱為“中間假設”；,,終結(jié)點稱為“證據(jù)”或“事實”；,產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的主要優(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ù)庫為媒介。并且，其求解過程是一種反復進行的“匹配,—,沖突消解,—,執(zhí)行”過程。這樣的執(zhí)行方式將導致執(zhí)行的低效率。,,不便于表示結(jié)構(gòu)性知識：,由于產(chǎn)生式表示中的知識具有一致格式，且規(guī)則之間不能相互調(diào)用，因此那種具有結(jié)構(gòu)關系或?qū)哟侮P系的知識則很難以自然的方式來表示。,,問題？,