人工智能課件3-推理

第7章高級知識推理高級知識推理經典邏輯確定性推理單調性推理歸約推理肖解演繹推理規(guī)則演繹推理非經典邏輯不確定性推理非單調性推理時序推理概率推理經典邏輯與非經典邏輯的不同

經典非經典推理方法演繹邏輯歸納邏輯轄域取值二值多值模糊運算法則有些不成立邏輯算符邏輯算符引入模態(tài)算符單調性單調非單調單調推理和非單調推理單調推理基于謂詞邏輯的推理系統是單調的系統中已知為真的命題隨著推理的進行而增加,結論越來越多非單調推理推理系統的定理集合不隨推理過程的進行而單調增大新推理出的定理可能修正以至否定原有的一些定理,使得原來能夠解釋的一些現象變得不可解釋.

非單調推理非單調推理用來處理那些不適合用謂詞邏輯表示的知識。它能夠較好地處理不完全信息、不斷變化的情況以及求解復雜問題過程中生成的假設，具有較為有效的求解效率。缺省推理在沒有證據能夠證明某命題不成立時,就承認該命題成立.不具備命題的全部知識,也能夠進行合理的推理并給出正確的結論定義如果X不知道，那么得結論Y。如果X不能被證明，那么得結論Y。如果X不能在某個給定的時間內被證明，那么得結論Y。不確定性推理精確推理的局限性推理依據已知事實（證據）、相關知識（規(guī)則）證明某個假設成立or不成立精確推理及其不足將原本為不確定性的關系“硬性”轉化為精確關系將原本不存在明確界限的事物“人為”劃定界限歪曲了現實情況的本來面目舍棄了事物的某些重要屬性失去了真實性不確定性推理的定義及意義1.定義也稱“不精確性推理”從不確定性的初始證據（即已知事實）出發(fā)運用不確定性的知識（或規(guī)則）推出具有一定程度的不確定性但卻是合理或近乎合理的結論2.意義使計算機對人類思維的模擬更接近于人類的真實思維過程不確定性推理的定義及意義不確定性推理中的基本問題不確定性的表示與度量不確定性匹配不確定性的傳遞算法不確定性的合成不確定性的表示與度量1.不確定性的表示選擇不確定性表示方法時應考慮的因素充分考慮領域問題的特征恰當地描述具體問題的不確定性滿足問題求解的實際需求便于推理過程中對不確定性的推算不確定性的表示與度量（續(xù)1）2.不確定性的度量針對不同的領域問題采用不同的度量方法用不同的數值刻畫不同的不確定性程度事先規(guī)定不確定性程度的取值范圍3.常用的度量方法測度理論（基于概率統計的度量方法）Shannon信息熵其它度量方法……不確定性的表示與度量（續(xù)2）在選擇不確定性度量方法時應考慮的因素：充分表達相應知識及證據不確定性的程度度量范圍便于領域專家及用戶估計不確定性便于計算過程中的不確定性傳遞，結論的不確定性度量不超出規(guī)定的范圍度量的確定應直觀，且有相應的理論依據不確定性匹配解決不確定性匹配的常用方法設計一個匹配算法用以計算相似度指定一個相似度的“限定”（即閾值）證據不確定性的組合單一證據&

組合證據單一證據：前提條件僅為一個簡單條件組合證據：一個復合條件對應于一組證據前提條件用AND（與）或OR（或）把多個簡單條件連接起來構成復合條件不確定性的傳遞包含兩個子問題在每一步推理中，如何把證據及知識的不確定性傳遞給結論在多步推理中，如何把初始證據的不確定性傳遞給最終結論結論不確定性的合成用不同知識進行推理得到相同的結論相同結論的不確定性程度卻不相同需要用合適的算法對它們進行合成不確定性推理方法的分類不確定性推理的兩條研究路線模型方法在推理一級上擴展確定性推理不確定證據和知識與某種度量標準對應給出更新結論不確定性的算法構成相應的不確定性推理模型控制方法在控制策略一級上處理不確定性無統一的不確定性處理模型，其效果依賴于控制策略不確定性推理方法的分類不確定性推理模型方法控制方法數值方法非數值方法概率統計方法模糊推理方法粗糙集方法絕對概率方法貝葉斯方法證據理論方法HMM方法發(fā)生率計算相關性制導回溯、機緣控制、啟發(fā)式搜索等可信度方法關于不確定性推理方法的說明數值方法對不確定性的一種定量表示和處理方法其研究及應用較多，已形成多種應用模型非數值方法除數值方法外的其它處理不確定性的模型方法典型代表：“發(fā)生率計算方法”，它采用集合來描述和處理不確定性，且滿足概率推理的性質關于不確定性推理方法的說明（續(xù)1）概率統計方法有完整、嚴密的數學理論為不確定性的合成與傳遞提供了現成的數學公式最早、最廣泛地用于不確定性知識的表示與處理已成為不確定性推理的重要手段證據理論方法1967年Dempster首次提出，1976年Shafer完善可表示并處理“不知道”等不確定性信息關于不確定性推理方法的說明（續(xù)2）模糊推理方法可表示并處理由模糊性引起的不確定性已廣泛應用于不確定性推理粗糙集理論方法1981年Z.Pawlak首次提出一種新的可表示并處理“含糊”等不確定性的數學方法可用于不確定性推理、數據挖掘等領域概率推理概率論是研究隨機現象中數量規(guī)律的科學。所謂隨機現象是指在相同的條件下重復進行某種實驗時，所得實驗結果不一定完全相同且不可預知的現象擲硬幣實驗人工智能所討論的不確定性現象，雖然不完全是隨機的過程，但是實踐證明，采用概率論的思想方法考慮能夠得到較好的結果。概率論基礎（概率定義）定義：設Ω為一個隨機實驗的樣本空間，對Ω上的任意事件A，規(guī)定一個實數與之對應，記為P(A)，滿足以下三條基本性質，稱為事件A發(fā)生的概率：若二事件A、B互斥，即，則以上三條基本規(guī)定是符合常識的。概率論基礎（條件概率）定義：設A，B為事件且P(A)>0，稱

