第四章非經典推理4.1概述4.2不確定性推理4.3非單調推理4.4概率方法4.5主觀貝葉斯方法4.6貝葉斯網絡4.7可信度方法4.8證據理論2023/1/13人工智能導論-劉珊1基本框架2023/1/13人工智能導論-劉珊2貝葉斯網絡全聯(lián)合概率分布貝葉斯網絡的定義獨立和條件獨立貝葉斯網絡的構造貝葉斯網絡的應用精確推理近似推理2023/1/13人工智能導論-劉珊34.6貝葉斯網絡全聯(lián)合概率分布定義設X={X1,X2,…,Xn}為任何隨機變量集，其全聯(lián)合概率分布是指當對每個變量取特定值時xi（i=1,2,…,n）時的合取概率，即P(X1=x1∧X2=x2∧…∧Xn=xn)，其簡化表示形式為P(x1,x2,…,xn)。重復使用乘法法則2023/1/13人工智能導論-劉珊4得到如下全聯(lián)合概率分布表示4.6貝葉斯網絡貝葉斯網絡基本概念一系列變量的聯(lián)合概率分布的圖形表示一個表示變量之間的相互依賴關系的數據結構定義是一個有向無環(huán)圖隨機變量集X={X1,X2,…,Xn}組成網絡節(jié)點，變量可離散或連續(xù)連接節(jié)點對的有向邊組成邊集合每節(jié)點Xi都有一個條件概率分布表：P(Xi|par(Xi))，量化其父節(jié)點對該節(jié)點的影響2023/1/13人工智能導論-劉珊54.6貝葉斯網絡示例例1、假設學生在碰見難題和遇到干擾時會產生焦慮，而焦慮又可導致思維遲緩和情緒波動。請用貝葉斯網絡描述這一問題。解：在該貝葉斯網絡中，大寫英文字母A、D、I、C和E分別表示節(jié)點“產生焦慮”、“碰見難題”、“遇到干擾”、“認知遲緩”和“情緒波動”，并將各節(jié)點的條件概率表置于相應節(jié)點的右側。所有隨機變量取布爾變量，因此可以分別用小寫英文字母a、d、i、c和e來表示布爾變量A、D、I、C和E取邏輯值為“True”，用﹁a、﹁d、﹁i、﹁c和﹁e來表示布爾變量A、D、I、C和E取邏輯值為“False”。2023/1/13人工智能導論-劉珊64.6貝葉斯網絡示例右圖貝葉斯網絡中每個節(jié)點的概率表就是該節(jié)點與其父節(jié)點之間的一個局部條件概率分布。由于節(jié)點D和I無父節(jié)點，故它們的條件概率表由其先驗概率來填充2023/1/13人工智能導論-劉珊7碰見難題產生焦慮遇到干擾思維遲緩情緒波動ADIECAP(C)T0.8AP(E)T0.9

