讀DaphneKoller的“概率圖模型”

1、結(jié)構(gòu)結(jié)構(gòu)+平均平均 -讀讀Daphne Koller的的“概率圖模型概率圖模型”王玨王玨中國(guó)科學(xué)院自動(dòng)化研究所中國(guó)科學(xué)院自動(dòng)化研究所模式識(shí)別國(guó)家重點(diǎn)實(shí)驗(yàn)室模式識(shí)別國(guó)家重點(diǎn)實(shí)驗(yàn)室2011年年4月月7日日一、引子一、引子二、表示二、表示三、推斷三、推斷四、學(xué)習(xí)四、學(xué)習(xí)五、結(jié)束語(yǔ)五、結(jié)束語(yǔ)講座分為五個(gè)部分，開頭一個(gè)引講座分為五個(gè)部分，開頭一個(gè)引子，說明講座的動(dòng)機(jī)，最后一個(gè)子，說明講座的動(dòng)機(jī)，最后一個(gè)結(jié)束語(yǔ)，從歷史發(fā)展的角度討論結(jié)束語(yǔ)，從歷史發(fā)展的角度討論關(guān)注概率圖模型的原因，中間三關(guān)注概率圖模型的原因，中間三個(gè)部分，介紹個(gè)部分，介紹Koller這本書的三這本書的三個(gè)部分：表示個(gè)部分：表示(repre

2、sentation)、推斷推斷(inference)和學(xué)習(xí)和學(xué)習(xí)(learning)的基本思想和主要方法。的基本思想和主要方法。標(biāo)題，標(biāo)題，AI與與ML采用采用“結(jié)構(gòu)結(jié)構(gòu)+平均平均”作為標(biāo)題，沒有使用作為標(biāo)題，沒有使用“結(jié)構(gòu)結(jié)構(gòu)+統(tǒng)計(jì)統(tǒng)計(jì)”或或者者“人工智能人工智能+統(tǒng)計(jì)學(xué)統(tǒng)計(jì)學(xué)”，或，或“圖圖+概率概率”。“結(jié)構(gòu)結(jié)構(gòu)”與與“統(tǒng)計(jì)統(tǒng)計(jì)”似乎不具有同等地位，似乎不具有同等地位，“人工智能人工智能”與與“統(tǒng)計(jì)學(xué)統(tǒng)計(jì)學(xué)”水火不相容，水火不相容，“圖圖+概率概率”直觀確切，其本質(zhì)對(duì)應(yīng)直觀確切，其本質(zhì)對(duì)應(yīng)“結(jié)構(gòu)結(jié)構(gòu)”與與“平均平均”，對(duì)中文，對(duì)中文，“結(jié)構(gòu)結(jié)構(gòu)+平均平均”更美一些。更美一些。思考：人工智

3、能思考：人工智能(AI)與統(tǒng)計(jì)機(jī)器學(xué)習(xí)與統(tǒng)計(jì)機(jī)器學(xué)習(xí)(ML)是否存在一個(gè)結(jié)是否存在一個(gè)結(jié)合點(diǎn)。但是，在理念上，合點(diǎn)。但是，在理念上，AI強(qiáng)調(diào)因果率強(qiáng)調(diào)因果率(結(jié)構(gòu)結(jié)構(gòu))，不惜對(duì)排中，不惜對(duì)排中率破缺，統(tǒng)計(jì)方法強(qiáng)調(diào)排中率，不惜對(duì)因果率破缺，兩者率破缺，統(tǒng)計(jì)方法強(qiáng)調(diào)排中率，不惜對(duì)因果率破缺，兩者水火不相容。鑒于兩者均已遇到根本性困難，有沒有一種水火不相容。鑒于兩者均已遇到根本性困難，有沒有一種折衷的理念。折衷的理念。Koller這本書應(yīng)該是這種折中的理念。這本書應(yīng)該是這種折中的理念。極端的例子極端的例子對(duì)任意三角形識(shí)別對(duì)任意三角形識(shí)別(最簡(jiǎn)單的圖形最簡(jiǎn)單的圖形)，如果采用句法，如果采用句法(單純結(jié)

4、單純結(jié)構(gòu)構(gòu))方法，需要方法，需要“上下文敏感文法上下文敏感文法”描述，沒有描述，沒有Parsing算法。算法。成都地區(qū)暴雨預(yù)報(bào)，十年的數(shù)據(jù)。神經(jīng)網(wǎng)絡(luò)成都地區(qū)暴雨預(yù)報(bào)，十年的數(shù)據(jù)。神經(jīng)網(wǎng)絡(luò)(平均平均)，獲得模，獲得模型，驗(yàn)證，誤報(bào)型，驗(yàn)證，誤報(bào)5%。誤報(bào)中有一個(gè)樣本，預(yù)報(bào)大暴雨，實(shí)。誤報(bào)中有一個(gè)樣本，預(yù)報(bào)大暴雨，實(shí)際是晴天，各種因素均說明有暴雨，際是晴天，各種因素均說明有暴雨，但是但是，單純結(jié)構(gòu)或單純平均需要滿足嚴(yán)厲的條件，否則無(wú)效單純結(jié)構(gòu)或單純平均需要滿足嚴(yán)厲的條件，否則無(wú)效濕度指標(biāo)低，濕度指標(biāo)低，沒有水沒有水！當(dāng)然沒有暴雨！平均將這個(gè)重要指！當(dāng)然沒有暴雨！平均將這個(gè)重要指標(biāo)與其他指標(biāo)一起平均

5、了。小學(xué)生不會(huì)犯的差錯(cuò)標(biāo)與其他指標(biāo)一起平均了。小學(xué)生不會(huì)犯的差錯(cuò)(80年代末年代末)書中書中“學(xué)生學(xué)生”的例子的例子課程課程(D:難難=0，易，易=1) 智力智力(I: 聰明聰明=0，一般，一般=1)考試考試(G: A, B, C) SAT (S: 好好=0，壞，壞=1)推薦推薦(L: 強(qiáng)強(qiáng)=0，弱，弱=1)。 以推薦作為查詢變量以推薦作為查詢變量(L)If D=0 G=A thenL=0If I=0 G=A thenL=0If D=1 I=1 G=A then L=1問題是：?jiǎn)栴}是：If D=1 I=0 G=A then L=?這就是人工智能遇到的難題！無(wú)這就是人工智能遇到的難題！無(wú)法泛化！

6、法泛化！不同查詢，不同規(guī)則！不同查詢，不同規(guī)則！構(gòu)造一個(gè)函數(shù)：構(gòu)造一個(gè)函數(shù)：L = f ( ,D,I,G,S)觀察一組學(xué)生，獲得樣本集。基函觀察一組學(xué)生，獲得樣本集。基函數(shù)數(shù)L = 1D + 2I + 3G + 4S設(shè)計(jì)算法，確定設(shè)計(jì)算法，確定 ，獲得模型。，獲得模型。問題：模型為真需要多少樣本，對(duì)問題：模型為真需要多少樣本，對(duì)高維數(shù)據(jù)，不知道！模型不可解釋高維數(shù)據(jù)，不知道！模型不可解釋這就是統(tǒng)計(jì)機(jī)器學(xué)習(xí)遇到的難題。這就是統(tǒng)計(jì)機(jī)器學(xué)習(xí)遇到的難題。可以泛化，可以泛化，精度未知精度未知，不可解釋。，不可解釋。根據(jù)觀察和專家經(jīng)驗(yàn)，構(gòu)造規(guī)則集根據(jù)觀察和專家經(jīng)驗(yàn)，構(gòu)造規(guī)則集問題本身的語(yǔ)義問題本身的語(yǔ)義課

7、程難易程度與考試分?jǐn)?shù)有關(guān)。課程難易程度與考試分?jǐn)?shù)有關(guān)。學(xué)生智力與考試成績(jī)有關(guān)。學(xué)生智力與考試成績(jī)有關(guān)。學(xué)生智力與學(xué)生智力與SAT有關(guān)。有關(guān)。考試成績(jī)與考試成績(jī)與“推薦信強(qiáng)弱推薦信強(qiáng)弱”有關(guān)。有關(guān)。AI方案充分考慮了這種語(yǔ)義，方案充分考慮了這種語(yǔ)義，但是，將這種語(yǔ)義強(qiáng)化到唯但是，將這種語(yǔ)義強(qiáng)化到唯一表示程度一表示程度(當(dāng)且僅當(dāng)當(dāng)且僅當(dāng))，缺，缺失靈活性。失靈活性。統(tǒng)計(jì)學(xué)習(xí)方案完全不考慮這統(tǒng)計(jì)學(xué)習(xí)方案完全不考慮這種語(yǔ)義，盡管具有靈活性種語(yǔ)義，盡管具有靈活性(泛泛化化)，但是，需要充分的觀察，但是，需要充分的觀察樣本。樣本。兩者的共同代價(jià)是：維數(shù)災(zāi)難。前者，需要考慮所有可能兩者的共同代價(jià)是：維數(shù)災(zāi)難

