概率图表示之马尔可夫随机场

贝叶斯网络可以以一种紧凑的方式表示许多概率分布。然而，我们在前一章中已经看到，一些分布可能具有独立性假设，无法用贝叶斯网络完美地表示。

在这种情况下，除非我们想在模型的变量之间引入虚假的独立性，否则我们必须回到一种不太紧凑的表示法（可以看作是一个带有额外不必要边的图）。这会导致模型中出现额外的、不必要的参数，并使学习这些参数和进行预测变得更加困难。

然而，还有另一种基于无向图的紧凑表示和可视化概率分布的技术，我们称之为马尔可夫随机场或MRF。这类模型可以简洁地表示有向模型无法表示的独立性假设。在本章中，我们将探讨这类模型的优点和缺点。

马尔可夫随机场

举个能激发大家兴趣的例子，假设我们正在模拟 $A,B,C,D$ 4人的投票偏好，设$(A,B)$, $(B,C)$, $(C,D)$, $(D,A)$ 是朋友，且朋友往往有相似的投票偏好。这些影响可以自然地用无向图表示。

四人投票偏好联合概率的无向图表达。右图说明了模型中存在的成对因素。

定义 $A,B,C,D$ 投票决策的联合概率的一种方法是将分数分配给这些变量的每一个赋值，然后将概率定义为标准化分数。分数可以是任何函数，但在我们的例子中，我们将其定义为以下形式：

$$
\tilde p(A,B,C,D) = \phi(A,B)\phi(B,C)\phi(C,D)\phi(D,A)
$$
其中 $\phi(X,Y)$ 是一个为朋友 $X,Y$ 之间的一致投票赋予更高权重的因子。例如：

$$
\begin{align}
\phi(X,Y) =
\begin{cases}
10 & \text{如果 } X = Y = 1 \
5 & \text{如果 } X = Y = 0 \
1 & \text{其他情况}
\end{cases}
\end{align}
$$

非正态分布中的因子通常称为因子。最终概率定义为：

$$
p(A,B,C,D) = \frac{1}{Z} \tilde p(A,B,C,D)
$$
其中 $Z = \sum_{A,B,C,D} \tilde p(A,B,C,D)$ 是一个规范化常数，用于确保分布和为1。

当规范化时，我们将 $\phi(A,B)$ 视作一个交互，推动 $B$ 的投票接近 $A$。$\phi(B,C)$ 推动 $B$ 的投票接近C，而最有可能的投票需要调和这些相互冲突的影响。

注意，与有向图不同，我们并没有说一个变量是如何从另一组变量中生成的（正如条件概率分布所做的那样）。我们只是简单地表示图中因变量之间的耦合程度。某种意义上，这里需要较少的先验知识，因为我们不再需要详细说明 $B$ 的投票是如何从 $A$ 的投票中构建的（如果我们有$P(B \mid A)$，我们就需要详细说明），相反，我们只需要识别因变量并定义其相互作用强度即可；这反过来定义了可能分配空间上的能量分布，我们通过归一化常数将能量转换为概率。

正式定义

马尔可夫随机场是无向图$G$中定义的随机变量$x_1, x_2, \dots, x_n$的概率分布 $p$。图$G$中每一个节点表示一个变量$x_i$，该概率 $p$ 可以表述为如下形式：
$$
p(x_1,\dots, xn) = \frac{1}{Z}\prod{c \in C}\phi_c(x_c)
$$
其中$C$表示图$G$中的团（例如全联通子图）集合，且每个因子$\phic$是团中变量的非负函数。配分函数：
$$
Z = \sum{x_1,\dots, xn}\prod{c \in C}\phi_c(x_c)
$$
是一个标准化常数，确保分布总和为1。

因此，给定图$G$，概率分布可能包含$G$中任何团的因子，这些团可以是单个节点、边、三角形等。注意，我们不需要为每个团指定一个因子。上面的例子中，我们为每个边定义了一个因子（这是两个节点的团）。然而，我们选择不指定任何一元因子，即单个节点的团。

与贝叶斯网络的比较

前面举的投票的例子中，$A, B, C, D$上的概率满足$A \perp C \mid {B, D}, B \perp D \mid {A, C}$（因为只有朋友会直接影响投票）。我们可以很容易地通过反例检验，这些独立性不能用贝叶斯网络完美地表示。然后马尔可夫随机场可以完美地描述这种分布。

四变量投票示例的有向模型示例。没有一个能够准确地表达我们对变量之间依赖结构的先验知识。

