1、因子圖 與 和-積算法 Factor graph and sum-product algorithm 孫偉,概述： 圖模型（ graphical model ）、因子圖（factor graph） 、和-積 算法（sum-product algorithm）: 1）常見的電路圖、信號(hào)流程圖、格子圖以及各種框圖都屬于圖模型的范疇； 2）因子圖（factor graph）是圖模型的一種； 3）因子圖的典型代表是Forney-style factor graph，簡稱FFG。 4）和-積算法 又稱“概率傳播(probability propagation )算法”或“置信傳播(belief prop

2、agation)算法”, 意味著圖模型（graphical model）中的信息傳遞； 5）編碼領(lǐng)域、信號(hào)處理、人工智能方面的大量算法實(shí)際上都可看作和-積算法的實(shí)例； 檢測(cè)、估計(jì)方面的一些新算法也可看作和-積算法的衍生實(shí)例。,編碼領(lǐng)域、信號(hào)處理、人工智能等方面的大量算法實(shí)際上都可看作和-積算法的實(shí)例： 具體的應(yīng)用實(shí)例： 1）卡爾曼濾波（Kalman filtering）（especially in the form of the RLS algorithm）； 2）隱馬爾可夫模型的前向-后向算法（forward-backward algorithm for hidden Markov mode

3、ls）; 3）貝葉斯網(wǎng)絡(luò)中的概率傳播（probability propagation in Bayesian networks）; 4）解碼算法：例如針對(duì)糾錯(cuò)碼的Viterbi 算法，BCJR算法等解碼算法； 例如針對(duì)turbo codes，LDPC codes等的循環(huán)解碼算法。,1. 因子圖（factor graph）： 1）典型代表FFG（Forney-style factor graph） FFG優(yōu)點(diǎn)：支持分層建模，兼容標(biāo)準(zhǔn)框圖； 以后都用FFG來描述; 2）FFG：代表對(duì)一個(gè)函數(shù)的因子分解（一個(gè)全局函數(shù)分解為若干個(gè)局部函數(shù)） 例：函數(shù)f(u, w, x, y, z) 可以分解成下面三個(gè)

4、因子式，其FFG如下圖所示。,3）FFG的定義規(guī)則 一般而言，F(xiàn)FG由結(jié)點(diǎn)，邊緣，半邊緣（只與一個(gè)結(jié)點(diǎn)連接）組成； FFG的定義規(guī)則如下： a) 每個(gè)因子對(duì)應(yīng)唯一的結(jié)點(diǎn)； b) 每個(gè)變量對(duì)應(yīng)唯一的邊緣或者半邊緣； c) 代表因子g的結(jié)點(diǎn)與代表變量x的邊緣（或半邊緣）相連，當(dāng)且僅當(dāng)g是關(guān)于x的函數(shù)。,例：在左圖中, 3個(gè)結(jié)點(diǎn)對(duì)應(yīng)3個(gè)因子 2個(gè)邊緣對(duì)應(yīng)2個(gè)變量 x, z; 3個(gè)半邊緣對(duì)應(yīng)3個(gè)變量 u, w, y;,割集獨(dú)立原理（Cut-Set Independence Theorem）: 假設(shè)一個(gè)FFG代表關(guān)于若干隨機(jī)變量的聯(lián)合概率分布（或聯(lián)合概率密度），進(jìn)一步假設(shè)對(duì)應(yīng)于其中一些變量 的邊緣組成了

5、一個(gè)割集（換言之，移除這些邊緣將圖表分割成了不相連的兩部分）。在這種情況下，以 （即任何確定值 ）為條件，一部分圖表中的每個(gè)隨機(jī)變量（或這些隨機(jī)變量組成的任意集合）與另一部分圖表中的每個(gè)隨機(jī)變量（或這些隨機(jī)變量組成的任意集合）都是相互獨(dú)立的。 例：下圖是一個(gè)表示一個(gè)馬爾可夫鏈的FFG。 變量x, y, z的聯(lián)合概率密度 若將邊緣Y移除，則圖表被分割成不相連的兩部分，運(yùn)用割集獨(dú)立原理，則有,FFG應(yīng)用舉例：線性狀態(tài)空間模型（linear state-space model） 注1：若假定U.和W.是高斯白噪聲過程，則圖表中的相應(yīng)結(jié)點(diǎn)就代表高斯概率分布函數(shù) （例：如果U.是個(gè)標(biāo)量，則左圖中最左上方

