一、概述

总的来说，推断的任务就是求概率。假如我们知道联合概率 $P(x)=P(x_{1},x_{2},\cdots ,x_{p})$ ，我们需要使用推断的方法来求：

$边缘概率：P(x_{i})=\sum_{x_{1}}\cdots\sum_{x_{i-1}} \sum_{x_{i+1}}\cdots \sum_{x_{p}}P(x)$
$条件概率：P(x_{A}|x_{B}),x=x_{A}\cup x_{B}$
$MAP\; Inference：\hat{z}=\underset{z}{argmax}P(z|x)\propto \underset{z}{argmax}P(z,x)$

以下是一些推断的方法：
①精确推断：
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（变量消除法）

变量消除法

图结构

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

$P(d)=\sum _{a,b,c}P(a,b,c,d)\\ =\underset{因子分解}{\underbrace{\sum _{a,b,c}P(a)P(b|a)P(c|b)P(d|c)}}\\ =\sum _{b,c}P(c|b)P(d|c)\underset{\phi _{a}(b)}{\underbrace{\sum _{a}P(a)P(b|a)}}\\ =\sum _{c}P(d|c)\underset{\phi _{b}(c)}{\underbrace{\sum _{b}P(c|b)\phi _{a}(b)}}\\ =\sum _{c}P(d|c)\phi _{b}(c)\\ =\phi _{c}(d)$

解释

我们可以通过观察直接将 $P(d)$ 展开计算的形式来理解变量消除法的作用。首先我们假设 $a$ ， $b$ ， $c$ ， $d$ 都是离散的二值随机变量，只能取 $0$ 和 $1$ 两个值，然后直接将 $P(d)$ 展开：

$P(d)=\sum _{a,b,c}P(a,b,c,d)\\ =\sum _{a,b,c}P(a)P(b|a)P(c|b)P(d|c)\\ =P(a=0)P(b=0|a=0)P(c=0|b=0)P(d|c=0)\\ +P(a=0)P(b=0|a=0)P(c=1|b=0)P(d|c=1)\\ +P(a=0)P(b=1|a=0)P(c=0|b=1)P(d|c=0)\\ +P(a=0)P(b=1|a=0)P(c=1|b=1)P(d|c=1)\\ +P(a=1)P(b=0|a=1)P(c=0|b=0)P(d|c=0)\\ +P(a=1)P(b=0|a=1)P(c=1|b=0)P(d|c=1)\\ +P(a=1)P(b=1|a=1)P(c=0|b=1)P(d|c=0)\\ +P(a=1)P(b=1|a=1)P(c=1|b=1)P(d|c=1)\\ =8\cdot 因子积$

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

$P(d)=\\ (将与a有关的放到一起)\\ ={\color{Red}{P(c=0|b=0)P(d|c=0)\cdot P(a=0)P(b=0|a=0)}}\\ +{\color{Green}{P(c=1|b=0)P(d|c=1)\cdot P(a=0)P(b=0|a=0)}}\\ +{\color{Blue}{P(c=0|b=1)P(d|c=0)\cdot P(a=0)P(b=1|a=0)}}\\ +{\color{Yellow}{P(c=1|b=1)P(d|c=1)\cdot P(a=0)P(b=1|a=0)}}\\ +{\color{Red}{P(c=0|b=0)P(d|c=0)\cdot P(a=1)P(b=0|a=1)}}\\ +{\color{Green}{P(c=1|b=0)P(d|c=1)\cdot P(a=1)P(b=0|a=1)}}\\ +{\color{Blue}{P(c=0|b=1)P(d|c=0)\cdot P(a=1)P(b=1|a=1)}}\\ +{\color{Yellow}{P(c=1|b=1)P(d|c=1)\cdot P(a=1)P(b=1|a=1)}}\\ (应用乘法分配律)\\ ={\color{Red}{P(c=0|b=0)P(d|c=0)\cdot \phi _{a}(b=0)}}\\ +{\color{Green}{P(c=1|b=0)P(d|c=1)\cdot \phi _{a}(b=0)}}\\ +{\color{Blue}{P(c=0|b=1)P(d|c=0)\cdot \phi _{a}(b=1)}}\\ +{\color{Yellow}{P(c=1|b=1)P(d|c=1)\cdot \phi _{a}(b=1)}}\\ (将与b有关的放到一起)\\ ={\color{Red}{P(d|c=0)\cdot P(c=0|b=0)\phi _{a}(b=0)}}\\ +{\color{Green}{P(d|c=1)\cdot P(c=1|b=0)\phi _{a}(b=0)}}\\ +{\color{Red}{P(d|c=0)\cdot P(c=0|b=1)\phi _{a}(b=1)}}\\ +{\color{Green}{P(d|c=1)\cdot P(c=1|b=1)\phi _{a}(b=1)}}\\ (应用乘法分配律)\\ ={\color{Red}{P(d|c=0)\cdot \phi _{b}(c=0)}}\\ +{\color{Green}{P(d|c=1)\cdot \phi _{b}(c=1)}}\\ =\phi _{c}(d)$

