第四章 不確定推理

1、第四章第四章 不確定性推理不確定性推理王醒策王醒策信息科學(xué)與技術(shù)學(xué)院信息科學(xué)與技術(shù)學(xué)院不確定推理方法不確定推理方法l概述l可信度方法l主觀Bayes方法l證據(jù)理論概概 述述l不確定性推理的概念l不確定性推理的方法l不確定性推理中的基本問題不確定性推理的概念不確定性推理的概念l 一個人工智能系統(tǒng)，由于知識本身的不精確和不完全，采用標(biāo)準(zhǔn)邏輯意義下的推理方法難以達(dá)到解決問題的目的。對于一個智能系統(tǒng)來說，知識庫是其核心。在這個知識庫中，往往大量包含模糊性、隨機(jī)性、不可靠性或不知道等不確定性因素的知識。為了解決這種條件下的推理計算問題，不確定性推理方法應(yīng)運(yùn)而生。 不確定性推理的概念不確定性推理的概念l

2、產(chǎn)生原因 很多原因?qū)е峦唤Y(jié)果 推理所需的信息不完備 背景知識不足 信息描述模糊 信息中含有噪聲 規(guī)劃是模糊的 推理能力不足 解題方案不唯一 不精確思維并非專家的習(xí)慣或愛好所至，而是客觀現(xiàn)實的要求不確定性推理方法的分類不確定性推理方法的分類l模型方法定義：定義：把不確定性的證據(jù)和不確定性的知識分別與某種度量標(biāo)準(zhǔn)對應(yīng)起來，并給出更新結(jié)論不確定性的合適算法，從而構(gòu)成相應(yīng)的不確定性推理模型分類：分類：數(shù)值方法、非數(shù)值方法l控制方法不確定性推理中的基本問題不確定性推理中的基本問題l 不確定性的表示證據(jù)的不確定性表示l通過觀察而得到的所要求解問題的初始證據(jù)不確定l推理過程中，利用前面推理出來的結(jié)論作為當(dāng)

3、前新的推理證據(jù)知識的不確定性表示l將領(lǐng)域問題的特征比較準(zhǔn)確地描述出來，滿足問題求解的需要l便于在推理過程中對不確定性的推算不確定性推理中的基本問題不確定性推理中的基本問題l計算問題不確定性的傳遞問題證據(jù)不確定性的合成問題結(jié)論不確定性的合成問題不確定性推理中的基本問題不確定性推理中的基本問題l不確定性的量度定義：定義： 用一定的數(shù)值來表示知識、證據(jù)和結(jié)論的不確定性程度時，這種數(shù)值的取值方法、意義和相應(yīng)的取值范圍不確定性推理中的基本問題不確定性推理中的基本問題確定量度注意事項l量度要能充分表達(dá)相應(yīng)知識及證據(jù)的不確定性程度；l量度范圍的指定應(yīng)便于領(lǐng)域?qū)＜壹坝脩魧Σ淮_定性的估計；l量度要便于不確定性的

4、推理計算，而且所得到的結(jié)論的不確定值應(yīng)該落在不確定量度所規(guī)定的范圍之內(nèi)；l量度的確定應(yīng)當(dāng)是直觀的，同時應(yīng)當(dāng)有相應(yīng)的理論依據(jù)可信度方法可信度方法l可信度的概念l知識不確定性的表示l證據(jù)不確定性的表示l不確定性的推理計算l例題可信度方法可信度方法l MYCIN系統(tǒng)研制過程中采用的不確定性推理方法，第一個采用了不確定性的推理邏輯，在70年代很有名。l 提出方法時遵循的原則 不采用嚴(yán)格的統(tǒng)計理論，采用一種接近統(tǒng)計理論的近似方法 用專家的經(jīng)驗估計代替統(tǒng)計數(shù)據(jù) 盡量減少需要專家提供的經(jīng)驗數(shù)據(jù)，盡量使少量數(shù)據(jù)包含更多信息 新方法適用于證據(jù)為增量式增加的情況 專家數(shù)據(jù)的輕微擾動不影響最終的推理結(jié)論?？尚哦雀拍?/p>

5、可信度概念l可信度：人們在實際生活中根據(jù)自己的經(jīng)驗或者觀察后，對某一事件或者現(xiàn)象為真的相信程度。可信度具有較大的主觀性和經(jīng)驗性，相對來講準(zhǔn)確性難以把握。知識不確定性的表示知識不確定性的表示l在基于可信度的不確定性推理模型中，知識是以產(chǎn)生式規(guī)則來表示的，而只是的不確定性則是以可信度CF(H,E)來表示的，其一般的形式為：知識不確定性的表示知識不確定性的表示l 其中要注意的有：E是知識的前提條件或者稱為證據(jù)，它既可以是一個簡單的條件，也可以是用AND及OR把多個簡單條件連接起來所構(gòu)成的符合條件；H是結(jié)論，它可以是一個單一的結(jié)論，也可以是多個結(jié)論；CF(H,E)是該條知識的可信度，有的時候也成為可信