8、。前者，需要考慮所有可能的組合的規(guī)則集合，后者，需要考慮充分的樣本集合。的組合的規(guī)則集合，后者，需要考慮充分的樣本集合。這種語(yǔ)義可以根據(jù)統(tǒng)這種語(yǔ)義可以根據(jù)統(tǒng)計(jì)分布獲得，也可以計(jì)分布獲得，也可以根據(jù)常識(shí)經(jīng)驗(yàn)獲得。根據(jù)常識(shí)經(jīng)驗(yàn)獲得。ML強(qiáng)調(diào)給定變量集合張成的空間上計(jì)算平均的方法，抹煞強(qiáng)調(diào)給定變量集合張成的空間上計(jì)算平均的方法，抹煞變量之間的結(jié)構(gòu)；變量之間的結(jié)構(gòu)；AI強(qiáng)調(diào)變量的獨(dú)立性，忽視變量之間的條強(qiáng)調(diào)變量的獨(dú)立性，忽視變量之間的條件獨(dú)立關(guān)系。是否可將變量子集件獨(dú)立關(guān)系。是否可將變量子集(甚至一個(gè)變量甚至一個(gè)變量)的局部分布，的局部分布，根據(jù)變量之間內(nèi)在的結(jié)構(gòu)，轉(zhuǎn)變?yōu)閷?duì)變量集合整體的聯(lián)合分根據(jù)變量

9、之間內(nèi)在的結(jié)構(gòu)，轉(zhuǎn)變?yōu)閷?duì)變量集合整體的聯(lián)合分布。這樣，就可以既顧及了變量之間存在結(jié)構(gòu)，又考慮了平布。這樣，就可以既顧及了變量之間存在結(jié)構(gòu)，又考慮了平均的必要性。概率圖模型應(yīng)該是一個(gè)這樣的方案。均的必要性。概率圖模型應(yīng)該是一個(gè)這樣的方案。這本著作包羅萬(wàn)象這本著作包羅萬(wàn)象(1200頁(yè)頁(yè))，這個(gè)講座是根據(jù)，這個(gè)講座是根據(jù)我個(gè)人偏好我個(gè)人偏好，抽出，抽出最基本的思考、研究方法，以及實(shí)現(xiàn)這個(gè)思考的基本理論。而書最基本的思考、研究方法，以及實(shí)現(xiàn)這個(gè)思考的基本理論。而書中羅列的大量具體的方法則認(rèn)為：不是解決問題的唯一途徑，而中羅列的大量具體的方法則認(rèn)為：不是解決問題的唯一途徑，而是存在的問題。這本著作數(shù)學(xué)符

10、號(hào)體系繁雜，談不上是存在的問題。這本著作數(shù)學(xué)符號(hào)體系繁雜，談不上“優(yōu)美優(yōu)美”。著作有四個(gè)部分：表示、推斷、學(xué)習(xí)和著作有四個(gè)部分：表示、推斷、學(xué)習(xí)和action and decision，我們，我們只討論前三個(gè)部分。只討論前三個(gè)部分。致謝致謝在我準(zhǔn)備這個(gè)在我準(zhǔn)備這個(gè)“筆記筆記”之前，王飛躍、宗成慶和我的之前，王飛躍、宗成慶和我的12個(gè)個(gè)學(xué)生參加了我們的一個(gè)討論班，大家一起通讀了學(xué)生參加了我們的一個(gè)討論班，大家一起通讀了Koller的這的這本書。這個(gè)討論班對(duì)我準(zhǔn)備這個(gè)本書。這個(gè)討論班對(duì)我準(zhǔn)備這個(gè)“筆記筆記”有很大的幫助，有很大的幫助，這些學(xué)生是：王飛躍教授的學(xué)生，顧原、周建英、陳誠(chéng)和這些學(xué)生是：王

11、飛躍教授的學(xué)生，顧原、周建英、陳誠(chéng)和李泊；宗成慶教授的學(xué)生，莊濤和夏睿；我的學(xué)生韓彥軍、李泊；宗成慶教授的學(xué)生，莊濤和夏睿；我的學(xué)生韓彥軍、馬奎俊、孫正雅、黃羿衡和吳蕾，以及吳高巍博士。在此馬奎俊、孫正雅、黃羿衡和吳蕾，以及吳高巍博士。在此表示謝意。特別感謝韓素青和韓彥軍幫助我檢查和修改了表示謝意。特別感謝韓素青和韓彥軍幫助我檢查和修改了全部全部ppt。一、引子一、引子二、表示二、表示三、推斷三、推斷四、學(xué)習(xí)四、學(xué)習(xí)五、結(jié)束語(yǔ)五、結(jié)束語(yǔ)為什么為什么“表示表示”是一個(gè)專題是一個(gè)專題統(tǒng)計(jì)機(jī)器學(xué)習(xí)的表示統(tǒng)計(jì)機(jī)器學(xué)習(xí)的表示-基函數(shù)。確定基函數(shù)，沒有表示問題。基函數(shù)。確定基函數(shù)，沒有表示問題。給定變量集

12、，完全圖或給定變量集，完全圖或完全不連接，完全不連接，平凡平凡！圖的結(jié)構(gòu)圖的結(jié)構(gòu)(不完全連接不完全連接)統(tǒng)計(jì)上條件獨(dú)立統(tǒng)計(jì)上條件獨(dú)立-因子因子條件獨(dú)立的集合條件獨(dú)立的集合(I-map)成為圖結(jié)構(gòu)的表征。成為圖結(jié)構(gòu)的表征。聯(lián)合分布與邊緣分布是圖結(jié)構(gòu)的概率描述聯(lián)合分布與邊緣分布是圖結(jié)構(gòu)的概率描述ABCDEBACDE不完全圖不完全圖-條件獨(dú)立條件獨(dú)立,兩種表示兩種表示。非平凡。非平凡概率圖模型概率圖模型Bayes網(wǎng)網(wǎng)(Bayesian Network, BN)，有向圖，有向圖Markov網(wǎng)網(wǎng)(Markov Network, MN)，無(wú)向圖，無(wú)向圖各種局部概率模型各種局部概率模型(CPD)從聯(lián)合分布構(gòu)

13、造從聯(lián)合分布構(gòu)造Bayes網(wǎng)網(wǎng)(BN)學(xué)生問題，五個(gè)變量排成一個(gè)任意的序：學(xué)生問題，五個(gè)變量排成一個(gè)任意的序：I, D, G, L, S，其聯(lián)合分布其聯(lián)合分布(左左)，對(duì)應(yīng)的完全，對(duì)應(yīng)的完全BN(右右)：P(I, D, G, S, L) =difficultyIntelligenceGradeSATLetterP(I)P(S | I, D, G, L)P(D | I)P(G | I, D)P(L | I, D, G)構(gòu)造構(gòu)造Bayes網(wǎng)網(wǎng)因子因子完全圖完全圖節(jié)點(diǎn)節(jié)點(diǎn)G上的條件概率分布上的條件概率分布(CPD)圖上的獨(dú)立性圖上的獨(dú)立性P(I,D,G,L,S) = P(I)P(D | I)P(G

14、| I, D)P(L | I, D, G)P(S | I, D, G, L)P(I)P(D)I與與D相互獨(dú)立相互獨(dú)立L只與只與G有關(guān)，與其他獨(dú)立有關(guān)，與其他獨(dú)立P(G | I, D)P(L | G)S只與只與I有關(guān)，與其他獨(dú)立有關(guān)，與其他獨(dú)立P(S | I)difficultyIntelligenceGradeSATLetter分布分布P中的條件獨(dú)立中的條件獨(dú)立P(X)是隨機(jī)變量集是隨機(jī)變量集X中所有變量的聯(lián)合分布，中所有變量的聯(lián)合分布，P(Xi | Z)是是Xi關(guān)于關(guān)于Z的條件分布。的條件分布。Z X, Xi X且且Xi Z。條件獨(dú)立：如果兩個(gè)變量條件獨(dú)立：如果兩個(gè)變量Xi, Xj X，對(duì)條

