统计学习方法第十一章条件随机场

条件随机场（conditional random field，CRF）是给定一组输入随机变量条件下另一组输出随机变量的条件概率模型，其特点是假设输出随机变量构成马尔科夫随机场。

条件随机场可以用于不同的预测问题，本节仅讨论它在标注问题的应用，因此主要讲述线性链（linear chain）条件随机场。这时，问题变成了由输入序列对输出序列预测的判别模型，形式为对数线性模型，其学习方法通常是极大似然估计或正则化的极大似然估计。

11.1 概率无向图模型

概率无向图模型（probabilistic undirected graphical model），又称为马尔科夫随机场（Markov random file），是一个可以由无向图表示的联合概率分布。

11.1.1 模型定义

图是由结点及连接结点的边组成的集合。结点和边分别记作 $\textsf{v}$ 和 $\textsf{e}$ ，结点和边的集合分别记作 $\textsf{V}$ 和 $\textsf{E}$ ，图记作 $\textsf{G}=(\textsf{V},\textsf{E})$ ，无向图是指边没有方向的图。

概率图模型（probabilistic graphical model）是由图表示的概率分布。设有联合概率分布 $P(Y)$，$Y\in{\cal Y}$ 是一组随机变量。由无向图 $\textsf{G}$ 表示概率分布，即在图 $\textsf{G}$ 中，结点 $\textsf{v}\in\textsf{G}$ 表示一个随机变量 $Y_\textsf{v}$，$Y=(Y_\textsf{v})_{\textsf{v}\in\textsf{V}}$；边 $e\in\textsf{E}$ 表示随机变量之间的概率依赖关系。

给定一个联合概率分布 $P(Y)$ 和表示它的无向图 $\textsf{G}$。首先定义无向图表示的随机变量之间存在的成对马尔科夫性局（pairwise Markov property）、部马尔科夫性（local Markov property）和全局马尔科夫性（global Markov property）。分别介绍一下三个概念：

成对马尔科夫性：设 $\textsf{u}$ 和 $\textsf{v}$ 是无向图 $\textsf{G}$ 中任意两个没有边连接的结点，结点 $\textsf{u}$ 和 $\textsf{v}$ 分别对应随机变量 $Y_\textsf{u}$ 和 $Y_\textsf{v}$。其他所有结点为 $\textsf{O}$（集合），对应的随机变量组是 $Y_\textsf{O}$。成对马尔科夫性是指给定随机变量组 $Y_\textsf{O}$ 的条件下随机变量 $Y_\textsf{u}$ 和 $Y_\textsf{v}$ 是条件独立的，其实意思就是说没有直连边的任意两个节点是独立的，即

$$P(Y_\textsf{u},Y_\textsf{v}|Y_\textsf{O})=P(Y_\textsf{u}|Y_\textsf{O})P(Y_\textsf{v}|Y_\textsf{O})$$

局部马尔科夫性：设 $\textsf{v} \in \textsf{V}$ 是无向图 $\textsf{G}$ 中任意一个结点，$\textsf{W}$ 是与 $\textsf{v}$ 有边连接的所有结点，$\textsf{O}$ 是 $\textsf{v}$，$\textsf{W}$ 以外的其他所有结点。$\textsf{v}$ 表示的随机变量是 $Y_\textsf{v}$，$\textsf{W}$ 表示的随机变量组是 $Y_\textsf{W}$，$\textsf{O}$ 表示的随机变量组是 $Y_\textsf{O}$。局部马尔科夫性是指在给定随机变量组 $Y_\textsf{W}$ 的条件下随机变量 $\textsf{v}$ 与随机变量组 $Y_\textsf{O}$ 是独立的，即

$$P(Y_\textsf{v},Y_\textsf{O}|Y_\textsf{W})=P(Y_\textsf{v}|Y_\textsf{W})P(Y_\textsf{O}|Y_\textsf{W})$$

在 $P(Y_\textsf{O}|Y_\textsf{W})>0$ 时，等价地

$$P(Y_\textsf{v}|Y_\textsf{W})=P(Y_\textsf{v}|Y_\textsf{W},Y_\textsf{O})$$

下图表示了局部马尔科夫性。

局部马尔科夫性

全局马尔科夫性：设结点集合 $\textsf{A}$，$\textsf{B}$ 是在无向图 $\textsf{G}$ 中被结点集合 $\textsf{C}$ 分开的任意结点集合，如图所示。结点集合 $\textsf{A}$，$\textsf{B}$ 和 $\textsf{C}$ 所对应的随机变量组分别是 $Y_\textsf{A}$，$Y_\textsf{B}$ 和 $Y_\textsf{C}$。全局马尔科夫性是指给定随机变量组 $Y_\textsf{C}$ 条件下随机变量组 $Y_\textsf{A}$ 和 $Y_\textsf{B}$ 是条件独立的，即

