机器学习08：概率图模型(PGM)2

上一篇博客介绍了有关概率图模型表示的基本内容，本篇博客介绍有关推断的内容。

推断的主要目的是求各种概率分布，包括边缘概率，条件概率，以及使用 MAP 来求得参数。本篇博客介绍三种算法

推断-变量消除（VE）

变量消除的方法是在求解概率分布的时候，将相关的条件概率先行求和或积分，从而一步步地消除变量，例如在马尔可夫链中：

graph LR;
    a((a))-->b((b));
    b-->c((c));
    c-->d((d))

变量消除的缺点很明显：

1. 计算步骤无法存储
2. 消除的最优次序是一个 NP-hard 问题

推断-信念传播（BP）

为了克服 VE 的第一个缺陷-计算步骤无法存储。我们进一步地对上面的马尔可夫链进行观察：

graph LR;
    a((a))-->b((b));
    b-->c((c));
    c-->d((d));
    d-->e((e));

要求 ，当然使用 VE，从 一直消除到 ，记 ，表示这是消除 后的关于 的概率，类似地，记 。于是 。进一步观察，对 ： 我们发现了和上面计算 类似的结构，这个式子可以分成两个部分，一部分是从 传播过来的概率，第二部分是从 传播过来的概率。

一般地，对于图（只对树形状的图）：

graph TD;
    a((a))---b((b));
    b---c((c));
    b---d((d));

这四个团（对于无向图是团，对于有向图就是概率为除了根的节点为1），有四个节点，三个边： 套用上面关于有向图的观察，如果求解边缘概率 ，定义 ，，，这样概率就一步步地传播到了 ： 写成一般的形式，对于相邻节点 ： 这个表达式，就可以保存计算过程了，只要对每条边的传播分别计算，对于一个无向树形图可以递归并行实现：（类似于深搜的过程）

1. 任取一个节点 作为根节点
2. 对这个根节点的邻居中的每一个节点，收集信息（计算入信息）
3. 对根节点的邻居，分发信息（计算出信息）

推断-Max-Product 算法

在推断任务中，MAP 也是常常需要的，MAP 的目的是寻找最佳参数： 类似 BP，我们采用信息传递的方式来求得最优参数，不同的是，我们在所有信息传递中，传递的是最大化参数的概率，而不是将所有可能求和： 于是对于上面的图： 这个算法是 Sum-Product 算法的改进，也是在 HMM 中应用给的 Viterbi 算法的推广。