15、件，對(duì)條件Z獨(dú)立，獨(dú)立，iff P(Xi Xj | Z) = P(Xi | Z) P(Xj | Z)滿足條件獨(dú)立的所有斷言滿足條件獨(dú)立的所有斷言(Xi Xj | Z)，構(gòu)成一個(gè)集合，構(gòu)成一個(gè)集合，稱為關(guān)于稱為關(guān)于P的的I-map，記為，記為I(P)。對(duì)圖對(duì)圖G，所有彼此不相連的節(jié)點(diǎn)對(duì)集合為，所有彼此不相連的節(jié)點(diǎn)對(duì)集合為I(G)。如果如果I(G) I(P)，G是一個(gè)對(duì)獨(dú)立集合是一個(gè)對(duì)獨(dú)立集合I(P)的的I-map。BN上的獨(dú)立上的獨(dú)立YZXYZX (a) (d)絕對(duì)獨(dú)立絕對(duì)獨(dú)立(X Z), (d)。YZX(c)YXZ (b)YZX (e)復(fù)雜的圖可以考慮為由一些三個(gè)節(jié)點(diǎn)簡(jiǎn)單圖構(gòu)成，令復(fù)雜的圖可以

16、考慮為由一些三個(gè)節(jié)點(diǎn)簡(jiǎn)單圖構(gòu)成，令X,Y與與Z三個(gè)節(jié)點(diǎn)三個(gè)節(jié)點(diǎn)學(xué)生例子：學(xué)生例子：X(智力智力)，Z(推薦信推薦信), Y(成績(jī)成績(jī))。(a)(b): Y未被觀察未被觀察(成績(jī)未知成績(jī)未知)，從，從學(xué)生聰明學(xué)生聰明X，推斷學(xué)生分?jǐn)?shù)高，推斷學(xué)生分?jǐn)?shù)高Y，可能可能強(qiáng)推薦。強(qiáng)推薦。Y已被觀察，已被觀察，Z只與只與Y有關(guān)，與有關(guān)，與X獨(dú)立。獨(dú)立。(X Z | Y)。(c): Y未被觀察，從未被觀察，從X可能可能推斷推斷Z，Y已被觀察，兩者獨(dú)立。已被觀察，兩者獨(dú)立。(e)如何？復(fù)雜！如何？復(fù)雜！v-結(jié)構(gòu)結(jié)構(gòu)(e)XYZ，成績(jī)，成績(jī)Y優(yōu)秀，如果課程優(yōu)秀，如果課程X困困難，可以推出智力難，可以推出智力Z聰明

17、，這樣，聰明，這樣，X與與Z相相關(guān)。如果關(guān)。如果Y未知，未知，X和和Z獨(dú)立。這個(gè)結(jié)構(gòu)稱獨(dú)立。這個(gè)結(jié)構(gòu)稱為為v-結(jié)構(gòu)。結(jié)構(gòu)。G是是BN，存在三個(gè)節(jié)點(diǎn)，存在三個(gè)節(jié)點(diǎn)X, Y, Z。X與與Z是獨(dú)立，則：是獨(dú)立，則：(1)對(duì)對(duì)v-結(jié)構(gòu)，結(jié)構(gòu)，Y與它的全部子孫是未被觀察與它的全部子孫是未被觀察(e)。 (2)Y已被觀察已被觀察(a)(b)(c)。BN最麻煩的是最麻煩的是v-結(jié)構(gòu)，用樹結(jié)構(gòu)近似結(jié)構(gòu)，用樹結(jié)構(gòu)近似BN，就是刪除，就是刪除v-結(jié)構(gòu)。這時(shí)，結(jié)構(gòu)。這時(shí)，BN上，兩個(gè)節(jié)點(diǎn)之間沒有連線，它們一定獨(dú)立。上，兩個(gè)節(jié)點(diǎn)之間沒有連線，它們一定獨(dú)立。YZXBN上判定獨(dú)立的規(guī)則：上判定獨(dú)立的規(guī)則：不滿足條件，只能

18、說不滿足條件，只能說不能保證不能保證獨(dú)立獨(dú)立因子化因子化(factorization)鏈?zhǔn)揭?guī)則：鏈?zhǔn)揭?guī)則：P(D,I,G,S,L) = P(I) P(D) P(G|I, D) P(L|G) P(S|I)滿足條件獨(dú)立假設(shè)的鏈?zhǔn)揭?guī)則一般形式：令滿足條件獨(dú)立假設(shè)的鏈?zhǔn)揭?guī)則一般形式：令PaX是圖是圖G上變上變量量X的所有父結(jié)點(diǎn)，變量集合的聯(lián)合分布可以表示為：的所有父結(jié)點(diǎn)，變量集合的聯(lián)合分布可以表示為：P(X1, , Xn) = P(Xi | PaXi)，其中，其中P(Xi | PaXi)稱為因子。稱為因子。定理：如果圖定理：如果圖G是一個(gè)對(duì)是一個(gè)對(duì)I(P)的的I-map，則，則P可以根據(jù)可以根據(jù)G因子

19、因子化化(注意注意，因子的定義，滿足條件獨(dú)立假設(shè)，因子的定義，滿足條件獨(dú)立假設(shè))。逆定理成立。逆定理成立。注意：注意：僅是因子化，而不是任意僅是因子化，而不是任意P可以使用可以使用G描述。描述。 I(G) I(P)最小最小mapD,I,S,G,LL,S,G,I,DL,D,S,I,G分布的結(jié)構(gòu)，就是將所有分布的結(jié)構(gòu)，就是將所有“獨(dú)立獨(dú)立”的邊移除的圖。的邊移除的圖。最小最小map：令令G是一個(gè)對(duì)是一個(gè)對(duì)I(P)的最小的最小I-map，如果它是對(duì)，如果它是對(duì)I(P)的的I-map，且從且從G上移除任何一個(gè)單邊，它將不再是上移除任何一個(gè)單邊，它將不再是I-map(不在不在I(P)中中)。如果如果G是

20、一個(gè)最小是一個(gè)最小-map，我們似乎可以從中讀出分布的所有結(jié)構(gòu)，我們似乎可以從中讀出分布的所有結(jié)構(gòu)，即，從圖上讀出即，從圖上讀出P的所有獨(dú)立的所有獨(dú)立I(P)。由于圖的生成依賴變量序，由于圖的生成依賴變量序，即，不同的變量序?qū)?dǎo)致不即，不同的變量序?qū)?dǎo)致不同的圖，而不同的圖，可以同的圖，而不同的圖，可以分別具有最小分別具有最小I-map，具有，具有不同的結(jié)構(gòu)。沒有唯一性！不同的結(jié)構(gòu)。沒有唯一性！這個(gè)結(jié)論不成立！這個(gè)結(jié)論不成立！P-map(perfect)P-map：如果：如果I(G)=I(P)，G是一個(gè)是一個(gè)P-map。意義意義：對(duì)任何一個(gè)：對(duì)任何一個(gè)P，是否保證存在一個(gè)，是否保證存在一個(gè)G的

21、的P-mapABDCDBCA對(duì)對(duì)P,(A C|B,D)與與(B D|A,C)。存在使得。存在使得A與與C，B與與D不相連接的不相連接的BN？ 考察考察(B D | A, C)：考察考察(A C|B,D)考察考察(A C | B, D):(A C | B)，ABC是是(b)，如果，如果B已知，成立已知，成立(A C | D)，ADC是是(b)，如果，如果D已知，成立已知，成立(B D | A)，DAB是是(c), A已知已知, 成立。成立。(B D | C)，DCB(v-結(jié)構(gòu)結(jié)構(gòu))，C已知，已知，B與與D不獨(dú)立。不獨(dú)立。(B D|C)不成立。不成立。(B D|A,C)不成立不成立(A C|B,D

22、)成立成立CDA(c類類)，D已知，已知，(A C)，CBA，B已知，已知，(A C)。DCB(v)，C已知，已知，(D B)不成立不成立回答是不能保證回答是不能保證概率圖模型概率圖模型Bayes網(wǎng)網(wǎng)(Bayesian Network, BN)，有向圖，有向圖Markov網(wǎng)網(wǎng)(Markov Network, MN)，無(wú)向圖，無(wú)向圖各種局部概率模型各種局部概率模型(CPD) Markov網(wǎng)網(wǎng)(MN)n盡管盡管MN(MN(無(wú)向圖無(wú)向圖) )以完全子圖的因子為基礎(chǔ)，但以完全子圖的因子為基礎(chǔ)，但是，是，MNMN上的完全子圖依賴條件獨(dú)立，因?yàn)楣?jié)點(diǎn)上的完全子圖依賴條件獨(dú)立，因?yàn)楣?jié)點(diǎn)之間連線的刪除，將直接導(dǎo)