6、的結(jié)點(diǎn)就代表函數(shù) ） 注2：由此例可看出，在一個(gè)FFG中， “可見的”外部變量由半邊緣表示， “隱藏的”內(nèi)部變量由（全）邊 緣表示。 顯然，一個(gè)子系統(tǒng)的外部變量可能是整個(gè)大系統(tǒng)的內(nèi)部變量。,2. 和-積 算法（sum-product algorithm） 匯總傳播算法（summary propagation algorithm）: 和-積 算法（sum-product algorithm）； 最大值-積 算法（max-product algorithm）(or min-sum algorithm) 這里重點(diǎn)講述 和-積 算法； 和-積 算法的推導(dǎo)：由求解邊緣函數(shù)推導(dǎo)出和-積 算法 前面的例子說

7、明引入輔助變量（狀態(tài)變量）可以得到結(jié)構(gòu)更優(yōu)的模型， 現(xiàn)在我們考慮消除某些變量。 實(shí)際上，求解邊緣函數(shù)就是通過匯總運(yùn)算（”summary operator”）實(shí)現(xiàn)對(duì)變量的消除。,由求解邊緣函數(shù)推導(dǎo)出 和-積 算法： 例：假設(shè)函數(shù) f 可用如下左圖所示的FFG表示，即 考慮邊緣函數(shù)（邊緣概率） ，即 則 可用如下右圖所示公式表示。,求解邊緣函數(shù)的思路： 對(duì)內(nèi)部變量分別進(jìn)行匯總計(jì)算，“關(guān)閉”盒子（closing the box），即分塊消除內(nèi)部變量。 因子 ：對(duì)左圖中左邊虛線所圍盒子的內(nèi)部變量的信息匯總； 因子 ：對(duì)左圖中右邊虛線所圍小盒子的內(nèi)部變量的信息匯總； 因子 ：對(duì)左圖中右邊虛線所圍大盒子的

8、內(nèi)部變量的信息匯總； 最終，“關(guān)閉”所有盒子（即消掉了除 以外的其他所有內(nèi)部變量）之后， 得到 局部消除性質(zhì)（Local Elimination Property）： 一個(gè)全局的信息匯總（通過求和或者積分）可以由連續(xù)的子系統(tǒng)的局部信息匯總得到。,現(xiàn)在考慮信息的傳遞，如上圖所示，有三種情況： 從“關(guān)閉”盒子流出的信息：是盒子內(nèi)部的信息匯總； 從結(jié)點(diǎn)（例 ）流出的信息：是結(jié)點(diǎn)對(duì)應(yīng)的函數(shù)本身； 半邊緣（例 ）攜帶的信息：不攜帶任何信息，或者可認(rèn)為代表常數(shù)因子1；,由上面的分析可推得 和-積 算法 和-積 算法(sum-product rule)： 沿著邊緣x從結(jié)點(diǎn)（因子）g傳遞出的信息是g和沿著除x

9、以外其余所有邊緣傳入的信息的乘積，然后對(duì)除x以外其余所有相關(guān)變量進(jìn)行求和的結(jié)果。 即： 其中， 代表沿著邊緣 到達(dá)g的信息。,由sum-product rule計(jì)算邊緣函數(shù) ： 1） ，即邊緣概率為沿著邊緣 的兩個(gè)方向的信息的乘積； 2）對(duì)于所有k，邊緣函數(shù) 能夠同時(shí)得到； (分析：在非循環(huán)因子圖中，初始信息從葉子結(jié)點(diǎn)或半邊緣傳入，在兩個(gè) 方向上信息各傳遞一遍，因而所有邊緣對(duì)應(yīng)的邊緣概率都能同時(shí)得到),注： 1）和-積 算法 適用于任何非循環(huán)因子圖； 2）半邊緣（open half-edges）不攜帶任何的傳入信息，或者說攜帶的信息為常數(shù)因子1； 3）已知變量（例如前面提到的 ，可理解為常數(shù)）

