讀DaphneKoller的“概率圖模型”

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

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

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

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

5、了。小學生不會犯的差錯標與其他指標一起平均了。小學生不會犯的差錯(80年代末年代末)書中書中“學生學生”的例子的例子課程課程(D:難難=0，易，易=1) 智力智力(I: 聰明聰明=0，一般，一般=1)考試考試(G: A, B, C) SAT (S: 好好=0，壞，壞=1)推薦推薦(L: 強強=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問題是：問題是：If D=1 I=0 G=A then L=?這就是人工智能遇到的難題！無這就是人工智能遇到的難題！無法泛化！

6、法泛化！不同查詢，不同規(guī)則！不同查詢，不同規(guī)則！構造一個函數：構造一個函數：L = f ( ,D,I,G,S)觀察一組學生，獲得樣本集?；^察一組學生，獲得樣本集?；瘮禂礚 = 1D + 2I + 3G + 4S設計算法，確定設計算法，確定 ，獲得模型。，獲得模型。問題：模型為真需要多少樣本，對問題：模型為真需要多少樣本，對高維數據，不知道！模型不可解釋高維數據，不知道！模型不可解釋這就是統(tǒng)計機器學習遇到的難題。這就是統(tǒng)計機器學習遇到的難題。可以泛化，可以泛化，精度未知精度未知，不可解釋。，不可解釋。根據觀察和專家經驗，構造規(guī)則集根據觀察和專家經驗，構造規(guī)則集問題本身的語義問題本身的語義課

7、程難易程度與考試分數有關。課程難易程度與考試分數有關。學生智力與考試成績有關。學生智力與考試成績有關。學生智力與學生智力與SAT有關。有關?？荚嚦煽兣c考試成績與“推薦信強弱推薦信強弱”有關。有關。AI方案充分考慮了這種語義，方案充分考慮了這種語義，但是，將這種語義強化到唯但是，將這種語義強化到唯一表示程度一表示程度(當且僅當當且僅當)，缺，缺失靈活性。失靈活性。統(tǒng)計學習方案完全不考慮這統(tǒng)計學習方案完全不考慮這種語義，盡管具有靈活性種語義，盡管具有靈活性(泛泛化化)，但是，需要充分的觀察，但是，需要充分的觀察樣本。樣本。兩者的共同代價是：維數災難。前者，需要考慮所有可能兩者的共同代價是：維數災難

8、。前者，需要考慮所有可能的組合的規(guī)則集合，后者，需要考慮充分的樣本集合。的組合的規(guī)則集合，后者，需要考慮充分的樣本集合。這種語義可以根據統(tǒng)這種語義可以根據統(tǒng)計分布獲得，也可以計分布獲得，也可以根據常識經驗獲得。根據常識經驗獲得。ML強調給定變量集合張成的空間上計算平均的方法，抹煞強調給定變量集合張成的空間上計算平均的方法，抹煞變量之間的結構；變量之間的結構；AI強調變量的獨立性，忽視變量之間的條強調變量的獨立性，忽視變量之間的條件獨立關系。是否可將變量子集件獨立關系。是否可將變量子集(甚至一個變量甚至一個變量)的局部分布，的局部分布，根據變量之間內在的結構，轉變?yōu)閷ψ兞考险w的聯(lián)合分根據變量

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

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

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

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

13、造從聯(lián)合分布構造Bayes網網(BN)學生問題，五個變量排成一個任意的序：學生問題，五個變量排成一個任意的序：I, D, G, L, S，其聯(lián)合分布其聯(lián)合分布(左左)，對應的完全，對應的完全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)構造構造Bayes網網因子因子完全圖完全圖節(jié)點節(jié)點G上的條件概率分布上的條件概率分布(CPD)圖上的獨立性圖上的獨立性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相互獨立相互獨立L只與只與G有關，與其他獨立有關，與其他獨立P(G | I, D)P(L | G)S只與只與I有關，與其他獨立有關，與其他獨立P(S | I)difficultyIntelligenceGradeSATLetter分布分布P中的條件獨立中的條件獨立P(X)是隨機變量集是隨機變量集X中所有變量的聯(lián)合分布，中所有變量的聯(lián)合分布，P(Xi | Z)是是Xi關于關于Z的條件分布。的條件分布。Z X, Xi X且且Xi Z。條件獨立：如果兩個變量條件獨立：如果兩個變量Xi, Xj X，對條

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

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

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

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

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

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

21、的P-mapABDCDBCA對對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-結構結構)，C已知，已知，B與與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網網(Bayesian Network, BN)，有向圖，有向圖Markov網網(Markov Network, MN)，無向圖，無向圖各種局部概率模型各種局部概率模型(CPD) Markov網網(MN)n盡管盡管MN(MN(無向圖無向圖) )以完全子圖的因子為基礎，但以完全子圖的因子為基礎，但是，是，MNMN上的完全子圖依賴條件獨立，因為節(jié)點上的完全子圖依賴條件獨立，因為節(jié)點之間連線的刪除，將直接導

