条件随机场

条件随机场(Conditional Random Field,CRF)是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型，其特点是假设输出随机变量构成马尔科夫随机场。

1. 概率无向图模型

概率无向图模型(Prodbabilistic Undirected Graphical Model),又称为马尔科夫随机场(Markov Random Field)，是一个可以由无向图模型表示的联合概率分布。

1.1 模型定义

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

概率图模型(Prodbabilistic Graphical Model)是由图表示的概率分布。设有联合概率分布 P(Y) , Y ∈ 𝒴 是一组随机变量。由无向图 G = (V, E) 表示概率分布 P(Y) ，即在图 G 中，结点 v ∈ V 表示一个随机变量 Y_v, Y = (Y_v)_v ∈ V ；边 e ∈ E 表示随机变量之间的概率依赖关系。

给定一个联合概率分布 P(Y) 和表示它的无向图 G 。首先定义无向图表示的随机变量之间存在的成对马尔科夫性(Pairwise Markov Property)、局部马尔科夫性(Local Markov Property)和全局马尔科夫性(Global Markov Property).

成对马尔科夫性：设 u 和 v 是无向图 G 中任意两个没有边连接的结点，结点 u 和 v 分别对应随机变量 Y_u 和 Y_v 。其他所有结点为 O ,对应的随机变量组是 Y_O .成对马尔科夫性是指给定随机变量组 Y_O 的条件下随机变量 Y_u 和 Y_v 是条件独立的，即

P(Y_u, Y_v|Y_O) = P(Y_u|Y_O)P(Y_v|P_O)

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

P(Y_v, Y_O|Y_W) = P(Y_v|Y_W)P(Y_O|Y_W)

有

P(Y_O|Y_W) > 0 ⇒ P(Y_v|Y_W) = P(Y_v|Y_O, Y_W)

局部马尔科夫性如下图所示：

全局马尔科夫性:设结点集合 A, B 是在无向图 G 中被结点集合 C 分开的任意结点集合，如下图：

结点集合 A, B 和 C 对应的随机变量组分别是 Y_A, Y_B, Y_C ，全局马尔科夫性是指给定随机变量组 Y_C 条件下随机变量组 Y_A 和 Y_B 是条件独立的，即

P(Y_A, Y_B|Y_C) = P(Y_A|Y_C)P(Y_B|P_C)

概率无向图模型： 设有联合概率分布 P(Y) ，由无向图 G = (V, E) 表示，在图 G 中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布 P(Y) 满足成对、局部或全局马尔科夫性，就称此联合概率分布为概率无向图模型(Prodbabilistic Undirected Graphical Model),又称为马尔科夫随机场(Markov Random Field)。

概率无向图模型的最大特点就是易于因子分解，这样便于模型的学习与计算。

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

团与最大团： 无向图 G 中任何两个结点均有边连接的结点子集称为团(Clique).若 C 是无向图 G 的一个团，并且不能再加进任何一个 G 的结点使其成为一个更大的团，则称此 C 为最大团(Maximal Clique).

如上图表示由4个点组成的无向图。图中由2个结点组成的团由5个：

{Y₁, Y₂}, {Y₂, Y₃}, {Y₃, Y₄}, {Y₂, Y₄}, {Y₁, Y₃},

有两个最大团：

{Y₁, Y₂, Y₃}, {Y₂, Y₃, Y₄}

而

{Y₁, Y₂, Y₃, Y₄}

不是一个团。因为 Y₁ 和 Y₄ 没有边连接。

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

给定概率无向图模型，设其无向图为 G ， C 为 G 上的最大团， Y_C 表示 C 对应的随机变量。那么概率无向图模型的联合概率分布 P(Y) 可写作图中所有最大团 C 上的函数 Ψ_C(Y_C) 的乘积形式，即

其中， Z 是规范化因子(Normalization Factor)：

Z = ∑_Y∏_CΨ_C(Y_C)

规范化因子保证 P(Y) 构成一个概率分布，函数 Ψ_C(Y_C) 称为势函数(Potential Function). 这里要求势函数 Ψ_C(Y_C) 是严格正的，通常定义为指数函数：

Ψ_C(Y_C) = −exp {−E(Y_C)}

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

Z = ∑_Y∏_CΨ_C(Y_C)