6、因子或者是規(guī)則強(qiáng)度。知識不確定性的表示知識不確定性的表示在專家系統(tǒng)MYCIN中，CF(H,E)被定義為：CF(H,E)=MB(H,E)-MD(H,E)其中：MB(Measure Belif):稱為信任增長度，它表示前提條件E匹配的證據(jù)出現(xiàn)，使H為真的信任增長度MD(Measure Disbelif):稱為不信任度增長度，它表示前提條件E匹配的證據(jù)出現(xiàn)，使結(jié)論H為真的不信任增長度知識不確定性的表示知識不確定性的表示這里P(H/E)表示前提E所對應(yīng)的證據(jù)出現(xiàn)情況下，結(jié)論H的條件概率P(H)表示H得先驗條件概率知識不確定性的表示知識不確定性的表示這里P(H/E)表示前提E所對應(yīng)的證據(jù)出現(xiàn)情況下，結(jié)論

7、H的條件概率P(H)表示H得先驗條件概率知識不確定性的表示知識不確定性的表示MB(H,E)與MD(H,E)是互斥的解釋l當(dāng)MD(H,E)0時，應(yīng)該有P(H/E)0時，則為P(H/E) P(H),那么有MD(H,E)=0l如果P(H/E)= P(H),則MD(H,E)= MD(H,E)=0表示，E與H無關(guān)知識不確定性的表示知識不確定性的表示l由上面的兩個公式就可以總結(jié)出CF(H,E)的公式：證據(jù)的不確定性的表示證據(jù)的不確定性的表示l單個證據(jù)的不確定性表示證據(jù)如果為初始證據(jù)，其可信度的值一般由提供證據(jù)的用戶直接指定，指定的方法也是用可信度因子對證據(jù)的不確定性表示用先前推出的結(jié)論作為當(dāng)前推理的證據(jù)，

8、對于這種情況的證據(jù)，其可信度的值在退出該結(jié)論是通過不確定性傳遞算法得到。證據(jù)的不確定性的表示證據(jù)的不確定性的表示l組合證據(jù)的不確定性獲取方法當(dāng)多個證據(jù)以合取得方式構(gòu)成一個組合證據(jù)的時候，組合證據(jù)的可信度為這些單一證據(jù)的可信度最小值；當(dāng)多個證據(jù)以析取得方式構(gòu)成一個組合證據(jù)的時候，組合證據(jù)的可信度為這些單一證據(jù)的可信度最大值；不確定性的推理計算不確定性的推理計算l單條知識支持結(jié)論時，結(jié)論可信度的計算方法如果支持結(jié)論的知識只有一條，且已知證據(jù)E的可信度CF(E)和規(guī)則 IF E THEN H的可信度為CF(H,E),則結(jié)論H的可信度計算公式為：不確定性的推理計算不確定性的推理計算l多條知識支持同一結(jié)

9、論時，結(jié)論不確定性的合成計算方法先考慮兩條知識的情況，多條知識的時候可以應(yīng)用兩兩合成的方法實現(xiàn)不確定性的推理計算不確定性的推理計算利用單條知識支持結(jié)論共識，計算每一條知識的結(jié)論可信度CF(H)不確定性的推理計算不確定性的推理計算根據(jù)下面的公式，求出E1與E2對H的綜合影響形成的可信度CF(H)可信度方法總結(jié)可信度方法總結(jié)l可信度方法的宗旨不是理論上的嚴(yán)謹(jǐn)性，而是處理實際問題的可用性。l不可以一成不變的應(yīng)用與任何領(lǐng)域中的，甚至也不能適用于所有的科學(xué)領(lǐng)域，推廣到一個新的領(lǐng)域時，必須根據(jù)要求加以修正。主觀主觀Bayes方法方法l 基本的Bayes公式l 主觀 Bayes方法及其推理網(wǎng)絡(luò)l 知識的不確

