这几天准备的Reading List

1. Classical Probabilistic Models and Conditional Random Field, K. Roman et al,
http://www.scai.fraunhofer.de/fileadmin/images/bio/data_mining/paper/crf_klinger_tomanek.pdf
2. A Tutorial Introduction to Belief Propagation (crv09), James Coughlan
http://computerrobotvision.org/2009/tutorial_day/crv09_belief_propagation_v2.pdf
3. Understanding Belief Propagation and its Generalizations, Weiss,
http://portal.acm.org/citation.cfm?id=779352
4. Efficient Belief Propagation for Early Vision, PEDRO F. FELZENSZWALB and DANIEL P. HUTTENLOCHER,
http://www.cs.cornell.edu/~dph/papers/bp-cvpr.pdf
5. Fractional Belief Propagation (NIPS02), W. Wiegerinck et al.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.8426
6. Nonparametric Belief Propagation, Erik B. Sudderth et al.
http://ssg.mit.edu/~esuddert/papers/cvpr03.pdf
7. Data Driven Mean-Shift Belief Propagation For non-Gaussian MRFs(CVPR10), Minwoo Park et al.
http://vision.cse.psu.edu/paper/CVPR2010DDMSBP0291.pdf
8. A Constant-Space Belief Propagation Algorithm for Stereo Matching(CVPR10), Qingxiong Yang et al.
http://vision.ai.uiuc.edu/~qyang6/publications/cvpr-10-qingxiong-yang-csbp.pdf
9. Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing(UAI06), G Elidan et al.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.1828

这两天读完了前三篇，对BP和Graphical Model的理解比原来更清楚了，我简单写了一点总结。以下：

第一篇是一个Techinical Report，主要介绍了Graphical Model的一般概念，以及四种常见的Graphical Model和它们之间的相互关系。这几种Model分别为Naive Bayes Model, HMM Model, Maximum Entropy Model, Conditional Random Field. HMM是序列化的Naive Bayes，它们都属于Generative Model；而条件随机场则是序列化的最大熵模型，它们都属于判别模型（Discriminate Model）。生成模型和判别模型之间的区别在这里也有介绍。文章详细介绍了前三种模型的推导过程。在推导最大熵模型的时候，本文仅给出了最大熵模型对应的最优条件概率分布，但是没有指明Feature Function的权值lambda如何求。其实在这一点上，最大熵模型的求解非常类似SVM的最优话Margin的过程，在参数估计的时候用到的都是拉格朗日对偶式（Lagrange Duality）和凸优化的知识，具体参数求解过程可参考SVM的推导过程（Stanford CS229课程讲义）。

然后本文介绍了Graphical Model的分类（Undirected和Directed）。很显然NB和HMM属于有向图，而 Undirected Graphical Model我理解其实就是Markov Random Field。另外Factor Graph在文章中也有介绍，但是更详细的如何构造Factor Graph以及如何在Factor Graph和Bayes Network或MRF之间转换则在第三篇文章中有论述。还有一点，MRF也是表征一个Joint Distribution，CRF对应的是表征一个Conditional Distribution；MRF我理解其实是一个二维的HMM，CRF则是一个二维的Linear CRF。。。是不是很别扭。。不过应该是这样的。

本文的后半部分集中讨论了CRF，主要是Linear CRF的构造，训练，和推理。Linear CRF (L-CRF)的构造表征的是，给定一组Observation之后的一个隐藏变量序列的概率。L-CRF与HMM的区别是，L-CRF是对一个条件概率建模，而 HMM是对一个联合概率建模；而且HMM要求当前的Observation只和当前的Hidden Variable相关，而与其它Hidden Variabl是条件独立的，即别的时刻的隐藏变量不影响我当前的观测结果。但是L-CRF 放松了这一要求，允许更多的dependency出现，模型更加灵活。构建模型之前，L-CRF被转换成Factor Graph，每一个Factor都是一组特征函数的线性组合之后的指数形式，这一点与最大熵模型类似。本文讨论的训练L-CRF模型的方法是MAP方法，与MLE的区别是增加了一个关于参数lambda的先验分布，用来避免 overfitting的情况。而在进行推理时，本文采用的是与HMM中相同的Viterbi算法，用于求出给定 Observation后最可能的一个隐藏序列。其实我感觉BP算法的max-product版本和Viterbi算法非常类似。

第二篇是BP算法的一个Tutorial，主要重点如下：

