机器学习笔记之概率图模型(九)最大乘积算法(Max-Product Algorithm)

引言

上一节介绍了信念传播算法(Belief Propagation,BP)的思想以及具体算法过程，本节将介绍精确推断中的最大乘积算法(Max-Product Algorithm)。

回顾：推断的本质

已知数据集合$\mathcal{X}$共包含$p$维特征，并且假设每个特征都是离散型随机变量：
X = { x 1 , x 2 , ⋯   , x p } \mathcal X = \{x_1,x_2,\cdots,x_p\} X={x1​,x2​,⋯,xp​}
根据概率图的性质，这$p$维特征并非存在$p$个结点，而是每个结点可能包含一个/多个特征，这里假定共存在$n$个结点。我们关心的重点并不在结点的数量，而在于边的信息。假设随机变量$\mathcal{X}$表示的概率图中存在$\mathcal{K}$条边，即：
每一条边$e_i(i=1,2,\cdots ,\mathcal{K})$表示某两个结点之间的关联关系。概率图给定的条件下，将其理解成‘已知信息’。
E = { e 1 , e 2 , ⋯   , e K } \mathcal E = \{e_1,e_2,\cdots,e_{\mathcal K}\} E={e1​,e2​,⋯,eK​}

在推断基本介绍中提到，推断的本质即变量/特征概率的计算。如：

• 变量/特征的边缘概率：
  概率的加法/积分运算~,这里$x_i(i=1,2,\cdots ,n)$并非表示维度特征，而表示结点所包含的特征集合。
  $$\mathcal{P}(x_i)=\sum _{x_1}\cdots \sum _{x_{i-1}}\sum _{x_{i+1}}\cdots \sum _{x_n}\mathcal{P}(\mathcal{X})$$
  从概率图的角度观察，基于边的边缘概率$\mathcal{P}(e_i)$，其本质上是某两个结点关联关系的概率：
  • 从有向图的角度观察，该关联关系使用条件概率进行表示：
    $$\mathcal{P}(e_i)=\mathcal{P}(x_{i\to end}\mid x_{i\to start})$$
    其中$x_{i\to start}$表示边$e_i$的起始点，$x_{i\to end}$表示$e_i$的终止点。
  • 从无向图的角度观察，该关联关系使用势函数进行表示：
    不同于‘有向图’中$e_i$的有向性，无向图中$x_{i\to start},x_{i\to end}$没有顺序性，只是借用上述符号而已。
    $$\mathcal{P}(e_i)=\psi (x_{i\to start},x_{i\to end})$$
• 变量/特征的条件概率：将结点分成如下两个子集$x_{\mathcal{A}},x_{\mathcal{B}}$，结点集合间的条件概率分布表示如下：
  概率的乘法运算~
  $$\mathcal{P}(x_{\mathcal{A}}\mid x_{\mathcal{B}})x_{\mathcal{A}}\cup x_{\mathcal{B}}=\mathcal{X}$$
  在给定概率图的条件下，边本身的含义即确定了的结点/特征之间的关联关系。因此基于边的条件概率，实际上是 给定关联关系的条件下，关联关系对应结点的后验概率。即：
  $$\mathcal{P}(\mathcal{X}\mid \mathcal{E})$$
  根据任务需要，可能并不需要完整结点集合$\mathcal{X}$的概率结果，而只关心部分结点的后验概率结果。如：
  $$\mathcal{P}(x_{\mathcal{B}}\mid \mathcal{E})=\sum _{x_{\mathcal{A}}}\mathcal{P}(\mathcal{X}\mid \mathcal{E})$$
• 基于变量/特征的最大后验概率推断：
  根据条件概率公式：
  $$\mathcal{P}(x_{\mathcal{B}}\mid x_{\mathcal{A}})=\frac{\mathcal{P}(x_{\mathcal{A}},x_{\mathcal{B}})}{\mathcal{P}(x_{\mathcal{A}})}$$
  在求解关于$x_{\mathcal{B}}$的最优解$\widehat{x_{\mathcal{B}}}$时，由于分母$\mathcal{P}(x_{\mathcal{A}})$与$x_{\mathcal{B}}$无关，有：
  $$\widehat{x_{\mathcal{B}}}=\underset{x_{\mathcal{B}}}{\mathrm{argmax}}\mathcal{P}(x_{\mathcal{B}}\mid x_{\mathcal{A}})\propto \underset{x_{\mathcal{B}}}{\mathrm{argmax}}\mathcal{P}(x_{\mathcal{A}},x_{\mathcal{B}})$$
  基于边的最大后验概率推断，最终得到给定结点之间的关联关系(边)，从而找到表示优秀性能的结点组成的序列。因此有：
  $$\hat{\mathcal{X}}=\underset{\mathcal{X}}{\mathrm{argmax}}\mathcal{P}(\mathcal{X}\mid \mathcal{E})$$
  同理，局部最优序列也可进行如下表示：
  $$\widehat{x_{\mathcal{A}}}=\underset{x_{\mathcal{A}}}{\mathrm{argmax}}\mathcal{P}(x_{\mathcal{A}}\mid \mathcal{E})$$

