從概率譯碼到置信傳播，一個采用了校驗集合樹的概念，一個運用了Tanner圖。然而我們實際上還是計算的公式，具體來說是
加法和乘法的運用構(gòu)成了整個概率模型。但為何在這些算法中都引入了圖？圖在這里面起到了什么作用？《Pattern Recognition and Machine Learning》在圖模型章節(jié)的開篇是這樣說的
However, we shall find it highly advantageous to augment the analysis using diagrammatic representations of probability distributions, called probabilistic graphical models. These offer several useful properties:
1. They provide a simple way to visualize the structure of a probabilistic model and can be used to design and motivate new models.
2. Insights into the properties of the model, including conditional independence properties, can be obtained by inspection of the graph.
3. Complex computations, required to perform inference and learning in sophisticated models, can be expressed in terms of graphical manipulations, in which underlying mathematical expressions are carried along implicitly.
很多時候我們更關(guān)注問題的表示而非其本身。就像LDPC關(guān)注校驗矩陣的形式，以及數(shù)據(jù)的各種變換。概率模型也一樣，三種圖模型被用來表示概率模型，包括有向圖模型、無向圖模型（馬爾可夫隨機場）和因子圖。三種模型各有優(yōu)點，本節(jié)將介紹因子圖。
對于多項式而言，我們有因式分解。譬如在解高次方程的時候，我們非常希望方程能夠分解為多個低次方程的乘積。那么，對于概率分布函數(shù)而言，我們也希望能夠這樣做，即
其中是中變量的子集，至于到底能夠如何分解是取決于問題的，就好象多項式的分解取決于其具體形式。對于一個實際的問題，如果有以下關(guān)系
那么這一個式子的因子圖表示如下
圖 3 因子圖
從這個例子，我們總結(jié)一下因子圖是什么？因子圖有兩類節(jié)點，一是變量節(jié)點，另一個成為因子節(jié)點。這兩類節(jié)點的內(nèi)部沒有邊直接相連，變量的概率密度可以因式分解為因子節(jié)點的函數(shù)的乘積，因子節(jié)點的函數(shù)變量包括與其直接相連的變量節(jié)點。
寫到這里忽然發(fā)現(xiàn)了一個很嚴重的問題，因子圖這一表示是用來干什么的？不是我不想寫，是我也不知道。如果從和積算法來說，因子圖可以用來計算邊緣概率分布。這也是《Pattern Recognition and Machine Learning》中引入因子圖的理由。置信傳播算法可以看作是和積算法的一個特例。
目的：計算邊緣概率
手段：和積算法（要求兩個節(jié)點之間只有一條路徑，即多項式樹結(jié)構(gòu)）
實現(xiàn)方式：
- 邊緣概率
表示除之外的變量集合。
- 因子分解
圖 4 因子圖的分解
這里為何要這樣做呢？一個算法要盡可能多的利用已知的結(jié)構(gòu)和信息，和積算法的一個假設(shè)是圖無環(huán)。同時我們發(fā)現(xiàn)，對于一個最簡單的只有一個變量節(jié)點和因子節(jié)點的圖來說（這時實際上沒有意義了），我們已經(jīng)達到我們要的結(jié)果。如果圖無環(huán)的話，意味著只要我斷開一條邊，那么這個大的因子圖就變成了兩個小的因子圖。
如果我們將節(jié)點取出，那么因子圖變成了個小因子圖，這幾個小因子圖通過節(jié)點相連，故因子圖的概率分布可以寫成
其中代表和相連的因子節(jié)點，代表在這一個小因子圖上的所有因子節(jié)點的乘積。
- 將2代入1，得
我們設(shè) 如下
我們可以將其看作是因子節(jié)點傳遞的信息（也就是小因子圖傳遞的）。
- 計算
或許，我們將"計算"改為"表示"更為合適。上文中一直提到"小因子圖"顯然是可以因子化的，也就是說可以表示為
那么可以表示為
也就是說，實際上這個過程是小因子圖的繼續(xù)劃分的過程，具體可以表示為下圖
圖 5 因子圖的分解（續(xù)）
同理可設(shè) ，可將其看作變量節(jié)點向因子節(jié)點傳遞的信息。
- 因子圖的繼續(xù)分解
如果我們繼續(xù)將其分解下去，那么將再次計算到因子節(jié)點向變量節(jié)點傳遞的信息，而我們的目的正是如此，希望能夠得到， 之間相對簡單的公式，這樣我們就能夠計算出邊緣概率分布了。
圖 6因子圖的分解（續(xù)2）
由圖 6 易知
也就是說
- 總結(jié)
和積和積，何為和積？變量節(jié)點的信息傳遞是求乘積的過程，因子節(jié)點傳遞的過程是對求乘積后的結(jié)果進行求和的過程（依據(jù)該因子節(jié)點的方程）。
我們注意到實際上都有一個連接的其他節(jié)點求乘積的過程，這也就意味著如果一個節(jié)點只和一個節(jié)點相連，那么其傳遞的消息是（和1相乘值不變）
- 對應(yīng)變量節(jié)點；
- ，對應(yīng)因子節(jié)點
到這里，因子圖和和積算法已經(jīng)寫完了，要把因子圖和和積算法和LDPC譯碼算法對應(yīng)起來，我們要解決的問題實際上有兩個
- 在譯碼過程中觀測量如何處理？上述因子圖的所有變量節(jié)點都可以看作是隱藏節(jié)點，如何對觀測到的結(jié)果進行處理，計算條件概率？
- 如何處理因子節(jié)點和校驗節(jié)點之間的關(guān)系？
這兩個問題還有待進一步思考……
| 
變量節(jié)點和
個校驗節(jié)點，對應(yīng)校驗矩陣
的列數(shù)和行數(shù)。如果第
個變量節(jié)點和第
個校驗節(jié)點之間有邊相連，那么
，否則
。顯然，變量節(jié)點內(nèi)部是沒有邊相連的，校驗節(jié)點也是如此。