$$P(Y_\textsf{A},Y_\textsf{B}|Y_\textsf{C})=P(Y_\textsf{A}|Y_\textsf{C})P(Y_\textsf{B}|Y_\textsf{C})$$

全局马尔科夫性

上述成对的、局部的、全局的马尔科夫性定义是等价的。

定义 11.1（概率无向图模型）设有联合概率分布 $P(Y)$，由无向图 $\textsf{G}=(\textsf{V},\textsf{E})$ 表示，在图 $\textsf{G}$ 中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布 $P(Y)$ 满足成对、局部或全局马尔科夫性，就称此联合概率分布为概率无向图模型或马尔科夫随机场。

以上是概率无向图模型的定义，实际上，我们更关心的是如何求其联合概率分布。对给定的概率无向图模型，我们希望将整体的联合概率写成若干子联合概率的乘积的形式，也就是将联合概率进行因子分解，这样便于模型的学习与计算。事实上，概率无向图模型的最大特点就是易于因子分解。下面介绍这一结果。

11.1.2 概率无向图模型的因子分解

首先给出无向图中的团与最大团的定义。

定义 11.2（团与最大团）无向图 $\textsf{G}$ 中任何两个结点均有边连接的结点子集称为团（clique)。若 $\textsf{C}$ 是无向图 $\textsf{G}$ 的一个团，并且不能再加进任何一个 $\textsf{G}$ 的结点使其成为一个更大的团，则称此 $\textsf{C}$ 为最大团（maximal clique)。

下图表示由 4 个结点组成的无向图。图中由 2 个结点组成的团有 5 个：$\{\textsf{Y}_1,\textsf{Y}_2\}$，$\{\textsf{Y}_2,\textsf{Y}_3\}$，$\{\textsf{Y}_3,\textsf{Y}_4\}$ 和 $\{\textsf{Y}_4,\textsf{Y}_2\}$，$\{\textsf{Y}_1,\textsf{Y}_3\}$ 。有 2 个最大团：$\{\textsf{Y}_1,\textsf{Y}_2,\textsf{Y}_3\}$ 和 $\{\textsf{Y}_2,\textsf{Y}_3,\textsf{Y}_4\}$。

团和最大团

将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作，称为概率无向图模型的因子分解（factorization）。

给定概率无向图模型，设无向图为 $\textsf{G}$，$\textsf{C}$ 为 $\textsf{G}$ 上的最大团，$Y_\textsf{C}$表示 $\textsf{C}$ 对应的随机变量。那么概率无向图模型的联合概率分布 $P(Y)$ 可分解为图中所有最大团 $\textsf{C}$ 上的函数 $\Psi_{\textsf{C}}(Y_{\textsf{C}})$ 的乘积形式

$$P(Y)=\frac{1}{Z}\prod_\textsf{C}\Psi_{\textsf{C}}(Y_{\textsf{C}})$$

其中，$Z$ 是规范化因子（normalization factor)，形式如下：

$$Z=\sum_{\textsf{Y}}\prod_\textsf{C}\Psi_{\textsf{C}}(Y_{\textsf{C}})$$

规范化因子保证 $P(Y)$ 构成一个概率分布。函数 $\Psi_{\textsf{C}}(Y_{\textsf{C}})$ 称为势函数（potential function)。这里要求势函数 ΨC(YC) 是严格正的，通常定义为指数函数：

$$\Psi_{\textsf{C}}(Y_{\textsf{C}})=\exp\{-E(Y_\textsf{C})\}$$

其中 $E(Y_\textsf{C})$ 是能量函数。

定理 11.1（Hammersley-Clifford 定理）概率无向图模型的联合概率分布 $P(Y)$ 可以表示为如下形式：

$$P(Y)=\frac{1}{Z}\prod_\textsf{C}\Psi_{\textsf{C}}(Y_{\textsf{C}}) \\ Z=\sum_{\textsf{Y}}\prod_\textsf{C}\Psi_{\textsf{C}}(Y_{\textsf{C}})$$

其中，$\textsf{C}$ 是无向图的最大团，$Y_\textsf{C}$ 是 $\textsf{C}$ 的结点对应的随机变量，$\Psi_{\textsf{C}}(Y_{\textsf{C}})$ 是 $\textsf{C}$ 上定义的严格正函数，乘积是在无向图所有的最大团上进行的。

11.2 条件随机场的定义与形式

11.2.1 条件随机场的定义

条件随机场（conditional random field）是给定随机变量 $X$ 条件下，随机变量 $Y$ 的马尔可夫随机场。这里主要介绍定义在线性链上的特殊的条件随机场，称为线性链条件随机场（linear chain conditional random field)。

