条件随机场（CRF）（三）：三大核心问题之解码与概率计算

1. CRF的三大核心问题概述

一个训练好的概率模型，通常需要回答以下几个基本问题。对于CRF，这三大问题是：

1. 概率计算问题：

   • 问题描述：给定观测序列 $X$ 和标签序列 $Y$，计算条件概率 $p(Y|X)$。这个问题本身不太常用，但它的副产品——计算归一化因子 $Z(X)$——却是重中之重（为什么这么说呢？）。此外，计算某些边缘概率，如“序列第 $t$ 个位置的标签是名词的概率” $p(y_t=\text{名词}|X)$，也属于此类问题。
   • 核心算法：前向-后向算法 (Forward-Backward Algorithm)。

2. 解码问题：

   • 问题描述：给定观测序列 $X$，在所有可能的标签序列中，找到使条件概率 $p(Y|X)$ 最大的那一条序列 $Y^{\ast }$。这通常是我们最关心的应用问题，比如为一句话找到最可能的词性标注序列。

     $$Y^{\ast }=\arg \underset{Y}{\max }p(Y|X)$$

   • 核心算法：维特比算法 (Viterbi Algorithm)。

3. 学习问题：

   • 问题描述：给定一个训练数据集（包含观测序列和对应的真实标签序列），学习出模型的参数 $\theta$。
   • 核心算法：通常使用基于梯度的优化算法，如L-BFGS。我们将在后续详细讨论。

本文将聚焦于前两个问题。我们会发现，这两个问题的解决方法都巧妙地运用了动态规划 (Dynamic Programming) 的思想来避免暴力计算。

2. 概率计算问题：前向-后向算法

挑战：$Z(X)$ 的计算

回顾一下CRF的定义：$p(Y|X)=\frac{1}{Z(X)}\exp (\dots )$。要计算这个概率，我们必须先求出归一化因子 $Z(X)$。根据定义：

$$Z(X)=\sum _{Y^{\prime }}\prod _{t=1}^T{\Psi }_t(y_{t-1}^{\prime },y_t^{\prime },X)$$

假设句子长度 $T=10$，标签种类 $M=5$（比如，名词、动词、代词、介词、形容词）。那么总的标签序列数量为 $5^{10}$，这是一个天文数字。（是不是让你想起HMM的求解来了？）暴力遍历所有路径来求和是绝对不可行的。

前向算法

前向算法的核心思想是：与其在最后把所有路径的和加起来，不如每向前走一步，就把到达当前节点的所有路径的和计算出来并存起来，供下一步使用。

我们定义前向变量 ${\alpha }_t(j)$：

${\alpha }_t(j)$ 的含义：在观测序列 $X$ 的条件下，从序列开始到位置 $t$，且位置 $t$ 的标签为 $j$ 的所有部分路径的非归一化概率之和。

这里的“非归一化概率”就是路径上所有势函数的乘积。

前向变量的递推

让我们来推导 ${\alpha }_t(j)$ 是如何计算的。

• 初始化 (t=1)： 对于第一个位置，我们定义一个虚拟的起始状态 $y_0=\text{START}$。那么，到达位置1且标签为 $j$ 的路径只有一条，其非归一化概率就是势函数 ${\Psi }_1$ 的值。

  $${\alpha }_1(j)={\Psi }_1(y_0=\text{START},y_1=j,X)$$