缺点

变量消除的缺点很明显：
①计算步骤⽆法存储：每次计算一个边缘概率就要重新计算一遍整个图；
②消除的最优次序是⼀个NP-hard问题：对于复杂的图来说，想要找到一个最优的消除次序是困难的。

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

Variable Elimination算法的计算重复问题

对于以下图结构：

马尔可夫链

已知联合概率：

$P(a,b,c,d,e)=P(a)P(b|a)P(c|b)P(d|c)P(e|d)$

我们在计算 $e$ 的边缘概率时，使用变量消除法的步骤如下：

$P(e)=\sum_{a,b,c,d}P(a,b,c,d,e)\\ =\sum_{a,b,c,d}P(a)P(b|a)P(c|b)P(d|c)P(e|d)\\ =\underset{m_{d\rightarrow e}(e)}{\underbrace{\sum_{d}P(e|d)\underset{m_{c\rightarrow d}(d)}{\underbrace{\sum_{c}P(d|c)\underset{m_{b\rightarrow c}(c)}{\underbrace{\sum_{b}P(c|b)\underset{m_{a\rightarrow b}(b)}{\underbrace{\sum_{a}P(b|a)P(a)}}}}}}}}$

我们在计算 $c$ 的边缘概率时，使用变量消除法的步骤如下：

$P(c)=\sum_{a,b,d,e}P(a,b,c,d,e)\\ =\sum_{a,b,d,e}P(a)P(b|a)P(c|b)P(d|c)P(e|d)\\ =(\sum_{b}P(c|b)\sum_{a}P(b|a)P(a))\cdot (\sum_{c}P(d|c)\sum_{d}P(e|d))$

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

Belief Propagation的引出

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

无向树

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

$P(a,b,c,d)=\frac{1}{Z}\psi _{a}(a)\psi _{b}(b)\psi _{c}(c)\psi _{d}(d)\cdot \psi _{ab}(a,b) \psi _{bc}(b,c) \psi _{bd}(b,d)$

我们要求解边缘概率 $P(a)$ ，也要应用到变量消除法，大体步骤是先消去 $c$ 和 $d$ ，然后再消去 $b$ ，该过程如下所示：

$p(a)=\psi _{a}\underset{m_{b\rightarrow a}(a)}{\underbrace{\sum _{b}\psi _{b}\cdot \psi _{ab}(\underset{m_{c\rightarrow b}(b)}{\underbrace{\sum _{c}\psi _{c}\cdot \psi _{bc}}})(\underset{m_{d\rightarrow b}(b)}{\underbrace{\sum _{d}\psi _{d}\cdot \psi _{bd}}})}}$

我们可以看到求解的过程主要就是求以下两项（这里写得规范一些，比如 $a$ 写作 $x_a$ ）：

