概率图模型之精确推断

引入

通过概率图模型我们得到了定义的联合概率分布，通过联合概率分布我们一般可以计算变量的边际概率分布（积分或求和消去其他变量）和条件概率分布（概率的乘法公式），其中计算条件概率分布的过程即对应推断任务。
在推断任务中我们是假定图结构固定已知，然而有一类问题则需要我们从数据出发而推断图本身，即结构学习（structure learning）。一般图结构学习均采用贪心搜索的策略，即定义⼀个可能结构的空间和用于对每个结构评分的度量，通过评分奖励精度高的结构，同时对结构的复杂度做出惩罚，然后添加或移除少量边进行下一步搜索。
同时由于图结构的复杂度随结点数目的增加而呈指数增长，因此我们需要借助启发式的方法。根据贝叶斯学派的观点，基于数据D推断合理的图模型M，其本质是在求解后验概率估计 P(M|D) ，因此图结构的学习过程也即推断过程。

概率图模型的推断方法大致可分为两类：第一类是精确推断方法，希望能计算出目标变量的边际分布或者条件分布的精确值；遗憾的是，一般情况下，此类方法的计算复杂度随着极大团规模的增长呈指数增长，适用范围有限。第二类是近似推断方法，希望在较低的时间复杂度下获得愿问题的近似解；此类方法在现实任务中更加常用。
本节主要介绍精确推断方法。

变量消去法

精确推断的实质是一类动态规划算法，他利用图模型所描述的条件独立性来消减计算目标概率值所需的计算量。变量消去法是最直观的精确推断算法。也是构建其他精准推断算法的基础。
我们以下图为例来介绍

假定推断目标是计算边际概率 $P(x_5)$P(x5​)。显然，为了完成此目标，需要通过加法消去变量$x_1,x_2,x_3,x_4$x1​,x2​,x3​,x4​即：
$P(x_5)=\sum_{x_4}\sum_{x_3}\sum_{x_2}\sum_{x_1}P(x_1,x_2,x_3,x_4,x_5)$P(x5​)=∑x4​​∑x3​​∑x2​​∑x1​​P(x1​,x2​,x3​,x4​,x5​)

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=\sum_{x_4}\sum_{x_3}\sum_{x_2}\sum_{x_1}P(x_1)P(x_2|x_1)P(x_3|x_2)P(x_4|x_3)P(x_5|x_3)$=∑x4​​∑x3​​∑x2​​∑x1​​P(x1​)P(x2​∣x1​)P(x3​∣x2​)P(x4​∣x3​)P(x5​∣x3​)

可以发现，若采用$\begin{Bmatrix} x_1,x_2,x_4,x_3 \end{Bmatrix}${x1​,x2​,x4​,x3​​}顺序计算加法，则有：

$P(x_5)=\sum_{x_3}P(x_5|x_3)\sum_{x_4}P(x_4|x_3)\sum_{x_2}P(x_3|x_2)\sum_{x_1}P(x_1)P(x_2|x_1)$P(x5​)=∑x3​​P(x5​∣x3​)∑x4​​P(x4​∣x3​)∑x2​​P(x3​∣x2​)∑x1​​P(x1​)P(x2​∣x1​)

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=\sum_{x_3}P(x_5|x_3)\sum_{x_4}P(x_4|x_3)\sum_{x_2}P(x_3|x_2)m_{12}(x_2)$=∑x3​​P(x5​∣x3​)∑x4​​P(x4​∣x3​)∑x2​​P(x3​∣x2​)m12​(x2​)

因为$P(x_1)P(x_2|x_1)$P(x1​)P(x2​∣x1​)只与$x_1,x_2$x1​,x2​有关系，所以关于$x_1$x1​积分，剩下的就是关于$x_2$x2​的式子，将上述过程表示为$m_{12}(x_2)$m12​(x2​)，其中m的第一个下标表示对那一个变量进行求和，第二个下标表示的是求和剩下的变量，其中括号内的$x_2$x2​，即表示的是$x_2$x2​的函数。

$m_{ij}(x_j)$mij​(xj​)是求加和的过程的中间结果，下标$i$i表示的是此项是对$x_i$xi​求加和的结果，下标$j$j表示此项中剩下的其他变量。显然，$m_{ij}(x_j)$mij​(xj​)是关于$x_j$xj​的函数。