• 递推 (t > 1)： 要计算 ${\alpha }_t(j)$，我们需要考虑所有能够到达“位置 $t$ 且标签为 $j$”的路径。这些路径必然是从前一个位置 $t-1$ 的某个标签 $i$ 转移过来的。

  对于任意一个前一状态 $i$，到达它的所有路径的非归一化概率之和已经被我们计算并储存在 ${\alpha }_{t-1}(i)$ 中了。从 $i$ 转移到 $j$ 的这一小步，其分值为 ${\Psi }_t(y_{t-1}=i,y_t=j,X)$。

  因此，所有经过“$t-1$ 位置标签为 $i$”并到达“$t$ 位置标签为 $j$”的路径的总分就是 ${\alpha }_{t-1}(i)\cdot {\Psi }_t(i,j,X)$。

  我们把所有可能的前一状态 $i=1,2,\dots ,M$ 的情况都加起来，就得到了 ${\alpha }_t(j)$：

  $${\alpha }_t(j)=\sum _{i=1}^M{\alpha }_{t-1}(i)\cdot {\Psi }_t(y_{t-1}=i,y_t=j,X)$$

  这个过程可以用矩阵形式清晰地表示。如果我们把 ${\alpha }_{t-1}$ 看作一个行向量 $[{\alpha }_{t-1}(1),\dots ,{\alpha }_{t-1}(M)]$，把 $M_t(X)$ 看作在矩阵形式中定义的转移矩阵，那么：

  $${\alpha }_t^T={\alpha }_{t-1}^T{M}_t(X)$$

使用前向变量计算 $Z(X)$

当我们一路递推到最后一个位置 $T$ 时，我们就得到了所有终点为 $j$ 的路径的非归一化概率之和 ${\alpha }_T(j)$。把所有可能的终点 $j=1,\dots ,M$ 的情况加起来，就得到了所有路径的总和，这正是 $Z(X)$！

$$Z(X)=\sum _{j=1}^M{\alpha }_T(j)$$

(注：更严谨地，通常会再乘以一个从 $y_T$ 到虚拟终止状态 $y_{T+1}=\text{STOP}$ 的势函数，这里为简化暂不写出。)

通过这种方式，我们将指数级的计算复杂度降低到了 $O(T\cdot M^2)$，这是完全可以接受的。

后向算法

与前向算法类似，我们也可以从后往前定义后向变量 ${\beta }_t(i)$：

${\beta }_t(i)$ 的含义：在观测序列 $X$ 的条件下，从位置 $t$ 的标签为 $i$ 开始，一直到序列结束的所有部分路径的非归一化概率之和。

后向变量的递推

• 初始化 (t=T)： 我们定义一个虚拟的终止状态 $y_{T+1}=\text{STOP}$。

  $${\beta }_T(i)={\Psi }_{T+1}(y_T=i,y_{T+1}=\text{STOP},X)(\text{通常设为1})$$

• 递推 (t < T)：

  $${\beta }_t(i)=\sum _{j=1}^M{\Psi }_{t+1}(y_t=i,y_{t+1}=j,X)\cdot {\beta }_{t+1}(j)$$

  矩阵形式为：

  $${\beta }_t=M_{t+1}(X){\beta }_{t+1}$$

结合前向-后向变量计算边缘概率

前向和后向变量结合起来非常强大。例如，我们可以计算在 $t$ 时刻标签为 $i$ 的概率 $p(y_t=i|X)$。 任何一条在 $t$ 时刻经过标签 $i$ 的完整路径，其非归一化概率必然等于“从开始到 $t$ 位置标签 $i$ 的前半段路径”的概率，乘以“从 $t$ 位置标签 $i$ 到结尾的后半段路径”的概率。 因此，所有经过 $t$ 时刻标签 $i$ 的路径总分是 ${\alpha }_t(i)\cdot {\beta }_t(i)$。 再用全局的 $Z(X)$ 进行归一化，就得到了边缘概率：

$$p(y_t=i|X)=\frac{{\alpha }_t(i){\beta }_t(i)}{Z(X)}$$

（有没有觉得和 5.1 单个状态的概率：${\gamma }_t(i)$很像啊） 同理，我们也可以计算边的边缘概率 $p(y_{t-1}=i,y_t=j|X)$，这在学习算法中至关重要：

$$p(y_{t-1}=i,y_t=j|X)=\frac{{\alpha }_{t-1}(i)\cdot {\Psi }_t(i,j,X)\cdot {\beta }_t(j)}{Z(X)}$$

3. 解码问题：维特比算法

现在我们来解决最常用的解码问题：找到最优的标签序列 $Y^{\ast }$。