$\left\{\begin{matrix} m_{b\rightarrow a}(x_{a})=\sum _{x_{b}}\psi _{ab}\cdot \psi _{b}\cdot m_{c\rightarrow b}(x_{b})\cdot m_{d\rightarrow b}(x_{b})\\ p(x_{a})=\psi _{a}\cdot m_{b\rightarrow a}(x_{a}) \end{matrix}\right.$

现在我们可以将求解 $x_{a}$ 边缘概率的过程抽象出来得到求解 $x_{i}$ 边缘概率的过程：

$\left\{\begin{matrix} m_{j\rightarrow i}(x_{i})=\sum _{x_{j}}\psi _{ij}\cdot \psi _{j}\cdot \prod _{k\in Neighbor(j)-i}m_{k\rightarrow j}(x_{j})\\ p(x_{i})=\psi _{i}\cdot \prod _{k\in Neighbor(j)} m_{k\rightarrow i}(x_{i}) \end{matrix}\right.$

我们可以继续观察求解 $x_{i}$ 边缘概率的公式，并对一些部分做一下定义：

$\left\{\begin{matrix} m_{j\rightarrow i}(x_{i})=\sum _{x_{j}}\psi _{ij}\cdot\underset{belief(x_{j})}{ \underbrace{\underset{self}{\underbrace{\psi _{j}}}\cdot \underset{children}{\underbrace{\prod _{k\in Neighbor(j)-i}m_{k\rightarrow j}(x_{j})}}}}\\ p(x_{i})=\psi _{i}\cdot \prod _{k\in Neighbor(j)} m_{k\rightarrow i}(x_{i}) \end{matrix}\right.$

因此求解 $m_{j\rightarrow i}(x_{i})$ 需要两步：

$\left\{\begin{matrix} belief(x_{j})=self\cdot children\\ m_{j\rightarrow i}(x_{i})=\sum _{x_{j}}\psi _{ij}\cdot belief(x_{j}) \end{matrix}\right.$

如图展示了求解 $x_{a}$ 的边缘概率的消去（信息传递）过程：

信息传递

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

Belief Propagation

Belief Propagation算法的思想是：

不要直接求 $P(a)$ 、 $P(b)$ 、 $P(c)$ 、 $P(d)$ ，只需求所有的 $m_{j\rightarrow i}$ 。

Belief Propagation算法首先求所有的信息传递（收集或分发）的过程得到所有的 $m_{j\rightarrow i}$ （图的遍历），然后套用公式计算边缘概率，总的来说也就是 $BP=VE+Caching$ ：

Belief Propagation算法的信息传递

Belief Propagation算法遍历图的一种方法（Sequential Implementation）如下：
①Get root，assume a is root;
②Collect Message:

for $x_i$ in Neighbor(Root):
collectMsg( $x_i$ )

③Distribute Message:

for $x_i$ in Neighbor(Root):
distributeMsg( $x_i$ )

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

Max-product

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

仍然拿以下图结构来举例，只画出了要求解的节点（ $a$ ， $b$ ， $c$ ， $d$ ），其他节点（ $E$ ）未画出：

无向树

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

$(x_{a}^{*},x_{b}^{*},x_{c}^{*},x_{d}^{*})=\underset{x_{a},x_{b},x_{c},x_{d}}{argmax}\; P(x_{a},x_{b},x_{c},x_{d}|E)$

求解过程如下：

$①\; m_{c\rightarrow b} =\underset{x_{c}}{max}\; \psi _{c}\cdot \psi _{bc}\\ ②\; m_{d\rightarrow b} =\underset{x_{d}}{max}\; \psi _{d}\cdot \psi _{bd}\\ ③\; m_{b\rightarrow a} =\underset{x_{b}}{max}\; \psi _{b}\cdot \psi _{ab}\cdot m_{c\rightarrow b}\cdot m_{d\rightarrow b}\\ ④\; max\; P(x_{a},x_{b},x_{c},x_{d})=\underset{x_{a}}{max}\; \psi _{a}\cdot m_{b\rightarrow a}$

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

信息传递

与Sum-product不同的是，在求解 $max\; P(x_{a},x_{b},x_{c},x_{d})$ 这个过程中我们不需要求 $m_{a\rightarrow b}$ 、 $m_{b\rightarrow c}$ 、 $m_{b\rightarrow d}$ ，因为我们需要的是 $max\; P(x_{a},x_{b},x_{c},x_{d})$ 概率的值和 $x_{a}^{*}$ ， $x_{b}^{*}$ ， $x_{c}^{*}$ ， $x_{d}^{*}$ 这个序列。