P(D)0.15P(I)0.05DIP(A)TT0.8TF0.4FT0.5FF0.14.6貝葉斯網絡聯(lián)合概率分布表示貝葉斯網絡的聯(lián)合概率分布表示用par(Xi)表示Xi的所有父節(jié)點的相應取值，P(Xi|par(Xi))是節(jié)點Xi的一個條件概率分布函數，則對X的所有節(jié)點，有如下聯(lián)合概率分布：2023/1/13人工智能導論-劉珊8局部化特征每個節(jié)點只受到整個節(jié)點集中少數別的節(jié)點的直接影響，而不受這些節(jié)點外的其它節(jié)點的直接影響。貝葉斯網絡的語義4.6貝葉斯網絡獨立和條件獨立Weather和其它3個變量相互獨立。給定Cavity后，Toothache和Catch條件獨立2023/1/13人工智能導論-劉珊9WeatherCavityCatchToothache貝葉斯網絡能實現簡化計算的最根本基礎-----條件獨立性。兩個判別準則1）給定父節(jié)點，一個節(jié)點與非其后代的節(jié)點之間是條件獨立的。2）給定一個節(jié)點，該節(jié)點與其父節(jié)點、子節(jié)點和子節(jié)點的父節(jié)點一起構成了一個馬爾科夫覆蓋，則該節(jié)點與馬爾科夫覆蓋以外的所有節(jié)點之間都是條件獨立的。4.6貝葉斯網絡條件獨立2023/1/13人工智能導論-劉珊10U1UmXZ1jZnjY1Yn【說明】：給定節(jié)點X的父節(jié)點U1...Um，節(jié)點X與它的非后代節(jié)點（即Zij）是條件獨立的。4.6貝葉斯網絡……條件獨立2023/1/13人工智能導論-劉珊11【說明】：給定馬爾可夫覆蓋（兩圓圈之間的區(qū)域），節(jié)點X和馬爾可夫覆蓋中所有其它節(jié)點都是條件獨立的。U1UmXZ1jZnjY1Yn4.6貝葉斯網絡貝葉斯網絡的構造構造過程(1)首先建立不依賴于其它節(jié)點的根節(jié)點，并且根節(jié)點可以不止一個。(2)加入受根節(jié)點影響的節(jié)點，并將這些節(jié)點作為根節(jié)點的子節(jié)點。此時，根節(jié)點已成為父節(jié)點。(3)進一步建立依賴于已建節(jié)點的子節(jié)點。重復這一過程直到葉節(jié)點為止。(4)對每個根節(jié)點，給出其先驗概率；對每個中間節(jié)點和葉節(jié)點，給出其條件概率表。主要原則忽略過于微弱的依賴關系利用變量間的因果關系2023/1/13人工智能導論-劉珊124.6貝葉斯網絡貝葉斯網絡的簡單應用例2、對例1所示的貝葉斯網絡，若假設某學生已經產生了焦慮情緒，但實際上并未碰見難題，也未遇到干擾，請計算思維遲緩和情緒波動的概率。解：令相應變量的取值分別為：a,﹁d,﹁i,c,e，

P(c∧e∧a∧﹁d∧﹁i)=P(c|a)P(e|a)P(a|﹁d∧﹁i)P(﹁d)P(﹁i)=0.8×0.9×0.1×0.85×0.95=0.05814即所求的概率為0.058142023/1/13人工智能導論-劉珊134.6貝葉斯網絡貝葉斯網絡推理概念在給定一組證據變量觀察值的情況下，利用貝葉斯網絡計算一組查詢變量的后驗概率分布。變量分類查詢變量X證據變量集E={E1,E2,…,En}觀察到的特定事件s非證據變量集Y={y1,y2,…,ym}全部變量的集合V={x}EY其推理就是要查詢后驗概率P(X|s)。2023/1/13人工智能導論-劉珊144.6貝葉斯網絡貝葉斯網絡推理步驟首先確定各相鄰節(jié)點之間的初始條件概率分布；然后對各證據節(jié)點取值；接著選擇適當推理算法對各節(jié)點的條件概率分布進行更新；最終得到推理結果。分類精確推理：一種可以精確地計算查詢變量的后驗概率的推理方法，適用于單連通貝葉斯網絡。近似推理：在不影響推理正確性的前提下，通過適當降低推理精確度來提高推理效率的一類方法。2023/1/13人工智能導論-劉珊154.6貝葉斯網絡貝葉斯網絡精確推理主要方法基于枚舉的算法基于變量消元的算法基于團樹傳播的算法等基于枚舉的算法利用全聯(lián)合概率分布去推斷查詢變量的后驗概率2023/1/13人工智能導論-劉珊164.6貝葉斯網絡示例例3、以例1所示的貝葉斯網絡為例，假設目前觀察到的一個事件s={c,e}，求在該事件的前提下碰見難題的概率P(D|c,e)是多少？解：按照精確推理算法，該詢問可表示為：2023/1/13人工智能導論-劉珊17先對D的不同取值d和﹁d分別進行處理，當D取值d時，有4.6貝葉斯網絡示例2023/1/13人工智能導論-劉珊18當D取值﹁d時，有取α=1/(0.0519+0.0901)=1/0.142。因此有