其中， C 是无向图的最大团， Y_C 是 C 的结点对应的随机变量， Ψ_C(Y_C) 是 C 上定义的严格正函数，乘积是在无向图所有的最大团上进行的。

2. 条件随机场的定义与形式

2.1 条件随机场的定义

条件随机场(CRF)是给定随机变量 X 条件下，随机变量 Y 的马尔科夫随机场，本文主要介绍定义在线性链上的特殊的条件随机场，称为线性链条件随机场(Linear Chain Conditional Random Field).线性链条件随机场可以用于标注等问题。这时，在条件概率模型 P(Y|X) 中， Y 是输出量，表示标记序列， X 是输入变量，表示需要标注的观测序列。也把标记序列称为状态序列(参见 HMM ).学习时，利用训练数据集通过极大似然估计或正则化的极大似然估计得到条件概率模型 P̂(Y|X) ;预测是，对于给定的输入序列 x ，求出条件概率 P̂(y|x) 最大的输出序列 ŷ .

条件随机场： 设 X 与 Y 是随机变量， P(Y|X) 是在给定 X 的条件下 Y 的条件概率分布，若随机变量 Y 构成一个由无向图 G = (V, E) 表示的马尔科夫随机场，即

P(Y_v|X, Y_w, w ≠ v) = P(Y_v|X, Y_w, w ∼ v)

对任意结点 v 成立，则称条件概率分布 P(Y|X) 为条件随机场。式中 w ∼ v 表示在无向图 G = (V, E) 中与结点 v 有边连接的所有结点 w, w ≠ v 表示结点 v 以外的所有结点， Y_v, Y_w 为结点 u, w 对应的随机变量。

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

即

G = (V = {1, 2, ⋯, n},    E = {(i, i + 1)})

在此情况下， X = (X₁, X₂, ⋯, X_n),   Y = (Y₁, Y₂, ⋯, Y_n) ，最大团是相邻两个结点的集合。

线性链条件随机场： 设 X = (X₁, X₂, ⋯, X_n),   Y = (Y₁, Y₂, ⋯, Y_n) 均为线性链表示的随机变量序列，若在给定随机变量序列 X 的条件下，随机变量序列 Y 的条件概率分布 P(Y|X) 构成条件随机场，即满足马尔科夫性

P(Y_i|X, Y₁, ⋯, Y_i − 1, Y_i + 1, ⋯, Y_n) = P(Y_i|X, Y_i − 1, Y_i + 1),   i = 1, 2, ⋯, n

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

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

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

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

其中，

Z(x) = ∑_yexp (∑_i, kλ_kt_k(y_i − 1, y_i, x, i) + ∑_i, lμ_ls_l(y_i, x, i))

式中， t_k 和 s_l 是特征函数， λ_k 和 μ_l 是对应的权值， Z(x) 是规范化因子，求和是在所有可能的输出序列上进行的，

上述两个公式是线性链条件随机场模型的基本形式，表示给定输入序列 x ，对输出序列 y 预测的条件概率。式中 t_k 是定义在边上的特征函数，称为转移特征，依赖于当前和前一个位置， s_l 是定义在结点上的特征函数，称为状态特征，依赖于当前位置. t_k 和 s_l 都依赖于位置，是局部特征函数。通常，特征函数 t_k 和 s_l 取值为1或0；当满足特征条件时取值为 1，否则为0.条件随机场完全由特征函数 t_k, s_l 和对应的权值 λ_k, μ_l 确定。

线性链条件随机场也是对数线性模型(Log Linear Model).

例

设有一个标注问题：输入观测序列为 X = (X₁, X₂, X₃) ，输出标记序列为 Y = (Y₁, Y₂, Y₃), Y₁, Y₂, Y₃ 取值于

𝒴 = {1, 2}

假设特征 t_k, s_l 和对应的权值 λ_k, μ_l 如下:

t₁ = t₁(y_i − 1 = 1, y_i = 2, x, i),    i = 2, 3,    λ₁ = 1

这里只注明特征取值为 1 的条件，取值为 0 的条件省略，即

下同。

对给定的观测序列 x ，求标记序列为 y = (y₁, y₂, y₃) = (1, 2, 2) 的非规范化条件概率(即没有除以规范化因子的条件概率)。

解 线性链条随机场模型为

对给定的观测序列 x ，标记序列 y = (1, 2, 2) 的非规范化条件概率为