更一般地说，马尔可夫随机场比有向模型有如下几个优点：

• 它们可以应用于更广泛的问题，在这些问题中，不存在与变量相关性相关的自然方向性。
• 无向图可以简洁地表达贝叶斯网络难以描述的某些依赖关系（尽管反过来也是如此）。

当然，马尔可夫随机场也具有几个重要缺点：

• 计算归一化常数$Z$需要对潜在的指数数量的赋值求和。在一般情况下，这是个NP问题；因此，许多无向模型难以精确处理，需要使用近似技术。
• 无向模型可能难以解释。
• 从贝叶斯网络生成数据要容易得多，这在某些应用中很重要。

不难看出，贝叶斯网络是马尔可夫随机场的一种特殊情况，它具有特定类型的团因子（对应于条件概率分布，并在图中蕴含有向无环结构）和归一化常数1。特别是，如果我们取一个有向图$G$，并将边添加到给定节点的所有父节点（并移除它们的方向性），那么条件概率分布（被视为变量及其祖先上的因子）在生成的无向图上进行了因子分解。由此产生的过程称为道德化。

贝叶斯网络总是可以转换为归一化常数为1的无向网络。反过来也是可以的，但可能在计算上很难处理，并且可能产生非常大的（例如，完全连通的）有向图。

因此，马尔可夫随机场比贝叶斯网络更强大，但在计算上更难处理。一般的经验法则是尽可能使用贝叶斯网络，只有在无法自然地用有向图建模问题时才切换到马尔可夫速激长（如我们的投票示例）。

马尔可夫随机场中的独立性

回想一下，在贝叶斯网络的情况下，我们定义了一组由有向图$G$描述的独立性$I(G)$，并展示了它们如何描述蕴含在有向图因子分解得到的分布$p$的真实独立性，例如$I(G) \subseteq I(p)$。

那么，无向马尔可夫随机场可以描述哪些独立性？答案非常简单直观：如果变量$x, y$通过未观测变量的路径连接，则它们是相关的。然而，如果$x$的邻居都被观察到，那么$x$与所有其他变量无关，因为它们仅通过其邻居影响$x$。

在马尔可夫随机场中，给定节点X的邻居（称为X的马尔可夫毯），节点X独立于图的其余部分。

特别是，如果一组观察到的变量在图的两半之间形成割集，那么一半中的变量与另一半中的独立。

形式上，我们将变量$X$的马尔可夫毯$U$定义为最小节点集，如果观察到$U$，则$X$独立于图的其余部分，例如：$X \perp (\mathcal{X}-{X}-U) \mid U$。这一概念适用于有向和无向模型，但在无向模型下，马尔可夫毯仅等于节点的邻居。

在有向情况下，我们发现$I(G) \subseteq I(p)$，但有一些分布$p$的独立性不能用$G$来描述。无向的情况，也是如此。例如，考虑由有向v结构描述的概率，无向模型不能描述独立性假设 $X \perp Y$。

具有完美有向图表示但没有无向表示的概率分布的示例，反之亦然。

条件随机场

当将马尔可夫随机场应用于建模条件概率分布$p(y \mid x)$时（其中$x \in \mathcal{X}, y \in \mathcal{Y}$都是向量变量），出现了马尔可夫随机场的一个重要特例。这些分布在有监督学习环境中很常见，在这种环境中，我们已知$x$，并希望预测$y$。这类任务也称为结构化预测。

示例

我们先来看个例子，给定若干以像素矩阵形式提供的黑白字符图像序列$x_i \in [0, 1]^{d \times d}$，我们要从中识别出单词。预测结果是一系列字母$y_i \in {a, b, \dots, z}$。

用于OCR的链式结构条件随机场。

原则上，我们可以训练一个分类器，从$x_i$中分别预测每个$y_i$。然而，由于这些字母一起构成了一个单词，因此不同的预测应该相互通知。在上面的例子中，第二个字母本身可以是“U”或“V”；然而，由于我们可以很有信心地判断它的邻居是“Q”和“E”，我们可以推断“U”是最有可能的真实结果。条件随机场可以让我们实施此类预测。

正式定义