P(D|c,e)=α(0.0519,0.0901)=(0.3655,0.6345)即在思維遲緩和情緒波動都發(fā)生時，碰見難題的概率是P(d|c,e)=0.3655,沒有碰見難題的概率是P(﹁d|c,e)=0.63454.6貝葉斯網絡貝葉斯網絡近似推理馬爾可夫鏈蒙特卡羅（MCMC）算法是目前使用較廣的一類貝葉斯網絡推理方法。它通過對前一個事件狀態(tài)作隨機改變來生成下一個問題狀態(tài)，通過對某個隱變量進行隨機采樣來實現對隨機變量的改變。MCMC方法可視為：在狀態(tài)空間中的隨機走動，但是證據變量的值固定不變。2023/1/13人工智能導論-劉珊194.6貝葉斯網絡示例例4、學習情緒會影響學習效果。假設有一個知識點，考慮學生在愉快學習狀態(tài)下對該知識點的識記、理解、運用的情況，得到了如右圖所示的貝葉斯網絡。如果目前觀察到一個學生不但記住了該知識，并且還可以運用該知識，詢問這位學生是否理解了該知識。2023/1/13人工智能導論-劉珊20愉快學習知識識記知識理解知識運用EUMAEP(M)T0.9F0.4P(E)0.75MUP(A)TT0.95TF0.5FT0.65FF0.1EP(U)T0.85F0.34.6貝葉斯網絡示例解：要求的是P(U|m,a)。應用MCMC算法的推理步驟如下：(1)將“知識識記”節(jié)點M和“知識運用”節(jié)點A作為證據變量，并保持它們的觀察值不變；(2)隱變量“愉快學習”節(jié)點E和查詢變量“知識理解”節(jié)點U進行隨機初始化。假設，取值分別為e和﹁u，問題的初始狀態(tài)為{e,m,﹁u,a}；(3)反復執(zhí)行如下步驟，①對隱變量E進行采樣，由于E的馬爾科夫覆蓋（其父節(jié)點、子節(jié)點和子節(jié)點的父節(jié)點）僅包含節(jié)點M和U，可以按照變量M和U的當前值進行采樣，若采樣得到﹁e，則生成下一狀態(tài){﹁e,m,﹁u,a}；②對查詢變量U進行采樣，由于U的馬爾科夫覆蓋包含節(jié)點E、M和A，可以按照變量E、M和A的當前值進行采樣，若采樣得到u，則生成下一狀態(tài){﹁e,m,u,a}。(4)重復以上步驟直到所要求的訪問次數N。若為true和false的次數分別為n1,、n2，則查詢解為Normalize(<n1,n2>)=<n1/N,n2/N>2023/1/13人工智能導論-劉珊214.6貝葉斯網絡示例解：在上述采樣過程中，每次采樣都需要兩步。以對隱變量E的采樣為例，每次采樣步驟如下：1、先依據該隱變量的馬爾科夫覆蓋所包含的變量的當前值，計算該狀態(tài)轉移概率p；2、確定狀態(tài)是否需要改變。其基本方法是，生成一個隨機數r∈[0,1]，將其與第一步得到的轉移概率p進行比較，若r<p，則E取﹁e，轉移到下一狀態(tài)；否則，還處在原狀態(tài)不變。在初始狀態(tài)下，對變量E進行采樣，第一步計算P(E|m,﹁u)，以此判斷是否轉移到下一狀態(tài){﹁e,m,﹁u,a}。

