目錄,第一章緒論第二章知識表示第三章搜索技術第四章推理技術第五章機器學習第六章專家系統第七章自動規劃系統第八章自然語言理解第九章智能控制第十章人工智能程序設計,4.0推理的基本概念,4.0.1推理的定義從初始證據出發，按某種策略不斷應用知識庫中的已知知識，逐步推出結論的過程稱為推理。在人工智能系統中，推理是由程序實現的，稱為推理機。已知事實和知識是構成推理的兩個基本要素。事實又稱為證據，用以指出推理的出發點及推理時應該使用的知識。知識是使推理得以向前推進，并逐步達到最終目標的依據。,4.0推理的基本概念,4.0.2推理方式及其分類（1）按推出結論的途徑來劃分，推理可分為：演繹推理（deductiveresoning）：是從全稱判斷推導出單稱判斷的過程，即由一般性知識推出適合某一具體情況的結論。一般到個別。歸納推理（inductiveresoning）：是從足夠多的事例中歸納出一般性結論的推理過程。個別到一般。默認推理（defaultresoning）：是在知識不完全的情況下假設某些條件已經具備所進行的推理。,4.0推理的基本概念,4.0.2推理方式及其分類（2）按推理時所用的知識的確定性來劃分，推理可分為：確定性推理：是指推理時所用的知識與證據都是確定的，退出的結論也是確定的，其真值或者為真或者為假，沒有第三種情況出現。不確定性推理：是指推理時所用的知識與證據不都是確定的，推出的結論也是不確定的。,4.0推理的基本概念,4.0.2推理方式及其分類（3）按推理過程中推出的結論是否越來越接近最終目標來劃分，推理可分為：單調推理：是指在推理過程中隨著推理向前推進及新知識的加入，推出的結論越來越接近最終目標。非單調推理：是指在推理過程中由于新知識的加入，不僅沒有加強已推出的結論，反而要否定它，使推理退回到前面的某一步，然后重新開始。,4.0推理的基本概念,4.0.2推理方式及其分類（4）按推理中是否運用與推理有關的啟發性知識來劃分，推理可分為：啟發性推理：是指在推理過程中運用與推理有關的啟發性知識。非啟發性推理：是指在推理過程中未運用與推理有關的啟發性知識。,4.0推理的基本概念,4.0.3推理的方向（1）正向推理是以事實作為出發點的一種推理。基本思想：從用戶提供的初始已知事實出發，在知識庫KB中找出當前可適用的知識，構成可適用知識集KS，然后按某種沖突消解策略從KS中選出一條知識進行推理，并將推出的新事實加入到數據庫中作為下一步推理的已知事實，此后再在KB中選取可適用的知識進行推理，如此重復這一過程，直到求得了問題的解或者知識庫中再無可適用的知識為止。,4.0推理的基本概念,4.0.3推理的方向（2）逆向推理是以某個假設目標為出發點的一種推理。基本思想：首先選擇一個假設目標，然后尋找支持該假設的證據，若需的證據都能找到，則說明原假設是成立的；若無論如何都找不到所需的證據，則說明原假設不成立，為此需要另作新的假設。,4.0推理的基本概念,4.0.3推理的方向（3）混合推理正向推理具有盲目、效率低等缺點，推理過程中可能會推出許多與問題無關的子目標。逆向推理中，若提出的假設目標不符合實際，也會降低系統效率。可以把正向推理與逆向推理結合起來，使其各自發揮自己的優勢，取長補短。這種既有正向推理又有逆向推理稱為混合推理。,4.0推理的基本概念,4.0.3推理的方向（4）雙向推理雙向推理：是指正向推理與逆向推理同時進行，且在推理過程中的某一步驟上“碰頭”的一種推理。基本思想：一方面根據已知事實進行正向推理，但并不推倒最終目標；另一方面從某假設目標出發進行逆向推理，但不推至原始事實，而是讓它們在中途相遇，即由正向推理所得到的中間結論恰好是逆向推理此時所需求的證據，這時推理就可以結束，逆向推理時所做的假設就是推理的最終結論。,4.0推理的基本概念,4.0.4沖突消解策略系統將當前已知事實與KB中知識匹配的三種情況：（1）已知事實恰好只與KB中的一個知識匹配成功。（2）已知事實不能與KB中的任何知識匹配成功。（3）已知事實可與KB中的多個知識匹配成功；或者多個（組）事實都可與KB中的某一個知識匹配成功；或者多個（組）事實都可與KB中的多個知識匹配成功；第3種情況稱為發生了沖突。,4.0推理的基本概念,4.0.4沖突消解策略消解沖突的基本思想：對知識進行排序：（1）按針對性排序：優先選擇針對性強的知識（規則），即要求條件多的規則。（2）按已知事實的新鮮性排序：后生成的事實具有較大的新鮮性。（3）按匹配度排序：在不確定推理中，需要計算已知事實與知識的匹配度。（4）按條件個數排序：優先應用條件少的產生式規則。,4.1消解原理,4.1.1子句集的求取消解原理是針對謂詞邏輯知識表示的問題求解方法。消解原理的基礎知識：（1）謂詞公式、某些推理規則以及置換合一等概念。（2）子句：由文字的析取組成的公式(一個原子公式和原子公式的否定都叫做文字)。（3）消解：當消解可使用時，消解過程被應用于母體子句對，以便產生一個導出子句。例如，如果存在某個公理E1E2和另一公理E2E3，那么E1E3在邏輯上成立。這就是消解，而稱E1E3為E1E2和E2E3的消解式。,4.1消解原理,4.1.1子句集的求取步驟(1)消去蘊涵符號只應用和符號，以AB替換AB。(AB)BC=(AB)BC=(AB)BC=(AB)BC=（AB）（BB）C=（AB）C,4.1消解原理,4.1.1子句集的求取(2)減少否定符號的轄域每個否定符號最多只用到一個謂詞符號上，并反復應用狄摩根定律。例如：以AB代替(AB)以AB代替(AB)以A代替(A)以(彐x)A代替(x)A以(x)A代替(彐x)A,4.1消解原理,4.1.1子句集的求取(3)對變量標準化在任一量詞轄域內，受該量詞約束的變量為一啞元(虛構變量)，它可以在該轄域內處處統一地被另一個沒有出現過的任意變量所代替，而不改變公式的真值。合適公式中變量的標準化意味著對啞元改名以保證每個量詞有其自己唯一的啞元。如，對(x)P(x)(彐x)Q(x)標準化可得：(x)P(x)(彐y)Q(y),4.1消解原理,4.1.1子句集的求取(4)消去存在量詞Skolem函數：(y)(彐x)P(x,y)中，存在量詞是在全稱量詞的轄域內，允許所存在的x可能依賴于y值。令這種依賴關系明顯地有函數g(y)所定義，它把每個y值映射到存在的那個x。這種函數叫做Skolem函數。如果用Skolem函數代替存在的x，就可以消去全部存在量詞，并寫成：(y)P(g(y),y),4.1消解原理,4.1.1子句集的求取從一個公式消去一個存在量詞的一般規則是以一個Skolem函數代替每個出現的存在量詞的量化變量，而這個Skolem函數的變量就是由那些全稱量詞所約束的全稱量詞量化變量，這些全稱量詞的轄域包括要被消去的存在量詞的轄域在內。Skolem函數所使用的函數符號必須是新的，即不允許是公式中已經出現過的函數符號。如果要消去的存在量詞不在任何一個全稱量詞的轄域內，則用不含變量的Skolem函數即常量。例如，(彐x)P(x)化為P(A)，其中常量符號A用來表示人們知道的存在實體。A必須是個新的常量符號，它未曾在公式中其它地方使用過。,4.1消解原理,4.1.1子句集的求取(5)化為前束形把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。所得公式稱為前束形。前束形=（前綴）（母式）全稱量詞串無量詞公式(6)把母式化為合取范式任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。這種母式叫做合取范式。如：ABC化為ABBC,4.1消解原理,4.1.1子句集的求取(7)消去全稱量詞消去明顯出現的全稱量詞。(8)消去連詞符號用A，B代替(AB)，以消去明顯的符號。反復代替的結果，最后得到一個有限集，其中每個公式是文字的析取。任一個只由文字的析取構成的合適公式叫做一個子句。(9)更換變量名稱可以更換變量符號的名稱，使一個變量符號不出現在一個以上的子句中。,4.1消解原理,4.1.1子句集的求取例：將下列謂詞演算公式化為一個子句集(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)（1）消去蘊涵符號(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)（2）減少否定符號轄域(x)P(x)(y)P(y)P(f(x,y)(彐y)Q(x,y)P(y)(x)P(x)(y)P(y)P(f(x,y)(彐y)Q(x,y)P(y)（3）對變量標準化(x)P(x)(y)P(y)P(f(x,y)(彐w)Q(x,w)P(w),4.1消解原理,4.1.1子句集的求取（4）消去存在量詞(x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)P(g(x)w=g(x)為一個skolem函數。（5）化為前束形(x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)（6）把母式化為合取范式(x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x),4.1消解原理,4.1.1子句集的求取（7）消去全稱量詞P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)（8）消去連詞符號P(x)P(y)P(f(x,y)，P(x)Q(x,g(x)，P(x)P(g(x)（9）更換變量名稱P(x1)P(y)P(f(x1,y)，P(x2)Q(x2,g(x2)，P(x3)P(g(x3),4.1消解原理,4.1.2消解推理規則令L1為任一原子公式，L2為另一原子公式；L1和L2具有相同的謂詞符號，但一般具有不同的變量。已知兩子句L1和L2,如果L1和L2具有最一般合一者，那么通過消解可以從這兩個父輩子句推導出一個新子句()。這個新子句叫做消解式。它是由取這兩個子句的析取，然后消去互補對而得到的。,4.1消解原理,4.1.2消解推理規則常用消解規則(1)假言推理父輩子句PPQ(即PQ)消解式Q,4.1消解原理,4.1.2消解推理規則常用消解規則(2)合并父輩子句PQPQ消解式QQ=Q,4.1消解原理,4.1.2消解推理規則常用消解規則(3)重言式PQPQPQPQ消解式QQPP,4.1消解原理,4.1.2消解推理規則常用消解規則(4)空子句(矛盾)PP消解式NIL,4.1消解原理,4.1.2消解推理規則常用消解規則(5)鏈式(三段論)PQQR消解式PR,4.1消解原理,4.1.3含有變量的消解式為了對含有變量的子句使用消解規則，必須找到一個置換，作用于父輩子句使其含有互補文字。例：設有兩個字句P(x)Q(x)Q（f(y)）置換=f(y)/x消解可得：P（f(y)）,4.1消解原理,4.1.3含有變量的消解式令父輩子句由Li和Mi給出，假設這兩個子句中的變量已經分別標準化。設li是Li的一個子集，mi是Mi的一個子集，若是li和mi的最一般的合一，消解兩個子句Li和Mi，得到新子句Li-liMi-mi就是這兩個子句的消解式。消解兩個子句時，可能有一個以上的消解式，因為有多種選擇li和mi的方法。,4.1消解原理,4.1.3含有變量的消解式例：考慮兩個子句：Px,f(A)Px,f(y)Q(y)pz,f(A)Q(z)取li=Px,f(A)，mi=pz,f(A)可得消解式Pz,f(y)Q(y)Q(z),=z/x,4.1消解原理,4.1.3含有變量的消解式如果取li=Q(y)，mi=Q(z)則可得消解式Px,f(A)Px,f(y)py,f(A)進一步消解的消解式Py,f(y),=y/z,4.1消解原理,4.1.3含有變量的消解式幾個含有變量的子句使用消解的例子：,B(x),B(x)C(x),C(x),4.1消解原理,4.1.3含有變量的消解式幾個含有變量的子句使用消解的例子：,P(x)Q(x),Qf(y),Pf(y),=f(y)/x,4.1消解原理,4.1.3含有變量的消解式幾個含有變量的子句使用消解的例子：,P(x,f(y)Q(x)Rf(a),y,Pf(f(a),zR(z,w),Q(f(f(a)Rf(a),yR(f(y),w),=f(f(a)/x,f(y)/z,4.1消解原理,4.1.4消解反演求解過程1.基本思想把要解決的問題作為一個要證明的命題，其目標公式被否定并化成子句形，然后添加到命題公式集中去，把消解反演系統應用于聯合集，并推導出一個空子句(NIL)，產生一個矛盾，這說明目標公式的否定式不成立，即有目標公式成立，定理得證，問題得到解決，與數學中反證法的思想十分相似。,4.1消解原理,4.1.4消解反演求解過程2、消解反演反演求解的步驟給出一個公式集S和目標公式L，通過反證或反演來求證目標公式L，其證明步驟如下：(1)否定L，得L；(2)把L添加到S中去；(3)把新產生的集合L，S化成子句集；(4)應用消解原理，力圖推導出一個表示矛盾的空子句NIL。,4.1消解原理,4.1.4消解反演求解過程反演求解的正確性設公式L在邏輯上遵循公式集S，那么按照定義滿足S的每個解釋也滿足L。決不會有滿足S的解釋能夠滿足L的，所以不存在能夠滿足并集SL的解釋。如果一個公式集不能被任一解釋所滿足，那么這個公式是不可滿足的。因此，如果L在邏輯上遵循S，那么SL是不可滿足的。可以證明，如果消解反演反復應用到不可滿足的子句集，那么最終將要產生空子句NIL。因此，如果L在邏輯上遵循S，那么由并集SL消解得到的子句，最后將產生空子句；反之，可以證明，如果從SL的子句消解得到空子句，那么L在邏輯上遵循S。,4.1消解原理,4.1.4消解反演求解過程反演求解舉例例：儲蓄問題前提：每個儲蓄錢的人都獲得利息。結論：如果沒有利息，那么就沒有人去儲蓄錢證明：令S(x,y)表示“x儲蓄y”M(x)表示“x是錢”I(x)表示“x是利息”E(x,y)表示“x獲得y”于是上述命題寫成：,4.1消解原理,4.1.4消解反演求解過程(x)(彐y)(S(x,y)M(y)=(彐y)(I(y)E(x,y)結論：(彐x)I(x)=(x)(y)(M(y)=(S(x,y)化為子句集：S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x)其中，y=f(x)為Skolem函數。而L=(彐x)I(x)=(x)(y)(s(x,y)=M(y)=I(z),S(a,b),M(b),P=Q等價Q=P,4.1消解原理,4.1.4消解反演求解過程按4個步驟進行反演求解（1）否定L，即有L=I(z),S(a,b),M(b)（2）將L添加到S中去,即S=L,S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x),I(z),S(a,b),M(b)（3）把新產生的集合化成子句集，即S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x),I(z),S(a,b),M(b)（4）應用消解原理，推導出一個表示矛盾的空子句NIL。,4.1消解原理,4.1.4消解反演求解過程,S(x,y)M(y)I(f(x),I(z),S(x,y)M(y),=f(x)/z,M(b),S(a,b),=a/x,b/y,NIL,M(b),4.1消解原理,4.1.4消解反演求解過程反演求解過程步驟：(1)把由目標公式的否定產生的每個子句添加到目標公式否定之否定的子句中去。(2)按照反演樹，執行和以前相同的消解，直至在根部得到某個子句止。(3)用根部的子句作為一個回答語句。,4.1消解原理,4.1.4消解反演求解過程分析：答案求取涉及到把一棵根部有NIL的反演樹變換為在根部帶有可用作答案的某個語句的一顆證明樹。由于變換關系涉及到把由目標公式的否定產生的每個子句變換為一個重言式，所以被變換的證明樹就是一棵消解的證明樹，其在根部的語句在邏輯上遵循公理加上重言式，因而也單獨地遵循公理。因此被變換的證明樹本身就證明了求取辦法是正確的。,4.1消解原理,4.1.4消解反演求解過程例4.3如果無論約翰(John)到哪里去，菲多(Fido)也就去那里，那么如果約翰在學校里，菲多在哪里呢?事實公式集：S=(x)AT(JOHN,x)=AT(FIDO,x),AT(JOHN,SCHOOL)目標公式L：(彐x)AT(FIDO,x)首先證明L在邏輯上遵循公式集SL=(彐x)AT(FIDO,x)=(x)AT(FIDO,x)其子句為AT(FIDO,x),4.1消解原理,4.1.4消解反演求解過程例4.3的反演樹,AT(FIDO,x),AT(JOHN,y)AT(FIDO,y),AT(JOHN,x),=x/y,NIL,AT(JOHN,SCHOOL),=SCHOOL/x,4.1消解原理,4.1.4消解反演求解過程例4.3從消解求取答案的反演樹,AT(FIDO,x)AT(FIDO,y),AT(JOHN,y)AT(FIDO,y),AT(JOHN,x)AT(FIDO,x),=x/y,AT(FIDO,SCHOOL),AT(JOHN,SCHOOL),=SCHOOL/x,目標公式的重言式,4.2規則演繹系統,規則演繹系統的定義：基于規則的問題求解系統運用下述規則來建立：IfThen其中，If部分可能由幾個if組成，而Then部分可能由一個或一個以上的then組成。在所有基于規則系統中，每個if可能與某斷言(assertion)集中的一個或多個斷言匹配。有時把該斷言集稱為工作內存。在許多基于規則系統中，then部分用于規定放入工作內存的新斷言。這種基于規則的系統叫做規則演繹系統(rulebaseddeductionsystem)。在這種系統中，通常稱每個if部分為前項(antecedent)，稱每個then部分為后項(consequent)。,4.2規則演繹系統,4.2.1正向規則演繹系統正向規則演繹系統是從事實到目標進行操作的，即從狀況條件到動作進行推理的，也就是從if到then的方向進行推理的。1.事實表達式的與或形變換把事實表示為非蘊涵形式的與或形，作為系統的總數據庫。具體變換步驟與前述化為子句形類似。注意：我們不想把這些事實化為子句形，而是把它們表示為謂詞演算公式，并把這些公式變換為叫做與或形的非蘊涵形式。,4.2規則演繹系統,4.2.1正向規則演繹系統例：有事實表達式(彐u)(v)Q(v,u)(R(v)P(v)S(u,v)把它化為Q(v,A)R(v)P(v)S(A,v)對變量更名標準化，使得同一變量不出現在事實表達式的不同主要合取式中，得：Q(w,A)R(v)P(v)S(A,v),4.2規則演繹系統,4.2.1正向規則演繹系統2.事實表達式的與或圖表示將上例與或形的事實表達式用與或圖來表示,Q(w,A)R(v)P(v)S(A,v),Q(w,A),R(v)P(v)S(A,v),R(v)P(v),S(A,v),R(v),P(v),4.2規則演繹系統,4.2.1正向規則演繹系統3.與或圖的F規則變換這些規則是建立在某個問題轄域中普通陳述性知識的蘊涵公式基礎上的。把允許用作規則的公式類型限制為下列形式LW式中：L是單文字；W為與或形的唯一公式。,4.2規則演繹系統,4.2.1正向規則演繹系統3.與或圖的F規則變換將這類規則應用于與或圖進行推演。假設有一條規則L=W，根據此規則及事實表達式F(L)，可以推出表達式F(W)。F(W)是用W代替F中的所有L而得到的。當用規則L=W來變換以上述方式描述的F(L)的與或圖表示時，就產生一個含有F(W)表示的新圖；也就是說，它的以葉節點終止的解圖集以F(W)子句形式代表該子句集。這個子句集包括在F(L)的子句形和L=W的子句形間對L進行所有可能的消解而得到的整集。該過程以極其有效的方式達到了用其它方法要進行多次消解才能達到的目的。,4.2規則演繹系統,4.2.1正向規則演繹系統4.作為終止條件的目標公式應用F規則的目的在于從某個事實公式和某個規則集出發來證明某個目標公式。在正向推理系統中，這種目標表達式只限于可證明的表達式，尤其是可證明的文字析取形的目標公式表達式。用文字集表示此目標公式，并設該集各元都為析取關系。結論：當正向演繹系統產生一個含有以目標節點作為終止的解圖時，此系統就成功地終止。,4.2規則演繹系統,4.2.2逆向規則演繹系統基于規則的逆向演繹系統，其操作過程與正向演繹系統相反，即為從目標到事實的操作過程，從then到if的推理過程。逆向推理過程1.目標表達式的與或形式逆向演繹系統能夠處理任意形式的目標表達式。首先，采用與變換事實表達式同樣的過程，把目標公式化成與或形。,4.2規則演繹系統,4.2.2逆向規則演繹系統2.與或圖的B規則變換B規則是建立在確定的蘊涵式基礎上的，正如正向系統的F規則一樣。不過，我們現在把這些B規則限制為WL形式的表達式。其中，W為任一與或形公式，L為文字，而且蘊涵式中任何變量的量詞轄域為整個蘊涵式。3.作為終止條件的事實節點的一致解圖逆向系統成功的終止條件是與或圖包含有某個終止在事實節點上的一致解圖。,4.2規則演繹系統,4.2.2雙向規則演繹系統基于規則的正向演繹系統和逆向演繹系統的特點和局限性正向演繹系統能夠處理任意形式的if表達式，但被限制在then表達式為由文字析取組成的一些表達式。逆向演繹系統能夠處理任意形式的then表達式，但被限制在if表達式為文字合取組成的一些表達式。雙向(正向和逆向)組合演繹系統具有正向和逆向兩系統的優點，克服各自的缺點。,4.2規則演繹系統,4.2.2雙向規則演繹系統雙向(正向和逆向)組合演繹系統的構成正向和逆向組合系統是建立在兩個系統相結合的基礎上的。此組合系統的總數據庫由表示目標和表示事實的兩個與或圖結構組成，并分別用F規則和B規則來修正。,4.2規則演繹系統,4.2.2雙向規則演繹系統終止條件組合演繹系統的主要復雜之處在于其終止條件，終止涉及兩個圖結構之間的適當交接處。當用F規則和B規則對圖進行擴展之后，匹配就可以出現在任何文字節點上。在完成兩個圖間的所有可能匹配之后，目標圖中根節點上的表達式是否已經根據事實圖中根節點上的表達式和規則得到證明的問題仍然需要判定。只有當求得這樣的一個證明時，證明過程才算成功地終止。若能夠斷定在給定方法限度內找不到證明時過程則以失敗告終。,4.3產生式系統,在基于規則系統中，每個if可能與某斷言(assertion)集中的一個或多個斷言匹配，then部分用于規定放入工作內存的新斷言。當then部分用于規定動作時，稱這種基于規則的系統為反應式系統(reactionsystem)或產生式系統(productionsystem)。,4.3產生式系統,4.3.1產生式系統的結構產生式系統由3個部分組成，即總數據庫(或全局數據庫)、產生式規則和控制策略。,控制策略,產生式規則,總數據庫,4.3產生式系統,4.3.1產生式系統的結構總數據庫有時也被稱作上下文，當前數據庫或暫時存儲器。總數據庫是產生式規則的注意中心。產生式規則的左邊表示在啟用這一規則之前總數據庫內必須準備好的條件。例如在上述例子中，在得出該動物是食肉動物的結論之前，必須在總數據庫中存有“該動物是哺乳動物”和“該動物吃肉”這兩個事實。執行產生式規則的操作會引起總數據庫的變化，這就使其他產生式規則的條件可能被滿足。產生式規則是一個規則庫，用于存放與求解問題有關的某個領域知識的規則之集合及其交換規則。規則庫知識的完整性、一致性、準確性、靈活性和知識組織的合理性，將對產生式系統的運行效率和工作性能產生重要影響。,4.3產生式系統,4.3.1產生式系統的結構控制策略為一推理機構，由一組程序組成，用來控制產生式系統的運行，決定問題求解過程的推理線路，實現對問題的求解。產生式系統的控制策略隨搜索方式的不同可分為可撤回策略、回溯策略、圖搜索策略等。控制策略的作用是說明下一步應該選用什么規則，也就是如何應用規則。通常從選擇規則到執行操作分3步：匹配、沖突解決和操作。,4.3產生式系統,4.3.1產生式系統的結構（1）匹配在這一步，把當前數據庫與規則的條件部分相匹配。如果兩者完全匹配，則把這條規則稱為觸發規則。當按規則的操作部分去執行時，稱這條規則為啟用規則。被觸發的規則不一定總是啟用規則，因為可能同時有幾條規則的條件部分被滿足，這就要在解決沖突步驟中來解決這個問題。在復雜的情況下，在數據庫和規則的條件部分之間可能要進行近似匹配。,4.3產生式系統,4.3.1產生式系統的結構（2）沖突解決當有一條以上規則的條件部分和當前數據庫相匹配時，就需要決定首先使用哪一條規則，這稱為沖突解決。（3）操作操作就是執行規則的操作部分，經過操作以后，當前數據庫將被修改。然后，其他的規則有可能被使用。,4.3產生式系統,4.3.2產生式系統的表示1.事實的表示（1）孤立事實的表示三元組(AGEZHAO-LING43)(FATHERZHAO-YINZHAO-LING)(MANZHAO-LINGTRUE)(WOMANZHAO-LINGFALSE)不完全知識置信度,4.3產生式系統,4.3.2產生式系統的表示（2）事實之間的關系樹狀結構網狀結構,4.3產生式系統,4.3.2產生式系統的表示2.規則的表示（1）單個規則的表示前項與后項=(IFTHEN(ELSE)規則的可信度,4.3產生式系統,4.3.2產生式系統的表示（2）規則間的關系規則按參數分類網狀結構,4.3產生式系統,4.3.3產生式系統的推理1.正向推理從一組表示事實的謂詞或命題出發，使用一組產生式規則，用以證明該謂詞公式或命題是否成立。一般策略：先提供一批事實（數據）到總數據庫中。系統利用這些事實與規則的前提相匹配，觸發匹配成功的規則，把其結論作為新的事實添加到總數據庫中。繼續上述過程，用更新過的總數據庫的所有事實再與規則庫中另一條規則匹配，用其結論再次修改總數據庫的內容，直到沒有可匹配的新規則，不再有新的事實加到總數據庫中。,4.3產生式系統,4.3.3產生式系統的推理2.逆向推理從表示目標的謂詞或命題出發，使用一組產生式規則證明事實謂詞或命題成立，即首先提出一批假設目標，然后逐一驗證這些假設。一般策略：首先假設一個可能的目標，然后由產生式系統試圖證明此假設目標是否在總數據庫中。若在總數據庫中，則該假設目標成立；否則，若該假設為終葉（證據）節點，則詢問用戶。若不是，則再假定另一個目標，即尋找結論部分包含該假設的那些規則，把它們的前提作為新的假設，并力圖證明其成立。這樣反復進行推理，直到所有目標均獲證明或者所有路徑都得到測試為止。,4.3產生式系統,4.3.3產生式系統的推理3.雙向推理雙向推理的推理策略是同時從目標向事實推理和從事實向目標推理，并在推理過程中的某個步驟，實現事實與目標的匹配。,4.4定性推理,4.4.1定性推理概述動因：不是任何問題都可以用精確的數學或符號化方法對其建模。建模代價高，或效果不理想。人類解決問題：抓住主要參數人類針對物理系統的問題求解，基本上是通過定性分析方法完成。,4.4定性推理,4.4.1定性推理概述定性推理（qualitativereasoning）：從物理系統（包括自然系統和人造系統）的結構描述出發，以定性方法研究系統的結構、行為、功能以及它們之間的因果關系等，目的是預測系統的行為并給出合理的解釋。,4.4定性推理,4.4.1定性推理概述1952年simmons提出定性分析的因果關系；1977年Rieger發表了第一篇關于因果仿真的定性推理1984年，“ArtificialIntelligence”雜志第24卷出版了定性推理專輯,刊載了deKleer,Forbus和Kuipers對定性推理奠基性的文章,這標志著定性推理開始走向成熟。1986年，Iwasaki和Simmons發表了“CausalityinDeviceBehavior”的文章。1991年,“ArtificialIntelligence”雜志第59卷又發表了一組文章，回顧十年前這幾位定性推理奠基人所做的工作。,4.4定性推理,4.4.1定性推理概述定性推理的優勢（1）符合人類的常識推理，可實現對不完備、不一致、不精確知識的推理。如常識推理。（2）降低問題求解的代價，提高求解問題的效率。不需要問題的精確解，只需了解問題的定性結果,4.4定性推理,4.4.2定性推理方法對物理系統不同的結構描述,便提出了不同的定性推理方法。常用的有：（1）deKleer的定性模型方法：所涉及的物理系統是由管子、閥門、容器等裝置組成,約束條件(定性方程)反映在這些裝置的連接處,依定性方程給出定性解釋。（2）Forbus的定性進程方法中，一個物理系統的變化是由進程引起的,一個物理過程由一些進程來描述。（3）Kuipers定性仿真法直接用部件的參量作為狀態變量來描述物理結構,定性約束直接由物理規律得到,把一個參量隨時間的變化視作定性的狀態序列,求解算法是從初始狀態出發,生成各種可能的后續狀態,進而通過一致性過濾,重復這過程直到沒有新狀態出現。,4.4定性推理,4.4.2定性推理方法定性推理的基本方法：人類對物理世界的描述、解釋,常是以某種直觀的定性方法進行的,很少使用微分方程及具體的數值描述,如人們在騎自行車時,為了避免摔倒和撞車,并不需要使用書本上的運動方程,而是針對幾個主要參量的變化趨勢給予粗略的、直觀的,但大體上準確的描述,這就夠了。一般分析運動系統行為的標準過程可分為三個步驟：(1)決定描述對象系統特征的量。(2)用方程式表示量之間的相互關系。(3)分析方程式，得到數值解。,4.4定性推理,4.4.2定性推理方法這類運動系統行為的問題用計算機進行求解時，將面臨如下三個問題：(1)步驟(1)(2)需要相當多的知識，并且要有相應的算法(2)有的場合對象系統的性質很難用數學式子表示。(3)步驟(3)得到了數值解，但是對象系統的行為并不直觀明了。為了解決第二、第三個問題，定性推理一般采用下列分析步驟：(1)結構認識：將對象系統分解成部件的組合。(2)因果分析：當輸入值變化時，分析對象系統中怎樣傳播。,4.4定性推理,4.4.2定性推理方法(3)行為推理：輸入值隨著時間變化，分析對象系統的內部狀態怎樣變化。(4)功能說明：行為推理的結果表明對象系統的行為，由此可以說明對象系統的功能。定性推理的觀點大體上可這樣來理解:忽略被描述對象的次要因素,掌握主要因素簡化問題的描述。將隨時間t連續變化的參量x(t)的值域離散化為定性值集合,通常變量x的定性值x定義為,4.4定性推理,4.4.2定性推理方法-當x0依物理規律將微分方程轉換成定性(代數)方程,或直接依物理規律建立定性模擬或給出定性進程描述。最后給出定性解釋,4.5不確定性推理,關于證據的不確定性（1）不確定性的表示一般通過對事實賦于一個介于0和1之間的系數來表示事實的不確定性。1代表完全確定，0代表完全不確定。這個系數被稱為置信度。（2）不確定性的處理當規則具有一個以上的條件時，就需要根據各條件的置信度來求得總條件部分的置信度。已有的方法有兩類：以模糊集理論為基礎的方法按這種方法，把所有條件中最小的置信度作為總條件的置信度。這種方法類似于當把幾根繩子連接起來使用時，總的繩子強度與強度最差的繩子的相同。,4.5不確定性推理,以概率為基礎的方法這種方法同樣賦予每個證據以置信度。但當把單獨條件的置信度結合起來求取總的置信度時，它取決于各置信度的乘積。關于結論的不確定性（1）不確定性的表示關于結論的不確定性也叫做規則的不確定性，它表示當規則的條件被完全滿足時，產生某種結論的不確定程度。它也是以賦予規則在0和1之間的系數的方法來表示的。,4.5不確定性推理,（2）不確定性的處理如果規則的條件部分不完全確定，即置信度不為1時，如何求得結論的可信度的方法有以下兩種：取結論置信度為條件可信度與置述系數的乘積。按照某種概率論的解釋，我們假設規則的條件部分的置信度Cin和其結論部分的置信度Cout存在某種關系，這種關系可用來代表規則的不確定性。例：規則：如果今天悶熱，那么明天會下雨0.9證據：星期六悶熱0.8,4.5不確定性推理,4.5.1概率推理主觀Bayes方法設推理規則P=Q是不確定的，其不確定性可以由條件概率p(Q|P)表示；若已知前提P成立的概率p(P)，則可求得PQ成立的概率（P，Q聯合概率）p(P,Q)=p(Q|P)p(P)依據Bayes理論，有以下條件概率公式,4.5不確定性推理,4.5.1概率推理其中p(P)和p(Q)分別指示前提和結論的先驗概率；p(P|Q)稱為后驗概率，指示結論Q成立時前提P成立的概率。通常后驗概率比條件概率更易于獲取，所以可不經由統計手段去獲得條件概率，而是由上面公式計算。例：令P為汽車輪子發出的刺耳噪聲，Q為汽車剎車失調。P可視為征兆，Q則指示引起P的原因。原因和征兆之間的的對應關系可用后驗概率p(P|Q)表示。設想根據經驗，剎車調整不好會引起刺耳噪聲，并估計p(P|Q)=0.7，若同時又獲得先驗概率p(P)=0.04，p(Q)=0.05，則可求得,4.5不確定性推理,4.5.1概率推理即每當發現車輪的刺耳噪聲時，可以推測有0.88的可能性是剎車失調。,4.5不確定性推理,4.5.2Bayes（網絡）推理一個關于家庭防盜的貝葉斯網絡。家里安裝的報警器能夠有效感知盜賊的侵入，并對輕微的地震有一定的感知能力。兩個鄰居李和張聽到報警聲時都會友善地來電話提醒，但偶爾李會錯將門鈴聲當作報警聲，而張則會因為大聲聽音樂而聽不到報警聲。該網絡的拓撲結構表明盜賊和地震是警報聲響的直接原因，而鄰居李和張來電話的直接原因是聽到了警報聲。,4.5不確定性推理,4.5.2Bayes（網絡）推理,4.5不確定性推理,4.5.2Bayes（網絡）推理分別以字母B、E、A、L、Z指示節點（變量）“盜賊入侵”、“地震發生”、“報警聲響”、“李來電話”、“張來電話”，并將節點條件概率表置于每個節點的右側。由于所有5個節點對應的隨機變量都是布爾變量，節點的條件概率分布簡化為條件概率表；b、e、a、l、z分別指示這些變量取值為“Ture”，且