P(y₁ = 1, y₂ = 2, y₃ = 2|x) ∝ exp (3.2)

2.3条件随机场的简化形式

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

为简便起见，首先将转移特征和状态特征及其权值用统一的符号表示。设有 K₁ 个转移特征， K₂ 个状态特征， K = K₁ + K₂ ,记

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

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

于是有

若以 w 表示权值向量，即

w = (w₁, w₂, ⋯, W_K)^T

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

F(y, x) = (f₁(y, x), f₂(y, x), ⋯, f_K(y, x))^T

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

其中，

Z_w(x) = ∑_yexp (w ⋅ F(y, x))

2.4 条件随机场的矩阵形式

条件随机场还可以由矩阵表示。假设

表示对给定观测序列 x ,相应的标记序列 y 的条件概率，引进特殊的起点和终点状态标记 y₀ = start,,y_n − 1 = stop ,这时 P_w(y|x) 可以通过矩阵形式表示。

对观测序列 x 的每一个位置 i = 1, 2, ⋯, 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))

这样，给定观测序列 x ,相应标记序列 y 的非规范化概率可以通过该序列 n + 1 个矩阵适当元素的乘积 表示，条件概率是:

其中 Z_w(x) 是规范化因子，是 n + 1 个矩阵的乘积的 (start, stop) 元素：

Z_w(x) = (M₁(x)M₂(x)⋯M_n + 1(x))_{start, stop}

注意， y₀ = start, y_n + 1 = stop 表示开始状态与终止状态，规范化因子 Z_w(x) 是以 start 为起点 stop 为终点通过状态的所有路径 y₁y₂⋯y_n 的非规范化概率 之和。

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

条件随机场的概率计算问题是给定条件随机场 P(Y|X) ，输入序列 x 和输出序列 y ,计算条件概率 P(Y_i = y_i|x), P(Y_i − 1 = y_i − 1, Y_i = y_i|x) 以及相应的数学期望的问题。为了方便，像 HMM 那样，引进前向-后向向量，递归地计算以上概率记期望。这样的算法称为前向-后向算法。

3.1 前向-后向算法

对每个指标 i = 0, 1, ⋯, n + 1 ,定义前向向量 α_i(x)

递推公式为

α_i^T(y_i|x) = α_i − 1^T(y_i − 1|x)[M_i(y_i − 1, y_i|x)],      i = 1, 2, ⋯, n + 1

又可表示为

α_i^T(x) = α_i − 1^T(x)M_i(x)

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

同样，对每个指标 i = 0, 1, ⋯, n + 1 ,定义后向向量 β_i(x) :

β_i(y_i|x) = [M_i(y_i, y_i + 1|x)]β_i + 1(y_i + 1|x)

又可表示为

β_i(x) = M_i + 1(x)β_i + 1(x)

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

由前向-后向向量定义可得:

Z(x) = α_n^T(x) ⋅ 1 = 1^T ⋅ β₁(x)

这里， 1 是元素均为 1 的 m 维列向量。

3.2 概率计算

按照前向-后向向量的定义，很容易计算标记序列在位置 i 是标记 y_i 的条件概率和在位置 i − 1 与 i 是标记 y_i − 1 和 y_i 的条件概率:

其中，

Z(x) = α_n^T(x) ⋅ 1

3.3 期望计算

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

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

其中，

Z(x) = α_n^T(x) ⋅ 1

假设经验分布为 P̃(X) ,特征函数 f_k 关于联合分布 P(X, Y) 的数学期望是

其中，

Z(x) = α_n^T(x) ⋅ 1

上述两式是特征函数数学期望的一般计算公式。对于转移特征 t_k(y_i − 1, y_i, x, i), k = 1, 2, ⋯, K₁ ，可以将式中的 f_k 换成 t_k ;对于状态特征，可以将式中的 f_k 换成 s_i ，表示为 s_l(y_i, x, i), k = K₁ + l, l = 1, 2, ⋯, K₂ .

有了概率和期望计算的公式，对给定的观测序列 x 与标记序列 y ,可以通过一次前向扫描计算 α_i 及 Z(x) ，通过一次后向扫描计算 β_i ,从而计算所有的概率和期望特征。

4. 条件随机场的学习算法