10、只是簡單地融入相應(yīng)的因子，并不作為相關(guān)變量參與到算法中； 4）一般而言，得到正比于一個(gè)比例因子（up to a scale factor）的邊緣函數(shù) 就可以滿足需求，在這種情況下，信息只取決于一個(gè)比例因子。,補(bǔ)充： 最大值-積 算法（max-product rule）： 沿著邊緣x從結(jié)點(diǎn)（因子）傳遞出的信息是g和沿著除x以外其余所有邊緣傳入的信息的乘積，然后對(duì)除x以外其余所有相關(guān)變量進(jìn)行最大化的結(jié)果。 即： 實(shí)際上，sum-product rule和max-product rule都符合下面同一個(gè)規(guī)則： summary-product rule: 沿著邊緣x從結(jié)點(diǎn)（因子）傳遞出的信息是g和沿著

11、除x以外其余所有邊緣流入的信息的乘積，然后對(duì)除x以外其余所有相關(guān)變量進(jìn)行信息匯總的結(jié)果。 注：運(yùn)用這個(gè)規(guī)則的前提條件是因子圖沒有循環(huán)。,因子圖MATLAB程序 3.1 因子圖MATLAB程序設(shè)計(jì)流程 非循環(huán)因子圖： 1）instantiate nodes：即用唯一的整數(shù)標(biāo)注每一個(gè)結(jié)點(diǎn)，讓每一個(gè)結(jié)點(diǎn)擁有唯一的ID； 2）define connections：用setup_link()函數(shù)和connect()函數(shù)定義連接； 3）initialize parameters：例如對(duì)cpt_node的參數(shù)cpt進(jìn)行初始化，對(duì)Is_gain2_node的參數(shù)gain進(jìn)行初始化； 4）give eviden

12、t：通過setup_init_msg()函數(shù)給予結(jié)點(diǎn)(evident_node)相應(yīng)的已觀測(cè)事件的信息（這種信息稱為“evident”，承載這種信息的結(jié)點(diǎn)稱為“evident_node”）； 5）get marginal values：通過marginal()函數(shù)或者Is_marginal()函數(shù)計(jì)算得到邊緣概率。,循環(huán)因子圖： 1）初始化全局變量loopy，將其置為1； 2）對(duì)于線性標(biāo)量因子圖，初始化linear_scalar，將其置為1； 3）instantiate nodes：即用唯一的整數(shù)標(biāo)注每一個(gè)結(jié)點(diǎn)，讓每一個(gè)結(jié)點(diǎn)擁有唯一的ID； 4）define connections：用setu

13、p_link()函數(shù)和connect()函數(shù)定義連接； 5）initialize parameters：例如對(duì)cpt_node的參數(shù)cpt進(jìn)行初始化，對(duì)Is_gain2_node的參數(shù)gain進(jìn)行初始化； 6）give evident：通過setup_init_msg()函數(shù)給予結(jié)點(diǎn)(evident_node)相應(yīng)的已觀測(cè)事件的信息（這種信息稱為“evident”，承載這種信息的結(jié)點(diǎn)稱為“evident_node”）； 7）通過update_node()函數(shù)對(duì)每一個(gè)結(jié)點(diǎn)進(jìn)行更新； 8）通過設(shè)置迭代終止條件或者完成預(yù)設(shè)的迭代次數(shù)之后，終止更新。,3.2 具體實(shí)例應(yīng)用分析 1）因子圖測(cè)試程序（fa

14、ctor graph test）； 2）隱馬爾可夫鏈（hidden markov chain）; 3）卡爾曼濾波（kalman filtering）,程序段1 程序段2 程序段3,這是一個(gè)因子圖的測(cè)試程序，目的是實(shí)現(xiàn)偶校驗(yàn): 1）p, q, r, s四個(gè)結(jié)點(diǎn)都是代表相應(yīng)已觀測(cè)事件的evident_node （如前所述，這種結(jié)點(diǎn)只是為了承載相應(yīng)事件的觀測(cè)信息， 并非因子結(jié)點(diǎn)）； m, n二個(gè)因子結(jié)點(diǎn)都是偶校驗(yàn)結(jié)點(diǎn)(even_parity_node); 2）從程序段3和程序段4可以看出， 對(duì)p, q, r, s四個(gè)evident_node賦予的初始觀測(cè)信息為“0,0,1,0”， 即evidents

