Conditional random field (CRF)

CRF条件随机场，可应用于标注问题

概率无向图模型Probabilistic undirected graphical model(Markov random field)
是一个可以由无向图表示的联合概率分布

1. 模型定义

概率图模型：由图（Graph）表示的概率分布。

令无向图 G = (V, E) 表示联合概率分布P(Y)，即G中，

• 节点$v \in V$ 表示随机变量$Y_{v}, Y=\left(Y_{v}\right)_{v \in V}$；
• 边$e \in E$表示随机变量之间的概率依赖关系

无向图表示的随机变量的独立性假设:

• 成对马可夫性 pariwise Markov property
  • 指任意两个没有边连接的节点，在给定随机变量组（其他所有节点）条件下，该两节点是条件独立
• 局部马可夫性 local Markov property
  • 马科夫毯（Markov blanket）:节点 v 的所有相邻节点，
  • 指任意一个节点 v，在给定其所有相邻节点 W 条件下， v于除v，W以外的节点条件独立
• 全局马可夫性 global Markov property
  • 节点集合A、C被集合B所分开，在给定B条件下，A与C条件独立。

概率无向图模型：无向图 $G = (V, E)$ 表示联合概率分布 $P(Y)$，如果联合概率分布 $P(Y)$ 满足成对、局部或全局马可夫性，就称此联合概率分布 $P(Y)$ 为概率无向图模型，或马可夫随机场

团（clique）：图G中任何两个节点均有边连接的节点子集 最大团（maximal clique）：团C中不能再加任何一个节点使它成为更大的团，则称最大团

2. 条件随机场

条件随机场指给定随机变量X条件下， 随机变量Y的马可夫随机场。

2.1 条件随机场：

若随机变量$Y$构成一个由无向图$G = (V, E)$表示的马可夫随机场，即

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

对于任意节点$v$成立， 则称条件概率分布$P(Y\vert X)$为条件随机场。其中$w \sim v$表示在图$G = (V, E)$中与节点$v$有边连接的所有节点$w$， $w \neq v$表示节点v以外的所有节点。

2.2 线性链条件随机场（ linear chain conditional random field）

线性链条件随机场也是对数线性模型(log linear model)，定义为：

$$ P\left(Y_{i} | X, Y_{1}, \cdots, Y_{i-1}, Y_{i+1}, \cdots, Y_{n}\right)=P\left(Y_{i} | X, Y_{i-1}, Y_{i+1}\right) $$

在条件概率模型$P(Y | X)$中， $Y$是输出变量，表示标记序列（状态序列，参见HMM）；$X$使输入变量，表示需要标注的观测序列。利用训练集，通过极大似然估计或正则化的极大似然估计得到条件概率模型$\hat{P}(Y | X)$;预测时，对于给定输入序列$x$，求条件概率$\hat{P}(Y | X)$最大的输出序列$\hat{y}$。

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

设$P(Y\vert X)$为线性链条件随机场，X取值为x， Y取值为y的条件概率具有如下形式：

$$ P(y | x)=\frac{1}{Z(x)} \exp \left(\sum_{i, k} \lambda_{k} t_{k}\left(y_{i-1}, y_{i}, x, i\right)+\sum_{i, l} \mu_{l} s_{l}\left(y_{i}, x, i\right)\right) $$

其中，

$$ Z(x)=\sum_{y} \exp \left(\sum_{i, k} \lambda_{k} t_{k}\left(y_{i-1}, y_{i}, x, i\right)+\sum_{i, l} \mu_{l} s_{l}\left(y_{i}, x, i\right)\right) $$

式中，$t_{k}$和$s_{l}$是特征函数, $\lambda_{k}$和$\mu_{l}$是对应的权值。 $Z(x)$是规范化因子。在所有可能输出的序列上进行求和操作。

关于特征函数：

• 令$t_{k}$是定义在边上的特征函数，称为转移特征，依赖当前和前一个位置
• 令$s_{l}$是定义在节点上的特征函数，称为状态特征，依赖当前位置
• 特征函数$t_{k}$和$s_{l}$取值0或1；满足条件取1，反之0
• 条件随机长完全由特征函数$t_{k}$和$s_{l}$， 和对应的权值$\lambda_{k}$和$\mu_{l}$确定。

2.4 条件随机场的矩阵形式

对于观测序列x的每个位置，y在m个标记中取值，可以定义一个m阶的矩阵随机变量：

$$ M_{i}(x) = [ M_{i}(y_{i-1}, y_{i}|x) ] $$

矩阵随机变量元素为

$$ \begin{aligned} &M_{i}\left(y_{i-1}, y_{i} | x\right)=\exp \left(W_{i}\left(y_{i-1}, y_{i} | x\right)\right)\cr &W_{i}\left(y_{i-1}, y_{i} | x\right)=\sum_{k=1}^{K} w_{k} f_{k}\left(y_{i-1}, y_{i}, x, i\right) \end{aligned} $$

这里$w_k$为

$$ w_{k}=\begin{cases} \lambda_{k}, & k=1,2, \cdots, K_{1} \cr \mu_{l}, & k=K_{1}+l ; l=1,2, \cdots, K_{2} \end{cases} $$

和$f_k$为

$$ f_{k}\left(y_{i-1}, y_{i}, x, i\right)=\begin{cases} t_{k}\left(y_{i-1}, y_{i}, x, i\right), & k=1,2, \cdots, K_{1} \cr s_{l}\left(y_{i}, x, i\right), & k=K_{1}+l ; l=1,2, \cdots, K_{2} \end{cases} $$

于是，条件概率$P_{w}(y \vert x)$:

$$ P_{w}(y | x)=\frac{1}{Z_{w}(x)} \prod_{i=1}^{n+1} M_{i}\left(y_{i-1}, y_{i} | x\right) $$

其中，

$$ Z_{w}(x)=\left[M_{1}(x) M_{2}(x) \cdots M_{n+1}(x)\right]_{\mathrm{start}, \mathrm{stop}} $$

注， $y_{0} = \mathrm{start}$，表示开始状态； $y_{n+1} = \mathrm{stop}$， 表示终止状态

参考： 李航《统计学习方法》