回顾：维特比算法

在介绍隐马尔可夫模型的解码问题中介绍了维特比算法(Viterbi Algorithm)。解码问题的本质即给定观测序列 O = { o 1 , ⋯   , o T } \mathcal O = \{o_1,\cdots,o_T\} O={o1​,⋯,oT​}，求解对应状态序列的后验概率$\mathcal{P}(\mathcal{I}\mid \mathcal{O},\lambda )$。
$\lambda$表示隐马尔可夫模型的参数变量$\to \pi ,\mathcal{A},\mathcal{B}$

但使用的方法并非直接求解$\mathcal{P}(\mathcal{I}\mid \mathcal{O},\lambda )$，而是通过找出 $\mathcal{P}(\mathcal{I},\mathcal{O}\mid \lambda )$的最优解在相邻时刻间的关联关系：
其中${\mathcal{I}}_t$表示状态序列 { i 1 , ⋯   , i t } \{i_1,\cdots,i_t\} {i1​,⋯,it​},其他符号${\mathcal{I}}_{t+1},{\mathcal{O}}_t,{\mathcal{O}}_{t+1}$同理。
$$\begin{gathered} {\delta }_t=\underset{{\mathcal{I}}_{t-1}}{\max }\mathcal{P}({\mathcal{I}}_t\mid {\mathcal{O}}_t,\lambda )\propto \underset{{\mathcal{I}}_{t-1}}{\max }\mathcal{P}({\mathcal{I}}_t,{\mathcal{O}}_t\mid \lambda ) \\ {\delta }_{t+1}=\underset{{\mathcal{I}}_t}{\max }\mathcal{P}({\mathcal{I}}_{t+1}\mid {\mathcal{O}}_{t+1},\lambda )\propto \underset{{\mathcal{I}}_t}{\max }\mathcal{P}({\mathcal{I}}_{t+1},{\mathcal{O}}_{t+1}\mid \lambda ) \\ {\delta }_t\to {\delta }_{t+1} \end{gathered}$$
从初始时刻开始，将迭代过程的中间步骤记录下来，从而找出一条最优状态序列$\widehat{{\mathcal{I}}_T}$。由于最优序列的子集同样是最优的，因此任意两个时刻之间的状态序列均可以通过记录查找的方式获取，从而减少运算时间(动态规划问题)。
这明显是两步操作;
1. 本质上是描述$\underset{{\mathcal{I}}_{t-1}}{\max }\mathcal{P}({\mathcal{I}}_t\mid {\mathcal{O}}_t,\lambda )$和$\underset{{\mathcal{I}}_t}{\max }\mathcal{P}({\mathcal{I}}_{t+1}\mid {\mathcal{O}}_{t+1},\lambda )$之间的关联关系；
2. 通过‘最大后验概率推断’将步骤1的操作转化为$\underset{{\mathcal{I}}_{t-1}}{\max }\mathcal{P}({\mathcal{I}}_t,{\mathcal{O}}_t\mid \lambda )$和$\underset{{\mathcal{I}}_t}{\max }\mathcal{P}({\mathcal{I}}_{t+1},{\mathcal{O}}_{t+1}\mid \lambda )$之间的关联关系。

最大乘积算法

回顾：信念传播