23、致不同的完全子圖。之間連線的刪除，將直接導致不同的完全子圖。n因子是一個從變量因子是一個從變量D D子集到正實數域子集到正實數域 + +上的映上的映射射( (函數函數) )。表示聯(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稱為劃分函數稱為

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

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

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

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

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

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

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

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

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

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

34、概率查詢變?yōu)橛屑s束率查詢變?yōu)橛屑s束的優(yōu)化問題，并使的優(yōu)化問題，并使用拉格朗日乘子法用拉格朗日乘子法求解。求解。將無向圖構成將無向圖構成clique樹，采用消息傳播樹，采用消息傳播的方法，計算查詢的方法，計算查詢的分布。對圖上任的分布。對圖上任何節(jié)點的查詢有效何節(jié)點的查詢有效BN變量消去法變量消去法-計算計算P(D)BN網：網：ABCD對對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)計算計算 2(B, C) = 1(B) P(C | B)， 2(C) = B 2(B, C) (消去消去B)最后，計算出最后，計算出P(D)。ABCD聯(lián)合分布：聯(lián)合分布：P(A,B,C,D)=P(A) P(B|A) P(C|B) P(D|C)MN變量消去法變量消去法-因子邊緣化因子邊緣化對對BN，條件概率，條件概率P(X | Y)為因子，在為因子，在MN中，因子中，因子 (X, Y)，盡管，盡管圖結構不同圖結構不同(有向有向 vs. 無向無向)，但是，在變量消去法上，沒有本質，但是，在變量消去法上，沒有本質區(qū)別。稱為因子邊緣化。區(qū)別。稱為因子邊緣化。P(

36、D) = C B A A B C D滿足交換律和結合律滿足交換律和結合律 = 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)合分布計算邊緣分布的基本形式合分布計算邊緣分布的基本形式“推斷推斷”問題的解法問題的解法提取公因子，提取公因子，以避免變量的以避免變量的重復計算，空重復計算，空間換時間，折間換時間，折中。動態(tài)規(guī)劃中。動態(tài)規(guī)劃動態(tài)規(guī)劃動態(tài)規(guī)劃Clique樹法樹法將無向

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

38、一個變量少存在一個變量X，使得，使得X Ci且且X Cj，如果這，如果這個通路上的所有個通路上的所有cluster均將包含均將包含X，稱其滿足，稱其滿足“RIP” (Running Intersection Property) 。一條通路滿足一條通路滿足RIP，將保證這條通路均有某個，將保證這條通路均有某個變量，同時，構成的變量，同時，構成的cluster圖與圖與MN具有相同具有相同的連接形式的連接形式(拓撲結構拓撲結構)。Clique樹樹 基于基于clique樹的變量消去法樹的變量消去法(1)C1，根據，根據 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),只需計只需計算算 G,L,S 5。 (C)=是初始勢能。對是初始勢能。對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)每個每個clique Cj賦予初始勢能賦予初始勢能(每個因子對應一個每個因子對應一個clique)(2)計算計算Cj的鄰居的鄰居Ci向其傳播消向其傳播消息，總計為：息，總計為：(3)計算根節(jié)點的信度：計算根節(jié)點的信度：(計算計算聯(lián)合分布聯(lián)合分布)方法的優(yōu)點：設定不同根節(jié)點，可以計算任意變量的邊緣分布方法的優(yōu)點：設定不同根節(jié)點，可以計算任意變量的邊緣分布P(C)。改變根節(jié)點只涉及個別消息傳播改變

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

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

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

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

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

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

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

48、SC 是信度是信度(節(jié)點節(jié)點) 是是i與與j傳遞的所有消息傳遞的所有消息(邊上邊上)Q是節(jié)點和邊上信息的并集，是節(jié)點和邊上信息的并集，即，消息的網圖上的傳播。即，消息的網圖上的傳播?；诨赾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)化問題以后類似感知機算法的推導，對以后類似感知機算法的推導，對 與與 計算偏導，獲得下式計算

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

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

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

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

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

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

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樹上，這個約束是在樹上，這個約束是在圖的一個局部圖的一個局部U上。上。在圖結構下推斷的

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

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

58、數，參數估計。任務：學習參數，參數估計。CPD方法：方法：(1)最大似然估計最大似然估計, (2)Bayes預測預測假設：結構未知，但是，樣本完整。假設：結構未知，但是，樣本完整。任務：學習結構和參數。任務：學習結構和參數?？紤]一個可能結構的假設空間，結構選擇變?yōu)閮?yōu)化問題?？紤]一個可能結構的假設空間，結構選擇變?yōu)閮?yōu)化問題。假設：樣本不完整，或某些變量未知。假設：樣本不完整，或某些變量未知。任務：發(fā)現非顯現表現的變量，知識發(fā)現。任務：發(fā)現非顯現表現的變量，知識發(fā)現。 對對BN：工具：最大似然和工具：最大似然和Bayes估計。估計。特點：從局部到整體的學習。特點：從局部到整體的學習。困難：魯棒性，

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

60、率與似然函數，問題變?yōu)橛嬎氵@兩個函數的問題。驗概率與似然函數，問題變?yōu)橛嬎氵@兩個函數的問題。Bayes預測：數據集合預測：數據集合D，BN的參數的參數 或圖或圖G的后驗概率。的后驗概率。P( | D)其中其中 可以是參數可以是參數 (給定給定BN結構結構)，或者是圖，或者是圖G(學習結構學習結構)BN的似然函數的似然函數假設假設BN結構給定，任務是確定參數。結構給定，任務是確定參數。令令Xi是給定是給定BN上的一個節(jié)點上的一個節(jié)點(變量變量)，其父輩節(jié)點集合為，其父輩節(jié)點集合為Pai。Xi的的CPD (因子因子)為為P(Xi | PaXi)。給定數據集合。給定數據集合D，P(Xi | PaXi