P(B|A)為事件A已發(fā)生的條件下，事件B的條件概率，P(A)在概率推理中稱為邊緣概率。簡稱P(B|A)為給定A時B發(fā)生的概率。P(AB)稱為A與B的聯合概率。有聯合概率公式：概率論基礎（條件概率性質）

，

乘法公式：

全概率公式：設A1，A2，…An互不相交，，且，則對于任意事件A有概率論基礎（貝葉斯定理）設A，B1，B2，…，Bn為一些事件，P(A)>0，B1，B2，…，Bn互不相交，P(Bi)>0,i=1,2,…,n，且，則對于k=1,2,…,n，

貝葉斯公式容易由條件概率的定義，乘法公式和全概率公式得到。在貝葉斯公式中，P(Bi),i=1,2,…,n稱為先驗概率，而P(Bi|A)i=1,2,…,n稱為后驗概率也是條件概率。獨立性Ａ和Ｂ是獨立的在給定Ｃ時，Ａ和Ｂ是條件獨立的概率推理

設H1,H2,H3為三個結論,E是支持這些結論的證據,且已知:P(H1)=0.3,P(H2)=0.4,P(H3)=0.5

P(E|H1)=0.5,P(E|H2)=0.3,P(E|H3)=0.4求:P(H1|E),P(H2|E),P(H3|E)解:貝葉斯網絡二十世紀八十年代貝葉斯網絡（BayesNetwork）成功地應用于專家系統，成為表示不確定性專家知識和推理的一種流行的方法?；谪惾~斯方法的貝葉斯網絡是一種適應性很廣的手段和工具，具有堅實的數學理論基礎。在綜合先驗信息（領域知識）和數據樣本信息的前提下，還可避免只使用先驗信息可能帶來的主觀偏見。雖然很多貝葉斯網絡涉及的學習問題是NP難解的。但是，由于已經有了一些成熟的近似解法，加上一些限制后計算可大為簡化，很多問題可以利用近似解法求解。貝葉斯網絡貝葉斯網絡方法的不確定性表示基本上是保持了概率的表示方式，可信度計算也是概率計算方法，只是在實現時，各具體系統根據應用背景的需要采用各種各樣的近似計算方法。推理過程稱為概率推理。貝葉斯網絡沒有其它確定性推理方法擁有的確定性表示、計算、語義解釋等問題。貝葉斯網絡的由來全聯合概率計算復雜性十分巨大樸素貝葉斯太過簡單現實需要一種自然、有效的方式來捕捉和推理——不確定性知識變量之間的獨立性和條件獨立性可大大減少為了定義全聯合概率分布所需的概率數目貝葉斯網絡（基本概念）貝葉斯網絡：一系列變量的聯合概率分布的圖形表示。一個表示變量之間的相互依賴關系的數據結構；圖論與概率論的結合。貝葉斯網絡的定義

是一個有向無環(huán)圖(DAG)隨機變量集組成網絡節(jié)點，變量可離散或連續(xù)連接節(jié)點對的有向邊組成邊集合每節(jié)點Xi都有一個條件概率分布表：P(Xi|Parents(Xi))，量化其父節(jié)點對該節(jié)點的影響獨立和條件獨立WeatherCavityCatchToothacheWeather和其它3個變量相互獨立貝葉斯網絡示例BurglaryEarthquakeMaryCallsJohnCallsAlarmBEP(A)tttfftff0.950.940.290.001AP(J)tf0.900.05AP(M)tf0.700.01P(B)0.001P(E)0.002

貝葉斯網絡的語義貝葉斯網就是一個在弧的連接關系上加入連接強度的因果關系網絡。貝葉斯網絡的語義P(x1,...,xn)=P(x1|parent(x1))...P(xn|parent(xn))貝葉斯網絡的語義公式計算示例：

試計算：報警器響了，但既沒有盜賊闖入，也沒有發(fā)生地震，同時John和Mary都給你打電話的概率。解：

