人工智能課件3-推理

第7章高級(jí)知識(shí)推理高級(jí)知識(shí)推理經(jīng)典邏輯確定性推理單調(diào)性推理歸約推理肖解演繹推理規(guī)則演繹推理非經(jīng)典邏輯不確定性推理非單調(diào)性推理時(shí)序推理概率推理經(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é)論越來(lái)越多非單調(diào)推理推理系統(tǒng)的定理集合不隨推理過(guò)程的進(jìn)行而單調(diào)增大新推理出的定理可能修正以至否定原有的一些定理,使得原來(lái)能夠解釋的一些現(xiàn)象變得不可解釋.

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

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

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

，

乘法公式：

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

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

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

是一個(gè)有向無(wú)環(huán)圖(DAG)隨機(jī)變量集組成網(wǎng)絡(luò)節(jié)點(diǎn)，變量可離散或連續(xù)連接節(jié)點(diǎn)對(duì)的有向邊組成邊集合每節(jié)點(diǎn)Xi都有一個(gè)條件概率分布表：P(Xi|Parents(Xi))，量化其父節(jié)點(diǎn)對(duì)該節(jié)點(diǎn)的影響?yīng)毩⒑蜅l件獨(dú)立WeatherCavityCatchToothacheWeather和其它3個(gè)變量相互獨(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ò)的語(yǔ)義貝葉斯網(wǎng)就是一個(gè)在弧的連接關(guān)系上加入連接強(qiáng)度的因果關(guān)系網(wǎng)絡(luò)。貝葉斯網(wǎng)絡(luò)的語(yǔ)義P(x1,...,xn)=P(x1|parent(x1))...P(xn|parent(xn))貝葉斯網(wǎng)絡(luò)的語(yǔ)義公式計(jì)算示例：

試計(jì)算：報(bào)警器響了，但既沒(méi)有盜賊闖入，也沒(méi)有發(fā)生地震，同時(shí)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)，一個(gè)節(jié)點(diǎn)與它的非后代節(jié)點(diǎn)是條件獨(dú)立的給定一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)、子節(jié)點(diǎn)以及子節(jié)點(diǎn)的父節(jié)點(diǎn)——馬爾可夫覆蓋(Markovblanket)，這個(gè)節(jié)點(diǎn)和網(wǎng)絡(luò)中的所有其它節(jié)點(diǎn)是條件獨(dú)立的主觀Bayes方法用產(chǎn)生式規(guī)則表示知識(shí):

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

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

即有，

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

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

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

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

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

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

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

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

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

IFETHEN(LS,LN)H(P(H))LS,LN是充分性和必要性度量，P(H)是專家給出的先驗(yàn)概率。推理就由P(H)，P(E)，LS和LN求出的過(guò)程。證據(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年給出的公式

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

證據(jù)E

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

故

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

故有

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

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

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

該公式稱為EH公式。

P(E)(E|S)1

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

該公式稱為CP公式。

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

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

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