概述

条件随机场（Conditional Random Field，CRF）是给定一组输入随机变量条件下，另一组输出随机变量的条件概率分布模型，其特点是假设输出随机变量构成马尔科夫随机场。本文主要讨论线性链条件随机场，这一方法在标注问题中被广泛使用，例如自然语言处理中的词性标注等。

备注：马尔科夫随机场

马尔科夫随机场是随机场中的一个特例，它假设随机场中某一个位置的赋值仅仅与和它相邻位置的复制有关，而和与其不相邻位置的赋值无关。

线性链条件随机场

定义

设 $X$ 和 $Y$ 是随机变量， $P (Y | X)$ 是在给定 $X$ 的条件下 $Y$ 的概率分布。如果随机变量 $Y$ 构成一个无向图 $G = (V, E)$ 表示的马尔科夫随机场，即 $P (Y_{v} | X, Y_{w}, w \neq v) = P (Y_{v} | X, Y_{w}, w \sim v)$ 对于任意结点 $v$ 成立，那么条件概率分布 $P (Y | X)$ 为条件随机场。式中 $w \sim v$ 表示在图 $G = (V, E)$ 中与结点 $v$ 有边连接的所有结点 $w$ ， $w \neq v$ 表示结点 $v$ 以外的所有结点。 $Y_{v}$ ， $Y_{w}$ 为结点 $v$ ， $w$ 对应的随机变量。

如果考虑线性链的情况，即 $G = (V = {1, 2, \dots, n}, E = {(i, i + 1)}), i = 1, 2, \dots, n - 1$ 。在此情况下， $X = (X_{1}, X_{2}, \dots, X_{n})$ ， $Y = (Y_{1}, Y_{2}, \dots, Y_{n})$ 。此时 $P (Y | X)$ 为线性链条件随机场，如下图所示：

在标注问题中， $X$ 表示输入观测序列， $Y$ 表示对应的输出标记序列或者状态序列。

在线性链条件随机场中，如果随机变量 $X$ 取值为 $x = {x_{1}, x_{2}, \dots, x_{n}}$ ，那么随机变量 $Y$ 取值为 $y = {y_{1}, y_{2}, \dots, y_{n}}$ 的条件概率具有如下形式： $P (y | x) = \frac{1}{Z (x)} \exp (\sum_{i, k} λ_{k} t_{k} (y_{i - 1}, y_{i}, x, i) + \sum_{i, l} μ_{l} s_{l} (y_{i}, x, i))$ 其中 $Z (x) = \sum_{y} \exp (\sum_{i, k} λ_{k} t_{k} (y_{i - 1}, y_{i}, x, i) + \sum_{i, l} μ_{l} s_{l} (y_{i}, x, i))$ 为归一化因子； $t_{k}$ ， $s_{l}$ 代表特征函数； $λ_{k}$ 和 $μ_{l}$ 为对应的权值。 $t_{k}$ 是定义在边上的特征函数，被称为转移特征，依赖于当前和前一个位置； $s_{l}$ 是定义在结 l 点上的特征函数，称为状态特征，它依赖于当前位置。通常，两个特征函数的取值为 0 或 1，当满足特征条件时取值为 1，否则为 0。因此，一个条件随机场完全由其特征函数 $t_{k}$ ， $s_{l}$ 及其对应的权值 $λ_{k}$ ， $μ_{l}$ 确定。

以词性标注问题为例，特征方程 $t_{k} (y_{i - 1}, y_{i}, x, i)$ 可以被定义为如果 $y_{i - 1}$ 是形容词而 $y_{i}$ 是名词时等于 1，否则等于 0。为了构建一个用于词性标注的 CRF 模型，通常需要定义很多个类似于这样的特征方程，每一个特征方程对应于一个语法规则。

简化形式

条件随机场还可以由简化形式表示。在条件随机场的表达式中，同一特征在每个位置都有定义，因此可以对同一个特征在各个位置求和，将局部特征函数转化为一个全局特征函数。这样，就可以将条件随机场写成权值向量和特征向量的内积形式，从而得到简化的形式。