不断的执行上述过程可得：
$P(x_5)=\sum_{x_3}P(x_5|x_3)\sum_{x_4}P(x_4|x_3)m_{23}(x_3)$P(x5​)=∑x3​​P(x5​∣x3​)∑x4​​P(x4​∣x3​)m23​(x3​)

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=\sum_{x_3}P(x_5|x_3)m_{23}(x_3)\sum_{x_4}P(x_4|x_3)$=∑x3​​P(x5​∣x3​)m23​(x3​)∑x4​​P(x4​∣x3​)

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=\sum_{x_3}P(x_5|x_3)m_{23}(x_3)m_{43}(x_3)$=∑x3​​P(x5​∣x3​)m23​(x3​)m43​(x3​)

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=m_{35}(x_5)$=m35​(x5​)

最后，$m_{35}(x_5)$m35​(x5​)是关于$x_5$x5​的函数，仅与变量$x_5$x5​的取值有关。
事实上，上述方法对无向图也适用。不妨把前面图中的箭头忽略，将其看作一个无向图模型，就可以得到：
$P(x_1,x_2,x_3,x_4,x_5)=\frac1Z\psi_{12}(x_1,x_2)\psi_{23}(x_2,x_3)\psi_{34}(x_3,x_4)\psi_{35}(x_3,x_5)$P(x1​,x2​,x3​,x4​,x5​)=Z1​ψ12​(x1​,x2​)ψ23​(x2​,x3​)ψ34​(x3​,x4​)ψ35​(x3​,x5​)

其中Z为规范化因子，边际分布$P(x_5)$P(x5​)这样计算：
$P(x_5)=\sum_{x_3}\psi_{35}(x_3,x_5)\sum_{x_4}\psi_{34}(x_3,x_4)\sum_{x_2}\psi_{23}(x_2,x_3)\sum_{x_1}P(x_1)\psi_{12}(x_1,x_2)$P(x5​)=∑x3​​ψ35​(x3​,x5​)∑x4​​ψ34​(x3​,x4​)∑x2​​ψ23​(x2​,x3​)∑x1​​P(x1​)ψ12​(x1​,x2​)

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=\sum_{x_3}\psi_{35}(x_3,x_5)\sum_{x_4}\psi_{34}(x_3,x_4)\sum_{x_2}\psi_{23}(x_2,x_3)m_{12}(x_2)$=∑x3​​ψ35​(x3​,x5​)∑x4​​ψ34​(x3​,x4​)∑x2​​ψ23​(x2​,x3​)m12​(x2​)

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=……$=……

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=\frac1Zm_{35}(x_5)$=Z1​m35​(x5​)

显然，通过利用乘法对加法的分配律【$ab+ac=a(b+c)$ab+ac=a(b+c)】，变量消去法把多个变量的积的求和问题，转化为对部分变量交替进行求积与求和的问题。这种转化使得每次的求和与求积运算限制在局部，仅与部分变量有关，从而简化了计算。

但是，变量消去法有一个明显的缺点：若需计算多个边际分布，重复使用变量消去法会造成大量的冗余计算。其次，变量消元法计算的复杂度和消元的顺序有关系，而在实际计算中找到一个最优的消元顺序是一个NP难的问题，所以实际计算中都是采取启发式的规则进行计算，比如选择最小临接点的节点进行消元。

信念传播-belief propagation

信念传播（Belief Propagation,BP）算法，也称为和积（Sum-Product）算法或消息传递（Message Passing）算法，是将变量消除法中的和积（Sum-Product）操作看作是消息，并保存起来，这样可以节省大量的计算资源。
具体来说，变量消去法通过求和操作
$m_{ij}(x_j)=\sum_{x_i}\psi(x_i,x_j)\prod_{k\in n(i)\backslash j}m_{ki}(x_i)$mij​(xj​)=∑xi​​ψ(xi​,xj​)∏k∈n(i)\j​mki​(xi​)