23、致不同的完全子圖。之間連線的刪除，將直接導(dǎo)致不同的完全子圖。n因子是一個(gè)從變量因子是一個(gè)從變量D D子集到正實(shí)數(shù)域子集到正實(shí)數(shù)域 + +上的映上的映射射( (函數(shù)函數(shù)) )。表示聯(lián)合分布與因子表示聯(lián)合分布與因子),.,(1),.,(11nnXXfZXXP)(),.,(1iinXXfDnnXXiiXXnXXfZ,.,.,111)(),.,(D其中其中Di(i=1,k)是是MN H上的完全子圖上的完全子圖(典型是典型是clique)， = 1(D1), , k(Dk)稱為分布稱為分布P 的因子集合。的因子集合。 1(D1), , k(Dk)滿足滿足: P稱為稱為Gibbs分布分布Z稱為劃分函數(shù)稱為

24、劃分函數(shù)與與BN比較，聯(lián)合分布是對(duì)完全子圖勢(shì)能的平均。計(jì)算比較，聯(lián)合分布是對(duì)完全子圖勢(shì)能的平均。計(jì)算Clique(最大完全子圖最大完全子圖)是是NPC。勢(shì)能函數(shù)勢(shì)能函數(shù)CADBI-map與因子化與因子化I-map: I(P)是在是在P中形如中形如 (X Y | Z)獨(dú)立的集合。與獨(dú)立的集合。與BN定義一致。定義一致。MN與與BN一樣，有一個(gè)關(guān)于因子化的定理一樣，有一個(gè)關(guān)于因子化的定理BNMN令令P 0，G是一個(gè)是一個(gè)P的的I-map，iff P可被因子化為：可被因子化為：niiinXPaXPXXP11)(|(),.,(令令P 0，H是一個(gè)是一個(gè)P的的I-map，iff P可被因子化為可被因子化

25、為(完全子圖的完全子圖的勢(shì)函數(shù)勢(shì)函數(shù))：)(1),.,(1iinZXXPD注意：注意：G(或或H)是一個(gè)是一個(gè)P的的I-map就是就是 I(G) I(P)“偶對(duì)偶對(duì)”獨(dú)立獨(dú)立IP(H) = (X Y | U-X,Y) : XY H意味著：不連接的偶對(duì)節(jié)點(diǎn)在其他節(jié)點(diǎn)條件下相互獨(dú)立。意味著：不連接的偶對(duì)節(jié)點(diǎn)在其他節(jié)點(diǎn)條件下相互獨(dú)立。(A D | B,C,E)(B C | A,D,E)(D E | A,B,C)DABCEBlanket獨(dú)立獨(dú)立這是這是“偶對(duì)偶對(duì)”獨(dú)立的推廣。令獨(dú)立的推廣。令B(X)是節(jié)點(diǎn)是節(jié)點(diǎn)X在在H(MN)的所的所有直接鄰居節(jié)點(diǎn)集合。有直接鄰居節(jié)點(diǎn)集合。IL(H) = (X U-X

26、-B(X) | B(X) : X H意味著：意味著：X在所有直接鄰居條件下，與其他節(jié)點(diǎn)獨(dú)立。在所有直接鄰居條件下，與其他節(jié)點(diǎn)獨(dú)立。DABCE對(duì)節(jié)點(diǎn)對(duì)節(jié)點(diǎn)B，B(B)=A, D, E, B與與C是是Blanket獨(dú)立。獨(dú)立。獨(dú)立形式與構(gòu)圖方法獨(dú)立形式與構(gòu)圖方法d-分離：分離：在任意節(jié)點(diǎn)在任意節(jié)點(diǎn)x X與與y Y通路上，存在一個(gè)節(jié)點(diǎn)通路上，存在一個(gè)節(jié)點(diǎn)Z已知已知,在在Z下，其他節(jié)點(diǎn)相互獨(dú)立。下，其他節(jié)點(diǎn)相互獨(dú)立。I(P)BCAD(D A,C | B) 偶對(duì)：不連接的偶對(duì)獨(dú)立，偶對(duì)：不連接的偶對(duì)獨(dú)立，IP(P)IP(H)=(X Y|U-X,Y):X-Y H(A D | B,C,E)DABCEDABC

27、EBlanket：對(duì)：對(duì)X的所有直接鄰居，的所有直接鄰居，X與其與其他節(jié)點(diǎn)獨(dú)立。他節(jié)點(diǎn)獨(dú)立。IL(P)節(jié)點(diǎn)節(jié)點(diǎn)B，B(B)=A, D, E, 與與C是是Blanket獨(dú)立獨(dú)立IP(P) IL(P) I(P)如果如果P 0(正分布正分布)，則則IP(P) = IL(P) = I(P)構(gòu)圖方法：偶對(duì)或構(gòu)圖方法：偶對(duì)或Blanket。構(gòu)成的構(gòu)成的MN，均是唯一最小，均是唯一最小I-map。BN的的Moral圖圖-BNMNG是是BN的的Moral圖是一個(gè)無(wú)向圖，對(duì)兩個(gè)節(jié)點(diǎn)圖是一個(gè)無(wú)向圖，對(duì)兩個(gè)節(jié)點(diǎn)X與與Y滿足：滿足：(1)G中，連接的節(jié)點(diǎn)保持連接。中，連接的節(jié)點(diǎn)保持連接。(2)G中，中，X與與Y有共同

28、子孫，有共同子孫，X與與Y連接。連接。v-結(jié)構(gòu)。結(jié)構(gòu)。 BNBN的的Moral圖圖v-結(jié)構(gòu)結(jié)構(gòu):DKI，如，如果果K未被觀察，未被觀察，D與與I獨(dú)立，獨(dú)立，K以被觀察，以被觀察，D和和I就相關(guān)。相連！就相關(guān)。相連！概率圖模型概率圖模型Bayes網(wǎng)網(wǎng)(Bayesian Network, BN)，有向圖，有向圖Markov網(wǎng)網(wǎng)(Markov Network, MN)，無(wú)向圖，無(wú)向圖各種局部概率模型各種局部概率模型各種各種CPD-局部概率模型局部概率模型討論了網(wǎng)絡(luò)的結(jié)構(gòu)之后，需要關(guān)注附加在節(jié)討論了網(wǎng)絡(luò)的結(jié)構(gòu)之后，需要關(guān)注附加在節(jié)點(diǎn)點(diǎn)(邊邊)上的各種不同描述的條件上的各種不同描述的條件(局部局部)概率

29、概率分布分布(CPD)，如何確定因子。，如何確定因子。滿足：滿足： P(x | paX) = 1。各種各種CPDTabular CPD：使用表描述：使用表描述P(X | PaX)0，判定判定CPD：判定函數(shù)：判定函數(shù).0)(1)|(otherwisepafxpaxPXX)(),.,|(1011ikiikXsigmoidXXyPLogistic CPD：線性高斯線性高斯 CPD：);(),|(12,0,kiuiiuuyaaNyuXp樹與規(guī)則樹與規(guī)則CPD網(wǎng)圖有兩個(gè)要素：其一，網(wǎng)圖的結(jié)構(gòu)，其二，網(wǎng)圖有兩個(gè)要素：其一，網(wǎng)圖的結(jié)構(gòu)，其二，網(wǎng)圖節(jié)點(diǎn)上的條件概率分布。在學(xué)習(xí)時(shí)，這兩網(wǎng)圖節(jié)點(diǎn)上的條件概率分布

30、。在學(xué)習(xí)時(shí)，這兩個(gè)要素將成為學(xué)習(xí)的兩個(gè)方面。結(jié)構(gòu)可以由經(jīng)個(gè)要素將成為學(xué)習(xí)的兩個(gè)方面。結(jié)構(gòu)可以由經(jīng)驗(yàn)來(lái)構(gòu)造。驗(yàn)來(lái)構(gòu)造。對(duì)節(jié)點(diǎn)上的概率分布的學(xué)習(xí)，將基于這些對(duì)節(jié)點(diǎn)上的概率分布的學(xué)習(xí)，將基于這些CPD表示形式，可以理解為學(xué)習(xí)的表示形式，可以理解為學(xué)習(xí)的“基函數(shù)基函數(shù)” (局局部表示部表示)。經(jīng)驗(yàn)知識(shí)可以無(wú)障礙地被引入。經(jīng)驗(yàn)知識(shí)可以無(wú)障礙地被引入。一、引子一、引子二、表示二、表示三、推斷三、推斷四、學(xué)習(xí)四、學(xué)習(xí)五、結(jié)束語(yǔ)五、結(jié)束語(yǔ)查詢問題查詢問題-基于圖的推斷基于圖的推斷概率查詢概率查詢(Y邊緣邊緣)：根據(jù)：根據(jù)給定圖給定圖，計(jì)算，計(jì)算P(Y | E = e)，其中，其中，E是證據(jù)變量，是證據(jù)變量，Y

31、是查詢變量。讀為：在證是查詢變量。讀為：在證據(jù)據(jù)e條件下，條件下，Y出現(xiàn)的概率出現(xiàn)的概率(邊緣概率邊緣概率)。MAP查詢：計(jì)算查詢：計(jì)算MAP(W | e) = arg maxw P(w, e)。其中，。其中，W= -E。讀為：在證據(jù)讀為：在證據(jù)e條件下，在條件下，在W中求出最適合的賦值。中求出最適合的賦值。邊緣邊緣MAP查詢：令查詢：令Z= -Y-E，計(jì)算，計(jì)算MAP(Y | e) = arg maxY P(Y, Z | e)。邊緣查詢邊緣查詢-基于圖的推斷基于圖的推斷邊緣查詢?cè)磉吘壊樵冊(cè)?(1)根據(jù)根據(jù)BN，計(jì)算聯(lián)合分布，計(jì)算聯(lián)合分布P( )= P(Xi|PaXi)(2)計(jì)算在計(jì)算在E

32、下，變量下，變量Y的邊緣的邊緣分布：分布：P(Y | E)= X-Y-EP( )這個(gè)貌似簡(jiǎn)單的任務(wù)，由于計(jì)這個(gè)貌似簡(jiǎn)單的任務(wù)，由于計(jì)算邊緣分布需要取遍非查詢變算邊緣分布需要取遍非查詢變量所有值的組合。十分困難。量所有值的組合。十分困難。學(xué)生聰明學(xué)生聰明i1，不高興，不高興h0，BN下下，查詢學(xué)生工作機(jī)會(huì)。查詢學(xué)生工作機(jī)會(huì)。P(J | i1, h0)。變量集合變量集合: =C,D,I,G,S,L,J,H根據(jù)根據(jù)BN，計(jì)算聯(lián)合分布，計(jì)算聯(lián)合分布P( )。在證據(jù)在證據(jù)E下的下的J的邊緣分布：的邊緣分布：P(J | i1,h0)= WP( ), W= -J-H,I 精確推斷是精確推斷是NPC。無(wú)論無(wú)論

33、BN還是還是MN，其上的推斷是，其上的推斷是NPC問題，問題，計(jì)算近似推斷也不能幸免。計(jì)算近似推斷也不能幸免。近似推斷：圖近似近似推斷：圖近似(本質(zhì)近似本質(zhì)近似)，目標(biāo)近似，目標(biāo)近似和計(jì)算近似和計(jì)算近似(包括算法近似包括算法近似)。概率圖模型推斷研究的焦點(diǎn)是：概率圖模型推斷研究的焦點(diǎn)是：精度和效精度和效率率之間有效之間有效折中折中?！巴茢嗤茢唷眴栴}的解法問題的解法提取公因子，提取公因子，以避免變量的以避免變量的重復(fù)計(jì)算，空重復(fù)計(jì)算，空間換時(shí)間，折間換時(shí)間，折中。動(dòng)態(tài)規(guī)劃中。動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃Clique樹法樹法優(yōu)化法優(yōu)化法以相對(duì)熵為目標(biāo)以相對(duì)熵為目標(biāo)(多多種方法之一種方法之一)，將概，將

34、概率查詢變?yōu)橛屑s束率查詢變?yōu)橛屑s束的優(yōu)化問題，并使的優(yōu)化問題，并使用拉格朗日乘子法用拉格朗日乘子法求解。求解。將無(wú)向圖構(gòu)成將無(wú)向圖構(gòu)成clique樹，采用消息傳播樹，采用消息傳播的方法，計(jì)算查詢的方法，計(jì)算查詢的分布。對(duì)圖上任的分布。對(duì)圖上任何節(jié)點(diǎn)的查詢有效何節(jié)點(diǎn)的查詢有效BN變量消去法變量消去法-計(jì)算計(jì)算P(D)BN網(wǎng)：網(wǎng)：ABCD對(duì)對(duì)D的邊緣分布：的邊緣分布：P(D)= C B A P(A) P(B|A) P(C|B) P(D|C)(1) P(D) = C P(D|C) B P(C|B) A P(A) P(B|A)(2)令令 1(A, B) = P(A) P(B | A)， 1(B) =

