Factor graph 模型的前提知識有哪些？

學了一陣子factor graph模型以及belief propagation 演算法，還不是特別明白。覺得自己需要補一補一些前提知識。所以請問它的前提知識是哪些？Bayesian network 還有基本的graph model的理論是不是要掌握？除此之外還有哪些？謝謝

factor graph是Graphical Model的基礎之一。

不知道題主具體是哪裡不明白，但是一般Graphical Model的基礎課程，都會把factor graph講清楚，所以如果不明白可以查一查常用的基礎課程。比如Daphne Koller的課，coursera上有這門課https://zh.coursera.org/course/pgm 。

另外推薦一本書：Bayesian Reasoning and Machine Learninghttp://web4.cs.ucl.ac.uk/staff/D.Barber/textbook/181115.pdf 這本書思路清楚，講解方式也非常易讀。裡面對於Factor graph也有非常清晰的介紹。

factor graph是圖模型，message passing是需要基於factor graph的拓撲結構設計的演算法。這玩意有什麼用呢？典型應用是做marginalization。

舉個例子啊。假設我需要推算10000個用戶每個人買我的產品的後驗概率，有時候我們容易得到10000個人的joint posterior，但要想賣東西我們需要邊緣概率密度。積分掉9999個人是不現實的。

Factor graphs and the sum-product algorithm裡面的一個子問題，只看一個子問題就行。四個小問。

1）如何把state space model表達成一個factor graph？

決定於你用factor graph 的目的，需要的知識可能不一樣。看你的問題，你似乎主要專註於 belief propagation (也叫 sum-product algorithm) 這一種演算法的理解、實現。如果是這樣，需要的知識並不多。準確的說，理解belief propagation 你只需要知道加法和乘法，以及乘法分配律 ，這個咱們小學就學過啦。

從本質上說，belief propagation 只是乘法分配律的一個巧妙應用。乘法分配律的公式說，

公式左邊用到兩次乘法運算和一次加法運算，而公式右邊只用到一次加法和一次乘法。belief propagation 說到底就是在做這類計算的時候通過乘法分配律把乘法運算盡量往後推，把加法運算盡量提前，從而提高效率。通常用 belief propagation 的時候，我們是要計算一大堆這樣的表達式（即某個函數在它所涉及到的每個變數上的 marginal），而這些計算這些表達式之間有大量的重複計算。belief propagation 通過在圖上傳message 有效地避免了重複計算。

當然如果你是準備用factor graph and belief propagation 來做推斷（inference), 你必須有概率論的基礎知識。

如果你感興趣belief propagation 的其他泛化形式，這裡大致有兩個角度。

1）基於乘法分配律的泛化。實際上不止加法和乘法之間存在分配律。這種分配律可以泛化到其他形式的「加法」和「乘法」上。這就會引出一些其他的演算法，比如 max-product, 也叫belief revision. 著名的 Viterbi algorithm 可以理解為它的一個特例。理解這個需要簡單的代數知識。

2）基於free energy approximation 的泛化。一個角度理解 belief propagation （特別是當圖上有 cycle 的時候）是把它看作優化一種 free energy 的approximation. 通過定義不同形式的free energy approximation, 可以引出一系列演算法，叫做generalized belief propagation. 理解這類文獻需要一些統計物理的知識。

參考文獻：

Kschischang et al, "Factor graphs and the sum-product algorithm", http://vision.unipv.it/IA2/Factor%20graphs%20and%20the%20sum-product%20algorithm.pdf

Aji and McEliece, "Generalized distributive law", http://gladstone.systems.caltech.edu/EE/Courses/EE127/EE127A/handout/GDL.pdf

Yeddidia et al, "Constructing free energy approximation and generalized belief propagation",

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

最近在讀眾包里的用到factor graph 的 paper，mark一下。