第一，对于Factor的理解。在一个Bayes Network或者HMM等Directed Graphical Model中，Factor可以理解成各个变量节点的条件概率分布，我认为在这里可以理解成，一个factor对应于一个节点的CPT（条件概率表）；但是在MRF等Undirected Graphical Model中，节点之间没有明确的条件概率关系，这时候Factor就可以理解成是一个关于若干变量的Compatibility Function，可以理解成描述节点之间的相互作用或者节点本身的特性。比如在MRF中，我的理解是，每个节点都是被两种因素影响，一个是和周围neighbor节点们的相互作用，另一个是节点本身的“势能”，也即Hidden Variable和对应Observed Variable之间的相互关系，因为观测值是已知的，所以可以把它们之间的相互关系类比成一种“势能”。

第二，明确了研究MRF或者Bayes Nets的目的，即求隐藏变量的Marginalized Probability和求使一个联合分布最大化的一组隐藏变量的取值。

第三，介绍的BP的基本形式，是一种Messsage Passing算法，本质即是通过不断地迭代求局部最佳值来最终获得全局的一组变量取值。如果图结构中不存在环（loop），则 BP算法是确定推理；若存在环结构，则BP算法成为一种近似推理。我对此的理解是，如果不存在环，则这张图一定存在若干“入口”（比如Bayes Nets的Root节点们），可先从这些“入口”节点入手，求出这些节点对应的Belief，然后将这些Belief 顺次传递message给其它节点；但是如果图结构中有环，则必须首先随机初始化所有message，然后通过迭代的方法求出最终解。那么这样看的话，BP算法和其它很多Gradient Descent算法（如EM，Hill Climbing算法等）共同的问题就是无法保证一定会获得全局最优解，而且这些迭代算法本身需要的迭代时间也会比较长。所以这样就有两个BP算法的研究方向，一个是如何保证或者尽量求得全局最优解，一个是如何减少迭代计算的开销。

具体的Belief计算方法和Message更新算法我省略掉，可以参考原文，实现起来应该不是太复杂。本文最后给出的一个例子就是利用BP算法解决Stereo Matching，以及若干改进建议。

第三篇文章是Weiss的一个technical report，引用次数很高。这篇文章侧重于揭示BP算法的本质，用热力学中的模型和概率图模型进行类比，说明了BP算法的物理意义。本文的讨论主要基于Pairwise Markov Random Field，由一个stereo matching的例子引出了其基本模型。这篇文章详细说明了如何将Pairwise MRF、Bayes Nets和Factor Graph之间的相互转换，并最终在MRF上对BP算法进行讨论，这样的好处是，MRF是无向的，而且Message Upadate只有一种形式（与Factor Graph不同）。

一个节点的Belief由以下因素决定：节点本身的Local Evidence（即该节点和对应的观测变量之间的关系，用Compatibility Function表示）；该节点的neighbor节点向这个节点传送的message的乘积。Message的更新函数也类似：由节点i向节点j传送的message由不包括j的和节点i相邻的节点向节点i发送的message之积，节点i本身的特性（Local Evidence），以及节点i和节点j之间的相互关系共同决定。文章稍后给出了更一般的形式，即message的更新其实是节点belief的marginalization的过程，即bi = sigma(j)bij。更一般地，文章还给出了多节点Belief的形式及其message如何更新，这个是后面文章所讲的GBP（Generalized Belief Propagation）的基础。

这篇文章另一个重点是讨论了热力学的几个能量模型及它们和BP/GBP算法之间的对应关系。文章首先介绍了玻尔兹曼定律，即系统的均衡分布由系统的能量状态和温度共同决定。接下来，根据不同的assumption，作者讨论了两种形式的自由能，即Mean-Field Free Energy和Bethe Free Energy。其中，后者假定Gibbs自由能下的Belief满足Normalization Condition以及Marginalization Condition，因而BP算法和Bethe Approximation是等价的。

最后，本文讨论了Generalized Belief Propagation。这是与物理学中Kikuchi Approximation等价的，可以看作是Bethe Approximation的一种扩展形式。具体细节参见原文，其主要思想是，将一个graph分成不同的region以及它们的sub-region，并由这些cluster构造一个新的graph，在这个新构造的graph上进行BP算法（用到之前介绍的多节点的BP形式），这样做的好处是，推理过程中图的节点数量变少了，而且多节点的Belief形式比单个节点的Belief表达信息要多，所以效果应该会更好。