条件随机场模型实际上是定义在时序数据上的对数线形模型，其学习方法包括极大似然估计和正则化的极大似然估计。具体地算法有改进的迭代尺度法 IIS ，梯度下降法以及拟牛顿法。

4.1 改进的迭代尺度法

已知训练数据集，由此可知经验概率分布 P̃(X, Y) 可以通过极大训练数据的对数似然函数来求模型参数。

训练书的对数似然函数为:

L(w) = L_P̃(P_w) = log ∏_x, yP_w(y|x)^P̃(X, Y) = ∑_x, yP̃(X, Y)log P_w(y|x)

当 P_w 是

时，对数似然函数为

改进的迭代尺度算法通过迭代的方法不断优化对数似然函数改变量的下界，达到极大化对数似然函数的目的。假设模型的当前参数向量为 w = (w₁, w₂, ⋯, w_K)^T ，向量的增量为 δ = (δ₁, δ₂, ⋯, delta_K)^T ,更新参数向量为 w + δ = (w₁ + δ₁, w₂ + δ₂, ⋯, w_K + δ_K)^T 。在每一步迭代过程中，改进的迭代尺度法依次通过求解 E_P̃[t_k] 和 E_P̃[s_l] ，得到 δ = (δ₁, δ₂, ⋯, delta_K)^T。

关于转移特征 t_k 的更新方程为

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

这里， T(x, y) 是在数据 (x, y) 中出现所有特征数的总和:

条件随机场模型学习的改进的迭代尺度法

输入: 特征函数 t₁, t₂, ⋯, t_K1,   s₁, s₂, ⋯, s_K2 ; 经验分布 P̃(x, y) ;

输出：参数估计值 ŵ ; 模型 P_ŵ .

(1)对所有

k ∈ {1, 2, ⋯, K}

取初值 w_k = 0

(2)对每一个

k ∈ {1, 2, ⋯, K}

有：

(a)当 k = 1, 2, ⋯, K₁ 时，令 δ_k 是方程

的解；当 k = k₁ + l,  l = 1, 2, ⋯, K₂ 时，令 δ_K1 + l 是方程

的解。

(b)更新 w_k 值： w_k ← w_k + δ_k

(3)如果不是所有 w_k 都收敛，重复步骤(2).

E_P̃[t_k] 和 E_P̃[s_l] 公式中， T(x, y) 表示数据 (x, y) 中的特征总数，对不同的数据 (x, y) 取值可能不同。为了处理这个问题，定义松弛特征

式中 S 是一个常数，选择足够大的常数 S 使得对训练数据集的所有数据 (x, y), s(x, y) ≥ 0 成立。这时特征总数可取 S .

由 E_P̃[t_k] 可得，对于转移特征 t_k, δ_k 的更新方程是

其中，

同样由 E_P̃[s_l] 可得，对于状态特征 s_l, δ_k 的更新方程是

其中，

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

T(x) = max_yT(x, y)

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

这时，关于转移特征参数的更新方程可以写成:

这里， a_k, t 是特征 t_k 的期待值， δ_k = log β_k . β_k 是上式唯一的实根，可以用牛顿法求得。从而求得相关 δ_k .

同样，关于状态特征的参数更新方程可以写成：

这里， b_l, t 是特征 s_l 的期望值， δ_l = log γ_l, γ_l 是上式得唯一实根，也可以用牛顿法求得。

4.2 拟牛顿法

条件随机场模型学习还可以应用牛顿法或拟牛顿法。对于条件随机场模型

学习的优化目标函数是

其梯度函数是

g(w) = ∑_xP̃(x)P_w(y|x)f(x, y) − E_P̃(f)

条件随机场模型学习的BFGS算法

输入：特征函数 f₁, f₂, ⋯, f_n ;经验分布 P̃(X, Y) ;

输出：最优参数值 ŵ ; 最优模型 P_ŵ(y|x) .

(1)选定初始点 w⁽⁰⁾ ,取 B₀ 为正定对称矩阵，置 k = 0

(2)计算 g_k = g(w^(k)) .若 g_k = 0 ,则停止计算；否则转(3)

(3)由 B_kp_k = −g_k 求出 p_k

(4)一维搜索：求 λ_k 使得

f(w^(k) + λ_kp_k) = min_λ ≥ 0f(w^(k) + λp_k)