35、A 1(A, B)，(消去消去A)(3)計(jì)算計(jì)算 2(B, C) = 1(B) P(C | B)， 2(C) = B 2(B, C) (消去消去B)最后，計(jì)算出最后，計(jì)算出P(D)。ABCD聯(lián)合分布：聯(lián)合分布：P(A,B,C,D)=P(A) P(B|A) P(C|B) P(D|C)MN變量消去法變量消去法-因子邊緣化因子邊緣化對(duì)對(duì)BN，條件概率，條件概率P(X | Y)為因子，在為因子，在MN中，因子中，因子 (X, Y)，盡管，盡管圖結(jié)構(gòu)不同圖結(jié)構(gòu)不同(有向有向 vs. 無(wú)向無(wú)向)，但是，在變量消去法上，沒有本質(zhì)，但是，在變量消去法上，沒有本質(zhì)區(qū)別。稱為因子邊緣化。區(qū)別。稱為因子邊緣化。P(

36、D) = C B A A B C D滿足交換律和結(jié)合律滿足交換律和結(jié)合律 = C B C D ( A A B) = C D ( B C ( A A B)其中，其中，Z: X-Y(A, B, C), 即，從變即，從變量集合中刪除查詢變量的變量集量集合中刪除查詢變量的變量集合，合， 是因子集合。是因子集合。 Z 是和積形式，是和積形式，它是從聯(lián)它是從聯(lián)合分布計(jì)算邊緣分布的基本形式合分布計(jì)算邊緣分布的基本形式“推斷推斷”問題的解法問題的解法提取公因子，提取公因子，以避免變量的以避免變量的重復(fù)計(jì)算，空重復(fù)計(jì)算，空間換時(shí)間，折間換時(shí)間，折中。動(dòng)態(tài)規(guī)劃中。動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃Clique樹法樹法將無(wú)向

37、圖構(gòu)成將無(wú)向圖構(gòu)成clique樹，采用消息傳播樹，采用消息傳播的方法，計(jì)算查詢的方法，計(jì)算查詢的分布。的分布。對(duì)圖上任對(duì)圖上任何節(jié)點(diǎn)的查詢有效何節(jié)點(diǎn)的查詢有效Clique樹樹2與與4有有G，通路上，通路上3, 5也有。也有。2-4構(gòu)成構(gòu)成cluster圖上的一個(gè)通路。圖上的一個(gè)通路。注意，邊是有向的，所有注意，邊是有向的，所有cluster的消的消息流向一個(gè)息流向一個(gè)cluster(7)，計(jì)算出最后結(jié)，計(jì)算出最后結(jié)果，其稱為根。果，其稱為根。滿足滿足RIP的的cluster圖稱圖稱為為clique樹。樹。Ci與與Cj是是cluster圖上一通路的兩個(gè)圖上一通路的兩個(gè)cluster，至，至少存在

38、一個(gè)變量少存在一個(gè)變量X，使得，使得X Ci且且X Cj，如果這，如果這個(gè)通路上的所有個(gè)通路上的所有cluster均將包含均將包含X，稱其滿足，稱其滿足“RIP” (Running Intersection Property) 。一條通路滿足一條通路滿足RIP，將保證這條通路均有某個(gè)，將保證這條通路均有某個(gè)變量，同時(shí)，構(gòu)成的變量，同時(shí)，構(gòu)成的cluster圖與圖與MN具有相同具有相同的連接形式的連接形式(拓?fù)浣Y(jié)構(gòu)拓?fù)浣Y(jié)構(gòu))。Clique樹樹 基于基于clique樹的變量消去法樹的變量消去法(1)C1，根據(jù)，根據(jù) C 1(C, D)，消去，消去C，并將其作為消息，并將其作為消息 12(D)送到送

