Question

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

1.1 变量消去法

1. 变量消去法是最直观的精确推断算法。

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

   

   为了计算 $ MathJax-Element-45 $ ，只需要通过加法消去变量 $ MathJax-Element-26 $ 即可。

   $ P(X_5)=\sum_{X_1}\sum_{X_2}\sum_{X_3}\sum_{X_4} P(X_1,X_2,X_3,X_4,X_5) $

   其中联合概率分布 $ MathJax-Element-27 $ 是已知的。

   • 根据条件独立性有： $ MathJax-Element-28 $ 。

     代入上式并重新安排 $ MathJax-Element-29 $ 的位置有：

   $ P(X_5)=\sum_{X_3}P(X_5\mid X_3)\sum_{X_4}P(X_4\mid X_3)\sum_{X_2}P(X_3\mid X_2)\sum_{X_1}P(X_1)P(X_2\mid X_1) $

   • 定义：

     $ m_{1,2}(X_2)=\sum_{X_1}P(X_1)P(X_2\mid X_1)\\ m_{2,3}(X_3)=\sum_{X_2}P(X_3\mid X_2)m_{1,2}(X_2)\\ m_{4,3}(X_3)=\sum_{X_4}P(X_4\mid X_3)\\ m_{3,5}(X_5)=\sum_{X_3}P(X_5\mid X_3)m_{2,3}(X_3)m_{4,3}(X_3) $

     其中： $ MathJax-Element-38 $ 仅仅是 $ MathJax-Element-39 $ 的函数； $ MathJax-Element-40 $ 仅仅是 $ MathJax-Element-41 $ 的函数； $ MathJax-Element-42 $ 仅仅是 $ MathJax-Element-43 $ 的函数。

     于是有：

     $ P(X_5)=\sum_{X_3}P(X_5\mid X_3)\sum_{X_4}P(X_4\mid X_3)\sum_{X_2}P(X_3\mid X_2)\sum_{X_1}P(X_1)P(X_2\mid X_1) \\ =\sum_{X_3}P(X_5\mid X_3)\sum_{X_4}P(X_4\mid X_3)\sum_{X_2}P(X_3\mid X_2)m_{1,2}(X_2)\\ =\sum_{X_3}P(X_5\mid X_3)\sum_{X_4}P(X_4\mid X_3)m_{2,3}(X_3)\\ =\sum_{X_3}P(X_5\mid X_3)m_{2,3}(X_3)\sum_{X_4}P(X_4\mid X_3)\\ =\sum_{X_3}P(X_5\mid X_3)m_{2,3}(X_3)m_{4,3}(X_3)\\ =m_{3,5}(X_5) $

     实际上图中有 $ MathJax-Element-36 $ ，最终 $ MathJax-Element-37 $
     

2. 如果是无向图模型，上述方法同样适用。

   

   • 根据马尔可夫随机场的联合概率分布有：

     $ P(X_1,X_2,X_3,X_4,X_5)=\frac 1Z \psi_{1,2}(X_1,X_2)\psi_{2,3}(X_2,X_3)\psi_{3,4}(X_3,X_4)\psi_{3,5}(X_3,X_5) $

     边际分布：

     $ P(X_5)=\sum_{X_1}\sum_{X_2}\sum_{X_3}\sum_{X_4} P(X_1,X_2,X_3,X_4,X_5)\\ =\sum_{X_1}\sum_{X_2}\sum_{X_3}\sum_{X_4}\frac 1Z \psi_{1,2}(X_1,X_2)\psi_{2,3}(X_2,X_3)\psi_{3,4}(X_3,X_4)\psi_{3,5}(X_3,X_5) $

   • 定义：

     $ m_{1,2}(X_2)=\sum_{X_1}\psi_{1,2}(X_1,X_2)\\ m_{2,3}(X_3)=\sum_{X_2}\psi_{2,3}(X_2,X_3)m_{1,2}(X_2)\\ m_{4,3}(X_3)=\sum_{X_4}\psi_{3,4}(X_3,X_4)\\ m_{3,5}(X_5)=\sum_{X_3}\psi_{3,5}(X_3,X_5)m_{2,3}(X_3)m_{4,3}(X_3) $

     其中： $ MathJax-Element-38 $ 仅仅是 $ MathJax-Element-39 $ 的函数； $ MathJax-Element-40 $ 仅仅是 $ MathJax-Element-41 $ 的函数； $ MathJax-Element-42 $ 仅仅是 $ MathJax-Element-43 $ 的函数。

     于是有：

     $ P(X_5)= \sum_{X_1}\sum_{X_2}\sum_{X_3}\sum_{X_4}\frac 1Z \psi_{1,2}(X_1,X_2)\psi_{2,3}(X_2,X_3)\psi_{3,4}(X_3,X_4)\psi_{3,5}(X_3,X_5)\\ =\frac 1Z \sum_{X_3}\psi_{3,5}(X_3,X_5)\sum_{X_4}\psi_{3,4}(X_3,X_4)\sum_{X_2}\psi_{2,3}(X_2,X_3)\sum_{X_1}\psi_{1,2}(X_1,X_2)\\ =\frac 1Z \sum_{X_3}\psi_{3,5}(X_3,X_5)\sum_{X_4}\psi_{3,4}(X_3,X_4)\sum_{X_2}\psi_{2,3}(X_2,X_3)m_{1,2}(X_2)\\ =\frac 1Z \sum_{X_3}\psi_{3,5}(X_3,X_5)\sum_{X_4}\psi_{3,4}(X_3,X_4)m_{2,3}(X_3)\\ =\frac 1Z \sum_{X_3}\psi_{3,5}(X_3,X_5)m_{4,3}(X_3)m_{2,3}(X_3)\\ =\frac 1Z m_{3,5}(X_5) $
     • 其中的 $ MathJax-Element-44 $ 为归一化常量，使得 $ MathJax-Element-45 $ 满足概率的定义。
     • 这里 $ MathJax-Element-46 $ ，这就是无向概率图模型和有向概率图模型的一个重要区别。

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

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

   • 缺点：若需要计算多个边际分布，重复使用变量消去法将会造成大量的冗余计算。

     如：如果要同时计算 $ MathJax-Element-47 $ ，则变量消去法会重复计算 $ MathJax-Element-48 $ 。

1.2 信念传播

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

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

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

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

3. 在信念传播算法中：

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

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

   • 指定一个根节点，从所有叶结点开始向根节点传递消息，直到根节点收到所有邻接结点的消息。
   • 从根节点开始向叶结点传递消息，直到所有叶结点均收到消息。

   此时每条边上都有方向不同的两条消息