(5)置 w^(k + 1) = w^(k) + λ_kp_k

(6)计算 g_k + 1 = g(w^(k + 1)) ,若 g_k + 1 = 0 ，则停止计算；否则，按下士求出 B_k + 1 :

其中，

y_k = g_k + 1 − g_k,     δ_k = w^(k + 1) − w^(k)

(7)置 k = k + 1 ,转(3).

5. 条件随机场的预测算法

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

由

可得:

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

max_y(w ⋅ F(y, x))

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

w = (w₁, w₂, ⋯, w_K)^T

F(y, x) = (f₁(y, x), f₂(y, x), ⋯, f_K(y, x))^T

注意，这时只需计算非规范化概率，可以大大提高效率，为了求解最优路径，将目标函数写成:

其中，

F_i(y_i − 1, y_i, x) = (f₁(y_i − 1, y_i, x, i)f₂(y_i − 1, y_i, x, i), ⋯, f_K(y_i − 1, y_i, x, i))^T

是局部特征向量。

下面描述维特比算法，首先求出位置 1 的各个标记 j = 1, 2, ⋯, m 的非规范化概率:

δ₁(j) = w ⋅ F₁(y₀ = start, y₁ = j, x),    j = 1, 2, ⋯, m

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

δ_i(l) = max_{1 ≤ j ≤ m}{δ_i − 1(j) + w ⋅ F_i(y_i − 1 = j, y_i = l, x)}

Ψ_i(l) = arg max_{1 ≤ j ≤ m}{δ_i − 1(j) + w ⋅ F_i(y_i − 1 = j, y_i = l, x)}

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

max_y(w ⋅ F(y, x)) = max_{1 ≤ j ≤ m}δ_n(j)

及最优路径的终点

y_n^* = arg max_{1 ≤ j ≤ m}δ_n(j)

由此最优路径终点返回，

y_i^* = Ψ_i + 1(y_i + 1^*), i = n − 1, n − 2, ⋯, 1

求得最优路径y^* = (y₁^*, y₂^*, ⋯, y_n^*)^T.

条件随机场预测的维特比算法

输入：模型特征向量 F(y, x) 和权值向量 w ，观测序列 x = (x₁, x₂, ⋯, x_n) ;

输出：最优路径y^* = (y₁^*, y₂^*, ⋯, y_n^*)^T.

(1)初始化

δ₁(j) = w ⋅ F₁(y₀ = start, y₁ = j, x),    j = 1, 2, ⋯, m

(2)递推，对 i = 2, 3, ⋯, n

δ_i(l) = max_{1 ≤ j ≤ m}{δ_i − 1(j) + w ⋅ F_i(y_i − 1 = j, y_i = l, x)}

Ψ_i(l) = arg max_{1 ≤ j ≤ m}{δ_i − 1(j) + w ⋅ F_i(y_i − 1 = j, y_i = l, x)}

(3)终止

max_y(w ⋅ F(y, x)) = max_{1 ≤ j ≤ m}δ_n(j)

y_n^* = arg max_{1 ≤ j ≤ m}δ_n(j)

(4)返回路径

y_i^* = Ψ_i + 1(y_i + 1^*), i = n − 1, n − 2, ⋯, 1

求得最优路径

y^* = (y₁^*, y₂^*, ⋯, y_n^*)^T

例

在第一个例子中，用维特比算法求给定的输入序列 x 对应的最优输出序列(标记序列)y^* = (y₁^*, y₂^*, y₃^*).

解

特征函数及对应的权值均已给出，利用维特比算法求最优路径问题：

(1)初始化

δ₁(j) = w ⋅ F₁(y₀ = start, y₁ = j, x),   j = 1, 2 i = 1,   δ₁(1) = 1,    δ₁(2) = 0.5

(2)递推

(3)终止

max_y(w ⋅ F(y, x)) = max δ₃(l) = δ₃(1) = 4.3 y₃^* = arg max_lδ₃(l) = 1

(4)返回

y₂^* = Ψ₃(y₃^*) = Ψ₃(1) = 2

y₁^* = Ψ₂(y₂^*) = Ψ₂(2) = 1

最优标记序列

y^* = (y₁^*, y₂^*, y₃^*) = (1, 2, 1)

参考

1. 周志华 《机器学习》
2. 条件随机场（CRF）
3. 条件随机场