线性链条件随机场可以用于标注问题。这时，在条件概率模型 $P(Y|X)$ 中，$Y$ 是输出变量，表示标记序列，也把标记序列称为状态序列；$X$ 是输入变量，表示观测序列。

学习时，利用训练数据集通过极大似然估计或正则化的极大似然估计得到条件概率模型 $\hat{P}(Y|X)$；预测时，对于给定的输入序列 $x$，求出条件概率 $\hat{P}(y|x)$ 最大的输出序列 $y$。

定义 11.3（条件随机场）设 $X$ 与 $Y$ 是随机变量，$P(Y|X)$ 是在给定 $X$ 的条件下 $Y$ 的条件概率分布。若随机变量 $Y$ 构成一个由无向图 $\textsf{G}=(\textsf{V},\textsf{E})$ 表示的马尔可夫随机场，即：

$$P(Y_\textsf{v}|X,Y_\textsf{w},\textsf{w}\neq\textsf{v})=P(Y_\textsf{v}|X,Y_\textsf{w},\textsf{w}\sim\textsf{v})$$

对任意结点 $\textsf{v}$ 成立，则称条件概率分布 $P(Y|X)$ 为条件随机场。式中 $\textsf{w}\sim\textsf{v}$ 表示在图 $\textsf{G}=(\textsf{V},\textsf{E})$ 中与结点 $\textsf{v}$ 有边连接的所有结点 $\textsf{w}$，$\textsf{w}\neq\textsf{v}$ 表示结点 $\textsf{v}$ 以外的所有结点。其实就是说当前变量只跟与之相邻的变量有关系，而独立于没有直接连接的变量。

在定义中并没有要求 $X$ 和 $Y$ 具有相同的结构。现实中，一般假设 $X$ 和 $Y$ 有相同的图结构。这里主要考虑无向图如下图所示为线性链的情况，即

$$\textsf{G}=(\textsf{V}=\{1,2,\cdots,n\},\textsf{E}=\{(i,i+1)\}),\ i=1,2,\cdots,i-1$$

在此情况下，$X=(X_1,X_2,\cdots,X_n)$，$Y=(Y_1,Y_2,\cdots,Y_n)$，最大团是相邻两个节点的集合。线性链条件随机场有下面的定义

线性链条件随机场

定义 11.4（线性链条件随机场）设 $X=(X_1,X_2,\cdots,X_n)$，$Y=(Y_1,Y_2,\cdots,Y_n)$ 均为线性链表示的随机变量序列，若在给定随机变量序列 $X$ 的条件下，随机变量序列 $Y$ 的条件概率分布 $P(Y|X)$ 构成条件随机场，即满足马尔可夫性

$$P(Y_i|X,Y_1,\cdots,Y_{i−1},Y_{i+1},\cdots,Y_n)=P(Y_i|X,Y_{i−1},Y_{i+1})$$

则称 $P(Y|X)$ 为线性链条件随机场。注意当 $i=1$ 或 $i=n$ 时只考虑一侧，在标注问题中，$X$ 表示输入观测序列，$Y$ 表示对应的输出标记序列或状态序列。

11.2.2 条件随机场的参数化形式

根据 Hammersley-Clifford 定理,可以给出线性链条件随机场 $P(Y|X)$ 的因子分解式，各因子是定义在相邻两个结点上的函数。

定理 11.2（线性链条件随机场的参数化形式）设 $P(Y|X)$ 为线性链条件随机场，则在随机变量 $X$ 取值为 $x$ 的条件下，随机变量 $Y$ 取值为 $y$ 的条件概率具有如下形式

$$P(y|x)=\frac{1}{Z(x)}\exp\left(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i)\right)$$

其中
$$Z(x) = \sum_y \exp\left( \sum_{i,k}\lambda_k t_k (y_{i-1},y_i,x,i)+ \sum_{i,l}\mu_l s_l(y_i,x,i) \right)$$
式中，$t_k$ 和 $s_l$ 是特征函数，$\lambda_k$ 和 $\mu_l$ 是对应的权值。$Z(x)$ 是规范化因子，求和是在所有可能的输出序列上进行的。

以上两个式子是线性链条件随机场模型的基本形式，表示给定输入序列 $x$ ,对输出序列 $y$ 预测的条件概率。其中 $t_k$ 是定义在边上的特征函数，称为转移特征（ transition），依赖于当前和前一个位置，$s_l$ 是定义在结点上的特征函数，称为状态特征（status），依赖于当前位置。$t_k$ 和 $s_l$ 都依赖于位置，是局部特征函数。

