1. 精确推断的实质是一类动态规划算法。它利用图模型所描述的条件独立性来降低计算量。

1. 以下图为例来介绍变量消去法的工作流程。假设推断目标是计算边际概率

   

   为了计算 ，只需要通过加法消去变量 即可。

   其中联合概率分布 是已知的。

   • 根据条件独立性有： 。

     代入上式并重新安排 的位置有：

   • 定义：

     

     其中： 仅仅是 的函数； 仅仅是 的函数； 仅仅是 的函数。

     实际上图中有 ，最终

2. 变量消去法通过利用乘法对加法的分配律，将多个变量的积的求和转化为对部分变量交替进行求积与求和的问题。

   • 优点：这种转化使得每次的求和与求积运算限制在局部，仅与部分变量有关，从而简化了计算。

1.2 信念传播

1. 信念传播算法将变量消去法中的求和操作看作一个消息传递过程，解决了求解多个边际分布时的重复计算问题。

2. 在变量消去法中，求和操作为： 。其中 表示结点 的相邻结点的下标集合。

   在信念传播算法中，这个操作被看作从 向 传递了一个消息 。这样，变量消去的过程就可以描述为消息传递过程。

   每次消息传递操作仅与 及其邻接结点直接相关，消息传递相关的计算被限制在图的局部进行。

3. 在信念传播算法中：

   • 一个结点仅在接收到来自其他所有结点的消息后才能向另一个结点发送消息。
   • 结点的边际分布正比于它所接收的消息的乘积： 。

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

   • 从根节点开始向叶结点传递消息，直到所有叶结点均收到消息。