人工智能課件3-推理

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

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

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

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

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

，

乘法公式：

全概率公式：設(shè)A1，A2，…An互不相交，，且，則對于任意事件A有概率論基礎(chǔ)（貝葉斯定理）設(shè)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稱為先驗(yàn)概率，而P(Bi|A)i=1,2,…,n稱為后驗(yàn)概率也是條件概率。獨(dú)立性Ａ和Ｂ是獨(dú)立的在給定Ｃ時，Ａ和Ｂ是條件獨(dú)立的概率推理

設(shè)H1,H2,H3為三個結(jié)論,E是支持這些結(jié)論的證據(jù),且已知: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)解:貝葉斯網(wǎng)絡(luò)二十世紀(jì)八十年代貝葉斯網(wǎng)絡(luò)（BayesNetwork）成功地應(yīng)用于專家系統(tǒng)，成為表示不確定性專家知識和推理的一種流行的方法?；谪惾~斯方法的貝葉斯網(wǎng)絡(luò)是一種適應(yīng)性很廣的手段和工具，具有堅(jiān)實(shí)的數(shù)學(xué)理論基礎(chǔ)。在綜合先驗(yàn)信息（領(lǐng)域知識）和數(shù)據(jù)樣本信息的前提下，還可避免只使用先驗(yàn)信息可能帶來的主觀偏見。雖然很多貝葉斯網(wǎng)絡(luò)涉及的學(xué)習(xí)問題是NP難解的。但是，由于已經(jīng)有了一些成熟的近似解法，加上一些限制后計(jì)算可大為簡化，很多問題可以利用近似解法求解。貝葉斯網(wǎng)絡(luò)貝葉斯網(wǎng)絡(luò)方法的不確定性表示基本上是保持了概率的表示方式，可信度計(jì)算也是概率計(jì)算方法，只是在實(shí)現(xiàn)時，各具體系統(tǒng)根據(jù)應(yīng)用背景的需要采用各種各樣的近似計(jì)算方法。推理過程稱為概率推理。貝葉斯網(wǎng)絡(luò)沒有其它確定性推理方法擁有的確定性表示、計(jì)算、語義解釋等問題。貝葉斯網(wǎng)絡(luò)的由來全聯(lián)合概率計(jì)算復(fù)雜性十分巨大樸素貝葉斯太過簡單現(xiàn)實(shí)需要一種自然、有效的方式來捕捉和推理——不確定性知識變量之間的獨(dú)立性和條件獨(dú)立性可大大減少為了定義全聯(lián)合概率分布所需的概率數(shù)目貝葉斯網(wǎng)絡(luò)（基本概念）貝葉斯網(wǎng)絡(luò)：一系列變量的聯(lián)合概率分布的圖形表示。一個表示變量之間的相互依賴關(guān)系的數(shù)據(jù)結(jié)構(gòu)；圖論與概率論的結(jié)合。貝葉斯網(wǎng)絡(luò)的定義

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

貝葉斯網(wǎng)絡(luò)的語義貝葉斯網(wǎng)就是一個在弧的連接關(guān)系上加入連接強(qiáng)度的因果關(guān)系網(wǎng)絡(luò)。貝葉斯網(wǎng)絡(luò)的語義P(x1,...,xn)=P(x1|parent(x1))...P(xn|parent(xn))貝葉斯網(wǎng)絡(luò)的語義公式計(jì)算示例：

試計(jì)算：報(bào)警器響了，但既沒有盜賊闖入，也沒有發(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%貝葉斯網(wǎng)絡(luò)的推理計(jì)算貝葉斯網(wǎng)絡(luò)中的條件獨(dú)立關(guān)系：

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

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

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

即有，

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

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

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

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

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

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

對于組合證據(jù)E＝E1ORE2OR…OREn

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

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

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

即有，

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

計(jì)算出

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

證據(jù)E

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

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

的計(jì)算公式。證據(jù)E

不確定不能用上面的公式計(jì)算后驗(yàn)概率，可用Duda于1976年給出的公式

來計(jì)算出后驗(yàn)概率。這分為以下情況：證據(jù)肯定存在證據(jù)肯定不存在Ｅ與Ｓ無關(guān)當(dāng)P（E|S）為其它值時

證據(jù)E

不確定(續(xù))當(dāng)

故

這就是證據(jù)肯定存在的情況。當(dāng)

故有

這就是證據(jù)肯定不存在的情況。證據(jù)E

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

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

該公式稱為EH公式。

P(E)(E|S)1

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

該公式稱為CP公式。

這樣，當(dāng)用初始證據(jù)進(jìn)行推理時，根據(jù)用戶告知的C(E|S)

通過運(yùn)用CP公式就可以求出P(H|S).當(dāng)用推理過程中得到的中間結(jié)論作為證據(jù)進(jìn)行推理時，通過運(yùn)用EH公式就可求出P(H|S).

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