【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.学习与推断
基于概率图模型定义的联合概率分布，我们能对目标变量的边际分布（marginal distribution）或以某些可观测变量为条件的条件分布进行推断。条件分布我们已经接触过很多，例如在隐马尔可夫模型中要估算观测序列$\mathbf{x}$在给定参数$\lambda$下的条件概率分布。边际分布则是指对无关变量求和或积分后得到结果，例如在马尔可夫网中，变量的联合分布被表示成极大团的势函数乘积，于是，给定参数$\Theta$求解某个变量$x$的分布，就变成对联合分布中其他无关变量进行积分的过程，这称为“边际化”（marginalization）。
关于联合概率、边际概率、边际化、边际分布的介绍见本文第4部分。
对概率图模型，还需确定具体分布的参数（个人理解：这里指的是总体分布的参数，也就是模型的参数），这称为参数估计或参数学习问题，通常使用极大似然估计或最大后验概率估计求解。但若将参数视为待推测的变量，则参数估计过程和推断十分相似，可以“吸收”到推断问题中。因此，下面我们只讨论概率图模型的推断方法。
具体来说，假设图模型所对应的变量集$\mathbf{x} = \{ x_1,x_2,…,x_N \}$能分为$\mathbf{x}_E$和$\mathbf{x}_F$两个不相交的变量集，推断问题的目标就是计算边际概率$P(\mathbf{x}_F)$或条件概率$P(\mathbf{x}_F \mid \mathbf{x}_E)$。由条件概率定义有：
\[P(\mathbf{x}_F \mid \mathbf{x}_E) = \frac{P(\mathbf{x}_E,\mathbf{x}_F)}{P(\mathbf{x}_E)} = \frac{P(\mathbf{x}_E,\mathbf{x}_F)}{\sum_{\mathbf{x}_F}P(\mathbf{x}_E,\mathbf{x}_F)} \tag{1}\]其中联合概率$P(\mathbf{x}_E,\mathbf{x}_F)$可基于概率图模型获得，因此，推断问题的关键就是如何高效地计算边际分布，即：
\[P(\mathbf{x}_E) = \sum_{\mathbf{x}_F} P(\mathbf{x}_E,\mathbf{x}_F) \tag{2}\]概率图模型的推断方法大致可分为两类。第一类是精确推断方法，希望能计算出目标变量的边际分布或条件分布的精确值；遗憾的是，一般情形下，此类算法的计算复杂度随着极大团规模的增长呈指数增长，适用范围有限。第二类是近似推断方法，希望在较低的时间复杂度下获得原问题的近似解；此类方法在现实任务中更常用。本文介绍两种代表性的精确推断方法，下一篇介绍近似推断方法。
2.变量消去
精确推断的实质是一类动态规划算法，它利用图模型所描述的条件独立性来削减计算目标概率值所需的计算量。变量消去法是最直观的精确推断算法，也是构建其他精确推断算法的基础。
我们先以图14.7(a)中的有向图模型为例来介绍其工作流程。
假定推断目标是计算边际概率$P(x_5)$。显然，为了完成此目标，只需通过加法消去变量$\{ x_1,x_2,x_3,x_4 \}$，即：
\[\begin{align} 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) \\&= \sum_{x_4} \sum_{x_3} \sum_{x_2} \sum_{x_1} P(x_1) P(x_2 \mid x_1) P(x_3 \mid x_2) P(x_4 \mid x_3) P(x_5 \mid x_3) \end{align} \tag{3}\]基于有向图模型所描述的条件独立性。
不难发现，若采用$\{ x_1,x_2,x_4,x_3 \}$的顺序计算加法，则有：
\[\begin{align} 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_{12} (x_2) \end{align} \tag{4}\]其中$m_{ij}(x_j)$是求加过程的中间结果，下标$i$表示此项是对$x_i$求加的结果，下标$j$表示此项中剩下的其他变量。显然，$m_{ij}(x_j)$是关于$x_j$的函数。不断执行此过程可得：
\[\begin{align} P(x_5) &= \sum_{x_3} P(x_5 \mid x_3) \sum_{x_4} P(x_4 \mid x_3) m_{23} (x_3) \\&= \sum_{x_3} P(x_5 \mid x_3) m_{23} (x_3) \sum_{x_4} P(x_4 \mid x_3) \\&= \sum_{x_3} P(x_5 \mid x_3) m_{23} (x_3) m_{43} (x_3) \\&= m_{35} (x_5) \end{align} \tag{5}\]显然，最后的$m_{35}(x_5)$是关于$x_5$的函数，仅与变量$x_5$的取值有关。
事实上，上述方法对无向图模型同样适用。不妨忽略图14.7(a)中的箭头，将其看作一个无向图模型，有：
\[P(x_1,x_2,x_3,x_4,x_5) = \frac{1}{Z} \psi_{12} (x_1,x_2) \psi_{23} (x_2,x_3) \psi_{34} (x_3,x_4) \psi_{35} (x_3,x_5) \tag{6}\]参考：【机器学习基础】第六十三课：[概率图模型]马尔可夫随机场中的式(1)。
其中$Z$为规范化因子。边际分布$P(x_5)$可这样计算：
\[\begin{align} P(x_5) &= \frac{1}{Z} \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} \psi_{12} (x_1,x_2) \\&= \frac{1}{Z} \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) \\&= ... \\&= \frac{1}{Z} m_{35} (x_5) \end{align} \tag{7}\]显然，通过利用乘法对加法的分配律，变量消去法把多个变量的积的求和问题，转化为对部分变量交替进行求积与求和的问题。这种转化使得每次的求和与求积运算限制在局部，仅与部分变量有关，从而简化了计算。
变量消去法有一个明显的缺点：若需计算多个边际分布，重复使用变量消去法将会造成大量的冗余计算。例如在图14.7(a)的贝叶斯网上，假定在计算$P(x_5)$之外还希望计算$P(x_4)$，若采用$\{ x_1,x_2,x_5,x_3 \}$的顺序，则$m_{12} (x_2)$和$m_{23} (x_3)$的计算是重复的。
2.1.式(5)的推导
式(4)第2步的推导：
\[m_{12}(x_2) = \sum_{x_1} P(x_1) P(x_2 \mid x_1) = P(x_2)\]式(5)第1步的推导：
\[\sum_{x_2}P(x_3 \mid x_2) m_{12} (x_2) = \sum_{x_2}P(x_3 \mid x_2) P(x_2) = m_{23}(x_3) = P(x_3)\]又因为$m_{23}(x_3)$不依赖$x_4$，所以可以从$\sum_{x_4}$里面拿出来，从而得到式(5)的第2步。
注意，在式(5)的第3步中，这里是$m_{43}$而不是$m_{34}$，即该项是对$x_4$求加的结果，且有：
\[m_{43}(x_3) = \sum_{x_4} P(x_4 \mid x_3) = 1\]式(5)第4步的推导：
\[\sum_{x_3} P(x_5 \mid x_3) m_{23} (x_3) m_{43} (x_3) = \sum_{x_3} P(x_5 \mid x_3) m_{23} (x_3) = m_{35}(x_5) = P(x_5)\]3.信念传播
信念传播（Belief Propagation）算法（亦称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) \tag{8}\]消去变量$x_i$，其中$n(i)$表示结点$x_i$的邻接结点。在信念传播算法中，这个操作被看作从$x_i$向$x_j$传递了一个消息$m_{ij}(x_j)$。这样，式(4)和(5)所描述的变量消去过程就能描述为图14.7(b)所示的消息传递过程。不难发现，每次消息传递操作仅与变量$x_i$及其邻接结点直接相关，换言之，消息传递相关的计算被限制在图的局部进行。
在信念传播算法中，一个结点仅在接收到来自其他所有结点的消息后才能向另一个结点发送消息，且结点的边际分布正比于它所接收的消息的乘积，即：
\[P(x_i) \propto \prod_{k \in n(i)} m_{ki} (x_i) \tag{9}\]例如在图14.7(b)中，结点$x_3$要向$x_5$发送消息，必须事先收到来自结点$x_2$和$x_4$的消息，且传递到$x_5$的消息$m_{35} (x_5)$恰为概率$P(x_5)$。
若图结构中没有环，则信念传播算法经过两个步骤即可完成所有消息传递，进而能计算所有变量上的边际分布：
- 指定一个根结点，从所有叶结点开始向根结点传递消息，直到根结点收到所有邻接结点的消息；
- 从根结点开始向叶结点传递消息，直到所有叶结点均收到消息。
例如在图14.7(a)中，令$x_1$为根结点，则$x_4$和$x_5$为叶结点。以上两步消息传递的过程如图14.8所示。此时图的每条边上都有方向不同的两条消息，基于这些消息和式(9)即可获得所有变量的边际概率。
个人理解：变量消去法和信念传播法本质上都是在计算$P(x_i)=\sum_{其他变量} P(x_1,…,x_n)$，但不同之处在于，变量消去法每次都从头算一遍，比如计算$P(x_3)$或$P(x_5)$，要分别算两遍，中间结果不会共享。而信念传播法会先把中间结果算好，以后重复用，比如先算好中间结果$m_{12}(x_2)$等。
3.1.式(8)的解释
$k \in n(i) \backslash j$表示$k$属于除去$j$之外的$x_i$的邻接结点，比如：
- $n(1) \backslash 2$为空集，因为$x_1$只有邻接结点$x_2$。
- $n(2) \backslash 3 = \{ 1 \}$，因为$x_2$有邻接结点$x_1$和$x_3$。
- $n(4) \backslash 3$为空集，因为$x_4$只有邻接结点$x_3$。
- $n(3) \backslash 5 = \{ 2,4 \}$，因为$x_3$有邻接结点$x_2,x_4,x_5$。
接下来，仍然以图14.7计算$P(x_5)$为例：
\[m_{12} (x_2) = \sum_{x_1} \psi _{12} (x_1,x_2) \prod_{k \in n(1) \backslash 2} m_{k1} (x_1) = \sum_{x_1} \psi _{12} (x_1,x_2)\] \[m_{23} (x_3) = \sum_{x_2} \psi_{23} (x_2,x_3) \prod _{k \in n(2) \backslash 3} m_{k2} (x_2)= \sum_{x_2} \psi_{23} (x_2,x_3) m_{12} (x_2)\] \[m_{43} (x_3) = \sum_{x_4} \psi_{34} (x_3,x_4) \prod _{k \in n(4) \backslash 3} m_{k4} (x_4) = \sum_{x_4} \psi_{34} (x_3,x_4)\] \[m_{35} (x_5) = \sum_{x_3} \psi_{35} (x_3,x_5) \prod _{k \in n(3) \backslash 5} m_{k3} (x_3) = \sum_{x_3} \psi_{35} (x_3,x_5) m_{23} (x_3) m_{43} (x_3)\]4.边际化、边际概率、边际分布
边际概率就是只关注一个变量发生的概率，而不关心其他变量的具体取值。换句话说，就是把其他变量“加总（求和）掉”之后得到的概率。这个对某些变量进行求和（离散）或积分（连续）的过程就是边际化。而对其他变量进行边际化之后得到的概率分布就是边际分布。
举个例子，假设$X$表示是否生病，$Y$表示是否发烧，有以下联合分布：
| X | Y | 概率 |
|---|---|---|
| 是 | 是 | 0.3 |
| 是 | 否 | 0.2 |
| 否 | 是 | 0.1 |
| 否 | 否 | 0.4 |
那么针对变量$X$，其取值为“是”时的边际概率为（即不考虑$Y$的取值）：
\[P(X = 是) = P(X=是,Y=是) + P(X=是,Y=否)=0.3+0.2=0.5\]类似的，$X$取值为“否”时的边际概率为：
\[P(X=否)=P(X=否,Y=是)+P(X=否,Y=否)=0.1+0.4=0.5\]至此，我们便得到了变量$X$的边际分布：
| X | 概率 |
|---|---|
| 是 | 0.5 |
| 否 | 0.5 |
上面求$X$边际分布的过程就是对$Y$进行的边际化。