条件随机场是变量$\mathcal{X} \cup \mathcal{Y}$上的马尔可夫网络，它指定了条件分布
$$
P(y \mid x) = \frac{1}{Z(x)}\prod_{c \in C}\phi_c(x_c, yc)
$$
其配分函数为：
$$
Z(x) = \sum{y \in \mathcal{Y}}\prod_{c \in C}\phi_c(x_c, y_c)
$$
注意，在这种情况下，分区常数取决于$x$（因此，我们说它是一个函数），这并不奇怪：$p(y \mid x)$是$y$上由$x$参数化的概率，即，它为每个$x$编码不同的概率函数。在这个意义上，条件随机场导致每个输入$x$的新马尔可夫随机场的实例化。

示例（续）

更正式地说，假设$p(y \mid x)$是具有两种因素的链式条件随机场：因子$\phi(x_i, y_i)$将与输入$x_i$一致的较高值分配给$y_i$；以及因子$\phi(yi, y{i+i})$。我们也可以认为$\phi(x_i, y_i)$是由标准（非结构化）softmax回归给出的概率$p(y_i \mid x_i)$，$\phi(yi, y{i+i})$可以看作是从大量英语文本中获得的字母共现的经验频率。

给定这种形式的模型，我们可以用MAP联合推断出结构化标签$y$:
$$
\arg \max_y \phi(x_1, y1)\prod{i=2}^{n}\phi(y_{i-1}, y_i)\phi(x_i, y_i)
$$

CRF特性

在大多数实际应用中，我们进一步假设因子$\phi_c(x_c,y_c)$的形式为：
$$
\phi_c(x_c,y_c) = \exp(w_c^T f_c(x_c, y_c))
$$
其中$f_c(x_c, y_c)$可以是描述$x_c$和$y_c$之间兼容性的任意一组特性。

在我们的OCR示例中，我们可以引入对字母$y_i$与像素$x_i$的兼容性进行编码的特征$f(x_i, y_i)$。例如$f(x_i, y_i)$可能是逻辑回归（或深度神经网络）根据像素$x_i$产生的字母$y_i$的概率。此外，我们在相邻字母之间引入了特征$f(yi, y{i+1})$。可以形式化地表述为$f(yi, y{i+1}) = II(y_i = \ell1, y{i+1} = \ell_2)$，其中$\ell_1, \ell_2$是字母表中的2个字母。然后，条件随机场会学习权重$w$，这将为更常见的连续字母$(\ell_1, \ell_2)$概率分配更多的权重，同时确保预测的$y_i$与输入的$x_i$一致。这个过程可以让我们在$x_i$不明确的情况下确定$y_i$，就像上面的例子一样。

关于CRF特征最重要的认知是它们可以任意复杂。事实上，我们可以用因子$\phi(x,y_i) = \exp(w_i^T f(x, y_i))$定义OCR模型，这样将完全依赖输入$x$。这完全不会影响计算性能，因为在推断时，$x$总是被观察到的，而我们的解码问题涉及最大化
$$
\phi(x, y1) \prod{i=2}^n \phi(y_{i-1}, y_i) \phi(x, y_i) = \phi'(y1) \prod{i=2}^n \phi(y_{i-1}, y_i) \phi'(y_i),
$$
其中$\phi'(y_i) = \phi(x,y_i)$。使用全局特征只会改变因子的值，而不会改变它们的范围，因为它们具有相同类型的链结构。我们将在下一节中看到，这种结构是确保我们能够轻松解决这个优化问题所需的全部。

这一观察结果可以用更加一般的形式来解释。如果我们使用马尔可夫随机场对$p(x, y)$进行建模（视为$x，y$上的单一模型，具有标准化常数$Z = \sum_{x,y} \tilde{p}(x,y)$），那么我们需要将两个分布拟合到数据中：$p(y\mid x)$ 和 $p(x)$。然而，如果我们感兴趣的是预测给定$x$的$y$，那么建模$p(x)$就没有必要了。事实上，在统计上这样做可能是不利的（例如：我们可能没有足够的数据来拟合$p(y\mid x)$和$p(x)$；由于模型具有共享参数，因此拟合其中一个可能不会得到另一个的最佳参数），并且在计算上这可能也不可行（我们需要在分布中作出简化假设，这样$p(x)$就可以容易地处理）。CRF放弃了这一假设，通常在预测任务中表现更好。

因子图

在展示马尔可夫随机场时，经常使用因子和变量明确分离的方式来表示。因子图就是常用的表示方法。因子图由两部分组成，其中一部分是用于建模分布的变量，另一部分是在这些变量上定义的因子。边位于因子和因子所依赖的变量之间。

具有三个变量和四个因子的因子图示例。

这个视图使我们能够更容易地看到变量之间的因子依赖关系，稍后我们将看到它使我们能够更加容易地计算一些概率分布。