通常，特征函数 $t_k$ 和 $s_l$ 取值为 1 或 0；当满足特征条件时取值为 1，否则为 0。条件随机场完全由特征函数和对应的权值 $\lambda_k$，$\mu_l$ 确定,线性链条件随机场也是对数线性模型（log linear model)。

11.2.3 条件随机场的简化形式

条件随机场还可以由简化形式表示。注意到条件随机场式中同一特征在各个位置都有定义，可以对同一个特征在各个位置求和，将局部特征函数转化为一个全局特征函数，这样就可以将条件随机场写成权值向量和特征向量的内积形式，即条件随机场的简化形式，为简便起见，首先将转移特征和状态特征及其权值用统一的符号表示。设有 $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,\cdots,K_1 \\ s_t(y_i,x,i),\ k = K_1 + l;\ l=1,2,\cdots,K_2 \end{cases}$$

然后，对转移与状态特征在各个位置 $i$ 求和，记作

$$f_k(y,x) = \sum_{i=1}^nf_k(y_{i-1},y_i,x,i),\ k = 1,2,\cdots,K$$

用 $w_k$ 表示特征 $f_k(y,x)$ 的权值，即

$$w_k = \begin{cases} \lambda_k, \ k=1,2,\cdots,K_1 \\ \mu_l,\ k=K_1+l;\ l=1,2,\cdots,K_2 \end{cases}$$

于是，条件随机场可表示为

$$\begin{aligned} 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}^Kw_kf_k(y,x) \end{aligned}$$

若 $w$ 表示权值向量，即

$$w= (w_1,w_2,…,w_K)^\text{T}$$

以 $F(y,x)$ 表示全局特征向量，即

$$F(y,x)=(f_1(y,x), f_2(y,x),\cdots,f_K(y,x))^\text{T}$$

则条件随机场可以写成向量 $w$ 与 $F(y,x)$ 的内积的形式

$$P_w(y|x) = \frac{\exp\left(w \cdot F(y,x)\right ) }{Z_w(x)}$$

其中

$$Z_w(x) = \sum_y \exp \left ( w \cdot F(y,x) \right )$$

11.2.4 条件随机场的矩阵形式

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

对观测序列 $x$ 的每一个位置 $i=1,2,\cdots,n+1$，定义一个 $m$ 阶矩阵（$m$ 是标记 $y_i$ 取值的个数，因为 $x$ 是给定的，位置$i-1$ 和位置 $i$ 各有 $m$ 种可能，所以是 $m$ 阶矩阵，对于 $i=1$ 是 $1\times m$ 的矩阵，对于 $i=n+1$ 是 $m\times 1$ 的矩阵）

$$\begin{aligned} M_i(x) &= \left [ M_i(y_{i-1},y_i|x)\right ] \\ M_i(y_{i-1},y_i|x)&= \exp \left [ W_i(y_{i-1} ,y_i|x)\right ] \\ W_i(y_{i-1},y_i|x)&= \sum_{k=1}^Kw_kf_k(y_{i-1},y_i,x,i) \end{aligned}$$

其实矩阵定义了一个状态 $y_{i−1}$ 的 $m$ 种状态到 $y_i$ 的 $m$ 种状态的转移的概率

$$\begin{aligned} M_i(y_{i-1} ,y_i|x) &= \exp\left(\sum_k\lambda_kf_k(y_{i-1},y_i,x,i)\right) \\ &=\exp\left( \sum_k\lambda_kt_k(y_{i-1},y_i,x,i) + \sum_l\mu_l s_l(y_i,x,i) \right) \end{aligned}$$

举例来说，当 $m=3$ 时，除了 $i=1$ 或者 $i=n-1$，每个矩阵 $M_i(x)\in\mathbb{R}^{3\times 3}$，如下图所示

条件随机场的矩阵形式

矩阵的形式类似于隐马尔科夫中的转移矩阵，代表了状态之间转移的概率，其形式是这样的

$$M_1(x)=\begin{bmatrix} M_1(y_0,y_1|x) & M_1(y_0,y_3|x) & M_1(y_0,y_3|x) \end{bmatrix} \\ M_2(x)=\begin{bmatrix} M_2(y_1,y_1|x) & M_2(y_1,y_2|x) & M_2(y_1,y_3|x)\\ M_2(y_2,y_1|x) & M_2(y_2,y_2|x) & M_2(y_2,y_3|x)\\ M_2(y_3,y_1|x) & M_2(y_3,y_2|x) & M_2(y_3,y_3|x) \end{bmatrix} \\ M_i(x)\ \ \text{具有和}\ M_2(x)\ \text{同样的形式}, \ i = 3,\cdots,n \\ M_{n+1}(x)=\begin{bmatrix} M_{n+1}(y_1,y_n|x)\\ M_{n+1}(y_2,y_n|x)\\ M_{n+1}(y_3,y_n|x) \end{bmatrix} \\$$