P(e|m,﹁u)=P(e,m,﹁u)/P(m,﹁u)=P(e)P(m|e)P(﹁u|e)/[P(e)P(m|e)P(﹁u|e)+P(﹁e)P(m|﹁e)P(﹁u|﹁e)]=(0.75×0.9×0.3)/[0.75×0.9×0.3+0.25×0.4×0.3]=0.2025/0.2325=0.8710第二步，假設產生的隨機數r=0.46，有0.46<0.871，則E取﹁e，轉移到下一狀態(tài){﹁e,m,﹁u,a}2023/1/13人工智能導論-劉珊224.6貝葉斯網絡第四章非經典推理4.1概述4.2不確定性推理4.3非單調推理4.4概率方法4.5主觀貝葉斯方法4.6貝葉斯網絡4.7可信度方法4.8證據理論2023/1/13人工智能導論-劉珊23基本概念可信度：根據經驗對一個事物或現象為真的相信程度。C－F模型：基于可信度表示的不確定性推理的基本方法。主要內容1、C-F模型中規(guī)則的不確定性表示2、C-F模型中證據的不確定性表示3、C-F模型中組合證據不確定性的計算4、C-F模型中不確定性的更新5、C-F模型中結論的不確定性合成6、帶加權因子的可信度推理2023/1/13人工智能導論-劉珊244.7可信度方法1、規(guī)則不確定性的表示產生式規(guī)則表示IFETHENH(CF(H,E))CF(H,E)：可信度因子，反映前提條件與結論的聯(lián)系強度。CF(H，E)的取值范圍：[-1,1]。若由于相應證據的出現增加結論H為真的可信度，則CF(H，E)>0，證據的出現越是支持H為真，就使CF(H，E)的值越大。反之，CF(H，E)<0，證據的出現越是支持H為假，CF(H，E)的值就越小。若證據的出現與否與H無關，則CF(H，E)=02023/1/13人工智能導論-劉珊254.7可信度方法2、證據不確定性的表示證據E的可信度取值范圍：[-1，1]。對于初始證據，若所有觀察S能肯定它為真，則CF(E)=1；若肯定它為假，則CF(E)=–1。若以某種程度為真，則0<CF(E)<1。若以某種程度為假，則－1<CF(E)<0。若未獲得任何相關的觀察，則CF(E)=0。靜態(tài)強度CF(H，E)：知識的強度，即當所對應的證據E為真時對H的影響程度。動態(tài)強度CF(E)：證據E當前的不確定性程度2023/1/13人工智能導論-劉珊264.7可信度方法3、組合證據不確定性的算法組合證據：多個單一證據的合取E=E1

AND

E2AND…ANDEn則CF(E)=min{CF(E1),CF(E1),…,CF(En)}組合證據：多個單一證據的析取E=E1ORE2

OR…

OREn

則CF(E)=max{CF(E1),CF(E1),…,CF(En)}2023/1/13人工智能導論-劉珊274.7可信度方法4、不確定性的傳遞算法C-F模型中的不確定性推理：從不確定的初始證據出發(fā)，通過運用相關的不確定性知識，最終推出結論并求出結論的可信度值。結論H的可信度由下式計算:2023/1/13人工智能導論-劉珊28CF(E)<0時，CF(H)=0;CF(E)=1時，CF(H)=CF(H,E)4.7可信度方法5、結論不確定性的合成算法設知識：IFE1THENH(CF(H,E1))IFE2THENH(CF(H,E2))（1）分別對每一條知識求出CF(H)：CF1(H)=CF(H,E1)×max{0,CF(E1)}CF2(H)=CF(H,E2)×max{0,CF(E2)}(2)用如下公式求E1與E2對H的綜合可信度2023/1/13人工智能導論-劉珊294.7可信度方法6、帶加權因子的可信度推理當知識的前提條件為多個子條件組合，且這些子條件對結論的重要程度不同時，在前提條件中加入加權因子，以說明每個前提的重要程度。知識的不確定性表示ifE1(w1)andE2(w2)and…andEn(wn)thenHCF(H,E)

