第3章 確定性推理方法 人工智能課件.ppt

第3章確定性推理方法,2,第3章確定性推理方法,第3章確定性推理方法,3,第3章確定性推理方法,3.1推理的基本概念3.2自然演繹推理3.3謂詞公式化為子句集的方法3.4海伯倫定理3.5魯賓遜歸結原理3.6歸結反演3.7應用歸結反演求解問題,4,第3章確定性推理方法,3.1推理的基本概念3.2自然演繹推理3.3謂詞公式化為子句集的方法3.4海伯倫定理3.5魯賓遜歸結原理3.6歸結反演3.7應用歸結反演求解問題,5,3.1推理的基本概念,3.1.1推理的定義3.1.2推理方式及其分類3.1.3推理的方向3.1.4沖突消解策略,6,3.1.1推理的定義,推理：,7,3.1推理的基本概念,3.1.1推理的定義3.1.2推理方式及其分類3.1.3推理的方向3.1.4沖突消解策略,8,（1）演繹推理(deductivereasoning):一般個別三段論式（三段論法）足球運動員的身體都是強壯的；高波是一名足球運動員；所以，高波的身體是強壯的。,3.1.2推理方式及其分類,演繹推理、歸納推理、默認推理,（大前提）（小前提）（結論）,9,3.1.2推理方式及其分類,演繹推理、歸納推理、默認推理,檢查全部產(chǎn)品合格,該廠產(chǎn)品合格,完全歸納推理,檢查全部樣品合格,該廠產(chǎn)品合格,不完全歸納推理,10,3.1.2推理方式及其分類,演繹推理、歸納推理、默認推理,（3）默認推理（defaultreasoning，缺省推理）知識不完全的情況下假設某些條件已經(jīng)具備所進行的推理。,11,3.1.2推理方式及其分類,2.確定性推理、不確定性推理,（1）確定性推理：推理時所用的知識與證據(jù)都是確定的，推出的結論也是確定的，其真值或者為真或者為假。（2）不確定性推理：推理時所用的知識與證據(jù)不都是確定的，推出的結論也是不確定的。,12,X：鳥X：會飛X:企鵝,3.1.2推理方式及其分類,3.單調(diào)推理、非單調(diào)推理（1）單調(diào)推理：隨著推理向前推進及新知識的加入，推出的結論越來越接近最終目標。（2）非單調(diào)推理：由于新知識的加入，不僅沒有加強已推出的結論，反而要否定它，使推理退回到前面的某一步，重新開始。,默認推理是非單調(diào)推理,基于經(jīng)典邏輯的演繹推理,13,3.1.2推理方式及其分類,4啟發(fā)式推理、非啟發(fā)式推理啟發(fā)性知識：與問題有關且能加快推理過程、提高搜索效率的知識。,目標：在腦膜炎、肺炎、流感中選擇一個產(chǎn)生式規(guī)則r1：腦膜炎r2：肺炎r3：流感啟發(fā)式知識：“腦膜炎危險”、“目前正在盛行流感”。,14,3.1推理的基本概念,3.1.1推理的定義3.1.2推理方式及其分類3.1.3推理的方向3.1.4沖突消解策略,15,3.1.3推理的方向,16,3.1.3推理的方向,正向推理（事實驅(qū)動推理）:已知事實結論基本思想（1）從初始已知事實出發(fā)，在知識庫KB中找出當前可適用的知識，構成可適用知識集KS。（2）按某種沖突消解策略從KS中選出一條知識進行推理，并將推出的新事實加入到數(shù)據(jù)庫DB中作為下一步推理的已知事實，再在KB中選取可適用知識構成KS。（3）重復（2），直到求得問題的解或KB中再無可適用的知識。,1.正向推理,17,18,3.1.3推理的方向,實現(xiàn)正向推理需要解決的問題：確定匹配（知識與已知事實）的方法。按什么策略搜索知識庫。沖突消解策略。正向推理簡單，易實現(xiàn)，但目的性不強，效率低。,1.正向推理,19,3.1.3推理的方向,逆向推理（目標驅(qū)動推理）：以某個假設目標作為出發(fā)點。基本思想：選定一個假設目標。尋找支持該假設的證據(jù)，若所需的證據(jù)都能找到，則原假設成立；若無論如何都找不到所需要的證據(jù)，說明原假設不成立的；為此需要另作新的假設。主要優(yōu)點：不必使用與目標無關的知識，目的性強，同時它還有利于向用戶提供解釋。主要缺點：起始目標的選擇有盲目性。,2.逆向推理,20,21,3.1.3推理的方向,逆向推理需要解決的問題：如何判斷一個假設是否是證據(jù)？當導出假設的知識有多條時，如何確定先選哪一條？一條知識的運用條件一般都有多個，當其中的一個經(jīng)驗證成立后，如何自動地換為對另一個的驗證？.逆向推理：目的性強，利于向用戶提供解釋，但選擇初始目標時具有盲目性，比正向推理復雜。,2.逆向推理,22,3.1.3推理的方向,正向推理:盲目、效率低。逆向推理:若提出的假設目標不符合實際，會降低效率。正反向混合推理：（1）先正向后逆向：先進行正向推理，幫助選擇某個目標，即從已知事實演繹出部分結果，然后再用逆向推理證實該目標或提高其可信度；（2）先逆向后正向：先假設一個目標進行逆向推理，然后再利用逆向推理中得到的信息進行正向推理，以推出更多的結論。,3.混合推理,23,24,25,雙向推理：正向推理與逆向推理同時進行，且在推理過程中的某一步驟上“碰頭”的一種推理。,3.1.3推理的方向,4.雙向推理,中間結論證據(jù),26,3.1推理的基本概念,3.1.1推理的定義3.1.2推理方式及其分類3.1.3推理的方向3.1.4沖突消解策略,27,3.1.4沖突消解策略,已知事實與知識的三種匹配情況：（1）恰好匹配成功（一對一）；（2）不能匹配成功；（3）多種匹配成功（一對多、多對一、多對多）,沖突消解,28,3.1.4沖突消解策略,多種沖突消解策略：（1）按針對性排序（2）按已知事實的新鮮性排序（3）按匹配度排序（4）按條件個數(shù)排序（5）按上下文限制排序（6）按冗余限制排序（7）根據(jù)領域問題的特點排序,r1:IFA1ANDA2THENH1r2:IFA1ANDA2ANDA3ANDA4THENH2,29,第3章確定性推理方法,3.1推理的基本概念3.2自然演繹推理3.3謂詞公式化為子句集的方法3.4海伯倫定理3.5魯賓遜歸結原理3.6歸結反演3.7應用歸結反演求解問題,30,自然演繹推理：從一組已知為真的事實出發(fā)，運用經(jīng)典邏輯的推理規(guī)則推出結論的過程。推理規(guī)則：P規(guī)則、T規(guī)則、假言推理、拒取式推理,3.2自然演繹推理,拒取式推理：PQ,QP“如果下雨，則地下就濕”,“地上不濕”推出“沒有下雨”,31,（1）如果下雨，則地上是濕的（PQ）；（2）沒有下雨（P）；（3）所以，地上不濕（Q）。,3.2自然演繹推理,錯誤1否定前件：PQ,PQ,（1）如果行星系統(tǒng)是以太陽為中心的，則金星會顯示出位相變化（PQ）；（2）金星顯示出位相變化（Q）；（3）所以，行星系統(tǒng)是以太陽為中心（P）。,錯誤2肯定后件：PQ,QP,32,3.2自然演繹推理,例1已知事實：（1）凡是容易的課程小王(Wang)都喜歡；（2）C班的課程都是容易的；（3）ds是C班的一門課程。求證：小王喜歡ds這門課程。,33,3.2自然演繹推理,證明：定義謂詞：EASY(x)：x是容易的LIKE(x,y)：x喜歡yC(x)：x是C班的一門課程,已知事實和結論用謂詞公式表示：()(EASY(x)LIKE(Wang,x)()(C(x)EASY(x)C(ds)LIKE(Wang,ds),34,3.2自然演繹推理,應用推理規(guī)則進行推理：,()(C(x)EASY(x)C(y)EASY(y)全稱固化,所以C(ds),C(y)EASY(y)EASY(ds)P規(guī)則及假言推理,所以EASY(ds),EASY(z)LIKE(Wang，z)LIKE(Wang,ds)T規(guī)則及假言推理,35,優(yōu)點：表達定理證明過程自然，易理解。擁有豐富的推理規(guī)則，推理過程靈活。便于嵌入領域啟發(fā)式知識。,3.2自然演繹推理,36,第3章確定性推理方法,3.1推理的基本概念3.2自然演繹推理3.3謂詞公式化為子句集的方法3.4海伯倫定理3.5魯賓遜歸結原理3.6歸結反演3.7應用歸結反演求解問題,37,歸結演繹推理,反證法：，當且僅當，即Q為P的邏輯結論，當且僅當是不可滿足的。,定理：Q為，的邏輯結論，當且僅當是不可滿足的。,38,歸結演繹推理,思路：定理不可滿足子句集不可滿足海伯倫定理魯賓遜歸結原理,39,3.3謂詞公式化為子句集的方法,原子（atom）謂詞公式：一個不能再分解的命題。文字（literal）：原子謂詞公式及其否定。：正文字，：負文字。子句（clause）：任何文字的析取式。任何文字本身也都是子句?？兆泳洌∟IL）：不包含任何文字的子句。子句集：由子句構成的集合。,空子句是永假的，不可滿足的。,40,3.3謂詞公式化為子句集的方法,例2將下列謂詞公式化為子句集。解：（1）消去謂詞公式中的“”和“”符號,（2）把否定符號移到緊靠謂詞的位置上,（3）變量標準化,3.3謂詞公式化為子句集的方法,41,（4）消去存在量詞a.存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)。b.存在量詞出現(xiàn)在一個或者多個全稱量詞的轄域內(nèi)。,（5）化為前束形前束形=（前綴）母式,（前綴）：全稱量詞串。母式：不含量詞的謂詞公式。,3.3謂詞公式化為子句集的方法,42,3.3謂詞公式化為子句集的方法,（6）化為Skolem標準形,（7）略去全稱量詞,（8）消去合取詞,（9）子句變量標準化,43,3.3謂詞公式化為子句集的方法,例3將下列謂詞公式化為子句集。（1）消去蘊含符號（2）把否定符號移到每個謂詞前面（3）變量標準化（4）消去存在量詞，設y的函數(shù)是f(x)，則,44,3.3謂詞公式化為子句集的方法,例3將下列謂詞公式化為子句集。（續(xù)）（5）化為前束形（6）化為標準形（7）略去全稱量詞（8）消去合取詞，把母式用子句集表示（9）子句變量標準化,45,3.3謂詞公式化為子句集的方法,例4將下列謂詞公式化為不含存在量詞的前束形。（1）消去存在量詞（2）消去蘊含符號（3）設z的函數(shù)是g(y)，則,46,3.3謂詞公式化為子句集的方法,定理3.1:謂詞公式不可滿足的充要條件是其子句集不可滿足。,47,第3章確定性推理方法,3.1推理的基本概念3.2自然演繹推理3.3謂詞公式化為子句集的方法3.4海伯倫定理3.5魯賓遜歸結原理3.6歸結反演3.7應用歸結反演求解問題,48,定義3.1（H域）設S為子句集，則按下述方法構造的域稱為海伯倫域，簡記為H域。（1）令是S中所有個體常量的集合，若S中不包含個體常量，則令，其中為任意指定的一個個體常量。（2）令S中所有n元函數(shù)是H中的元素，其中。,3.4海伯倫（Herbrand）定理,49,3.4海伯倫（Herbrand）定理,例5求子句集的H域。,解：指定一個常量作為個體常量，則得：,.,50,3.4海伯倫（Herbrand）定理,例6求子句集的H域。,解：根據(jù)H域的定義得：,.,51,3.4海伯倫（Herbrand）定理,例7求子句集的H域。,解：根據(jù)H域的定義得：,例8求子句集的H域。,解：根據(jù)H域的定義得：,52,3.4海伯倫（Herbrand）定理,基子句：用H域中的元素代換子句中的變元后所得的子句，其中的謂詞稱為基原子。原子集：子句集中所有基原子構成的集合。子句集在H域上的解釋：對子句集中出現(xiàn)的常量、函數(shù)及謂詞取值，一次取值就是一個解釋。,例9子句集,H域：S的原子集：則S的解釋為：,53,3.4海伯倫（Herbrand）定理,定理3.2（海伯倫定理）：子句集不可滿足的充要條件是存在一個有限的不可滿足的基子句集。,54,第3章確定性推理方法,3.1推理的基本概念3.2自然演繹推理3.3謂詞公式化為子句集的方法3.4海伯倫定理3.5魯賓遜歸結原理3.6歸結反演3.7應用歸結反演求解問題,55,3.5魯賓遜歸結原理,魯賓遜歸結原理（消解原理）的基本思想：檢查子句集S中是否包含空子句，若包含，則S不可滿足。若不包含，在S中選擇合適的子句進行歸結，一旦歸結出空子句，就說明S是不可滿足的。,子句集中子句之間是合取關系，只要有一個子句不可滿足，則子句集就不可滿足。,56,3.5魯賓遜歸結原理,1.命題邏輯中的歸結原理（基子句的歸結）定義3.3（歸結）：設C1與C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，那么從C1和C2中分別消去L1和L2，并將二個子句中余下的部分析取，構成一個新子句C12。,57,推論1：設C1與C2是子句集S中的兩個子句，C12是它們的歸結式，若用C12代替C1與C2后得到新子句集S1，則由S1不可滿足性可推出原子句集S的不可滿足性，即：,推論2：設C1與C2是子句集S中的兩個子句，C12是它們的歸結式，若C12加入原子句集S，得到新子句集S1，則S與S1在不可滿足的意義上是等價的，即：,定理3.3：歸結式C12是其親本子句C1與C2的邏輯結論。即如果C1與C2為真，則C12為真。,3.5魯賓遜歸結原理,的不可滿足性S的不可滿足性,S1的不可滿足性S的不可滿足性,58,3.5魯賓遜歸結原理,2.謂詞邏輯中的歸結原理（含有變量的子句的歸結）例：,？,定義3.4：設是兩個沒有相同變元的子句，和分別是中的文字，若是的最一般合一，則稱為的二元歸結式。,最一般合一,59,3.5魯賓遜歸結原理,例10設：,求其二元歸結式。,得：,解：令選則,60,3.5魯賓遜歸結原理,例11設：,求其二元歸結式。,則得：,解：選,61,3.5魯賓遜歸結原理,對于謂詞邏輯，歸結式是其親本子句的邏輯結論。對于一階謂詞邏輯，即若子句集是不可滿足的，則必存在一個從該子句集到空子句的歸結演繹；若從子句集存在一個到空子句的演繹，則該子句集是不可滿足的。如果沒有歸結出空子句，則既不能說S不可滿足，也不能說S是可滿足的。,62,第3章確定性推理方法,3.1推理的基本概念3.2自然演繹推理3.3謂詞公式化為子句集的方法3.4海伯倫定理3.5魯賓遜歸結原理3.6歸結反演3.7應用歸結反演求解問題,63,3.6歸結反演,應用歸結原理證明定理的過程稱為歸結反演。用歸結反演證明的步驟是：（1）將已知前提表示為謂詞公式F。（2）將待證明的結論表示為謂詞公式Q，并否定得到Q。（3）把謂詞公式集F，Q化為子句集S。（4）應用歸結原理對子句集S中的子句進行歸結，并把每次歸結得到的歸結式都并入到S中。如此反復進行，若出現(xiàn)了空子句，則停止歸結，此時就證明了Q為真。,64,3.6歸結反演,例12某公司招聘工作人員，A，B，C三人應試，經(jīng)面試后公司表示如下想法：（1）三人中至少錄取一人。（2）如果錄取A而不錄取B，則一定錄取C。（3）如果錄取B，則一定錄取C。,求證：公司一定錄取C。,65,3.6歸結反演,證明：公司的想法用謂詞公式表示：。,把要求證的結論用謂詞公式表示出來并否定，得：,（1）（2）（3）,（4）,把上述公式化成子句集：,（1）（2）（3）（4）,66,3.6歸結反演,應用歸結原理進行歸結：,（5）（1）與（2）歸結（6）（3）與（5）歸結（7）（4）與（6）歸結,67,3.6歸結反演,例13已知：規(guī)則1：任何人的兄弟不是女性；規(guī)則2：任何人的姐妹必是女性。事實：Mary是Bill的姐妹。求證：Mary不是Tom的兄弟。證明：定義謂詞brother(x,y):x是y的兄弟sister(x,y):x是y的姐妹woman(x):x是女性,68,3.6歸結反演,證明：將規(guī)則與事實用謂詞公式表示：,把要求證的結論用謂詞公式表示出來并否定，得：,把上述公式化成子句集：,（1）（2）（3）,（4）,將子句集進行歸結：,6