这样，给定观测序列 $x$，标记序列 $y$ 的非规范化概率可以通过 $n+1$ 个矩阵的乘积 $\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$ 表示，于是，条件概率是

$$P_w(y|x) = \frac{1}{Z_w(x)} \prod_{i=1}^{n+1} M_i(y_{i-1},y_i|x)$$

其中，$Z_w(x)$ 为规范化因子，是 $n+1$ 个矩阵的乘积

$$Z_w(x) =M_1(x)M_2(x)\cdots M_{n+1}(x)$$

11.3 条件随机场的概率计算问题

条件随机场的概率计算问题是给定条件随机场 $P(Y|X)$，输入序列 $x$ 和输出序列 $y$，计算条件概率 $P(Y_i=y_i|x)$，$P(Y_{i-1}=y_{i-1},Y_i=y_i|x)$ 以及相应的数学期望的问题。

11.3.1 前向-后向算法

对每个指标 $i=0,1,\cdots,n+1$，定义前向向量 $\alpha_i(x)$

$$\alpha_0(y|x)=\begin{cases}1,& y=\text{start} \\ 0,& \text{否则}\end{cases}$$

递推公式为

$$\alpha_i^\text{T}(y_i|x)=\alpha_{i-1}^\text{T}(y_{i-1}|x)[M_i(y_{i-1},y_i|x)],\ i=1,2,\cdots,n+1$$

又可表示为

$$\alpha_i^\text{T}(x)=\alpha_{i-1}^\text{T}(x)M_i(x)$$

$\alpha_i(y_i|x)$ 表示在位置 $i$ 的标记是 $y_i$ 并且到位置 $i$ 的前部分标记序列的非规范化概率，$y_i$ 可取的值有 $m$ 个，所以 $\alpha_i(x)$ 是 $m$ 维列向量。

同样，对给个指标 $i=0,1,\cdots,n+1$，定义后向向量 $\beta_i(x)$

$$\beta_{n+1}(y_{n+1}|x)=\begin{cases}1,& y_{n+1}=\text{stop} \\ 0,& \text{否则}\end{cases} \\ \beta_i(y_i|x)=[M_i(y_i,y_{i+1}|x)]\beta_{i+1}(y_{i+1}|x)$$

又可表示为

$$\beta_i(x)=M_{i+1}(x)\beta_{i+1}(x)$$

$\beta_i(y_i|x)$ 表示在位置 $i$ 的标记为 $y_i$ 并且从 $i+1$ 到 $n$ 的后部分标记序列的非规范化概率。

由定义不难得到

$$Z(x)=\alpha_n^\text{T}(x)\cdot\mathbf{1}=\mathbf{1}^\text{T}\cdot\beta_1(x)$$

这里，$\mathbf{1}$ 是元素均为 1 的 $m$ 维列向量。

11.3.2 概率计算

