1. 引言
条件随机场，conditional random field，CRF，是给定一组输入随机变量的条件下，输出随机变量的条件概率分布模型。
条件随机场和隐马尔可夫模型的联系：
可以看到，条件随机场是一种无向图。
2. 概率无向图
概率无向图模型，又称马尔科夫随机场，是一个由无向图表示的联合概率分布。
- 成对马尔可夫性
设 u , v u,v u,v是无向图G中没有边连接的结点，对应的随机变量为 Y u , Y v Y_u, Y_v Yu?,Yv?. 其他结点为 Y O Y_O YO?.
P ( Y u , Y v ∣ Y o ) = P ( Y u ∣ Y O ) P ( Y v ∣ Y o ) P\left(Y_{u}, Y_{v} | Y_{o}\right)=P\left(Y_{u} | Y_{O}\right) P\left(Y_{v} | Y_{o}\right) P(Yu?,Yv?∣Yo?)=P(Yu?∣YO?)P(Yv?∣Yo?)
- 局部马尔可夫性
设 W W W是与 v v v有边连接的所有结点。
P ( Y v , Y o ∣ Y W ) = P ( Y v ∣ Y W ) P ( Y O ∣ Y W ) P\left(Y_{v}, Y_{o} | Y_{W}\right)=P\left(Y_{v} | Y_{W}\right) P\left(Y_{O} | Y_{W}\right) P(Yv?,Yo?∣YW?)=P(Yv?∣YW?)P(YO?∣YW?)
- 全局马尔科夫性
设结点集合 A , B A,B A,B是在无向图G中被结点集合 C C C分开的任意结点集合。
P ( Y A , Y B ∣ Y C ) = P ( Y A ∣ Y C ) P ( Y B ∣ Y C ) P\left(Y_{A}, Y_{B} | Y_{C}\right)=P\left(Y_{A} | Y_{C}\right) P\left(Y_{B} | Y_{C}\right) P(YA?,YB?∣YC?)=P(YA?∣YC?)P(YB?∣YC?)
-
团：任意两结点均有边连接的结点子集。
-
最大团：不能再加入任一结点组成更大的团。
-
势函数， Ψ C Ψ_C ΨC?函数
Ψ c ( Y c ) = exp ? { ? E ( Y c ) } \Psi_{c}\left(Y_{c}\right)=\exp \left\{-E\left(Y_{c}\right)\right\} Ψc?(Yc?)=exp{ ?E(Yc?)}
3. 条件随机场CRF
条件随机场是给定随机变量 X 下，随机变量Y的马尔科夫随机场。
P ( Y v ∣ X , Y n , w ≠ v ) = P ( Y v ∣ X , Y w , w ? v ) P\left(Y_{v} | X, Y_{n}, w \neq v\right)=P\left(Y_{v} | X, Y_{w}, w \sim v\right) P(Yv?∣X,Yn?,w??=v)=P(Yv?∣X,Yw?,w?v)
其中， w ? v w \sim v w?v代表与结点 v v v有边连接的所有结点 w w w; w ≠ v w \neq v w??=v代表结点 v v v以外的所有结点。
条件随机场的简单形式：
f k ( y i ? 1 , y i , x , i ) = { t k ( y i ? 1 , y i , x , i ) , k = 1 , 2 , ? , K 1 s i ( y i , x , i ) , k = K 1 + l ; l = 1 , 2 , ? , K 2 f_{k}\left(y_{i-1}, y_{i}, x, i\right)=\left\{\begin{array}{ll} t_{k}\left(y_{i-1}, y_{i}, x, i\right), & k=1,2, \cdots, K_{1} \\ s_{i}\left(y_{i}, x, i\right), & k=K_{1}+l ; l=1,2, \cdots, K_{2} \end{array}\right. fk?(yi?1?,yi?,x,i)={ tk?(yi?1?,yi?,x,i),si?(yi?,x,i),?k=1,2,?,K1?k=K1?+l;l=1,2,?,K2??
f k ( y , x ) = ∑ i = 1 n f k ( y i ? 1 , y i , x , i ) , k = 1 , 2 , ? , K f_{k}(y, x)=\sum_{i=1}^{n} f_{k}\left(y_{i-1}, y_{i}, x, i\right), \quad k=1,2, \cdots, K fk?(y,x)=i=1∑n?fk?(yi?1?,yi?,x,i),k=1,2,?,K
P ( y ∣ x ) = 1 Z ( x ) exp ? ∑ k = 1 K w k f k ( y , x ) Z ( x ) = ∑ y exp ? ∑ k = 1 K w k f k ( y , x ) \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}^{K} w_{k} f_{k}(y, x) \end{aligned} P(y∣x)Z(x)?=Z(x)1?expk=1∑K?wk?fk?(y,x)=y∑?expk=1∑K?wk?fk?(y,x)?
t k t_k tk?代表转移特征， s l s_l sl?代表状态特征， f k ( y , x ) f_k(y,x) fk?(y,x)代表在该点的全局特征， w k w_k wk?代表特征 f k ( y , x ) f_k(y,x) fk?(y,x)的权值， Z ( x ) Z(x) Z(x)是归一化因子。
条件随机场的矩阵形式：
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 ) = ∑ k = 1 K w k f k ( y i ? 1 , y i , x , i ) \begin{array}{c} M_{i}(x)=\left[M_{i}\left(y_{i-1}, y_{i} | x\right)\right] \\ M_{i}\left(y_{i-1}, y_{i} | x\right)=\exp \left(W_{i}\left(y_{i-1}, y_{i} | x\right)\right) \\ W_{i}\left(y_{i-1}, y_{i} | x\right)=\sum\limits_{k=1}^{K} w_{k} f_{k}\left(y_{i-1}, y_{i}, x, i\right) \end{array} Mi?(x)=[Mi?(yi?1?,yi?∣x)]Mi?(yi?1?,yi?∣x)=exp(Wi?(yi?1?,yi?∣x))Wi?(yi?1?,yi?∣x)=k=1∑K?wk?fk?(yi?1?,yi?,x,i)?
条件概率：
P w ( y ∣ x ) = 1 Z w ( x ) ∏ 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}\left(y_{i-1}, y_{i} | x\right) Pw?(y∣x)=Zw?(x)1?i=1∏n+1?Mi?(yi?1?,yi?∣x)
3.1 概率计算问题
前向-后向算法；
1、概率计算：
α 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 \alpha_{i}^{T}\left(y_{i} | x\right)=\alpha_{i-1}^{T}\left(y_{i-1} | x\right)\left[M_{i}\left(y_{i-1}, y_{i} | x\right)\right], i=1,2, \cdots, n+1 αiT?(yi?∣x)=αi?1T?(yi?1?∣x)[Mi?(yi?1?,yi?∣x)],i=1,2,?,n+1
β i ( y i ∣ x ) = [ M i ( y i , y i + 1 ∣ x ) ] β i + 1 ( y i + 1 ∣ x ) \beta_{i}\left(y_{i} | x\right)=\left[M_{i}\left(y_{i}, y_{i+1} | x\right)\right] \beta_{i+1}\left(y_{i+1} | x\right) βi?(yi?∣x)=[Mi?(yi?,yi+1?∣x)]βi+1?(yi+1?∣x)
即，
α i T ( x ) = α i ? 1 T ( x ) M i ( x ) \alpha_{i}^{\mathrm{T}}(x)=\alpha_{i-1}^{\mathrm{T}}(x) M_{i}(x) αiT?(x)=αi?1T?(x)Mi?(x)
β i ( x ) = M i + 1 ( x ) β i + 1 ( x ) \beta_{i}(x)=M_{i+1}(x) \beta_{i+1}(x) βi?(x)=Mi+1?(x)βi+1?(x)
因此，条件概率：
P ( Y i = y i ∣ x ) = α i ? ( y i ∣ x ) β i ( y i ∣ x ) Z ( x ) \begin{array}{c} P\left(Y_{i}=y_{i} | x\right)=\frac{\alpha_{i}^{\top}\left(y_{i} | x\right) \beta_{i}\left(y_{i} | x\right)}{Z(x)} \end{array} P(Yi?=yi?∣x)=Z(x)αi??(yi?∣x)βi?(yi?∣x)??
P ( Y i ? 1 = y i ? 1 , Y i = y i ∣ x ) = α i ? 1 T ( y i ? 1 ∣ x ) M i ( y i ? 1 , y i ∣ x ) β i ( y i ∣ x ) Z ( x ) \begin{array}{c} P\left(Y_{i-1}=y_{i-1}, Y_{i}=y_{i} | x\right)=\frac{\alpha_{i-1}^{\mathrm{T}}\left(y_{i-1} | x\right) M_{i}\left(y_{i-1}, y_{i} | x\right) \beta_{i}\left(y_{i} | x\right)}{Z(x)} \end{array} P(Yi?1?=yi?1?,Yi?=yi?∣x)=Z(x)αi?1T?(yi?1?∣x)Mi?(yi?1?,yi?∣x)βi?(yi?∣x)??
3.2 条件随机场的学习算法
改进的迭代尺度法
拟牛顿法
3.3 条件随机场的预测算法
给定条件随机场P(Y|X)，和输入序列x，求条件概率最大的输出序列y。
参考：
1、条件随机场_刘建平
2、IIS算法