10、定性表示l 證據(jù)的不確定性表示l 不確定性的推理計算l 結(jié)論的不確定性的合成l 主觀Bayes方法應(yīng)用舉例基本的基本的Bayes公式公式P(Bi)是事件Bi的先驗概率P(A/Bi)是事件Bi發(fā)生的條件下事件A發(fā)生的條件概率P(Bi/A)是事件A發(fā)生的條件下事件Bi發(fā)生的條件概率主觀主觀Bayes方法及其推理網(wǎng)絡(luò)方法及其推理網(wǎng)絡(luò)主觀Bayes方法是由杜達(dá)（Duda）在1976年提出的一種不確定推理模型，并在地礦探測專家系統(tǒng)PROSEPCTOR中得到了成功的應(yīng)用推理網(wǎng)絡(luò)：為了進(jìn)行不確定性推理，把所有的知識規(guī)則連接成為一個有向圖，圖中的各節(jié)點代表假設(shè)結(jié)論，弧則代表規(guī)則，并引入兩個數(shù)值（LS,LN）與

11、每一條弧相連，用來度量規(guī)則成立的充分性和必要性。主觀主觀Bayes方法及其推理網(wǎng)絡(luò)方法及其推理網(wǎng)絡(luò)推理網(wǎng)絡(luò)把一些證據(jù)和重要的假設(shè)結(jié)論連接起來。圖中的端節(jié)點或者是“葉子”節(jié)點是向用戶提問所獲得的證據(jù)，其它的節(jié)點就是假設(shè)的結(jié)論。推理網(wǎng)絡(luò)中的連接實際上就是測定一個結(jié)論的概率變化是如何地影響了其他結(jié)論。在推理網(wǎng)絡(luò)中證據(jù)和結(jié)論是相對的。知識的不確定性表示知識的不確定性表示l在主觀Bayes方法中，知識（規(guī)則）就是推理網(wǎng)絡(luò)中的一條弧，它的不確定性是以一個數(shù)值對（LS,LN）來進(jìn)行描述的。若以產(chǎn)生是規(guī)則來表示則為：知識的不確定性表示知識的不確定性表示l解釋：（LS,LN）是為度量產(chǎn)生式規(guī)則的不確定性而引入的

12、一組數(shù)值。E是該條知識的前提條件。H是結(jié)論。P(H)是H的先驗概率，由領(lǐng)域?qū)＜业慕?jīng)驗給出。證據(jù)的不確定性表示證據(jù)的不確定性表示l單個證據(jù)的不確定表示方法在主觀Bayes方法中，證據(jù)的不確定是用概率來表示的。E是證據(jù)，S是對證據(jù)的觀察由于后驗概率P(E/S)的給出比較困難，因此引入了可信度C(E/S)的概念。證據(jù)的不確定性表示證據(jù)的不確定性表示給定了可信度C(E/S)，就等價于告知了P(E/S)，二者有簡單的保持大小次序?qū)?yīng)的關(guān)系證據(jù)的不確定性表示證據(jù)的不確定性表示證據(jù)的不確定性表示證據(jù)的不確定性表示l組合證據(jù)的不確定性表示當(dāng)證據(jù)E是由多個單一證據(jù)合取組合而成當(dāng)證據(jù)E是由多個單一證據(jù)析取組合而成

13、對于非運(yùn)算不確定性的推理計算不確定性的推理計算主觀Bayes方法推理計算的任務(wù)就是根據(jù)證據(jù)E的概率P(E)及影響知識的規(guī)則強(qiáng)度(LS,LN)，把H的先驗概率P(H)更新為后驗概率P(H/E)或者是P(H/E)。在推理網(wǎng)絡(luò)中，一條知識對結(jié)論的影響是依賴于證據(jù)的，證據(jù)出現(xiàn)的情況時不同時，推理計算結(jié)論H信任程度的變化方法就不同。不確定性的推理計算不確定性的推理計算l確定證據(jù)預(yù)備知識證據(jù)肯定出現(xiàn)證據(jù)肯定不出現(xiàn)LS和LN的意義討論預(yù)備知識預(yù)備知識l為了解釋方便，我們引入幾率函數(shù)O(x)， 它與概率之間的關(guān)系為：l很顯然，P(x)與O(x)具有相同的單調(diào)性，只是相應(yīng)的值域不同。預(yù)備知識預(yù)備知識由Bayes

14、公式可得同理有預(yù)備知識預(yù)備知識兩個式子相除得由LS的定義和概率和幾率的關(guān)系可得證據(jù)肯定出現(xiàn)證據(jù)肯定出現(xiàn)當(dāng)證據(jù)肯定出現(xiàn)的時候P(E)=P(E/S)=1肯定出現(xiàn)的時候，用下面的式子既可以把先驗幾率O(H)更換為后驗幾率O(H/E)如果我們把幾率用概率替換即可得預(yù)備知識預(yù)備知識由Bayes公式可得兩式相除得預(yù)備知識預(yù)備知識根據(jù)LN的定義，以及概率與幾率之間的關(guān)系可得：證據(jù)肯定不出現(xiàn)證據(jù)肯定不出現(xiàn)在證據(jù)肯定不出現(xiàn)時P(E)=P(E/S)=0, P(E)=1.那么用下式計算當(dāng)E肯定不出現(xiàn)的情況下，把先驗幾率O(H)更新為O(H/E)根據(jù)概率和幾率的換算關(guān)系可得對對LS和和LN的討論的討論l充分性度量LS