$$P(Y_i=y_i|x)=\frac{\alpha_i^\text{T}(y_i|x)\beta_i(y_i|x)}{Z(x)} \\ P(Y_{i-1}=y_{i-1},Y_i=y_i|x)=\frac{\alpha_{i-1}^\text{T}(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}$$

其中

$$Z(x)=\alpha_n^\text{T}(x)\cdot\mathbf{1}$$

11.3.3 期望值的计算

特征函数 $f_k$ 关于条件分布 $P(Y|X)$ 的数学期望是

$$\begin{eqnarray} \text{E}_{P(Y|X)}[f_k] &=& \sum_yP(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{\alpha_{i-1}^\text{T}(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)} \end{eqnarray} \\ k=1,2,\cdots,K$$

假设经验分布是 $\tilde{P}(X)$，特征函数 $f_k$ 关于联合分布 $P(X,Y)$ 的数学期望是

$$\begin{eqnarray} \text{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_yP(y|x)\sum_{i=1}^{n+1}f_k(y_{i-1},y_i,x,i) \\ &=& \sum_x\tilde{P}(x)\text{E}_{P(Y|X)}[f_k] \end{eqnarray} \\ k=1,2,\cdots,K$$

这些是特征函数数学期望的一般计算公式。

对于转移特征，可以将式中的 $f_k$ 换成 $t_k$，表示为

$$t_k(y_{i-1},y_i,x,i),\ k=1,2,\cdots,K_1$$

对于状态特征，可以将式中的 $f_k$ 换成 $s_i$，表示为

$$s_l(y_i,x,i),\ k=K_1+1,\ l=1,2,\cdots,K_2$$

有了本节的公式，对于给定的观测序列 $x$ 和标记序列 $y$，可以通过一次前向扫描计算 $\alpha_i$ 及 $Z(x)$，通过一次后向扫描计算 $\beta_i$，从而计算所有的概率和特征的期望。

11.4 条件随机场的学习算法

本节讨论给定训练数据集估计条件随机场模型参数的问题。条件随机场模型实际上是定义在时序数据上的对数线性模型，其学习方法包括极大似然估计和正则化的极大似然估计。具体的优化实现算法有改进的迭代尺度法 IIS、梯度下降法和拟牛顿法。

11.4.1 改进的迭代尺度法

已知训练数据集，由此可知经验概率分布 $\tilde{P}(X,Y)$，训练数据的对数似然函数为

$$L(w)=L_{\tilde{P}}(P_w)=\log\prod_{x,y}P_w(y|x)^{\tilde{P}(x,y)}=\sum_{x,y}\tilde{P}(x,y)\log P_w(y|x)$$

其中

$$\begin{aligned} P_w(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}^Kw_kf_k(y,x) \end{aligned}$$

则

$$\begin{eqnarray} L(w) &=& \sum_{x,y}\tilde{P}(x,y)\log P_w(y|x) \\ &=& \sum_{x,y}\left[\tilde{P}(x,y)\sum_{k=1}^Kw_kf_k(y,x)-\tilde{P}(x,y)\log Z_w(x)\right] \\ &=& \sum_{j=1}^N\sum_{k=1}^Kw_kf_k(y_j,x_j)-\sum_{j=1}^N\log Z_w(x_j) \end{eqnarray}$$

改进的迭代尺度法通过迭代的方法不断优化对数似然函数改变量的下界，达到极大化对数似然函数的目的。

设参数向量 $w$ 的增量是

$$\delta=(\delta_1,\delta_2,\cdots,\delta_K)^\text{T}$$

根据第六章的方法，得到关于转移特征 $t_k$ 的更新方程是

$$\begin{eqnarray} \text{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(\delta_kT(x,y)) \end{eqnarray} \\ k=1,2,\cdots,K_1$$

关于状态特征 $s_l$ 的更新方程是

$$\begin{eqnarray} \text{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}s_l(y_i,x,i)\exp(\delta_{K_1+l}T(x,y)) \end{eqnarray} \\ l=1,2,\cdots,K_2$$

这里，$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)$$

算法 11.1（条件随机场模型学习的改进的迭代尺度法）
输入：特征函数 $t_1,t_2,\cdots,t_{K_1}$，$s_1,s_2,\cdots,s_{K_2}$；经验分布 $\tilde{P}(x,y)$
输出：参数估计值 $\hat{w}$；模型 $P_{\hat{w}}$
(1) 对所有 $k\in\{1,2,\cdots,K\}$，取初值 $w_k=0$
(2) 对每一 $k\in\{1,2,\cdots,K\}$
(2.a) 当 $k=1,2,\cdots,K_1$ 时，令 $\delta_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(\delta_kT(x,y))=\text{E}_{\tilde{P}}[t_k]$$

当 $k=K_1+l$，$l=1,2,\cdots,K_2$ 时，令 $\delta_{K_1+l}$ 是下面方程的解
$$\sum_{x,y}\tilde{P}(x)P(y|x)\sum_{i=1}^{n}s_l(y_i,x,i)\exp(\delta_{K_1+l}T(x,y))=\text{E}_{\tilde{P}}[s_l]$$
其中
$$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)$$
(2.b) 更新 $w_k$：$w_k\gets w_k+\delta_k$
(3) 如果不是所有的 $w_k$ 都收敛，重复步骤 (2)

上面算法中 $T(x,y)$ 对不同的数据 $(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)\geq0$ 成立。这时特征总可取 $S$。

对于转移特征 $t_k$，$\delta_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(\delta_kS)=\text{E}_{\tilde{P}}[t_k] \\ \delta_k=\frac{1}{S}\log\frac{\text{E}_{\tilde{P}}[t_k]}{\text{E}_P[t_k]}$$

其中

$$\text{E}_P[t_k]=\sum_x\tilde{P}(x)\sum_{i=1}^{n+1}\sum_{y_{i-1}y_i}t_k(y_{i-1},y_i,x,i)\frac{\alpha_{i-1}^\text{T}(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}$$

对于状态特征 $s_l$，$\delta_k$ 的更新方程是

$$\sum_{x,y}\tilde{P}(x)P(y|x)\sum_{i=1}^{n}s_l(y_i,x,i)\exp(\delta_{K_1+l}S)=\text{E}_{\tilde{P}}[s_l] \\ \delta_{K_1+l}=\frac{1}{S}\log\frac{\text{E}_{\tilde{P}}[s_l]}{\text{E}_P[s_l]}$$

其中

$$\text{E}_P[s_l]=\sum_x\tilde{P}(x)\sum_{i=1}^{n}\sum_{y_i}s_l(y_i,x,i)\frac{\alpha_{i}^\text{T}(y_{i}|x)\beta_i(y_i|x)}{Z(x)}$$

以上算法称为算法 S，在算法 S 中需要使常数 $S$ 取足够大，这样一来，每步迭代的增量会变大，算法收敛会变慢。算法 T 试图解决这个问题。算法 T 对每个观测序列 $x$ 计算其特征总数最大值 $T(x)$

$$T(x)=\max_yT(x,y)$$

利用前向-后向递推公式，可以很容易计算 $T(x)=t$

这时，关于转移特征参数的更新方程是

$$\begin{eqnarray} \text{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(\delta_kT(x)) \\ &=& \sum_x\tilde{P}(x)\sum_yP(y|x)\sum_{i=1}^{n+1}t_k(y_{i-1},y_i,x,i)\exp(\delta_kT(x)) \\ &=& \sum_x\tilde{P}(x)a_{k,t}\exp(\delta_k\cdot t) \\ &=& \sum_{t=1}^{T_\text{max}}a_{k,t}\beta_k^t \end{eqnarray}$$

这里，$a_{k,t}$ 是特征 $t_k$ 的期望值，$\delta_k=\log\beta_k$。$\beta_k$ 是上面方程唯一的实根，可以用牛顿法求解，从而得到相关的 $\delta_k$。

同理，关于状态特征的更新方程是

$$\begin{eqnarray} \text{E}_{\tilde{P}}[s_l] &=& \sum_{x,y}\tilde{P}(x)P(y|x)\sum_{i=1}^{n}s_l(y_i,x,i)\exp(\delta_{K_1+l}T(x)) \\ &=& \sum_x\tilde{P}(x)\sum_yP(y|x)\sum_{i=1}^{n}s_l(y_i,x,i)\exp(\delta_{K_1+l}T(x)) \\ &=& \sum_x\tilde{P}(x)b_{l,t}\exp(\delta_k\cdot t) \\ &=& \sum_{t=1}^{T_\text{max}}b_{l,t}\gamma_l^t \end{eqnarray}$$

这里，$b_{l,t}$ 是特征 $s_l$ 的期望值，$\delta_l=\log\gamma_l$。$\gamma_l$ 是上面方程唯一的实根，可以用牛顿法求解，从而得到相关的 $\delta_{K_1+l}$。

11.4.2 拟牛顿法

对于条件随机场模型

$$P_w(y|x)=\frac{\exp\left(\sum_{i=1}^nw_if_i(x,y)\right)}{\sum_y\exp\left(\sum_{i=1}^nw_if_i(x,y)\right)}$$

学习的优化目标函数是

$$\min_{w\in\mathbb{R}^n}f(w)=\sum_x\tilde{P}(x)\log\sum_y\exp\left(\sum_{i=1}^nw_if_i(x,y)\right)-\sum_{x,y}\tilde{P}(x,y)\sum_{i=1}^nw_if_i(x,y)$$

其梯度函数是

$$g(w)=\sum_{x,y}\tilde{P}(x)P_w(y|x)f(x,y)-\text{E}_\tilde{P}[f]$$

算法 11.2（条件随机场模型学习的 BFGS 算法）
输入：特征函数 $f_1,f_2,\cdots,f_n$；经验分布 $\tilde{P}(X,Y)$
输出：最优参数值 $\hat{w}$；最优模型 $P_{\hat{w}}(y|x)$
(1) 选定初始点 $w^{(0)}$，取 $\mathbf{B}_0$ 为正定对称矩阵，置 $k=0$
(2) 计算 $g_k=g\left(w^{(k)}\right)$，若 $g_k=0$，则停止计算，否则转 (3)
(3) 由 $\mathbf{B}_kp_k=-g_k$ 求出 $p_k$
(4) 一维搜索：求 $\lambda_k$ 使得

$$f\left(w^{(k)}+\lambda_kp_k\right)=\min_{\lambda\geq0}f\left(w^{(k)}+\lambda p_k\right)$$

(5) 置 $w^{(k+1)}=w^{(k)}+\lambda_k p_K$
(6) 计算 $g_{k+1}=g\left(w^{(k+1)}\right)$，若 $g_{k+1}=0$，则停止计算；，否则按下式计算 $\mathbf{B}_{k+1}$
$$\mathbf{B}_{k+1}=\mathbf{B}_k+\frac{y_ky_K^\text{T}}{y_k^\text{T}\delta_k}-\frac{\mathbf{B}_k\delta_k\delta_k^\text{T}\mathbf{B}_k}{\delta_k^\text{T}\mathbf{B}_k\delta_k}$$
其中
$$y_k=g_{k+1}-g_k,\ \delta_k=w^{(k+1)}-w^{(k)}$$
(7) 置 $k=k+1$，转 (3)

11.5 条件随机场的预测算法

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

由条件随机场的简化形式，得

$$\begin{eqnarray} y^\star &=& \arg\max_yP_w(y|x) \\ &=& \arg\max_y\frac{\exp\left(w\cdot F(y,x)\right)}{Z_w(x)} \\ &=& \arg\max_y\exp(w\cdot F(y,x)) \\ &=& \arg\max_y(w\cdot F(y,x)) \end{eqnarray}$$

于是，条件随机场的预测问题成为求非规范化概率最大的最优路径问题

$$\max_y(w\cdot F(y,x))$$

这里，路径表示标记序列，其中

$$w=(w_1,w_2,\cdots,w_K)^\text{T} \\ F(y,x)=(f_1(y,x),f_2(y,x),\cdots,f_K(y,x))^\text{T} \\ f_k(y,x)=\sum_{i=1}^nf_k(y_{i-1},y_i,x,i),\ k=1,2,\cdots,K$$

这里只需要计算非规范化概率，可以大大提高效率。将优化问题改写为

$$\max_y\sum_{i=1}^nw\cdot F_i(y_{i-1},y_i,x)$$

其中

$$F_i(y_{i-1},y_i,x)=(f_1(y_{i-1},y_i,x,i),f_2(y_{i-1},y_i,x,i),\cdots,f_K(y_{i-1},y_i,x,i))^\text{T}$$

是局部特征向量。

下面叙述维特比算法。首先求出位置 1 的各个标记 $j=1,2,\cdots,m$ 的非规范化概率

$$\delta_1(j)=w\cdot F_1(y_0=\text{start},y_1=j,x),\ j=1,2,\cdots,m$$

一般的，由递推公式，求出到位置 $i$ 的各个标记 $l=1,2,\cdots,m$ 的非规范化概率的最大值，同时记录非规范化概率最大值的路径

$$\delta_i(l)=\max_{1\leq j\leq m}\left\{\delta_{i-1}(j)+w\cdot F_i(y_{i-1}=j,y_i=l,x)\right\},\ l=1,2,\cdots,m \\ \Psi_i(l)=\arg\max_{1\leq j\leq m}\left\{\delta_{i-1}(j)+w\cdot F_i(y_{i-1}=j,y_i=l,x)\right\},\ l=1,2,\cdots,m$$

直到 $i=n$ 时终止。这时求得非规范化概率最大值是

$$\max_y(w\cdot F(y,x))=\max_{1\leq j\leq m}\delta_n(j)$$

以及最优路径的终点

$$y_n^\star=\arg\max_{1\leq j\leq m}\delta_n(j)$$

由此最优路径终点返回

$$y_i^\star=\Psi_{i+1}(y_{i+1}^\star),\ i=n-1,n-2,\cdots,1$$

求得最优路径 $y^\star=(y_1^\star,y_2^\star,\cdots,y_n^\star)^\text{T}$

算法 11.3（条件随机场预测的维特比算法）
输入：模型特征向量 $F(y,x)$ 和权值向量 $w$，观测序列 $x=(x_1,x_2,\cdots,x_n)$
输出：最优路径 $y^\star=(y_1^\star,y_2^\star,\cdots,y_n^\star)^\text{T}$
(1) 初始化

$$\delta_1(j)=w\cdot F_1(y_0=\text{start},y_1=j,x),\ j=1,2,\cdots,m$$

(2) 递推，对 $i=2,3,\cdots,n$

$$\delta_i(l)=\max_{1\leq j\leq m}\left\{\delta_{i-1}(j)+w\cdot F_i(y_{i-1}=j,y_i=l,x)\right\},\ l=1,2,\cdots,m \\ \Psi_i(l)=\arg\max_{1\leq j\leq m}\left\{\delta_{i-1}(j)+w\cdot F_i(y_{i-1}=j,y_i=l,x)\right\},\ l=1,2,\cdots,m$$
(3) 终止
$$\max_y(w\cdot F(y,x))=\max_{1\leq j\leq m}\delta_n(j) \\ y_n^\star=\arg\max_{1\leq j\leq m}\delta_n(j)$$
(4) 返回路径
$$y_i^\star=\Psi_{i+1}(y_{i+1}^\star),\ i=n-1,n-2,\cdots,1$$
求得最优路径 $y^\star=(y_1^\star,y_2^\star,\cdots,y_n^\star)^\text{T}$