39、到C2。(2)C2， 2(G,D,I)= 12(D) 2(G,D,I)，消去，消去D， 23(G,I)送到送到C3。(3)C3， 3(G,S,I)= 23(G,I) 3(G,S,I)，消去，消去I， 35(G,I)送到送到C5。(4)C4， H 4(H,G,J)，消去，消去H，送消息，送消息 45(G,J)到到C5。(5)C5， 5(G,J,S,L)= 35(G,S) 45(G,J) 5(G,J,S,L)。 5=P(G,J,L,S)是聯(lián)合是聯(lián)合分布，求分布，求P(J),只需計(jì)只需計(jì)算算 G,L,S 5。 (C)=是初始勢(shì)能。對(duì)是初始勢(shì)能。對(duì)BN， (C, D) = P(C) P(D | C)。

40、注意注意:消息消息 2-3(G,I)= D 2(G,D,I)Clique變量消去算法變量消去算法-消息傳播消息傳播 jajjC:,( )ii jiijikiCSkN bj()rrrrkrk N bC(1)每個(gè)每個(gè)clique Cj賦予初始勢(shì)能賦予初始勢(shì)能(每個(gè)因子對(duì)應(yīng)一個(gè)每個(gè)因子對(duì)應(yīng)一個(gè)clique)(2)計(jì)算計(jì)算Cj的鄰居的鄰居Ci向其傳播消向其傳播消息，總計(jì)為：息，總計(jì)為：(3)計(jì)算根節(jié)點(diǎn)的信度：計(jì)算根節(jié)點(diǎn)的信度：(計(jì)算計(jì)算聯(lián)合分布聯(lián)合分布)方法的優(yōu)點(diǎn)：設(shè)定不同根節(jié)點(diǎn)，可以計(jì)算任意變量的邊緣分布方法的優(yōu)點(diǎn)：設(shè)定不同根節(jié)點(diǎn)，可以計(jì)算任意變量的邊緣分布P(C)。改變根節(jié)點(diǎn)只涉及個(gè)別消息傳播改變

41、根節(jié)點(diǎn)只涉及個(gè)別消息傳播(對(duì)傳入多個(gè)消息的對(duì)傳入多個(gè)消息的clique也是如此也是如此)(4)計(jì)算查詢變量的邊緣分布計(jì)算查詢變量的邊緣分布()()rrrrrCP CC 消元消元步驟步驟 i被校準(zhǔn)的被校準(zhǔn)的Clique樹樹-圖近似圖近似jijiiSCjjjSCiiCC, jijjiiSCjSCijijiCCS,Clique樹的主要問題之一是消息樹的主要問題之一是消息 ik= ki可能不成立?？赡懿怀闪?。滿足右式的兩個(gè)滿足右式的兩個(gè)cluster C1與與C2，稱為被校準(zhǔn)，稱為被校準(zhǔn)Clique樹上所有樹上所有cluster是被校準(zhǔn)，這個(gè)是被校準(zhǔn)，這個(gè)樹稱為被校準(zhǔn)的樹稱為被校準(zhǔn)的clique樹。樹

42、。這樣，連接兩個(gè)節(jié)點(diǎn)的這樣，連接兩個(gè)節(jié)點(diǎn)的信度定義為：信度定義為：被校準(zhǔn)的被校準(zhǔn)的clique樹是聯(lián)合分布的替代表示樹是聯(lián)合分布的替代表示iNbkikii jiijSCjNbkikijiSCiijijijiiijiiCS, ,TTiii vi ji ji jCPS被校準(zhǔn)被校準(zhǔn)clique樹的聯(lián)合分布樹的聯(lián)合分布(Gibbs)：其中其中將將 與與 代入上式代入上式分子分子()iiikiik N bC分母分母jiiji j因?yàn)槊總€(gè)因?yàn)槊總€(gè) 在分子分母只出現(xiàn)一在分子分母只出現(xiàn)一次，可以消去，聯(lián)合分布為各個(gè)次，可以消去，聯(lián)合分布為各個(gè)clique初始能量的乘積。初始能量的乘積。 ()iiiPC意義：意

43、義：Clique樹可以作為聯(lián)合分布樹可以作為聯(lián)合分布的替代表示。但需假設(shè)校準(zhǔn)成立。的替代表示。但需假設(shè)校準(zhǔn)成立。近似！近似！“推斷推斷”問題的解法問題的解法提取公因子，提取公因子，以避免變量的以避免變量的重復(fù)計(jì)算，空重復(fù)計(jì)算，空間換時(shí)間，折間換時(shí)間，折中。動(dòng)態(tài)規(guī)劃中。動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃Clique樹法樹法優(yōu)化法優(yōu)化法將無(wú)向圖構(gòu)成將無(wú)向圖構(gòu)成clique樹，采用消息傳播樹，采用消息傳播的方法，計(jì)算查詢的方法，計(jì)算查詢的分布。對(duì)圖上任的分布。對(duì)圖上任何節(jié)點(diǎn)的查詢有效何節(jié)點(diǎn)的查詢有效以相對(duì)熵為目標(biāo)以相對(duì)熵為目標(biāo)(多多種方法之一種方法之一)，將概，將概率查詢變?yōu)橛屑s束率查詢變?yōu)橛屑s束的優(yōu)化問題，

44、并使的優(yōu)化問題，并使用拉格朗日乘子法用拉格朗日乘子法求解。求解。(1)變量消去法與變量消去法與clique樹消去法等價(jià)；樹消去法等價(jià)；(2)后者后者可以同時(shí)獲可以同時(shí)獲得多個(gè)查詢結(jié)果，且與變量序無(wú)關(guān)得多個(gè)查詢結(jié)果，且與變量序無(wú)關(guān)(校準(zhǔn)條件校準(zhǔn)條件)?；趦?yōu)化的推斷基于優(yōu)化的推斷P與與Q分別是精確推斷與優(yōu)化推斷，使得分別是精確推斷與優(yōu)化推斷，使得Q與與P的的距離最小。距離最小。三個(gè)步驟：三個(gè)步驟：(1)距離；距離；(2)圖結(jié)構(gòu)的目標(biāo)函數(shù)和約圖結(jié)構(gòu)的目標(biāo)函數(shù)和約束函數(shù)束函數(shù)；(3)求解優(yōu)化問題。求解優(yōu)化問題。優(yōu)化推斷分為優(yōu)化精確推斷和優(yōu)化近似推斷，優(yōu)化推斷分為優(yōu)化精確推斷和優(yōu)化近似推斷，前者是前者

45、是目標(biāo)和約束空間目標(biāo)和約束空間精確，后者是兩者至少精確，后者是兩者至少存在一個(gè)非精確。存在一個(gè)非精確。目標(biāo)：相對(duì)熵最小目標(biāo)：相對(duì)熵最小能量泛函最大能量泛函最大()( |) l n l n() l n() ()QQQQ XD QPEEQ XEPXPX1()PUZl nl n l nPZ相對(duì)熵相對(duì)熵注意注意取對(duì)數(shù)取對(duì)數(shù)令能量泛函令能量泛函, l n()() l n ()QQQQF PQEP XHXEHX( |) l n, D QPZF PQ代入相對(duì)熵代入相對(duì)熵計(jì)算一個(gè)計(jì)算一個(gè)Q使得其與精確推斷使得其與精確推斷P 的相對(duì)熵最小，由于的相對(duì)熵最小，由于lnZ與與Q無(wú)關(guān)，這樣，以相對(duì)熵最小的目標(biāo)可以使用