为了简便起见，我们将转移特征和状态特征及其权值用统一的符号表示。设有 $K_{1}$ 个转移特征， $K_{2}$ 个状态特征， $K = K_{1} + K_{2}$ ，记 $f_{k} (y_{i - 1}, y_{i}, x, i) = {\begin{cases} t_{k} (y_{i - 1}, y_{i}, x, i), & k = 1, 2, \dots, K_{1} \\ s_{l} (y_{i}, x, i), & k = K_{1} + l; l = 1, 2, \dots, K_{2} \end{cases}$ 然后对转移和状态特征在各个位置 $i$ 求和，记作： $f_{k} (y, x) = \sum_{i = 1}^{n} f_{k} (y_{i - 1}, y_{i}, x, i), k = 1, 2, \dots, K$ 用 $w_{k}$ 表示特征 $f_{k} (y, x)$ 的权值，即 $w_{k} = {\begin{cases} λ_{k}, & k = 1, 2, \dots, K_{1} \\ μ_{l}, & k = K_{1} + l; l = 1, 2, \dots, K_{2} \end{cases}$ 于是条件随机场可以表示为如下形式： $P (y | x) = \frac{1}{Z (x)} \exp \sum_{k = 1}^{K} w_{k} f_{k} (y, x) Z (x) = \sum_{y} \exp \sum_{k = 1}^{K} w_{k} f_{k} (y, x)$ 如果记 $w = (w_{1}, w_{2}, \dots, w_{K})$ 为权值向量， $F (y, x) = (f_{1} (y, x), f_{2} (y, x), \dots, f_{K} (y, x))^{T}$ 为全局特征向量，那么条件随机场可以写成向量 $w$ 和 $F (y, x)$ 的内积形式： $P (y | x) = \frac{\exp (w \cdot F (y, x))}{Z (x)} Z (x) = \sum_{y} w \cdot F (y, x))$

矩阵形式

条件随机场还可以由矩阵表示。假设 $P (y | x)$ 是一个线性链条件随机场，表示对给定观测序列 $x$ ，相应的标记序列 $y$ 的条件概率。引入特殊的起点和终点状态标记 $y_{0} = start$ ， $y_{n + 1} = stop$ ，此时 $P (y | x)$ 可以通过矩阵形式表示。

对观测序列 $x$ 的每一个位置 $i = 1, 2, \dots, n + 1$ ，定义一个 $m$ 阶矩阵（ $m$ 代表标记 $y_{i}$ 取值的个数）： $M_{i} (x) = [M_{i} (y_{i - 1}, y_{i} | x)]$ 其中， $M_{i} (y_{i - 1}, y_{i} | x) = \exp (W_{i} (y_{i - 1}, y_{i} | x))$ ， $W_{i} (y_{i - 1}, y_{i} | x) = \sum_{i = 1}^{K} w_{k} f_{k} (y_{i - 1}, y_{i}, x, i)$ 。这样，给定观测序列 $x$ ，标记序列 $y$ 的非规范化概率可以通过 $n + 1$ 个矩阵的乘积 $\prod_{i = 1}^{n + 1} M_{i} (y_{i - 1}, y_{i} | x)$ 表示，于是条件概率 $P (y | x)$ 可以写为： $P (y | x) = \frac{1}{Z (x)} \prod_{i = 1}^{n + 1} M_{i} (y_{i - 1}, y_{i} | x)$ 其中 $Z (x)$ 为规范化因子，是 $n + 1$ 个矩阵乘积的 $(start,stop)$ 元素，表示以 start 为起点 stop 为终点通过状态的所有路径 $y_{1} y_{2} \dots y_{n}$ 的非规范化概率之和。

概率计算

前向 - 后向算法

条件随机场的概率计算问题是给定条件随机场 $P (Y | X)$ ，输入序列 $x$ 和输出序列 $y$ ，计算条件概率 $P (Y_{i} = y_{i} | x)$ ， $P (Y_{i - 1} = y_{i - 1}, Y_{i} = y_{i} | x)$ 以及相应的数学期望的问题。为了方便起见，通过引入像隐马尔科夫模型一样的前向 - 后向向量，递归地计算概率和期望值。这样的算法被称为前向 - 后向算法。

对于 $i = 0, 1, \dots, n + 1$ ，定义前向向量 $α_{i} (x)$ ： $α_{0} = {\begin{cases} 1, & y = start \\ 0, & Otherwise \end{cases}$ 递推公式为： $α_{i}^{T} (y_{i} | x) = α_{i - 1}^{T} (y_{i} | x) M_{i} (y_{i - 1}, y_{i} | x), i = 1, 2, \dots, n + 1$ $α_{i} (y_{i} | x)$ 表示在位置 $i$ 的标记是 $y_{i}$ 并且到位置 $i$ 的前部分标记序列的非规范化概率。由于 $y_{i}$ 可取的值有 $m$ 个，因此 $α_{i} (x)$ 为 $m$ 维列向量。

同样地，对于 $i = 0, 1, \dots, n + 1$ ，定义后向向量 $β_{i} (x)$ ： $β_{n + 1} (y_{n + 1} | x) = {\begin{cases} 1, & y_{n + 1} = stop \\ 0, & Otherwise \end{cases}$ 递推公式为： $β_{i} (y_{i} | x) = M_{i} (y_{i}, y_{i + 1} | x) β_{i - 1} (y_{i + 1} | x), i = 1, 2, \dots, n + 1$ $β_{i} (y_{i} | x)$ 表示在位置 $i$ 的标记为 $y_{i}$ 并且从 $i + 1$ 到 $n$ 的后部分标记序列的非规范化概率。

根据前向 - 后向向量的定义可以得到： $Z (x) = α_{n}^{T} (y_{n} | x) \cdot 1 = 1 \cdot β_{1} (y_{1} | x)$

概率计算

按照前向 - 后向向量的定义，很容易计算标记序列在位置 $i$ 是标记 $y_{i}$ 的条件概率，和在位置 $i - 1$ 与 $i$ 是标记 $y_{i - 1}$ 和 $y_{i}$ 的条件概率： $P (Y_{i} = y_{i} | x) = \frac{α_{i}^{T} (y_{i} | x) β_{i} (y_{i} | x)}{Z (x)} P (Y_{i - 1} = y_{i - 1}, Y_{i} = y_{i} | x) = \frac{α_{i - 1}^{T} (y_{i - 1} | x) M_{i} (y_{i - 1}, y_{i} | x) β_{i} (y_{i} | x)}{Z (x)}$

期望值的计算

利用前向 - 后向向量，可以计算特征函数关于联合分布 $P (X, Y)$ 和条件分布 $P (Y | X)$ 的数学期望。

特征函数 $f_{k}$ 关于条件分布 $P (Y | X)$ 的数学期望是： $\begin{aligned} E_{P (Y | X)} [f_{k}] = & \sum_{y} P (y | x) f_{k} (y, x) \\ = & \sum_{i = 1}^{n + 1} \sum_{y_{i - 1} y_{i}} f_{k} (y_{i - 1}, y_{i}, x, i) \frac{α_{i - 1}^{T} (y_{i - 1} | x) M_{i} (y_{i - 1}, y_{i} | x) β_{i} (y_{i} | x)}{Z (x)}, k = 1, 2, \dots, K \end{aligned}$ 假设经验分布为 $\tilde{P} (X)$ ，特征函数 $f_{k}$ 关于联合分布 $P (X, Y)$ 的数学期望是 $\begin{aligned} E_{P (X, Y)} [f_{k}] = & \sum_{x, y} P (x, y) \sum_{i = 1}^{n + 1} f_{k} (y_{i - 1}, y_{i}, x, i) \\ = & \sum_{x} \tilde{P} (x) \sum_{y} P (y | x) \sum_{i = 1}^{n + 1} f_{k} (y_{i - 1}, y_{i}, x, i) \\ = & \sum_{x} \tilde{P} (x) \sum_{i = 1}^{n + 1} \sum_{y_{i - 1} y_{i}} f_{k} (y_{i - 1}, y_{i}, x, i) \frac{α_{i - 1}^{T} (y_{i - 1} | x) M_{i} (y_{i - 1}, y_{i} | x) β_{i} (y_{i} | x)}{Z (x)} \end{aligned}$ 上式为特征函数数学期望的一般计算公式，可以将其中的 $f_{k}$ 替换为转移特征或者状态特征。

根据上述这些表达式，对于给定的观测序列和标记序列，可以通过一次前向扫描计算 $α_{i}$ 和 $Z (x)$ ，通过一次后向扫描计算 $β_{i}$ ，从而计算所有的概率和特征的期望。

学习算法

已知训练数据集，由此可知经验概率分布为 $\tilde{P} (X, Y)$ ，可以通过极大化训练数据的对数似然函数来求模型参数。训练数据的对数似然函数为： $L (w) = \log \prod_{x, y} P (y | x)^{\tilde{P} (x, y)} = \sum_{x, y} \tilde{P} (x, y) \log P (y | x)$ 当 $P (y | x)$ 是一个条件随机场模型时，对数似然函数为： $\begin{aligned} L (w) = & \sum_{x, y} \tilde{P} (x, y) \log P (y | x) \\ = & \sum_{x, y} [\tilde{P} (x, y) \sum_{k = 1}^{K} w_{k} f_{k} (y, x) - \tilde{P} (x, y) \log Z (x)] \\ = & \sum_{j = 1}^{N} \sum_{k = 1}^{K} w_{k} f_{k} (y_{j}, x_{j}) - \sum_{j = 1}^{N} \log Z (x_{j}) \end{aligned}$ 改进的迭代尺度法通过迭代的方法不断优化对数似然函数改变量的下界，达到极大化对数似然函数的目的。假设模型的当前参数向量为 $w = (w_{1}, w_{2}, \dots, w_{k})^{T}$ ，向量的增量为 $δ = (δ_{1}, δ_{2}, \dots, δ_{K})^{T}$ ，那么更新的参数向量为 $w + δ = (w_{1} + δ_{1}, w_{2} + δ_{2}, \dots, w_{K} + δ_{K})^{T}$ 。在每步迭代过程中，改进的迭代尺度法通过依次求解下式得到 $δ$ ： $\begin{aligned} E_{\tilde{P}} [t_{k}] = & \sum_{x, y} \tilde{P} (x, y) \sum_{i = 1}^{n + 1} t_{k} (y_{i - 1}, y_{i}, x, i) \\ = & \sum_{x, y} \tilde{P} (x) P (y | x) \sum_{i = 1}^{n + 1} t_{k} (y_{i - 1}, y_{i}, x, i) \exp (δ_{k} T (x, y)), k = 1, 2, \dots, K_{1} \end{aligned}$

$\begin{aligned} E_{\tilde{P}} [s_{l}] = & \sum_{x, y} \tilde{P} (x, y) \sum_{i = 1}^{n + 1} s_{l} (y_{i}, x, i) \\ = & \sum_{x, y} \tilde{P} (x) P (y | x) \sum_{i = 1}^{n + 1} s_{l} (y_{i}, x, i) \exp (δ_{K_{1} + l} T (x, y)), l = 1, 2, \dots, K_{2} \end{aligned}$

其中 $T (x, y)$ 代表在数据 $(x, y)$ 中出现所有特征数的总和： $T (x, y) = \sum_{k} f_{k} (y, x) = \sum_{k = 1}^{K} \sum_{i = 1}^{n + 1} f_{k} (y_{i - 1}, y_{i}, x, i)$ 对于不同的数据 $(x, y)$ ， $T (x, y)$ 的取值可能不同，为了处理这个问题定义松弛特征： $s (x, y) = S - \sum_{k = 1}^{K} \sum_{i = 1}^{n + 1} f_{k} (y_{i - 1}, y_{i}, x, i)$ 其中 $S$ 是个常数，选择足够大的常数 $S$ 使得对训练数据集的所有数据 $(x, y)$ ， $s (x, y) \geq 0$ 成立。这时特征总数可以取 $S$ 。

此时，对于转移特征 $t_{k}$ ， $δ_{k}$ 的更新方程为： $E_{\tilde{P}} [t_{k}] = \sum_{x, y} \tilde{P} (x) P (y | x) \sum_{i = 1}^{n + 1} t_{k} (y_{i - 1}, y_{i}, x, i) \exp (δ_{k} S) \Rightarrow δ_{k} = \frac{1}{S} \log \frac{E_{\tilde{P}} [t_{k}]}{E_{P} [t_{k}]}$ 对于状态特征 $s_{l}$ ， $δ_{k}$ 的更新方程为： $E_{\tilde{P}} [s_{l}] = \sum_{x, y} \tilde{P} (x) P (y | x) \sum_{i = 1}^{n + 1} s_{l} (y_{i}, x, i) \exp (δ_{K_{1} + l} S) \Rightarrow δ_{K_{1} + l} = \frac{1}{S} \log \frac{E_{\tilde{P}} [s_{l}]}{E_{P} [s_{l}]}$ 当 $S$ 取的足够大时，每步迭代的增量向量会变大，从而导致算法收敛变慢。

另一个改进方法是对每个观测序列 $x$ 计算其特征总数的最大值 $T (x) = max_{y} T (x, y)$ 。利用前向 - 后向递推公式，可以计算得到 $T (x) = t$ 。此时，关于转移特征参数的更新方程可以写成： $\begin{aligned} E_{\tilde{P}} [t_{k}] = & \sum_{x, y} \tilde{P} (x) P (y | x) \sum_{i = 1}^{n + 1} t_{k} (y_{i - 1}, y_{i}, x, i) \exp (δ_{k} T (x)) \\ = & \sum_{x} \tilde{P} (x) \sum_{y} P (y | x) \sum_{i = 1}^{n + 1} t_{k} (y_{i - 1}, y_{i}, x, i) \exp (δ_{k} T (x)) \\ = & \sum_{x} \tilde{P} (x) a_{k, t} \exp (δ_{k} \cdot t) \\ = & \sum_{t = 0}^{T_{max}} a_{k, t} β_{k}^{t} \end{aligned}$ 其中 $a_{k, t}$ 为特征 $t_{k}$ 的期望值， $δ_{k} = \log β_{k}$ 。 $β_{k}$ 为多项式方程的唯一实根，可以用牛顿法求得，从而求得对应的 $δ_{k}$ 。

同样，关于状态特征的参数更新方程可以写为： $\begin{aligned} E_{\tilde{P}} [s_{l}] = & \sum_{x, y} \tilde{P} (x) P (y | x) \sum_{i = 1}^{n + 1} s_{l} (y_{i}, x, i) \exp (δ_{K_{1 + l}} T (x, y)) \\ = & \sum_{x} \tilde{P} (x) \sum_{y} P (y | x) \sum_{i = 1}^{n} s_{l} (y_{i}, x, i) \exp (δ_{K_{1 + l}} T (x)) \\ = & \sum_{x} \tilde{P} (x) b_{l, t} \exp (δ_{k} \cdot t) \\ = & \sum_{t = 0}^{T_{max}} b_{l, t} γ_{l}^{t} \end{aligned}$ 其中 $b_{l, t}$ 是特征 $s_{l}$ 的期望值， $δ_{l} = \log γ_{l}$ ， $γ_{l}$ 为多项式方程的唯一实根，也可以用牛顿法求得。

备注：计算对数似然函数的极大值也可以使用梯度下降法、牛顿法等方法，不局限于迭代尺度法。

预测算法

条件随机场的预测问题是给定条件随机场 $P (Y | X)$ 和输入序列（观测序列） $x$ ，求条件概率最大的输出序列（标记序列） $y^{*}$ ，即对观测序列进行标注。条件随机场的预测算法是维特比算法。

$\begin{aligned} y^{*} = & \arg max_{y} P (y | x) \\ = & \arg max_{y} \frac{\exp (w \cdot F (y, x))}{Z (x)} \\ = & \arg max_{y} \exp (w \cdot F (y, x)) \\ = & \arg max_{y} (w \cdot F (y, x)) \end{aligned}$ 因此条件随机场的预测问题相当于是求非规范化概率最大的路径问题，此处的路径表示标记序列。由于只需要计算非规范化概率，因此可以大大提高效率。

维特比算法的步骤如下：

首先求出位置 1 的各个标记 $j = 1, 2, \dots, m$ 的非规范化概率： $δ_{1} (j) = w_{1} \cdot F_{1} (y_{0} = start, y_{1} = j, x), j = 1, 2, \dots, m$
由递推公式，可以计算得到位置 $i$ 的各个标记 $l = 1, 2, \dots, m$ 的非规范化概率的最大值： $δ_{i} (l) = max_{1 \leq j \leq m} {δ_{i - 1} (j) + w_{i} \cdot F_{i} (y_{i - 1} = j, y_{i} = l, x)}, l = 1, 2, \dots, m$ 同时记录非规范化概率最大值的路径： $ψ_{i} (l) = \arg max_{1 \leq j \leq m} {δ_{i - 1} (j) + w_{i} \cdot F_{i} (y_{i - 1} = j, y_{i} = l, x)}, l = 1, 2, \dots, m$ 直到 $i = n$ 时终止。
最终求得非规范化概率的最大值为： $max_{y} (w \cdot F (y, x)) = max_{1 \leq j \leq m} δ_{n} (j)$ 以及最优路径的终点： $y_{n}^{*} = \arg max_{1 \leq j \leq m} δ_{n} (j)$ 由此最优路径终点返回， $y_{i}^{*} = ψ_{i + 1} (y_{i + 1}^{*})$ ，求得最优路径 $y^{*} = (y_{1}^{*}, y_{2}^{*}, \dots, y_{n}^{*})^{T}$ 。

Yufei Luo's Blog

机器学习 - 条件随机场

概述

线性链条件随机场

定义

简化形式

矩阵形式

概率计算

前向 - 后向算法

概率计算

期望值的计算

学习算法

预测算法

参考