一、概述

总的来说，推断的任务就是求概率。假如我们知道联合概率

，我们需要使用推断的方法来求：

以下是一些推断的方法：

①精确推断：

Variable Elimination(VE,变量消除法)(针对树结构)；

Belief Propagation(BP,信念传播,Sum-Product Algo)(针对树结构)；

Junction Tree Algorithm(针对图结构)

②近似推断：

Loop Belief Propagation(针对有环图)；

Mente Carlo Inference(例如Importance Sampling,MCMC)；

Variational Inference

二、Variable Elimination（变量消除法）

1. 变量消除法

                                                            图结构

对于上述图结构，假如我们希望求边缘概率 ，我们就可以应用变量消除法：

2. 解释

如果直接计算上式中的每一项再加起来就会需要相当大的计算量，而且上式只是每个变量都是二值变量的情况下，如果每个变量能取更多的值就会有更大的计算量。变量消除法就是根据某些节点只与图中自己的邻接节点有关这一特性来简化计算，相当于应用了乘法分配律 来避免计算每一项在加起来。变量消除法在上式中的计算过程为：

3. 缺点

变量消除的缺点很明显：

①计算步骤⽆法存储：每次计算一个边缘概率就要重新计算一遍整个图；

②消除的最优次序是⼀个NP-hard问题：对于复杂的图来说，想要找到一个最优的消除次序是困难的。

三、Belief Propagation（信念传播算法）

1. Variable Elimination算法的计算重复问题

对于以下图结构：

                                          马尔可夫链

已知联合概率：

我们发现在计算 的边缘概率时的前一部分与在计算 的边缘概率时的一部分重复了，可以想象在求其他边缘概率的分布时也会有大量的重复，而Belief Propagation算法就是来解决这个问题。

2. Belief Propagation的引出

上面我们一直计算的是有向图的马尔可夫链，现在我们将问题从链结构引申到树结构，从有向图引申到无向图（Belief Propagation只针对树状结构）。举例来说，有如下无向树：

                                               无向树

现在我们知道该联合概率的因子分解可以写为：

                                               信息传递

可以想象，在求其他边缘概率时势必会有很多重复的消去过程，但是由于我们已经有了计算 的通项，我们就可以利用这个公式来消除计算上的重复，而Belief Propagation算法正是利用了这个通项解决了这个问题。

3. Belief Propagation

Belief Propagation算法的思想是：

Belief Propagation算法首先求所有的信息传递（收集或分发）的过程得到所有的 （图的遍历），然后套用公式计算边缘概率，总的来说也就是

                  Belief Propagation算法的信息传递

Belief Propagation算法遍历图的一种方法（Sequential Implementation）如下：

①Get root，assume a is root;

②Collect Message:

③Distribute Message:

还有另外一种遍历的方法（Parellel Implementation），这是一种应用在分布式计算中的方法，可以并行计算，这里不做过多介绍。

4. Max-product

事实上，信念传播算法分为Max-product和 Sum-product，上面讲的属于Sum-product，与Sum-product不同的是Max-product只需要将把求和符号换成求最大值 的符号即可。Max-product是 Sum-Product算法的改进，也是在HMM中应用到的 Viterbi算法的推⼴。

 

                                                  无向树

Max-product的作用是用来求一个序列来使得后验概率最大，也就是：

求解过程如下：

这里也进行了一次类似收集信息的过程：

                                          信息传递

四、概念补充

1. 道德图

我们常常想将有向图转为⽆向图，从⽽应⽤更⼀般的表达式。对于有向图中的三种结构，有不同的转换方法：

• 链式（head to tail）

              head to tail

这说明A，B和B，C是团，因此可以直接去掉箭头：

                       无向图

• V形（tail to tail）

                            tail to tail

这说明A，B和B，C是团，因此可以直接去掉箭头：

                      无向图

• 倒V形（head to head）

                              head to head

这说明A，B，C是一个团，需要在A，C之间加一条线：

               无向图

观察这三种情况可以将有向图到无向图的转换方法的步骤概括为：

①将每个节点的⽗节点两两相连

②将有向边替换为⽆向边

得到的无向图就是道德图。

2. 因子图
3. 
   

对于⼀个有向图，可以通过引⼊环的⽅式，可以将其转换为⽆向图（Tree-like graph），这个图就叫做道德图。但是我们上⾯的 BP 算法只对⽆环图有效，通过因⼦图可以变为⽆环图。

联合概率的因子图分解方法为：

其中：

有以下无向图：

                       无向图

可以将其转换成一个简单的因子图：

                        因子图

因子图不是唯一的，可以看做对因子分解的进一步分解，比如以下分解：

                             因子图

                                                          分层

也就是说因子图可以做到随机变量节点之间不直接相连，只与因子节点相连，因子节点只与变量节点相连。