46、能量泛函最大無(wú)關(guān)，這樣，以相對(duì)熵最小的目標(biāo)可以使用能量泛函最大代替，由此，優(yōu)化變?yōu)橛?jì)算能量泛函最大的代替，由此，優(yōu)化變?yōu)橛?jì)算能量泛函最大的Q。其中其中X為所有變量的集合，為所有變量的集合，Q是是P 的近似。的近似。Clique樹的因子能量泛函樹的因子能量泛函, l n()()iiii jCiii jiii jF PQEHCHS,TTiii vi ji ji jCPXS jajjC:上述泛函涉及所有變量的聯(lián)合分布，不易設(shè)計(jì)優(yōu)化算法。上述泛函涉及所有變量的聯(lián)合分布，不易設(shè)計(jì)優(yōu)化算法。Clique樹使用樹使用因子能量泛函，定義為：初始勢(shì)能與傳遞的能量因子能量泛函，定義為：初始勢(shì)能與傳遞的能量(消息消

47、息)。Clique樹節(jié)點(diǎn)樹節(jié)點(diǎn) Ci的的固有勢(shì)能的期望固有勢(shì)能的期望Clique樹分布樹分布(傳遞的能量傳遞的能量)的對(duì)數(shù)形式。的對(duì)數(shù)形式。iNbkikii,ii ji ji jiiCSSC 是信度是信度(節(jié)點(diǎn)節(jié)點(diǎn)(cluster)上的信息上的信息)， 是是i與與j傳遞的所有消息傳遞的所有消息(邊上的信息邊上的信息)這是研究校準(zhǔn)這是研究校準(zhǔn)clique樹的原因之一。樹的原因之一。Clique樹的約束精確優(yōu)化推斷樹的約束精確優(yōu)化推斷,ii jQ,( )( ) 1ii jii ji jiiCSiicscc計(jì)算計(jì)算使得使得, F PQ最大最大對(duì)約束對(duì)約束iNbkikii,ii ji ji jiiCS

48、SC 是信度是信度(節(jié)點(diǎn)節(jié)點(diǎn)) 是是i與與j傳遞的所有消息傳遞的所有消息(邊上邊上)Q是節(jié)點(diǎn)和邊上信息的并集，是節(jié)點(diǎn)和邊上信息的并集，即，消息的網(wǎng)圖上的傳播。即，消息的網(wǎng)圖上的傳播?；诨赾lique樹的優(yōu)化推斷算法樹的優(yōu)化推斷算法, ( ) 1) () )iii jii jiiii ji jiii ji jiCij N b SCSF PQcSCS ,( )ii ji ji jiiCSsc( ) 1iiicc使用拉格朗日乘子，將上述約束變?yōu)橄率龇匠痰膬?yōu)化問題使用拉格朗日乘子，將上述約束變?yōu)橄率龇匠痰膬?yōu)化問題以后類似感知機(jī)算法的推導(dǎo)，對(duì)以后類似感知機(jī)算法的推導(dǎo)，對(duì) 與與 計(jì)算偏導(dǎo)，獲得下式計(jì)算

49、偏導(dǎo)，獲得下式)(,jiiiSCjNbkikijijiijjiNbjijiii,)(這是一個(gè)迭代式，據(jù)此，可這是一個(gè)迭代式，據(jù)此，可以設(shè)計(jì)優(yōu)化精確推斷的算法以設(shè)計(jì)優(yōu)化精確推斷的算法基于優(yōu)化的近似推斷基于優(yōu)化的近似推斷一般地說，基于優(yōu)化的近似推理的直接考慮是兩個(gè)一般地說，基于優(yōu)化的近似推理的直接考慮是兩個(gè)近似因素：其一，目標(biāo)函數(shù)，其二，約束空間。近似因素：其一，目標(biāo)函數(shù)，其二，約束空間。但是，其關(guān)鍵是：表示問題的圖結(jié)構(gòu)。如果為了計(jì)但是，其關(guān)鍵是：表示問題的圖結(jié)構(gòu)。如果為了計(jì)算等原因，使用了一種近似表示的圖結(jié)構(gòu)，這類圖算等原因，使用了一種近似表示的圖結(jié)構(gòu)，這類圖將更容易構(gòu)造。相對(duì)精確描述，其目標(biāo)函

50、數(shù)和約束將更容易構(gòu)造。相對(duì)精確描述，其目標(biāo)函數(shù)和約束空間是近似的?？臻g是近似的。Cluster圖圖采用消息傳播方法的前提：其一，圖結(jié)構(gòu)是樹，其二，滿足采用消息傳播方法的前提：其一，圖結(jié)構(gòu)是樹，其二，滿足RIP。Cluster圖放棄條件圖放棄條件1，不要求樹，但需要滿足被擴(kuò)展的，不要求樹，但需要滿足被擴(kuò)展的RIP被擴(kuò)展的被擴(kuò)展的RIP：如果存在一個(gè)變量：如果存在一個(gè)變量X，使得，使得X Ci且且X Cj，則，在，則，在Ci與與Cj之間，存在一個(gè)之間，存在一個(gè)單一單一的通路，在這個(gè)通路的所有邊的通路，在這個(gè)通路的所有邊e上，上，包含這個(gè)變量，包含這個(gè)變量，X Se。關(guān)鍵關(guān)鍵：對(duì)一個(gè)變量，兩個(gè)：對(duì)一

51、個(gè)變量，兩個(gè)clusters之間只有一個(gè)單一通路，例如，之間只有一個(gè)單一通路，例如，3與與2之間，對(duì)變量之間，對(duì)變量B，3-4-2與與3-4-1-2兩個(gè)通路，如果兩個(gè)通路，如果1與與2的邊上是的邊上是B，就不滿足擴(kuò)展，就不滿足擴(kuò)展RIP。這是對(duì)圖結(jié)構(gòu)的約束。這是對(duì)圖結(jié)構(gòu)的約束。構(gòu)造構(gòu)造cluster圖圖對(duì)對(duì)Cluster圖近似，不同的圖可能導(dǎo)致完全不同的解答，這樣，圖近似，不同的圖可能導(dǎo)致完全不同的解答，這樣，就存在一個(gè)選擇哪個(gè)就存在一個(gè)選擇哪個(gè)cluster圖的問題，一般的原則是在高效計(jì)算圖的問題，一般的原則是在高效計(jì)算和精度之間的折中。和精度之間的折中。左圖是一個(gè)問題的兩個(gè)左圖是一個(gè)問題的

52、兩個(gè)Cluster圖。差別在于，上圖的圖。差別在于，上圖的4-2連連線在下圖不存在，在線在下圖不存在，在1-2連線連線上的變量下圖從上的變量下圖從C變?yōu)樽優(yōu)锽, C幾種構(gòu)圖的方法，動(dòng)機(jī)是容易幾種構(gòu)圖的方法，動(dòng)機(jī)是容易處理，但不能違反處理，但不能違反RIP：(1)偶對(duì)偶對(duì)MN。(2)Bethe Cluster圖。圖。構(gòu)造構(gòu)造“偶對(duì)偶對(duì)(Pairwise)MN”這類圖有兩類這類圖有兩類cluster，其一，單變量勢(shì)能，其一，單變量勢(shì)能 iXi，其二，變量偶對(duì)，其二，變量偶對(duì)勢(shì)能勢(shì)能 (i, j)Xi, Xj，后者可以理解為，后者可以理解為cluster邊上的勢(shì)能。邊上的勢(shì)能。Cluster Ci與

53、與Cj對(duì)應(yīng)單變量對(duì)應(yīng)單變量Xi與與Xj，cluster C(i, j)(Xi-Xj)對(duì)對(duì)應(yīng)應(yīng)XiXj邊。邊?？梢宰C明，可以證明，“偶對(duì)偶對(duì)MN”是是cluster圖。這樣，這個(gè)圖就可圖。這樣，這個(gè)圖就可以使用消息傳播的方式求解以使用消息傳播的方式求解推斷。推斷?！皩?duì)對(duì)MN”構(gòu)造容易。構(gòu)造容易。Bethe Cluster圖圖這類圖有兩層：其一，這類圖有兩層：其一，“大大”cluster，是表現(xiàn)，是表現(xiàn)MN結(jié)構(gòu)的因子結(jié)構(gòu)的因子 (Cluster或或clique)，其二，其二，“小小”cluster，是單變量。，是單變量?！按蟠蟆眂luster包含的變量與對(duì)應(yīng)包含的變量與對(duì)應(yīng)“小小”變量變量clus

54、ter使用邊連接。使用邊連接?？梢宰C明，這個(gè)圖也是可以證明，這個(gè)圖也是cluster圖，可以使用消息傳播方法圖，可以使用消息傳播方法求解推斷。這類圖容易構(gòu)造。求解推斷。這類圖容易構(gòu)造。Cluster圖的優(yōu)化推斷算法圖的優(yōu)化推斷算法, 10ii jii jiiCSi jii jiiciiscLocal Ucc 事實(shí)上，對(duì)事實(shí)上，對(duì)cluster圖，因子能量泛函也不能優(yōu)化成精確解，理由圖，因子能量泛函也不能優(yōu)化成精確解，理由: (1)對(duì)對(duì)邊緣分布構(gòu)成的多面體，每個(gè)邊緣分布構(gòu)成的多面體，每個(gè)cluster信度信度( )不一定在這個(gè)多面體上，不一定在這個(gè)多面體上，信度是對(duì)邊緣分布的近似，信度是對(duì)邊緣分

