条件随机场CRF

CRF简介

条件随机场（CRF）是给定一组输入随机变量的条件下另一组输出随机变量的条件概率分布。

1.概念引入

• 概率图模型 概率图模型是由图表示的概率分布。无向图G=(V,E)表示概率分布P(Y)，节点v∈V表示一个随机变量$Y_V$；边e∈E表示随机变量之间的概率依存关系。

• 成对马尔科夫性 u和v是G中任意两个没有边连接的节点，其他所有节点为O。成对马尔科夫性是指给定随机变量组$Y_O$的条件下随机变量$Y_u$和$Y_v$是条件独立的，即

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

• 局部马尔科夫性 v是G中任意一点，W是与v有边连接的所有节点，O是v,W以外的其他所有节点。局部马尔科夫性是指给定$Y_W$的条件下$Y_v$与$Y_O$是独立的，即

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

• 全局马尔科夫性 A,B是G中被C分开的任意节点集合。全局马尔科夫性是指给定$Y_C$条件下$Y_A$和$Y_B$是条件独立的，即

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

• 概率无向图模型 如果联合概率P(Y)满足成对、局部或者全局马尔科夫性，就称该联合概率分布为无向图模型，或者马尔科夫随机场。最大特点：易于因子分解。

• 团与最大团 无向图G中任何两个节点都有边连接的节点子集称为团（clique）。若不能再加进一个节点使团更大，称该团为最大团。

• 无向图模型的因子分解（factorization） C为G上最大团，P(Y)可以写作图中所有最大团C上的函数$Ψ_C(Y_C)$的乘积形式，即

$$P(Y)=\frac{1}{Z}\prod_c{Ψ_C(Y_C)}$$

其中，Z是归一化因子，$Z=\sum_r{\prod_c{Ψ_C(Y_C)}}$。$Ψ_C(Y_C)$称为势函数，通常定义为指数函数：

$$Ψ_C(Y_C)=exp\{-E(Y_C)\}$$

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

$$P(Y)=\frac{1}{Z}\prod_c{Ψ_C(Y_C)}$$

$$Z=\sum_r{\prod_c{Ψ_C(Y_C)}}$$

1.2 定义

• 条件随机场 条件随机场是给定随机变量X的条件下，随机变量Y的马尔科夫随机场。主要介绍定义在线性链想的线性链条件随机场（用于标注等问题）

$$P(Y_v|X,Y_w,w≠v)=P(Y_v|X,Y_w,w连v)$$ 对于任何节点v都成立，成条件概率分布P(Y|X)为条件随机场。w连v表示所有与v相连的节点w，w≠v表示所有除v外的节点w。也就是说，对于点v来说，只有与它相连的点会对它产生影响。

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

$$P(Y_i|X,Y_1,...,Y_{i-1},Y_{i+1},...,Y_n)=P(Y_i|X,Y_i-1,Y_i+1)$$

相当于是说，线性的模型只考虑两边的节点对它的影响，因为只有两边的节点与它相邻。

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

• 线性链条件随机场的参数化形式 P(Y|X)为线性链条件随机场，则在X取x的条件下，Y取y的条件概率：

$$P(y|x)=\frac {1}{Z(x)} exp(\sum_{i,k}λ_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}μ_ls_l(y_i,x,i))$$

其中Z(x)是归一化因子$t_k$和$s_l$ 是特征函数 $λ_k$和$μ_l$ 是对应的权值。$t_k$ 是定义在边上的特征函数，称为转移特征，依赖于当前和前一个位置。$s_l$ 是定义在节点上的特征函数，称为状态特征。特征函数的取值当满足特征条件时取1，否则取0。

1.4 条件随机场的矩阵形式

引入特殊的起点和终点状态标记$y_0=start,y_{N+1}=stop$,这时$P_w(Y|X)$ 可以通过矩阵形式表示。对x的每一个位置i=1,2,3,...,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 _{k=1}^K w_kf_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)$$

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

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

2.1 前向-后向算法

• 前向向量$α_i(x)$ :

$$α_0(y|x)=\left\{ \begin{aligned} 1, &\text{y=start} \\ 0, &\text{otherwise} \end{aligned} \right.$$

递推公式：

$$α_i^T(y_i|x)= α_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)$$

$α_i^T(y_i|x)$ 表示在位置i的标记是$y_i$ 并且到位置i的前部分标记序列的非关规范化概率。

$y_i$可取的值有m个，所以$α_i(x)$ 是m维列向量。

• 后向向量$β_i(x)$ ：

$$β_{n+1}(y_{n+1}|x)=\left\{ \begin{aligned} 1, &y_{n+1}=\text{stop} \\ 0, &\text{otherwise} \end{aligned} \right.\ $$

递推公式：

$$β_i(y_i|x)= M_i(y_i,y_{i+1}|x)β_{i-1}(y_{i+1}|x)$$

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

可知$Z(x)=α_n^T(x)·1=1^T· β_1(x)$

• 概率计算 $$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)}$$

• 期望值的计算 特征函数$f_k$ 关于条件分布P(Y|X)的数学期望：

$$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{α_i^T(y_i|x)M_i(y_{i-1},y_i|x)β_i(y_i|x)}{Z(x)}$$

特征函数$f_k$ 关于联合分布P(X,Y)的数学期望：

$$E_{P(X,Y)}[f_k]= \sum_yP(x,y)f_k(y,x)=\sum\hat P(x)\sum_{i=1}^{n+1}\sum_{y_{i-1},y_i}f_k(y_{i-1},y_i,x,i)\frac{α_i^T(y_i|x)M_i(y_{i-1},y_i|x)β_i(y_i|x)}{Z(x)}$$

其中，$\hat P(x)$ 是经验分布。

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

• 问题描述：给定训练集，估计条件随机场模型参数。
• 学习方法包括：
  • 极大似然估计
  • 正则化的极大似然估计
• 具体的优化实现算法：
  • 改进的迭代尺度法IIS
  • 梯度下降法
  • 拟牛顿法。

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

问题描述： 给定条件随机场P(Y|X)和输入序列x，求条件概率最大输出序列$y^*$

• 维特比算法