其中w1,w2,…,wn為加權因子，一般滿足歸一條件即w1+w2+…+wn=12023/1/13人工智能導論-劉珊304.7可信度方法帶加權因子的可信度推理組合證據不確定性的計算若E=E1(w1)andE2(w2)and…andEn(wn)則E的可信度因子可以按如下方式計算CF(E)=∑wi*CF(Ei)不確定性的更新直觀的方法為：CF(H)=CF(H，E)*CF(E)2023/1/13人工智能導論-劉珊314.7可信度方法示例例1、已知規(guī)則r1:ifE1(0.6)andE2(0.4)thenE5(0.8)r2:ifE3(0.5)andE4(0.3)andE5(0.2)thenH(0.9)以及CF(E1)=0.9,CF(E2)=0.8,CF(E3)=0.7,CF(E4)=0.6求CF(H)？2023/1/13人工智能導論-劉珊324.7可信度方法示例解：CF(E5)=CF(E5,E)*CF(E)=0.8*0.86=0.69CF(E3(0.5)andE4(0.3)andE5(0.2))=0.67CF(H)=0.9*0.67=0.6032023/1/13人工智能導論-劉珊334.7可信度方法第四章非經典推理4.1概述4.2不確定性推理4.3非單調推理4.4概率方法4.5主觀貝葉斯方法4.6貝葉斯網絡4.7可信度方法4.8證據理論2023/1/13人工智能導論-劉珊34證據理論又稱D－S理論在證據理論的基礎上已經發(fā)展了多種不確定性推理模型主要內容概率分配函數信任函數似然函數信任函數與似然函數的關系概率分配函數的正交和（證據的組合）基于證據理論的推理2023/1/13人工智能導論-劉珊354.8證據理論基本概念證據理論假設有一個不變的兩兩相斥的完備元素集合U，如右圖所示，其中2023/1/13人工智能導論-劉珊36證據理論說明圖4.8證據理論例如,U={三輪車，汽車，火車}U={赤，橙，黃，綠，青，藍，紫}U={馬，牛，羊，雞，狗，兔}基本概念證據理論用集合表示命題。設D是變量x所有可能取值的集合，且D中的元素是互斥的，在任一時刻x都取D中的某一個元素為值，稱D為x的樣本空間。在證據理論中，D的任何一個子集A都對應于一個關于x的命題，稱該命題為“x的值在A中”。設x：所看到的顏色，D={紅，黃，藍}，則A={紅}：“x是紅色”；

A={紅，藍}：“x或者是紅色，或者是藍色”。為了描述和處理不確定性，引入了概率分配函數、信任函數及似然函數等概念。2023/1/13人工智能導論-劉珊374.8證據理論概率分配函數設D為樣本空間，領域內的命題都用D的子集表示。定義：設函數M：,且滿足2023/1/13人工智能導論-劉珊384.8證據理論則稱M是上的概率分配函數，M(A)稱為A的基本概率函數。對樣本空間D的任一子集都分配一個概率值。概率分配函數2023/1/13人工智能導論-劉珊39幾點說明：（1）樣本空間D中有n個元素，則D中子集的個數為2n個。

2D：D的所有子集。（2）概率分配函數：把D的任意一個子集A都映射為[0,1]上的一個數M（A）。

AD，AD時，M（A）：對相應命題A的精確信任度。（3）概率分配函數與概率不同。

例如，設

A={紅}，

M（A）=0.3：命題“x是紅色”的信任度是0.3。

設D={紅，黃，藍}M（{紅}）=0.3，

M（{黃}）=0，

M（{藍}）=0.1，

M（{紅，黃}）=0.2，M（{紅，藍}）=0.2，M（{黃，藍}）=0.1，M（{紅，黃，藍}）=0.1，M（Φ）=0但：M（{紅}）+M（{黃}）+M（{藍}）=0.4設D={紅，黃，藍}則其子集個數23＝8，具體為：A={紅}，

A={黃}，

A={藍}，

A={紅，黃}，A={紅，藍}，

A={黃，藍}，A={紅，黃，藍}，A={}4.8證據理論信任函數

2023/1/13人工智能導論-劉珊40

設D={紅，黃，藍}M（{紅}）=0.3，