消去变量$x_i$xi​，其中$n(i)$n(i)表示结点$x_i$xi​的邻接结点。在信念传播过程中，这个操作被看作从$x_i$xi​向$x_j$xj​传递了一个消息$m_{ij}(x_j)$mij​(xj​)。这样$m_{ij}(x_j)$mij​(xj​)的计算变量消去的过程就能描述前面图b所示的消息传递过程。不难发现，每次消息的传递操作仅与变量$x_i$xi​及其邻接结点相关，换言之，消息传递相关的计算被限制在图的局部进行。

在信念传播算法中，一个结点仅在接收到来自其他所有节点的消息后才能向另外一个结点发送消息，且结点的边际分布正比与他所接收的消息的乘积，即：
$P(x_i)=\prod_{k\in n(i)}m_{ki}(x_i) --(A)$P(xi​)=∏k∈n(i)​mki​(xi​)−−(A)

例如在前面图b中，结点$x_3$x3​要想$x_5$x5​发送消息，必须事先收到来自结点$x_2$x2​和$x_4$x4​的消息，且传递到$x_5$x5​的消息$m_{35}(x_5)$m35​(x5​)恰为概率$P(x_5)$P(x5​)。

若图中没有环，则信念传播算法经过两个步骤即可完成所有消息传递，进而能计算所有变量上的边际分布：

• 指定一个跟结点，从所有叶结点开始向根结点传递消息，知道根结点收到所有邻居结点的消息；
• 从根结点开始向叶结点传递消息，直到所有的叶结点收到消息。

例如在前面图a中，令$x_1$x1​为根结点，则$x_4$x4​和$x_5$x5​为叶结点，以上两步消息传递过程如下图所示。此时图的每条边上都有方向不同的两条消息，基于这些消息和上式(A)即可获得所有变量的边际概率。

BP例子

情景一

若干士兵排成一个队列，每个士兵只能与他相邻的士兵交流，问如何才能使每个士兵都知道总的士兵数？

显然，对里面的任意一位士兵，他们只能与相邻的人交流传递信息。比如最左边的第一位向第二位传递：第二位左边只有1个。第二位向第三位传递：第三位左边有2个。一直依次传递到最右边最后一位，最后一位获得的信息是他的左边有5个人。

但是这个时候只有最右边那个人知道总人数（5+1=6），还不能使其他人知道总人数。其他人只知道他的左边有多少人，右边有多少并不知道。

这个时候怎么办呢？

最右边的人可以再依次往左边传递消息。比如最右边第一位告诉第二位说：第二位的右边只有他1个。依次传递。这样正向和反向各传递一遍，使得每个人拥有两个消息，一个是该士兵的左边有L个人，一个是右边有R个人。总人数=L+R+1。（加上他本人）

但是这样效率并不高，怎么快一点呢？
我们可以同时两边各向相反的方向传递消息，因为这并不影响工作流程。

抽象为因子图看一下：对应下图，引入几个概念：先验信息P、外信息E以及后验信息A。在图中，先验信息P表示每个士兵自身的数字“1”；外信息E表示从其他相邻的士兵获取的信息，即每个士兵的外信息均为5；后验信息A＝P＋E，在这里表示队列的总人数，即为6。从图中可以看出，得到最后的结果是通过前向计算和后向计算得到的。

情景二

若干士兵站好相应位置，有些士兵不止有2个相邻的士兵，可能有3个或更多。，每个士兵只能与他相邻的士兵交流，问如何才能使每个士兵都知道总的士兵数？

上图是不是可以和我们的 BP 算法联系起来了。传播的结果是使得每个节点都可以获得其他节点传来的消息，从而计算出边缘函数。

情景三

若干士兵排成环路，每个士兵只能与他相邻的士兵交流，问如何才能使每个士兵都知道总的士兵数？

由于有环路的存在，如果用上述信息更新方法来确定总人数，将会导致无法确定何时中止信息的传递，因此也就无法确定士兵人数。

根据信息更新规则分类，置信传播算法分为：Max-product 和 Sum-product。
这里不再对 max-product 进行研究，但只要弄懂了 sum-product，也就弄懂了 max-product 算法。因为 max-product 算法就在上面 sum-product 算法的基础上把求和符号换成求最大值max的符号即可！

例子来源