15、 ： p, q, r, s = 0,0,1,0時(shí)，計(jì)算每個(gè)邊緣對(duì)應(yīng)的邊緣概率； 3）從程序段5可以看出， 將q重置為1，即evidents：p, q, r, s = 0,1,1,0時(shí)，計(jì)算每個(gè)邊緣對(duì)應(yīng)的邊緣概率。,程序段4 程序段5,1）：factor graph test,程序運(yùn)行結(jié)果：,實(shí)驗(yàn)結(jié)果分析： 從邊緣概率來看， 1）在p, q, r, s=0,0,1,0時(shí)，link mn:0.5000,0.5000， 即上面兩個(gè)葉子結(jié)點(diǎn)的偶校驗(yàn)結(jié)果和下面兩個(gè)葉子結(jié)點(diǎn)的偶校驗(yàn)結(jié)果為1,0（或0,1）的概率相等，即上下兩部分偶校驗(yàn)的結(jié)果必然為：一個(gè)是偶數(shù)個(gè)1，另一個(gè)是奇數(shù)個(gè)1。 2）在p, q, r,

16、 s=0,1,1,0時(shí)，link mn:0.0460,0.9540 ，即上面和下面的偶檢驗(yàn)的結(jié)果都是1的可能性非常大（0.04600.9540），可判定為1，即上下都是奇數(shù)個(gè)1。 3）下圖以p, q, r, s =0,0,1,0 為例呈現(xiàn)了因子圖中的信息傳遞過程，即通過和-積算法計(jì)算邊緣概率。,2）：隱馬爾可夫鏈（hidden markov chain） 問題： 兩個(gè)朋友Alice 和 Bob，他們住的地方離彼此很遠(yuǎn)，每天通過電話告知對(duì)方當(dāng)天在做什么事情。Bob只對(duì)三種活動(dòng)感興趣：散步，購物，打掃。他選擇做什么主要取決于當(dāng)天的天氣。Alice對(duì)Bob那邊的天氣沒有確切消息，但是她知道一般的趨勢(shì)

17、?；贐ob告訴她的他當(dāng)天的活動(dòng)，Alice嘗試猜測(cè)Bob那邊的天氣如何。 顯然，Bob那邊的天氣情況可以用一個(gè)馬爾可夫鏈來表征。有兩種狀態(tài)， “Rainy” 和 “Sunny”, 因?yàn)锳lice不能直接觀察到，所以相當(dāng)于隱狀態(tài)（hidden state）。每一天，Bob都有一定的概率從事三種活動(dòng)中的某一種活動(dòng)：”walk”, ”shopping”, ”cleaning”。這些都是Bob告訴Alice的，因而都是觀察量。整個(gè)系統(tǒng)就可看作一個(gè)隱馬爾可夫模型（Hidden Markov Model, 即HMM）。 目標(biāo)：運(yùn)用和-積算法，通過觀察輸出值y，推斷隱狀態(tài)x，即求解邊緣概率P(x|y)。

18、definition of symbols % xn - the hidden variable of weather on Bob side % xn(1) - rain on the nth day % xn(2) - sunny on the nth day % yn - the observed variable % yn(1) - Bob walks on the nth day % yn(2) - Bob shops on the nth day % yn(3) - Bob cleans on the nth day,建立模型如下： x0-t1-x1-t2-x2.tn-xn-xn+

19、1 | | | e1 e2. en | | | y1 y2. yn,建立模型如下： x0-t1-x1-t2-x2.tn-xn-xn+1 | | | e1 e2. en | | | y1 y2. Yn 其中， ti代表狀態(tài)轉(zhuǎn)移概率結(jié)點(diǎn)， cptt：P(xi+1|xi)；ei代表觀察值的條件概率結(jié)點(diǎn)，cpte： P(yi|xi)。 求解思路： 在系統(tǒng)輸入觀察值yi的條件下，給x0,xn+1輸入初始化信息，整個(gè)系統(tǒng)同時(shí)進(jìn)行信息的前向-后向傳遞，就可得到相應(yīng)的邊緣概率，即后驗(yàn)概率P(xi|yi)。 顯然，所求的邊緣概率為邊緣ti-xi或者xi-ei所對(duì)應(yīng)的概率(xi是equ_node)。 注：由貝葉斯公式和馬爾可夫特性可知， P(xi|yi)=P(yi|xi)P(xi)/P(yi)= P(yi|xi)P(xi|xi-1)/P(yi) P(yi|xi)P(xi|xi-1),程序段1 程序段3,程序段2,程序段4 程序段5,實(shí)驗(yàn)結(jié)果分析: 實(shí)驗(yàn)首先對(duì)Bob 20天