機率圖模型推斷之Belief Propagation

初步打算把機率圖模型中推斷方法都介紹一下，包括Belief Propagation，變分方法，MCMC，以及像是Graph cut也做一些說明。

關于Belief Propagation是什麼?

Belief Propagation是一種資訊傳遞方法，一般用來解關于機率圖模型中的推斷問題，在這些問題中，單純地通過公式推導或者MC模拟是很難得到準确答案的，這就需要BP，能夠很有效地求解一些特定問題得邊緣機率。

首先說明一下為什麼邊緣機率如此難求，wiki上的例子：

X={xi} 是一個離散的随機變量集合，并且其聯合機率是 p ,關于某個變量的邊緣機率就是對于所有其他變量的一個求和

pXi(xi)=∑x′:x′i=xip(x′)

但是這個求和會随着變量的增多而變得呈指數增長，假設說有100個二進制變量，每個可以取01，那樣所需要的求和次數就是 299∼6.338×1029 ,BP能夠充分利用資料結構資訊，讓計算變得很簡便。像是以前學得動态規劃解決最短路徑，以及維特比方法求HMM的Hidden state的機率，都是用了BP的思想。

說道動态規劃(Dynamic programing)，可能大家都很熟悉，DP的主要思想就是構造最有子空間，把求解一個大問題分解成求解一系列的小問題，BP也是這個思想，BP利用了局部分消息傳遞，把計算全局的求和或者積分，轉換成了局部的消息傳遞，每個節點都能都過自身的狀态以及鄰近節點的狀态做出評價，得到自身的下一狀态，不斷地更新最終使系統達到穩定。

下面以MRF上的Belief Propagation為例來介紹BP是如何求解MRF中的Inference問題的。

一般一個MRF問題都可以表述成這樣的形式：

p({x})=1Z∏(i,j)ψi,j(xi,xj)∏iϕi(xi)

ϕi(xi) 一般是為了簡略，原本應該是 ϕi(xi,yi) 的形式， yi 是可測變量，觀察變量， xi 是hidden node，不可測的，一般 yi 的不可變，是以将其省略,而 xi 卻又很多種可能，例如很多可能性标簽，等等，一般用個 L 維的向量來表示。在BP中，不同的Hidden node之間（一般指有鄰接關系的）是通過message來傳遞消息的，這樣我們定義一個message變量mij(xj)，來表示從節點 i 向節點j傳遞的一個消息，也可以傳遞的belief，對于 xj 可能性的度量，

參考：

【1】http://en.wikipedia.org/wiki/Belief_propagation

【2】http://blog.sina.com.cn/s/blog_4dfdfdc30100q2el.html

【3】Jonathan S. Yedidia, William T. Freeman, and Yair Weiss, “Understanding Belief Propagation and Its Generalizations” in Exploring Artificial Intelligence in the New Millennium, Lakemeyer, G. and Nebel, B., Eds., ISBN: 1-55860-811-7, chapter 8, pp. 239-236, Morgan Kaufmann Publishers, January 2003

【5】Constructing Free Energy Approximations and Generalized Belief Propagation Algorithms

http://www.cs.princeton.edu/courses/archive/spr06/cos598C/papers/YedidaFreemanWeiss2004.pdf