http://blog.sina.com.cn/s/blog_461db08c0101jv5j.html
最近在學習Stanford的Daphne Koller講的Probabilistic Graphical Model的網絡課程。整個課程有10周，但我的水準有限，肯定要超過10周了。筆記是根據課程安排的，記錄了我覺得重要的地方，和我不明白的地方，以便自己以後快速檢視。我會随時根據學習情況更新這一篇微網誌的。歡迎讨論和指出錯誤之處。
6.Markov Network Fundamentals 6.1 Pairwise Markov Network
- Pairwise 的 Markov Network各個相鄰元素之間用Factor（Potential）來聯系。
- factor并不與機率成正比，因為真正的聯合機率要受到其他與之聯系的元素所影響。
6.2 General Gibbs Distribution
- Pairwise的network提供的資訊遠遠無法表達整個網絡裡所有節點之間的機率關系。是以要引入Gibbs分布。
- Gibbs分布由一些Factor組成。
- Gibbs分布可以表達多個節點之間的聯合機率（不隻是pairwise的，可以是3個、4個一起）。Gibbs分布有能力表述整個網絡裡所有節點之間的機率關系。因為它至少可以用一個包含所有節點的Factor來表示。
- Gibbs分布可以induce出Markov Network。
- Induced Markov Network，就是把Gibbs分布的Factor裡的節點都連起來。
- 假設有一組Factor，做一下Factor product，然後歸一化，求出所有元素的聯合機率P。同時，這組Factor又可以induce出一個圖H。那麼P可以factorize over H。
6.3 Conditional Random Field
- CRF是MRF的一種變形，非常相似，但用處不同。CRF用來解決Task specific prediction。其實就是labelling problem。（好像MRF也是幹這個的啊？）
- CRF也是由一組Factor表示。看起來很像Gibbs分布的表示方式。但是它們的歸一化方式不同，CRF把機率歸一化成條件機率。
- BN使用聯合機率表示，它假設X1....Xn導緻Y，而且各個X之間是獨立的。如果各X之間不獨立，則會出現Correlated feature，使機率的判斷失真。而CRF使用條件機率表示，這樣不管各X之間是否獨立，都不會影響最後機率的判斷。
- CRF與logistics regression的關系。sigmoid函數也是一種CRF？？？
6.4 Independencies in Markov Network
- Separation in MN.隻要active trail中的一個節點已知了，這個trail就斷了。
- 如果機率P factorizes over 圖H，那麼P也滿足H表達出的independencies，是以H就是P的一個I-map。
- 反過來，independency也可以推出factorization。假設有一個正分布P，H是它的一個I-Map，則P factorizes over 圖H。
6.5 I-maps and perfect maps
- P factorizes over G，則G是P的I-map。G表達了P中的某些independencies，但不一定是全部。
- 最小I-map是指除了P中表達的independencies沒有多餘的路徑的map。
- Perfect map是指 I（G）= I（P），但是Perfect map不一定存在。
- 這裡Koller舉了兩個例子說明Perfect map有時候不存在，但是沒怎麼聽懂。I-map必須是有向圖？？P可以等效于無向圖？？？
- I-map也不是唯一的，不同的I-map可以表示相同的independencies，它們是I-equivalent的。多數的圖都有很多I-equivalence。
- BN和MN互相轉換表示，會丢失independencies。
6.6 Log Linear Models
- 把factor前面加log，本來factor product要做乘法，現在變成做加法。
- Koller舉了一個自然語言識别的例子,來說明我們可以用單詞的feature來判斷機率，而不是單詞本身。
- Ising model的例子，有點像用MRF做圖像分割。溫度高的時候原子之間的聯系弱，溫度低時聯系強。但沒明白她舉這個例子想說明啥。這跟Log linear model有啥關系？
- Metric MRFs。MRF可以提供局部平滑的假設，但首先我們要定義一個Metric，也就是定義MRF元素取值空間的距離函數。
- 後面就講了一些如何利用MRF做圖像分割和圖像去噪。這部分比較熟了。
6.7 Shared Feature in Log-Linear Model
- 舉了Ising model和NLP兩個例子來說明有些條件（feature）是可以重複利用的。是以叫做Shared feature，這種feature對于所有的元素都适用。
- 還是不明白這根log-linear model有啥關系。
7 Representation Wrap-up: Knowledge Engineering 7.1 Knowledge Engineering
- 這部分講的是關于技巧方面的内容，不太涉及理論。
- Knowledge engineering有多種選擇：基于模闆的（圖像分割）還是特殊設計的（醫學診斷）？用有向圖還是無向圖？通用的（适合無label的資料，可以應對未知的資料）還是專用的（需要直接編寫條件機率，可以人工簡化高維的資料）？
- Variable Types。網絡中的變量有三類：目标變量，已觀察到的變量，latent變量
- Structure。要不要在網絡中表達出因果關系。因果關系可以簡化網絡，使它更加直覺。
- Parameter：Value。手工建立網絡時需要注意的問題。
- Parameter：Local structure。這裡讨論了幾種網絡的形式，但是沒有具體例子，不是很明白。
8 Inference: Variable Elimination 8.1 Overview: Conditional Probability Queries
- 如果我們想利用PGM算某個機率，Koller告訴我們，這也是NP-hard，那也是NP-hard，反正很困難就對了。但好在這隻是worst case，一般情況下，可以找到簡便的方法。
- Sum-product。比如我們想求變量J的機率，我們要把網絡内所有的變量的factor求product，得到所有變量的聯合機率，然後把除J之外的變量求和，得到J的邊緣分布，就是J的分布了。
- Evidence：Reduced Factors。如果我們已知了E=e（就是所謂的Evidence），再來求Y的機率，是以我們求的是條件機率P（Y|E=e）。這個機率等于 P(Y，E=e)/P(E=e)。分母用剛才的方法求。求分子的時候，要把所有包含E的factor删去不等于e的條目，然後在用剛才的方法求就行了。
- 在上面的方法中，求聯合機率的那一步，如果除target變量和evidence變量之外還有很多變量，那就難求了，因為複雜度是成指數形式增長的。
- 最後，介紹了一些解機率的算法：如動态規劃，置信傳播，Variational Approximation（？），蒙特卡洛，Importance Sampling（？）
8.2 Overview: MAP Inference
- Maximum a Posteriori(MAP)。最大後驗估計。給定E=e，求除E意外所有變量的值Y=y，使得P(y|e)最大。解可能不是唯一的。
- MAP != Max over Marginals。不能單獨看某個變量的邊緣分布來決定這個變量的解，而要看所有變量的聯合機率哪個最大。
- NP-hardness。XXXX等情況，又是NP-hard。但大部分情況下還是能解的。
- Max-Product。後驗機率P（Y|E=e）= P(Y，E=e)/P(E=e)。我們的目的是求Y使得P最大。分母與Y無關，是以隻用看分子了。分子是E=e條件下的聯合機率，等于是Reduced Factors的乘積，然後歸一化。其實歸一化因子也與Y無關，是以隻用看Reduced Factors的乘積就行了。
- Algorithm：MAP。有很多算法可以利用：Variable elimination（？），置信傳播，整數規劃，圖割法等等。
8.3 Variable Elimination Algorithm
- 這一節就是具體講怎麼算上一節提到的後驗機率。
- 第二個問題答案是C，為什麼不是D?
8.4 Complexity of Variable Elimination
- 這一節主要講Variable Elimination的複雜度問題。複雜度的衡量标準有計算中包括多少個乘法，多少個加法。然後得出結論：乘法的個數将随factor的個數成指數形式增長，這就是Exponential Blow Up。
- 是以在做Variable Elimination時，variable的先後順序就會對複雜度有很大影響。
8.5 Graph-Based Perspective on Variable Elimination
- 如何決定variable的順序呢？這一節從Graph的角度來解決這個問題
- 首先把有向圖變成無向圖，給存在V-structure的兩個父節點建立edge（這一步驟叫做“倫理教育”，因為既然生了孩子就要結婚）。這就得到了Induced MN。
- 在Elimination的過程中，會出現Factor同時包含兩個并沒有相連的variables，這時我們要給這兩個Variable加上edge。這就叫fill edge。
- Induced Graph。加入了fill edge的Graph就叫做Induced Graph，用I表示。I有兩個下标phi & alpha。Phi表示所有的factors，Alpha表示消除（Elimination）的順序。
- Cliques in the induced graph。在VE（variable elimination）中産生的每個factor都是induced graph中的一個clique。clique的定義是：最大全連接配接的sub-graph of the induced graph。“最大”是指無法再添加variable到clique中還保證sub-graph是全連接配接的，“全連接配接”是指每個variable都和其他variable有連接配接。在Koller的例子中一共有5個Clique，它們恰好是每次VE所産生的factor。接着，Koller還證明了一下為什麼“恰好”是這樣的。
- Induced Width。一個Induced Graph的width，等于其中最大的clique所包含節點的個數減1。至于為什麼要減1，沒啥理由，就是這麼定義的。Minimum Induced Width是指一個Induced graph的最小Induced width（因為VE的順序不同，Induced width也不同）。能夠産生Minimum Induced Width的VE順序就是計算效率最高的順序。
- 這一節真TM難了解
8.6 Finding Elimination Orderings
- 定理：判斷一個Graph的Minimum Induced Width是否小于等于K。這個問題是NP-complete的。這和inference的NP-hardness是無關的。
- 是以我們要用一些求近似解的方法。Greedy search是不錯的方法。每次選擇一個Variable消除，不考慮後續的反應。這需要用啟發式的cost評價函數，例如：選擇Neighbor最少的消除，或選擇值域空間最少的variable消除，或選擇fill edge最少的消除，或選擇fill edge（帶權重）最少的消除。
- 定理：一個Induced Graph必須是三角形化的，即Graph中不可能有3個節點以上的空心loop。這個理論可以幫我們找出VE的順序，但是俺沒了解
- Koller舉了一個機器人的例子說明幾種VE的政策的計算量是差别很大的。
9 Inference: Belief Propagation, Part 1 9.1 Belief Propagation
- VE的運算量太大，還有另一種求解方式，即Belief Propagation。
- Cluster Graph。Cluster Graph中的沒一個節點叫做一個Cluster，表示MN中variable的一個子集。而MN中的variable則變成了Cluster Graph中的邊（edge),這裡叫做Sepset。Sepset是由它連接配接的兩個Cluster的共同話題。
- 資訊傳播開始時，資訊delta=1。下一輪疊代時，傳播的資訊變為 Cluster自己的資訊乘以它從鄰居（除了将要接受資訊的那個Cluster）那裡得到的資訊，然後看接受資訊的Cluster關心哪個 Variable，就對那個Variable求邊緣分布，然後傳遞出去。
- 如何建立Cluster Graph？首先，如何選擇Cluster包含哪些Variable(這裡Koller沒講，下一節的Bethe Cluster Graph會講）。其次Cluster的factor（Psi）該是多少？這就需要把原來MN中的factor（Phi）乘進Psi裡。每個Phi隻能放 進一個Psi裡，條件是這個Psi包含了Phi的所有Variable，如果有多個符合條件的Psi，隻能選一個放進去。如果某個Psi沒有一個Phi放 進去，那這個Psi還保留初始值1。
- Koller舉了兩個Cluster Graph的例子。例子中Cluster沒有變，隻是連接配接它們的Sepset變了。下一節中，Koller會證明其中一個是illegal的
- Belief Propagation Algorithm。方法就是上面提到的。但是有兩個問題：1.什麼時候停止疊代？這個接下來會講。2.如何選擇資訊傳遞的edge？這個簡單，就是按照一定的順序就行了。比如Round Robin（循環賽）政策，其實就是輪流疊代。
- Belief Propagation Run。置信傳播的方法好不好？它并不能得到精确地解，但是複雜度比NP-hard要好。
9.2 Properties of Cluster Graphs
- Family preservation Property。對于每一個原來MN中的factor，都要有一個Cluster可以包含他。
- Running Intersection Property。假設有兩個Cluster都包含同一個variable，那麼這兩個Cluster之間必須有唯一的連接配接管道使該variable的信 息可以通過。所謂"唯一"的連接配接，是指sepset不能構成loop（或者說這個路徑必須是一個tree）。否則variable的資訊通過兩條管道分别 傳播，就會被重複考慮了。實際上，即使沒有loop，也不能完全消除variable被重複考慮。因為一個variable的資訊可以在通過 cluster的時候轉換成另一個variable的資訊，然後傳遞回自己，這樣資訊仍然會被重複考慮。
- Bethe Cluster Graph。這種graph有兩種cluster：大cluster包含原MN中的一個factor，小cluster包含原MN中的一個 variable。然後把它們互相連接配接。這種graph的好處是很容易建立，而且大cluster通過小cluster傳遞資訊時，variable之間 的相關性被消除（這算好處嗎？）
10 Inference: Belief Propagation, Part 2 10.1 Properties of Belief Propagation
- Calibration。首先複習一下Cluster Belief是什麼東東（之前講過嗎？）。Cluster Belief等于該Cluster的factor（Psi)乘以進入該Cluster的資訊，用Beta表示。如果兩個相鄰的Cluster對于他們的Sepset的資訊（也就是對他們求Sepset的邊緣機率）一緻，那麼我們就說這個Graph是被Calibrated。
- Convergence->Calibrated。edge的兩端傳遞的資訊相同，是以再疊代下去也不會改變Graph的資訊分布。
- Sepset Belief。即是Sepset兩個方向傳遞的資訊相乘。用Mu表示。
- Reparameterization。如果我們把所有Beta的乘積除以所有Mu的乘積，會得到所有Psi的乘積，也就等于所有Phi的乘積，也就是這個Graph表達的機率分布的Un-normalized measure。是以用Belief Propagation方法并沒有損失任何資訊，而且把問題轉換成了容易解的方式。
10.2 Clique Tree Algorithm - Correctness
- 這一節講的是Cluster Graph的一種特殊情況：資訊不再在整個Cluster Graph裡面傳播，而是在Clique Tree裡面傳播。這種情況下，BP算法不但收斂更加迅速，而且能夠得到精确解。
- Message Passing in Trees。
- Correctness。Cluster的Belief用Beta表示。Beta等于其本身的Psi乘以相鄰元素傳過來的Delta。而Delta又等于 相鄰Cluster的Psi乘以别的Delta。最後可以把所有的Delta都展開成Psi的乘積。這時我們會發現Beta實際上等于一堆Psi的乘積 （還有求和）。這跟我們用factor計算邊緣分布的形式是一樣的。是以這樣就證明了結果的正确性。
- Clique Tree（不記得Clique是什麼了都）。定義：首先它是一個無向樹（Tree就是沒有Loop的Graph）。它的節點是Cluster。連接配接節點的邊就是Sepset。（Clique Tree 就是Cluster Graph的一種特殊形式）
- Family Preservation。由于Clique Tree是特殊的Cluster Graph，是以Family Preservation的性質（9.2.1節）它也要符合。
- Running Intersection。這也是9.1節中的性質，同樣要符合。
- Clique Tree Message Passing。這就是舉了一個例子。
- RIP（Running Intersection Property） -> Clique Tree Correctness。用前面證明Correctness的方法可證明：Running Intersection Property保證了正确性！（為啥？？）
10.3 Clique Tree Algorithm - Computation
- Message Passing in Trees。在Koller舉得例子中，Tree實際上就是一個Chain。而兩端的元素所傳出的資訊是不随疊代而變化的。也就是說，兩端元素的輸出資訊 從一開始就已經收斂了。而端點的元素吧資訊傳遞給下個元素以後，下一個元素也收斂了。以此遞推，整個Graph會在向左向右兩次疊代之後收斂。
- Convergence of Message Passing。Tree的葉子節點上的元素從一開始就是收斂的。是以我們可以從葉子節點開始向内部傳播。如果選擇的順序合适，最少經過2（K-1)次pass，整個tree就會收斂。其中K是元素的個數。
- Message Passing Order。我們可以從葉子節點出發，把資訊向内傳播一步。然後挑出符合收斂條件的節點，再傳播一步……直到所有節點都收斂為止。（這種方法可以保證所有的Graph都适用嗎？）
- Answer Queries（這一步是在收斂後進行的嗎？）。如果我們想知道一個Variable（或者同一個Clique中的多個Variable）的後驗機率分 布，我們要選一個包含這些Variable的Clique，把其他不需要的Variable加起來求邊緣機率。當然，求出來的是未歸一化的邊緣機率，還需 要歸一化才行（怎麼歸？）。
- 如果我們已經觀察到了其中一些Variable的值Z=z，可以以此為基礎，再求其他Variable（用X表示）的機率，這叫做 increamental inferrence。這要分兩種情況。如果X和Z在同一個的Clique裡，這比較簡單，隻要做Clique Reduction就行了。就是把Z!=z的部分去掉，求和，歸一化。如果X和Z不在同一個Clique裡，情況稍複雜一些。因為我們觀察到了Z，是以包 含Z的clique資訊變化了，需要把這個資訊傳遞到包含X的Clique裡。但隻需要傳遞從Z到X之間的路徑就可以了。
- Summerize。用Clique Tree的方法，隻用傳遞2(K-1)次就可以得到所有的機率。而相比之下，用Variable Elimination的方法算的話，就慢很多了。是以我們隻用2倍于VE的計算量，而不是N倍，就完成了計算（這裡是啥意思，不懂）
10.4 Clique Tree and Independence
- Clique Tree可以快速的計算出Variable的邊緣機率，但理論上這個問題又是NP-hard的。那肯定有某種情況是Clique Tree也不能應付的。
- RIP（Running Intersection Property） and Independency。首先，我們定義如下概念：W<(i,j),隻出現在i側的Variables；W<(j,i),隻出現在j側的Variables；還有剩下的兩邊都出現的Variable，也就是Sepset（ij）裡的Variable。
- 定理：一個Clique Tree符合RIP，當且僅當W<(i,j)與W<(j,i)獨立，在給出S(ij)時。
- Koller又舉了兩個例子來說明，在特定情況下，這個問題是NP-Hard的。
10.5 Clique Trees and VE
- 那麼我們如何來構造一個Clique Tree呢？我們首先看如何用Clique Tree的視角去看VE。
- VE的步驟是怎麼樣的？1.每一步會産生一個大的factor lamda（i)；2.然後做VE使lamda（i)縮減成tau（i)；3.用tau（i)去計算下面的lamda（i)。
- 用Clique tree的視角去看，每個lamda就是一個clique，而tau則是clique之間傳遞的message。
- Example。這個例子展示了如何用VE的方法構造clique tree。要點在：VE之後有一步post process，如果相鄰的兩個Clique有包含關系，需要把較小的合進大的裡面。
- 構造出的這個graph到底是不是Clique tree呢？首先，它是一個tree。每個tao隻用到一次，是以資訊隻是一對一的傳播（什麼玩意？）。其次，這個tree是family preserving的（9.2.1）（這裡也不明）。第三，它還有RIP性質（9.2.2）
- Running Intersection Property。定理：VE産生的Cluster tree都有RIP性質。
- Summery。VE可以生成正确的Clique tree。是以我們可以模拟VE（隻選擇variable的順序，不做乘法運算）來生成Clique tree。Clique tree的運算量和VE的運算量相等。這樣看似乎沒什麼優勢，但是我們想獲得所有variable的邊緣分布時，clique tree的優勢就顯現出來了。因為它可以用動态規劃的方法使計算所有variable的運算量隻相當于計算兩次VE。
10.6 BP In Practice
- Misconception Revisited。BP的最壞情況會發生在：1.緊密的閉環網絡；2.強Potential；3.沖突的資訊。在這種情況下收斂會非常慢。
- Different Variants of BP。Synchronous BP，同步的BP，所有Variables同時BP。這種方法收斂會比較慢，盡管它的實作會比較簡單，而且适用于并行計算。Asynchronous BP，非同步的BP。Variable依次做BP，這會加快收斂的速度，同時提高收斂的程度。但如何選擇BP的順序呢？下一節再講。
- Observation。1.收斂是局部的概念，有些資訊收斂很快，有些卻怎麼也收斂不了。2.非同步比同步的好。3.非同步BP的順序很重要。
- Informed Message Scheduling。Tree reparameterization（TRP），選一個Tree進行BP，再選一個Tree進行...。還有一種Residual belief propagation（RBP），每次在最不agree的兩個cluster間BP。
- Smoothing （Damping） Messages。每次傳遞資訊時留一些餘地，避免資訊過快的變化。這樣可以避免震蕩。可以大幅提高收斂的程度。
10.7 Loopy BP and Message Decoding
- 一個很有趣的應用是将Loopy BP和Message Decoding這兩個看似無關的東西聯系在一起。
- 講了一段曆史，心情不好，沒怎麼注意聽。
11 Inference: MAP Estimation 11.1 Max Sum Message Passing
- 這一節突然轉變話題，反過來倒過去看了好幾天才弄明白過來。
- 到目前為止，我們都是在讨論如何計算邊緣機率，但另外還有一種很有價值的問題是：如何找出一個聯合機率最大的variable的組合。很顯然，我們不能把邊緣機率最大的variable組合到一起，我們需要一種不同的算法去解決這個問題。
- Product->Summation:首先，我們需要把乘法轉變成加法。這需要我們把factor都轉變為log的形式。（這個轉換之前的計算也适用，為什麼現在才提出來？）
- Max-Sum Elimination in Chains:我們可以像VE那樣每次eliminate一個variable。使之變成一個不包含此variable的中間變量lambda。
- Factor Summation：和sum-product算法類似，隻是把product變為summation。
- Factor Maximization：還是和sum-product算法類似，隻是把sum變成了max，在Eliminate一個variable的時候不是把相應的factor加起來，而是去最大的那個。這個過程又叫做max-marginalization
- Max-Sum Elimination in Chains：繼續之前的過程，當我們Eliminate到隻剩下一個Variable E的時候，這時候的lambda就代表了：E取e時，可能出現的最大的聯合機率。
- Max-Sum in Clique Tree：用Max-Sum代替Sum-Porduct在Clique Tree的資訊傳遞中也是一樣的。
- Simple Example：這個例子很好，很清晰。
- Max-Sum BP at Convergence：我們該如何判斷BP已經收斂了呢？每個Clique的資訊都在表達其所包含變量的max-marginals。而且clique tree此時會有所謂的calibration property，即是相鄰的clique之間要對sepset中的variable的max-mariginal資訊要一緻。
11.2 Finding a MAP Assignment
- 上一節我們隻讨論了如何獲得max-marginal，而沒有讨論如何得到MAP Assignment（即最大的聯合機率對應的各個variable的值）。
- 這其實很簡單，隻需要在每個Clique中挑出最大的機率對應的variable值就可以了。但如果Clique中有幾個機率相同的最大機率該如何處理 呢？有兩個方法：1.對機率做一點擾動，使最大值變成隻有一個；2.先在第一個Clique中選一個最大機率（随便選一個就行），然後記住選了哪個值，再 在下一個Clique中的對應值中選一個最大機率……。
![吳恩達機器學習筆記（3）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)