15、的討論當(dāng)LS1時，可得O(H/E)O(H)當(dāng)LS=1時，可得O(H/E)=O(H)當(dāng)LS1時，可得O(H/E)1時，可得O(H/E)O(H)當(dāng)LN=1時，可得O(H/ E)=O(H)當(dāng)LN1時，可得O(H/ E)1且LN1LS=LN=1LS1不確定性證據(jù)不確定性證據(jù)l用概率表示證據(jù)的不確定性上述針對確定性證據(jù)的后驗概率將不再適用而要使用下面的公式。不確定性證據(jù)不確定性證據(jù)P(E/S)=1; P(H/S)=P(H/E)P(E/S)=0; P(H/S)=P(H/E)P(E/S)=P(E); P(H/S)=P(H)不確定性證據(jù)不確定性證據(jù)l利用這三個特殊點，使用分段插值公式可得P(E/S)與P(H/

16、S)的解析表達(dá)式結(jié)論的不確定性合成結(jié)論的不確定性合成l若有n條知識都支持相同的結(jié)論，并且每條知識的前提條件所對應(yīng)的證據(jù)Ei都有相應(yīng)的觀察Si，這時需要按照下面的式子求得P(H/S1,Sn)舉例說明舉例說明l為了進(jìn)一步地熟悉主觀Bayes方法，下面給出一些例子說明證據(jù)理論證據(jù)理論l概述l數(shù)學(xué)基礎(chǔ)l基于特定概率分配函數(shù)的不確定性推理模型l證據(jù)理論例題概述概述l證據(jù)理論由Dempster首先提出，并由他的學(xué)生Shafer發(fā)展起來，也稱D-S理論。 l證據(jù)理論中引入了信任函數(shù)，它滿足概率論弱公理。l當(dāng)概率值已知時，證據(jù)理論就成了概率論。因此，概率論是證據(jù)理論的一個特例，有時也稱證據(jù)淪為廣義概率論。 概

17、述概述l :8080/UGAIWWW/lectures/dempster.html上有關(guān)于DempsterShafer理論的英文介紹。l 在http:/www.quiver.freeserve.co.uk/Dse.htm上有免費的利用證據(jù)理論實現(xiàn)的程序Dempster Shafer Engine下載。有興趣的同學(xué)可以安裝這一軟件，看看運(yùn)行效果。 D-S理論的數(shù)學(xué)基礎(chǔ)理論的數(shù)學(xué)基礎(chǔ)l集合論冪集并集交集互不相交D-S理論的數(shù)學(xué)基礎(chǔ)理論的數(shù)學(xué)基礎(chǔ)l函數(shù)介紹概率分配函數(shù) M(x)：2D0,1。 M () = 0 空的為零M (A) = 1 全空間的和為

18、1 D-S理論的數(shù)學(xué)基礎(chǔ)理論的數(shù)學(xué)基礎(chǔ)信任函數(shù) Bel：2D 0,1。D-S理論的數(shù)學(xué)基礎(chǔ)理論的數(shù)學(xué)基礎(chǔ)似然函數(shù) Pl: 2D 0,1D-S理論的數(shù)學(xué)基礎(chǔ)理論的數(shù)學(xué)基礎(chǔ)概率分配函數(shù)正交和設(shè)M1和M2是兩個概率分配函數(shù)，則他們的正交和M=M1 M2為lM() = 0;lM(A) = K-1m1(X)m2(Y), 當(dāng)XY = Al其中K = 1 - m1(X)m2(Y), 當(dāng)XY = m1(X)m2(Y), 當(dāng)XY 特定概率分配函數(shù)特定概率分配函數(shù)l 設(shè)樣本空間D=S1,S2,Sn,領(lǐng)域內(nèi)的命題都用D的子集來表示，則定義2D上的概率分配函數(shù)M(x)滿足如下條件特定概率分配函數(shù)特定概率分配函數(shù)其中，|A|表示命題A對應(yīng)的集合中所包含的元素個數(shù)。在這種特定的概率分配函數(shù)中，定義了只有單個元素構(gòu)成的子集和樣本空間D本身的基本概率數(shù)才有可能大于0，其它子集的基本概率數(shù)均為0