一个天真的想法是：我们用前向-后向算法计算出每个位置 $t$ 最可能的标签 $y_t$，然后把它们拼起来。这是错误的！ 这样得到的序列很可能不是一个合法的、全局最优的序列。（跟HMM的近似算法一样一样的）例如，可能在 $t-1$ 时刻“代词”概率最高，在 $t$ 时刻“名词”概率最高，但“代词-名词”这个转移本身的概率可能极低。

我们需要一个寻找全局最优路径的算法。这就是维特比算法。

维特比算法 vs. 前向算法

维特比算法的思路和前向算法几乎一模一样，都是动态规划。唯一的区别是：

• 前向算法在递推时，将所有可能路径的得分用 sum 加起来。
• 维特比算法在递推时，只保留所有可能路径中得分最高的那条，即用 max 操作。

我们定义维特比变量 ${\delta }_t(j)$：

${\delta }_t(j)$ 的含义：在观测序列 $X$ 的条件下，从序列开始到位置 $t$，且位置 $t$ 的标签为 $j$ 的所有部分路径中，得分最高的那条路径的非归一化概率。

同时，我们还需要一个回溯指针 ${\psi }_t(j)$来记录这条最优路径是从前一个时刻的哪个状态转移过来的。

维特比算法的递推

• 初始化 (t=1)： $$\begin{gathered} {\delta }_1(j)={\Psi }_1(\text{START},j,X) \\ {\psi }_1(j)=\text{START} \end{gathered}$$
• 递推 (t > 1)： 要计算 ${\delta }_t(j)$，我们考虑所有可能的前一状态 $i$。对于每一个 $i$，从它转移到 $j$ 的路径得分是 ${\delta }_{t-1}(i)\cdot {\Psi }_t(i,j,X)$。我们在所有 $i$ 中找到使这个值最大的那个： $${\delta }_t(j)=\underset{1\le i\le M}{\max }\left\{{\delta }_{t-1}(i)\cdot {\Psi }_t(i,j,X)\right\}$$ 同时，我们记录下这个最大值是从哪个 $i^{\ast }$ 来的： $${\psi }_t(j)=\arg \underset{1\le i\le M}{\max }\left\{{\delta }_{t-1}(i)\cdot {\Psi }_t(i,j,X)\right\}$$

终止与回溯 (Backtracking)

1. 终止：当递推到最后一个位置 $T$ 时，我们找到最终的最优路径得分和终点：

   $$\begin{gathered} P^{\ast }=\underset{1\le j\le M}{\max }{\delta }_T(j) \\ {y}_T^{\ast }=\arg \underset{1\le j\le M}{\max }{\delta }_T(j) \end{gathered}$$

2. 回溯：我们已经知道了最优路径的最后一个标签是 $y_T^{\ast }$。那么，它前一个标签是什么呢？我们只需查找回溯指针：

   $$y_{T-1}^{\ast }={\psi }_T(y_T^{\ast })$$

   然后继续往前找：

   $$y_{T-2}^{\ast }={\psi }_{T-1}(y_{T-1}^{\ast })$$

   如此反复，直到找到路径的起点。这样，我们就重建了整条最优路径 $Y^{\ast }=(y_1^{\ast },y_2^{\ast },\dots ,y_T^{\ast })$。

维特比算法的计算复杂度同样是 $O(T\cdot M^2)$，非常高效。

---

总结

在本报告中，我们攻克了CRF的两个核心推断问题：

1. 概率计算：我们学习了前向-后向算法，它利用动态规划高效地计算归一化因子 $Z(X)$ 以及各个节点和边的边缘概率，为学习算法打下了基础。
2. 解码：我们学习了维特比算法，它同样利用动态规划，通过 max 操作和回溯指针来高效地找出全局最优的标签序列。

至此，我们已经掌握了如何使用一个训练好的CRF。在后续 条件随机场（CRF）（四）：学习算法 中，我们将解答最后一个问题：CRF模型本身是如何从数据中学习出来的？