55、布的近似，(2)判定信度集合是否在多面體上是判定信度集合是否在多面體上是NP難解。難解。優(yōu)化從多面體上變?yōu)榫植恳恢聝?yōu)化從多面體上變?yōu)榫植恳恢?定義如下定義如下)多面體上。偽邊緣。多面體上。偽邊緣。Cluster圖的優(yōu)化圖的優(yōu)化LocalUQ Q,PF Q約束：最大使得：求：以下使用拉格朗日乘子推以下使用拉格朗日乘子推出具體算法，步驟如前。出具體算法，步驟如前。與與clique樹優(yōu)化約束的形式樹優(yōu)化約束的形式完全一樣，其區(qū)別僅在：完全一樣，其區(qū)別僅在： 與與 的作用域，的作用域，clique是在是在clique樹上，這個(gè)約束是在樹上，這個(gè)約束是在圖的一個(gè)局部圖的一個(gè)局部U上。上。在圖結(jié)構(gòu)下推斷的

56、本質(zhì)是：計(jì)算查詢變量的邊緣分布，在圖結(jié)構(gòu)下推斷的本質(zhì)是：計(jì)算查詢變量的邊緣分布，P=。關(guān)鍵是。關(guān)鍵是 ，是計(jì)算所有非查詢變量取值的全組合。，是計(jì)算所有非查詢變量取值的全組合。這個(gè)看似簡(jiǎn)單的問題，其復(fù)雜性遠(yuǎn)遠(yuǎn)超過我們的想象。這個(gè)看似簡(jiǎn)單的問題，其復(fù)雜性遠(yuǎn)遠(yuǎn)超過我們的想象?？偨Y(jié)總結(jié)近似推斷主要涉及三類近似的方法：近似推斷主要涉及三類近似的方法：(1)研究對(duì)圖結(jié)構(gòu)描述的近似，這是本質(zhì)近似。研究對(duì)圖結(jié)構(gòu)描述的近似，這是本質(zhì)近似。(2)研究對(duì)目標(biāo)函數(shù)的近似，對(duì)給定圖結(jié)構(gòu)的近似。研究對(duì)目標(biāo)函數(shù)的近似，對(duì)給定圖結(jié)構(gòu)的近似。(3)研究計(jì)算近似算法，精確算法無(wú)效，計(jì)算近似。研究計(jì)算近似算法，精確算法無(wú)效，計(jì)算近

57、似。概率圖模型近似推斷核心是：概率圖模型近似推斷核心是：“精度和效率精度和效率”的折中。歸的折中。歸根結(jié)底是表示的研究。根結(jié)底是表示的研究。BN如何直接使用各種近似？如何直接使用各種近似？三類近似沒有一個(gè)容易，特別是其誤差性質(zhì)，除了計(jì)算近三類近似沒有一個(gè)容易，特別是其誤差性質(zhì)，除了計(jì)算近似之外，并沒有本質(zhì)進(jìn)展。相當(dāng)復(fù)雜，遍地問題！似之外，并沒有本質(zhì)進(jìn)展。相當(dāng)復(fù)雜，遍地問題！一、引子一、引子二、表示二、表示三、推斷三、推斷四、學(xué)習(xí)四、學(xué)習(xí)五、結(jié)束語(yǔ)五、結(jié)束語(yǔ)概率圖模型學(xué)習(xí)任務(wù)概率圖模型學(xué)習(xí)任務(wù)假設(shè)：給定結(jié)構(gòu)且樣本是完整假設(shè)：給定結(jié)構(gòu)且樣本是完整(所有變量被賦值所有變量被賦值)的。的。任務(wù)：學(xué)習(xí)參

58、數(shù)，參數(shù)估計(jì)。任務(wù)：學(xué)習(xí)參數(shù)，參數(shù)估計(jì)。CPD方法：方法：(1)最大似然估計(jì)最大似然估計(jì), (2)Bayes預(yù)測(cè)預(yù)測(cè)假設(shè)：結(jié)構(gòu)未知，但是，樣本完整。假設(shè)：結(jié)構(gòu)未知，但是，樣本完整。任務(wù)：學(xué)習(xí)結(jié)構(gòu)和參數(shù)。任務(wù)：學(xué)習(xí)結(jié)構(gòu)和參數(shù)。考慮一個(gè)可能結(jié)構(gòu)的假設(shè)空間，結(jié)構(gòu)選擇變?yōu)閮?yōu)化問題。考慮一個(gè)可能結(jié)構(gòu)的假設(shè)空間，結(jié)構(gòu)選擇變?yōu)閮?yōu)化問題。假設(shè)：樣本不完整，或某些變量未知。假設(shè)：樣本不完整，或某些變量未知。任務(wù)：發(fā)現(xiàn)非顯現(xiàn)表現(xiàn)的變量，知識(shí)發(fā)現(xiàn)。任務(wù)：發(fā)現(xiàn)非顯現(xiàn)表現(xiàn)的變量，知識(shí)發(fā)現(xiàn)。 對(duì)對(duì)BN：工具：最大似然和工具：最大似然和Bayes估計(jì)。估計(jì)。特點(diǎn)：從局部到整體的學(xué)習(xí)。特點(diǎn)：從局部到整體的學(xué)習(xí)。困難：魯棒性，

59、泛化。困難：魯棒性，泛化。對(duì)對(duì)MN：工具工具:最大似然最大似然, Bayes估計(jì)估計(jì),迭代優(yōu)化迭代優(yōu)化特點(diǎn)：魯棒性，泛化。特點(diǎn)：魯棒性，泛化。困難：整體的劃分函數(shù)和推斷。困難：整體的劃分函數(shù)和推斷。BN的學(xué)習(xí)的學(xué)習(xí)-目標(biāo)函數(shù)目標(biāo)函數(shù)學(xué)習(xí)就是計(jì)算使得學(xué)習(xí)就是計(jì)算使得L( : D)最大的最大的 。似然函數(shù)：數(shù)據(jù)集合似然函數(shù)：數(shù)據(jù)集合D，BN的參數(shù)的參數(shù) 或或(與與)圖圖G的似然函數(shù)的似然函數(shù)L( : D)其中其中 可以是參數(shù)可以是參數(shù) (給定給定BN結(jié)構(gòu)結(jié)構(gòu))，或者是，或者是(學(xué)習(xí)結(jié)構(gòu)學(xué)習(xí)結(jié)構(gòu))學(xué)習(xí)就是計(jì)算使得學(xué)習(xí)就是計(jì)算使得P( | D)最大的最大的 。由于后驗(yàn)概率依賴先。由于后驗(yàn)概率依賴先驗(yàn)概

60、率與似然函數(shù)，問題變?yōu)橛?jì)算這兩個(gè)函數(shù)的問題。驗(yàn)概率與似然函數(shù)，問題變?yōu)橛?jì)算這兩個(gè)函數(shù)的問題。Bayes預(yù)測(cè)：數(shù)據(jù)集合預(yù)測(cè)：數(shù)據(jù)集合D，BN的參數(shù)的參數(shù) 或圖或圖G的后驗(yàn)概率。的后驗(yàn)概率。P( | D)其中其中 可以是參數(shù)可以是參數(shù) (給定給定BN結(jié)構(gòu)結(jié)構(gòu))，或者是圖，或者是圖G(學(xué)習(xí)結(jié)構(gòu)學(xué)習(xí)結(jié)構(gòu))BN的似然函數(shù)的似然函數(shù)假設(shè)假設(shè)BN結(jié)構(gòu)給定，任務(wù)是確定參數(shù)。結(jié)構(gòu)給定，任務(wù)是確定參數(shù)。令令Xi是給定是給定BN上的一個(gè)節(jié)點(diǎn)上的一個(gè)節(jié)點(diǎn)(變量變量)，其父輩節(jié)點(diǎn)集合為，其父輩節(jié)點(diǎn)集合為Pai。Xi的的CPD (因子因子)為為P(Xi | PaXi)。給定數(shù)據(jù)集合。給定數(shù)據(jù)集合D，P(Xi | PaXi