Belief Propagation

        Belief propagation是Machine learning泰斗—J. Pearl最重要的贡献。对于统计学来说，它最重要的意义在于提出了一种很有效的求解条件边缘概率（Conditional marginal probability）的方法。所谓求解条件边缘概率，通俗地说，就是在已知某些条件的情况下，推导另外某些事件发生的概率。如果涉及的因素只有几个，可以使用简单的概率公式计算。但现实世界中有成千上万的因素，它们相互联系，如按照传统方法，就要对数以千计的变量进行积分。考虑到运算量对于变量个数以指数增长，故实际中根本无法计算。尽管后来人们提出了蒙特卡罗（Monte Carlo）积分，但对于拥有数以千计变量的复杂系统，仍然可是computationally prohibitive。
        这个困难一直阻碍着统计推断方法在大规模系统中的应用。Belief propagation提出后，情况才发生了转变。J. Pearl在其书中分析，人们在头脑中经常进行各种各样的推断，可大脑里面发生了什么事情呢：穷举所有未知变量的可能状态进行积分（Traditional method）？还是随即产生各种状态求均值（Monte Carlo Integral），看来都不make sense。J. Pearl认为，虽然影响世界的因素繁多，但是每个因素实际上只与少数几个因素相关，这就构成了一个推断网络。在Machine learning中，这种推断网络有两种：Bayesian Network，反映的是因果推断关系（即，相互联系的因素中，其中一个是因，另一个是果），以及Markov Network， 反映的是相互影响的关系（两个因素互为因果，其变化相互影响）。根据这种建模方式，J.Pearl提出把inference局部化和分布化，把全局的积分变成局部的消息传递。网络中的每个节点通过和邻近节点交换信息对自身的概率状况进行评估。通过这种方式，使得计算量从指数增长变成近似线性增长，从而使得统计推断能在复杂系统中被应用。
        数学上可以证明，对于有向无环的Bayesian Network，通过BP得到的解和严格的积分计算得到的结果是一致的。这时的BP只是利用因素联系的局部性来简化计算，并把计算过程分散到各个节点。对于无向而且到处是环的Markov network，J.Pearl指出，这种传播过程可能导致不稳定。某些消息可能在环状的传播过程中无限加强，从而导致整个系统发散或偏离。但实际经验表明，对于大部分问题，BP在带环的系统中依然工作良好。很多人对这个现象进行了研究，对于某些特例给出了初步的解释，但是关于Loopy BP的稳定性以及收敛性问题，离理论上的最终解决，还有很长的路要走。
        在Computer vision领域，MIT的著名教授W.T. Freeman是BP方法的积极倡导者，他大量使用Markov random field和Belief propagation对图像进行建模，在很多应用领域取得了不错的结果。