M（{黃}）=0，M（{紅，黃}）=0.2,由信任函數及概率分配函數的定義推出：4.8證據理論似然函數似然函數定義為Pl：2D[0,1]且pl(A)=1-Bel(A)，AD2023/1/13人工智能導論-劉珊41

設D={紅，黃，藍}M({紅})=0.3，M({黃})=0，M({紅，黃})=0.2，Bel({紅,黃})=M({紅})+M({黃})+M({紅,黃})=0.5Pl({藍})=1-Bel({藍})=1-Bel({紅,黃})=1-0.5=0.5

4.8證據理論信任函數與似然函數的關系Pl(A)Bel(A)Bel(A)：對A為真的信任程度。Pl(A)：對A為非假的信任程度。A(Bel(A),Pl(A))：對A信任程度的下限與上限。例如{紅}：[0.3,0.9]表示{紅}的精確信任度為0.3，不可駁斥部分為0.9典型值A[0,1]：對A一無所知A[0,0]：說明A為假A[1,1]：說明A為真2023/1/13人工智能導論-劉珊424.8證據理論概率分配函數的正交和2023/1/13人工智能導論-劉珊43如果K0，則正交和M也是一個概率分配函數；如果K=0，則不存在正交和M，即沒有可能存在概率函數，稱M1與M2矛盾。4.8證據理論設M1和M2是兩個概率分配函數，則其正交和定義為概率分配函數的正交和設M1,M2,…,

Mn是n個概率分配函數，則其正交和M=M1

M2

…

Mn為M()=0,2023/1/13人工智能導論-劉珊44其中：4.8證據理論實例設D={黑，白}，且2023/1/13人工智能導論-劉珊45則，4.8證據理論實例同理可得：2023/1/13人工智能導論-劉珊46組合后得到的概率分配函數：4.8證據理論一類特殊的概率分配函數設D={s1,s2,…,sn}，M為定義在2D上的概率分配函數，且M滿足：M({si})≥0,對任給si

?D∑i=1nM({si})≤1M(D)=1-∑i=1nM({si})當A?D，且A的元素多于1個或沒有元素，M(A)=0。2023/1/13人工智能導論-劉珊474.8證據理論一類特殊的概率分配函數對這類概率分配函數，其信任函數和似然函數的性質為：Bel(A)=∑si?AM({si})Bel(D)

=

∑si?DM({si})+M(D)=1Pl(A)=1-Bel(?A)=1-∑si??AM({si})=1-∑si?DM({si})+∑si?AM({si})=M(D)+Bel(A)Pl(D)=1-Bel(?D)=12023/1/13人工智能導論-劉珊484.8證據理論類概率函數設D為有限域，對任何命題A?D，其類概率函數定義為f(A)=Bel(A)+|A|/|D|

[Pl(A)-Bel(A)]其中|A|和|D|表示A和D中的元素個數。類概率函數的性質∑si?Df({si})=1對任何A?D，有Bel(A)≤f(A)≤Pl(A)對任何A?D，有f(?A)=1-f(A)則，f(Φ)=0；f(D)=1；對任何A?D，0≤f(A)≤12023/1/13人工智能導論-劉珊494.8證據理論規(guī)則不確定性的表示D-S理論中，不確定性規(guī)則的表示形式為ifEthenH={h1,h2,…,hn}CF={c1,c2,…,cn}其中：E為前提條件，可以是簡單條件，也可以是復合條件；H是結論，用樣本空間的子集表示，h1,h2,…,hn是該子集的元素；CF是可信度因子，用集合的方式表示。c1,c2,…,cn用來表示h1,h2,…,hn的可信度。2023/1/13人工智能導論-劉珊504.8證據理論證據不確定性的表示證據E的不確定性由證據的類概率函數給出：

CER(E)=f(E)2023/1/13人工智能導論-劉珊514.8證據理論不確定性的更新設有知識ifEthenH={h1,h2,…,hn}CF={c1,c