信念传播的算法思想中，结点间的消息传递方式只是其中一部分，在 消息传递的过程中，将结点之间的消息记录下来并进行存储。一旦需要计算其他结点的边缘概率分布时，可以直接通过消息查找的方式进行计算，从而节省大量运算时间。
由于‘概率图结构’是给定不变的，因此无论从哪个结点作为根结点进行迭代，任意存在关联关系的‘结点对’$x_j,x_k$之间消息传递的结果$m_{j\to k}(x_k)$都不会发生变化。
$x_j,x_k$之间的 消息传递结果$m_{j\to k}(x_k)$ 表示如下：
$$\{\begin{array}{l}{m}_{j\to k}(x_k)={\sum }_{x_j}{\psi }_{jk}(x_j,x_k)\cdot {\prod }_{l\in n(i),l\ne k}{m}_{l\to j}(x_j)\\ \mathcal{P}(x_i)\propto {\prod }_{k\in n(i)}{m}_{k\to i}(x_i)\end{array}$$

对于联合概率分布的误区

联合概率分布并非某一具体数值，而是在变量取不同结果过程中，联合概率分布也会发生相应变化：

例如存在一枚质地不均匀的硬币，其正面朝上的概率$\mathcal{P}(up)=0.3$，反面朝上的概率$\mathcal{P}(down)=0.7$，投掷两次该硬币，第一次变量结果记作$x_1$，第二次变量结果记作$x_2$，针对四种情况：(正,正),(正,反),(反,正),(反,反) 对应的概率结果表示如下：

那么对应联合概率结果存在$3$种情况：$0.09,0.21,0.49$

由于设定数据集合$\mathcal{X}$中的各特征是离散型随机变量，因此 各特征内存在对应取值，并且每个取值对应相应概率结果。从而对应的联合概率分布结果也会存在多种情况。
这里并不局限于‘离散型随机变量’，连续型随机变量同样也会存在多种情况。

最大乘积算法(Max-Product Algorithm)示例

最大乘积算法既可以求解某结点变量的边缘概率分布，也可以求解多个结点变量的联合概率分布。

与信念传播算法之间不同的是，它求解的均是最大概率分布。而具体的迭代方式依然使用信念传播方法。

已知一个马尔可夫随机场表示如下：

求解目标包含两个阶段：

• 所有结点的最大联合概率分布；
• 最优结点变量的边缘概率分布；

具体传播过程如上述蓝色箭头所示，逐步推导迭代过程：

• 首先观察结点变量$i_8,i_9$，它们均只和$i_2$相关联，因此结点变量$i_9$基于自身随机变量的取值，向结点变量$i_2$传递的最大消息$m_{9\to 2}(i_2)$ 表示如下：
  需要注意的问题：$m_{9\to 2}(i_2)$中的变量只包含$i_2$，因为$i_9$已经选择了‘使${\psi }_{92}(i_9,i_2)$达到最大所对应的取值。下面同理。
  $$m_{9\to 2}(i_2)=\underset{i_9}{\max }{\psi }_{92}(i_9,i_2)$$
  同理，结点变量$i_8$向结点变量$i_2$传递的最大消息$m_{8\to 2}(i_2)$ 表示如下：
  $$m_{8\to 2}(i_2)=\underset{i_8}{\max }{\psi }_{82}(i_8,i_2)$$
  至此，$i_8,i_9$两个变量结点的路径全部处理完毕。$i_2,i_8,i_9$三个变量结点的最大联合概率分布$\underset{i_2,i_8,i_9}{\max }\mathcal{P}(i_2,i_8,i_9)$表示如下：
  这里将$i_2,i_8,i_9$看成一个独立的子图，后续同理。
  $$\underset{i_2,i_8,i_9}{\max }\mathcal{P}(i_2,i_8,i_9)=\underset{i_2}{\max }{m}_{9\to 2}(i_2)\cdot m_{8\to 2}(i_2)$$
  此时变量结点$i_2,i_8,i_9$的最优取值$i_2^{\ast },i_8^{\ast },i_9^{\ast }$也可以被表示出来：
  后面省略了~
  $$i_2^{\ast },i_8^{\ast },i_9^{\ast }=\underset{i_2,i_8,i_9}{\mathrm{argmax}}\mathcal{P}(i_2,i_8,i_9)$$
• 继续观察结点变量$i_6,i_7$，它们均只和$i_1$相关联，与$i_8,i_9$同理，$m_{7\to 1}(i_1),m_{6\to 1}(i_1)$以及最大联合概率分布$\underset{i_1,i_6,i_7}{\max }\mathcal{P}(i_1,i_6,i_7)$分别表示如下：
  $$\begin{array}{rl}{m}_{7\to 1}(i_1)& =\underset{i_7}{\max }{\psi }_{71}(i_7,i_1)\\ m_{6\to 1}(i_1)& =\underset{i_6}{\max }{\psi }_{61}(i_6,i_1)\\ \underset{i_1,i_6,i_7}{\max }\mathcal{P}(i_1,i_6,i_7)& =\underset{i_1}{\max }{m}_{7\to 1}(i_1)\cdot m_{6\to 1}(i_1)\end{array}$$
• 继续观察$i_1,i_2,i_3$部分，$i_1,i_2$变量结点向$i_3$传递的最大消息$m_{1\to 3}(i_3),m_{2\to 3}(i_3)$分别表示如下：
  相比于子集合 { i 2 , i 8 , i 9 } , { i 1 , i 6 , i 7 } \{i_2,i_8,i_9\},\{i_1,i_6,i_7\} {i2​,i8​,i9​},{i1​,i6​,i7​},随着迭代的加深，子集合扩张了~
  $$\begin{gathered} m_{1\to 3}(i_3)=\underset{i_1}{\max }{\psi }_{13}(i_1,i_3)\cdot m_{7\to 1}(i_1)\cdot m_{6\to 1}(i_1) \\ {m}_{2\to 3}(i_3)=\underset{i_2}{\max }{\psi }_{23}(i_2,i_3)\cdot m_{9\to 2}(i_2)\cdot m_{8\to 2}(i_2) \end{gathered}$$
  因此，对应最大联合概率分布$\mathcal{P}(i_1,i_2,i_3,i_6,i_7,i_8,i_9)$对应表示如下：
  $$\begin{array}{rl}\underset{i_1,i_2,i_3,i_6,i_7,i_8,i_9}{\max }P(i_1,i_2,i_3,i_6,i_7,i_8,i_9)& =\underset{i_3}{\max }{m}_{1\to 3}(i_3)\cdot m_{2\to 3}(i_3)\end{array}$$
• 最终剩余结点变量$i_4$，该点只与$i_3$相关联，因此$m_{3\to 4}(i_4)$可表示为：
  $$m_{3\to 4}(i_4)=\underset{i_3}{\max }{\psi }_{34}(i_3,i_4)\cdot m_{1\to 3}(i_3)\cdot m_{2\to 3}(i_3)$$
  对应最大联合概率分布$\mathcal{P}(i_1,i_2,i_3,i_4,i_6,i_7,i_8,i_9)$对应表示如下：
  $$\underset{i_1,i_2,i_3,i_4,i_6,i_7,i_8,i_9}{\max }\mathcal{P}(i_1,i_2,i_3,i_4,i_6,i_7,i_8,i_9)=\underset{i_4}{\max }{m}_{3\to 4}(i_4)$$

至此，整个概率图全部遍历结束，对上述结果进行整理，该概率图的最大联合概率分布 表示如下：
$$\begin{array}{rl}& \underset{i_1,i_2,i_3,i_4,i_6,i_7,i_8,i_9}{\max }\mathcal{P}(i_1,i_2,i_3,i_4,i_6,i_7,i_8,i_9)\\ & =\underset{i_4}{\max }{m}_{3\to 4}(i_4)\\ & =\underset{i_4}{\max }\underset{i_3}{\max }{\psi }_{34}(i_3,i_4)\cdot m_{1\to 3}(i_3)\cdot m_{2\to 3}(i_3)\\ & =\underset{i_4}{\max }\underset{i_3}{\max }{\psi }_{34}(i_3,i_4)\cdot \left(\underset{i_1}{\max }{\psi }_{13}(i_1,i_3)\cdot m_{7\to 1}(i_1)\cdot m_{6\to 1}(i_1)\right)\cdot \left(\underset{i_2}{\max }{\psi }_{23}(i_2,i_3)\cdot m_{9\to 2}(i_2)\cdot m_{8\to 2}(i_2)\right)\\ & =\underset{i_4}{\max }\underset{i_3}{\max }{\psi }_{34}(i_3,i_4)\cdot \left[\underset{i_1}{\max }{\psi }_{13}(i_1,i_3)\cdot \left(\underset{i_7}{\max }{\psi }_{71}(i_7,i_1)\right)\cdot \left(\underset{i_6}{\max }{\psi }_{61}(i_6,i_1)\right)\right]\cdot \left[\underset{i_2}{\max }{\psi }_{23}(i_2,i_3)\cdot \left(\underset{i_9}{\max }{\psi }_{92}(i_9,i_2)\right)\cdot \left(\underset{i_8}{\max }{\psi }_{82}(i_8,i_2)\right)\right]\end{array}$$

由于知道了各阶段的联合概率分布，边缘概率分布的计算变得非常简单。以$i_4$结点为例。现在已知联合概率分布$\mathcal{P}(i_1,i_2,i_3,i_4,i_6,i_7,i_8,i_9)$和概率分布$\mathcal{P}(i_1,i_2,i_3,i_6,i_7,i_8,i_9)$，$i_4$的边缘概率分布直接做除法即可：
$$\mathcal{P}(i_4^{\ast })=\frac{\underset{i_1,i_2,i_3,i_4,i_6,i_7,i_8,i_9}{\max }\mathcal{P}(i_1,i_2,i_3,i_4,i_6,i_7,i_8,i_9)}{\underset{i_1,i_2,i_3,i_6,i_7,i_8,i_9}{\max }\mathcal{P}(i_1,i_2,i_3,i_6,i_7,i_8,i_9)}$$

下一节将介绍针对环结构概率图的处理方法——因子图。

相关参考：
概率统计学习笔记（2）：联合分布
机器学习-概率图模型11-推断Inference-Max Product（1）