P(J,M,A,~B,~E)=P(J|A)P(M|A)P(A|~B,~E)P(~B)P(~E)=0.9x0.7x0.001x0.999x0.998=0.00062=0.062%貝葉斯網絡的推理計算貝葉斯網絡中的條件獨立關系：

給定父節(jié)點，一個節(jié)點與它的非后代節(jié)點是條件獨立的給定一個節(jié)點的父節(jié)點、子節(jié)點以及子節(jié)點的父節(jié)點——馬爾可夫覆蓋(Markovblanket)，這個節(jié)點和網絡中的所有其它節(jié)點是條件獨立的主觀Bayes方法用產生式規(guī)則表示知識:

IFETHEN(LS,LN)H式中,(LS,LN)表示知識的靜態(tài)強度LS:充分性因子LN:必要性因子充分性度量它表示E對H的支持程度，取值于[0,∞],由專家給出。必要性度量它表示~E對Ｈ的支持程度，即E對H為真的必要性程度，取值范圍為[0,+∞]，也是由專家憑經驗給出。主觀Bayes方法

幾率函數表示x的出現概率與不出現概率之比當P(x)=0時，有O(x)＝0當P(x)=1時，有O(x)＝∞把取值為[0,1]的P(X)放大為取值[0,+∞]的O(X).知識不確定性的表示由Bayes公式，由以上兩式可得，

即有，

同理可得:以上兩式是修改的Bayes公式當E為真時,利用LS將H的先驗幾率O(H)更新為后驗幾率O(H|E)當E為假時,利用LN將H的先驗幾率O(H)更新為后驗幾率O(H|~E)知識不確定性的表示LS→∞時,O(H|E)→∞,P(H|E)→1,E的存在導致H為真.因此稱E對H是充分的,LS為充分性因子LN→0時,O(H|~E)→0,P(H|~E)→0,E的不存在導致H為假.因此稱E對H是必要的,LN為必要性因子證據的不確定性描述根據觀察S直接求出P(E|S)非常困難，引進了可信度C(E|S)，用戶可根據實際情況在[-5,5]中選取一個整數作為初始證據的可信度?？尚哦菴(E|S)與概率P(E|S)的對應關系可用下式表示：

C(E|S)=-5，表示在觀察S下證據E肯定不存在，即P(E|S)=0；

C(E|S)=0，表示在觀察S與證據E無關，即P(E|S)=P(E)；

C(E|S)=5，表示在觀察S下證據E肯定存在，即P(E|S)=1。

這樣，用戶只要對證據E給出在觀察S下的可信度C(E|S)，系統即可求出相應的P(E|S)。組合證據的不確定性描述對于組合證據E＝E1ANDE2AND…ANDEn

則P(E|S)＝min{P(E1|S),P(E2|S),…,P(En|S)}

對于組合證據E＝E1ORE2OR…OREn

則P(E|S)＝max{P(E1|S),P(E2|S),…,P(En|S)}基于主觀Bayes方法的不確定性推理

在主觀Bayes方法中，知識是用產生式規(guī)則表示的，具體形式為：

IFETHEN(LS,LN)H(P(H))LS,LN是充分性和必要性度量，P(H)是專家給出的先驗概率。推理就由P(H)，P(E)，LS和LN求出的過程。證據E確定必出現P(E)=P(E/S)=1，由Bayes公式，由以上兩式可得，

即有，

若需要以概率的形式表示，再由公式

計算出

這就是把先驗概率P(H)更新為后驗概率P(H|E)的計算公式。

證據E

確定必不出現P(E)=P(E|S)=0所以

從而這就是把先驗概率P(H)更新為后驗概率

的計算公式。證據E

不確定不能用上面的公式計算后驗概率，可用Duda于1976年給出的公式

來計算出后驗概率。這分為以下情況：證據肯定存在證據肯定不存在Ｅ與Ｓ無關當P（E|S）為其它值時

證據E

不確定(續(xù))當

故

這就是證據肯定存在的情況。當

故有

這就是證據肯定不存在的情況。證據E

不確定(續(xù))當P(E|S)=P(E)時，Ｅ與Ｓ無關，利用全概率公式有

當P(E|S)為其它值時，通過分段線性插值的方法，就可以得到計算P(H|S)的公式，即

該公式稱為EH公式。

P(E)(E|S)1

對于初始證據，由于其不確定性是用可信度C(E|S)給出，此時只要把P(E|S)與C(E|S)的對應關系轉換公式代入EH公式，就可以得到用可信度C(E|S)計算P(H|S)的公式：

該公式稱為CP公式。

這樣，當用初始證據進行推理時，根據用戶告知的C(E|S)

通過運用CP公式就可以求出P(H|S).當用推理過程中得到的中間結論作為證據進行推理時，通過運用EH公式就可求出P(H|S).

結論不確定性的合成算法若有n條規(guī)則都支持相同的結論，而且每條規(guī)則的前提條件所對應的證據Ｅi（i=1,2,…,n）都有相應的觀察Si與之對應，此時只要先對每條規(guī)則分別求出H的后驗幾率O(H|Si),然后按下列公式求出所