【正文】 （ 2）變量消元算法 ? 消除重復(fù)計(jì)算，提高枚舉算法的效率 ? 保存中間結(jié)果，以備多次使用 ? 從右到左（在樹(shù)結(jié)構(gòu)中為自底向上）的次序計(jì)算 BN的計(jì)算公式 ? 算法過(guò)程：參見(jiàn) 《 人工智能：一種現(xiàn)代方法 》 中的第 14章 89 貝葉斯信念網(wǎng)的近似推理 ? 對(duì)任意貝葉斯網(wǎng)絡(luò)的概率的確切推理已經(jīng)知道是一個(gè) NP難題 ? Monte Carlo方法提供了一種近似的結(jié)果，通過(guò)對(duì)未觀察到的變量進(jìn)行隨機(jī)采樣 ? 理論上，即使是貝葉斯網(wǎng)絡(luò)中的近似推理也可能是 NP難題 ? 實(shí)踐中許多情況下近似的方法被證明是有效的 90 學(xué)習(xí)貝葉斯信念網(wǎng) ? 從訓(xùn)練數(shù)據(jù)中學(xué)到貝葉斯信念網(wǎng)，有多種討論的框架： – 網(wǎng)絡(luò)結(jié)構(gòu)可以預(yù)先給出，或由訓(xùn)練數(shù)據(jù)中得到 – 所有的網(wǎng)絡(luò)變量可以直接從每個(gè)訓(xùn)練樣例中觀察到，或某些變量不能觀察到 ? 如果網(wǎng)絡(luò)結(jié)構(gòu)已知且變量可以從訓(xùn)練樣例中完全獲得，那么得到條件概率表就比較簡(jiǎn)單 ? 如果網(wǎng)絡(luò)結(jié)構(gòu)已知，但只有一部分變量值能在數(shù)據(jù)中觀察到，學(xué)習(xí)問(wèn)題就困難多了。 ? P(X|e) = ?P(X,e) = ??yP(X,e,y) 而 P(X,e,y)可寫(xiě)成條件概率乘積的形式。 ? 一般情況下是很困難的，原因 – 不是所有的 CPT表都能夠得到 – 網(wǎng)絡(luò)結(jié)構(gòu)大且復(fù)雜 – NPhard推理 ? 我們要做的是，將問(wèn)題正確的表示為合理的網(wǎng)絡(luò)形式，選用適合的算法。如：患?。ㄎ鼰?，肺癌） ? 在某些場(chǎng)合下有有效的推理方法。 U1 Um X Z1j Znj Y1 Yn 貝葉斯網(wǎng)絡(luò) ? 建立貝葉斯網(wǎng)絡(luò)的目的 – 有了網(wǎng)絡(luò)。 參數(shù)復(fù)雜性問(wèn)題 ???niiin YP ar e nt syPyyP11 ))(|(),...,(貝葉斯信念網(wǎng)表示的聯(lián)合概率計(jì)算公式： 全聯(lián)合概率計(jì)算公式： ? ? ?? ni iin yyyPyyP 1 111 ),|(),( ??參數(shù)復(fù)雜性問(wèn)題 ? 5個(gè)二元變量 ? 全聯(lián)合概率計(jì)算公式共 32個(gè)參數(shù) ,需定義 31個(gè)參數(shù) . ? BBN的聯(lián)合概率計(jì)算公式共 20個(gè)參數(shù) ,需定義 10個(gè)參數(shù) 參數(shù)復(fù)雜性問(wèn)題 ? 假設(shè)節(jié)點(diǎn)數(shù) n=30, 每節(jié)點(diǎn)有 5個(gè)父節(jié)點(diǎn)，則BN需 30x25=960個(gè)數(shù)據(jù)，而全聯(lián)合概率分布需要 230= 10億個(gè)！ 貝葉斯網(wǎng)絡(luò)的構(gòu)造原則： ? 首先，添加“ 根本原因 ”節(jié)點(diǎn) ? 然后，加入受它們 直接影響的變量 ? 依次類(lèi)推，直到 葉節(jié)點(diǎn) ，即對(duì)其它變量沒(méi)有直接因果影響的節(jié)點(diǎn) ? 兩節(jié)點(diǎn)間的有向邊的取舍原則：更高精度概率的重要性與指定額外信息的代價(jià)的折衷 ? “因果模型”比“診斷模型”需要更少的數(shù)據(jù)，且這些數(shù)據(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) —— 馬爾可夫覆蓋 (Markov blanket)，這個(gè)節(jié)點(diǎn)和網(wǎng)絡(luò)中 的所有其它節(jié)點(diǎn)是條件獨(dú)立的 【 說(shuō)明 】 ： 給定節(jié)點(diǎn) X的父節(jié)點(diǎn) U1... Um，節(jié)點(diǎn) X與它的非后代節(jié)點(diǎn)（即 Zij）是條件獨(dú)立的。 69 貝葉斯信念網(wǎng)的表示（ 2） ? 貝葉斯信念網(wǎng)表示的全聯(lián)合概率計(jì)算公式如下： ???niiin YP ar e nt syPyyP11 ))(|(),...,(貝葉斯信念網(wǎng)的語(yǔ)義公式計(jì)算示例： ? 試計(jì)算：報(bào)警器響了，但既沒(méi)有盜賊闖入，也沒(méi)有發(fā)生地震，同時(shí) John和 Mary都給你打電話(huà)的概率。 在應(yīng)用證據(jù)理論時(shí)需要注意的是合理地劃分辨別框及有效地控制計(jì)算的復(fù)雜性等 。 該方法的基本思想是把 D劃分為若干組 ， 每組只包含相互排斥的元素 ， 稱(chēng)為一個(gè)辨別框 ， 求解問(wèn)題時(shí) ， 只需在各自的辨別框上考慮概率分配的影響 。 另外 ，證據(jù)理論要求 D中的元素是互斥的 ， 這一點(diǎn)在許多應(yīng)用領(lǐng)域也難以做到 。 1 2 1 2 1 2 1 2( ) , ( ) , 20 , { , }( , ) ( , ) ,C E R A C E R A U A A B b b c c? ? ? ? ? ? ? 解 先計(jì)算組合證據(jù) 的正確性 再計(jì)算結(jié)論的分配函數(shù) M({b1},{b2})= ( , )=(,) 12AA?1 2 1 2( ) m i n{ ( ) , ( ) } m i n{ , } ER A A C ER A C ER A? ? ? ? 證據(jù)理論 例子 得到結(jié)論的信任函數(shù) 隨之有 而對(duì)于 D的其他子集的 M值均賦予 0。如此反復(fù)運(yùn)用該過(guò)程，就可推出最終結(jié)論及它的確定性。 最后求出 12 nM M M M? ? ? ?12, , , nM M M( ) , ( ) ( )Be l H Pl H f H及11( ) ( { })( ) 1 ( )( ) ( ) [ ( ) ( ) ]niB e l H M hP l H B e l HHf H B e l H P l H B e l HD??? ? ?? ? ? ??( ) ( )HB e l H M DD? ? ? 證據(jù)理論 4）按如下公式求出 H的確定性 CER(H) CER (H)=MD(H|E) f(H) 其中， MD(H|E)是知識(shí)的前提條件與相應(yīng)證據(jù) E的匹配度，定義為 MD(H|E) 這樣，就對(duì)一條知識(shí)或者多條有相同結(jié)論的知識(shí)求出了結(jié)論的確定性。 首先分別對(duì)每一條知識(shí)求出概率分配函數(shù)： 然后再用公式 對(duì) 求正交和，從而得到 H的概率分配函數(shù) M。 對(duì)于上述知識(shí)， H的概率分配函數(shù)規(guī)定為 這樣便求得 M(H)。 CER(E)的取值范圍為 。 （ 3） CF 是可信度因子，用集合形式表示，其中，用來(lái)指出 的可信度， 與 一一對(duì)應(yīng) , 應(yīng)滿(mǎn)足如下條件 12{ , , , }nH h h h? 12, , , nc c c12, , , nh h hic( 1 , 2 , , )ih i n?ic ih ic0 ( 1 , 2 , , )ic i n?? ???niic11 證據(jù)理論 證據(jù)的不確定性的表示 不確定性證據(jù) E的確定性用 CER(E)表示。 E既可以是簡(jiǎn)單 條件，也可以是用 AND或 OR連接起來(lái)的復(fù)合條件。( 2 ) ( ) 1 。 定義 命題 A的類(lèi)概率函數(shù)為 其中，分別是 A及 D中元素的個(gè)數(shù)。 12, nM M M 設(shè) 是 n個(gè)概率分配函數(shù)，則其正交 和 為 其中， 。 如果 ,則正交和 M也是一個(gè)概率分配函數(shù)； 如果 K＝ 0,則不存在正交和 M，稱(chēng) 矛盾。例如，對(duì)于樣本空間 ，從不同的來(lái)源可分別得到如下兩個(gè)概率分配函數(shù)： 此時(shí)需要對(duì)它們進(jìn)行組合，德普斯特提出的組合方法可對(duì)這兩個(gè)概率分配函數(shù)進(jìn)行正交和運(yùn)算。 定義 似然函數(shù) : ,且 （ ） 命題 A的似然函數(shù)值就是所有與 A相交的子集的基本概率分配函數(shù)之和，用來(lái)表示不否定 A的信任度。 Bel函數(shù)又稱(chēng)為下限函數(shù)，以 Bel（ A）表示對(duì)命題 A為真的信任程度。 定義 設(shè)函數(shù) M： ,且滿(mǎn)足 則稱(chēng) M是 上的概率分配函數(shù)， M(A)稱(chēng)為 A的基本概率函數(shù)（ Function of Basic Probability Assignment），即對(duì)于樣本空間 D的任一子集都分配一個(gè)概率值。 證據(jù)理論中，為了描述和處理不確定性，引入了概率分 配函數(shù)、信任函數(shù)及似然函數(shù)等概念。 設(shè) D是變量 x所有可能 取值的集合 ， 且 D中的元素是互斥的 ， 在任一時(shí)刻 x都取 D中 的某一個(gè)元素為值 ， 則稱(chēng) D為 x的樣本空間 。 CF( )=，而 的可信度為初始制定的 1。 由題意得到推理網(wǎng)絡(luò)如下圖所示。 初始證據(jù)為 A1,A2,A3的可信度 CF均設(shè)為 1， 即 ,CF(A1)= CF(A2)= CF(A3)=1,對(duì) B1,B2一無(wú)所知 , 求 CF(B1)和 CF(B2)。 可信度方法 可信度方法 CF模型 CF模型是基于可信度表示的不確定性推理的基本方法， 其他可信度方法都是在此基礎(chǔ)上發(fā)展起來(lái)的。但是，對(duì)于某一具體領(lǐng)域而言，由于該領(lǐng)域的專(zhuān)家具有豐富的專(zhuān)業(yè)知識(shí)和實(shí)踐經(jīng)驗(yàn)，要給出該領(lǐng)域知識(shí)的可信度還是完全有可能的。 可信度方法 可信度的概念 在以產(chǎn)生式作為知識(shí)表示的專(zhuān)家系統(tǒng) MYCIN中 ， 用以度量知識(shí)和證據(jù)的不確定性 。 這里的相信程度就是我們說(shuō)的可信度。 主觀 Bayes方法 所謂可信度就是在實(shí)際生活中根據(jù)自己的經(jīng)驗(yàn)對(duì)某一事 物或現(xiàn)象進(jìn)行觀察，判斷相信其為真得程度。 ?它的主要缺點(diǎn)如下 （ 1）要求領(lǐng)域?qū)＜以诮o出知識(shí)的同時(shí)給出 H的先驗(yàn)概率P(H)，這是比較困難的。另外，由其推理過(guò)程可以看出，它確實(shí)實(shí)現(xiàn)了不確定性的逐級(jí)傳遞。另外，它既用 LS指出了證據(jù) E對(duì)結(jié)論 H的支持程度，又用 LN指出了 E對(duì) H的必要性程度，這就比較全面地反映了證據(jù)與結(jié)論間因果關(guān)系，符合現(xiàn)實(shí)世界中某些領(lǐng)域的實(shí)際情況，使推出的結(jié)論有較 準(zhǔn)確的確定性。 3） A對(duì) B1沒(méi)影響， P(B1|A1