与之前提到的朴素贝叶斯，HMM不同，条件随机场属于概率无向图模型。因此我们需要先介绍概率无向图模型的相关概念。
概率无向图模型
概率无向图模型，也称为马尔可夫随机场，使用无向图表示一组随机变量X X X P ( X ) P(X) P ( X ) G = ( V , E ) G=(V,E) G = ( V , E ) V V V E E E X v X_v X v v v v X V X_V X V e ∈ E e\in E e ∈ E
如果两个随机变量对应的结点在图中没有边直接相连，那么在给定其他所有结点的变量的条件下，这两个变量条件独立。其联合概率分布满足以下性质：
成对马尔可夫性u u u v v v G G G V ∖ { u , v } V\setminus\{u,v\} V ∖ { u , v } X V ∖ { u , v } X_{V\setminus\{u,v\}} X V ∖ { u , v } X u X_u X u X v X_v X v P ( X u , X v ∣ X V ∖ { u , v } ) = P ( X u ∣ X V ∖ { u , v } ) P ( X v ∣ X V ∖ { u , v } ) P(X_u, X_v|X_{V \setminus\{u,v\}}) =P(X_u|X_{V\setminus\{u,v\}})P(X_v|X_{V\setminus\{u,v\}}) P ( X u , X v ∣ X V ∖ { u , v } ) = P ( X u ∣ X V ∖ { u , v } ) P ( X v ∣ X V ∖ { u , v } ) X u ⊥ X v ∣ X V ∖ { u , v } X_u \perp X_v|X_{V \setminus \{u,v\}} X u ⊥ X v ∣ X V ∖ { u , v }
局部马尔可夫性u ∈ V u\in V u ∈ V G G G N ( u ) N(u) N ( u ) u u u V ∖ ( { u } ∪ N ( u ) ) V\setminus(\{u\}\cup N(u)) V ∖ ({ u } ∪ N ( u )) u u u N ( u ) N(u) N ( u ) X N ( u ) X_{N(u)} X N ( u ) X u X_u X u X V ∖ ( { u } ∪ N ( u ) ) X_{V\setminus(\{u\}\cup N(u))} X V ∖ ({ u } ∪ N ( u )) P ( X u , X V ∖ ( { u } ∪ N ( u ) ) ∣ X N ( u ) ) = P ( X u ∣ X N ( u ) ) P ( X V ∖ ( { u } ∪ N ( u ) ) ∣ X N ( u ) ) P(X_u, X_{V \setminus (\{u\} \cup N(u))}|X_{N(u)}) = P(X_u|X_{N(u)})P(X_{V \setminus (\{u\}\cup N(u))}|X_{N(u)}) P ( X u , X V ∖ ({ u } ∪ N ( u )) ∣ X N ( u ) ) = P ( X u ∣ X N ( u ) ) P ( X V ∖ ({ u } ∪ N ( u )) ∣ X N ( u ) ) X u ⊥ X V ∖ ( { u } ∪ N ( u ) ) ∣ X N ( u ) X_u \perp X_{V\setminus (\{u\} \cup N(u))}|X_{N(u)} X u ⊥ X V ∖ ({ u } ∪ N ( u )) ∣ X N ( u )
全局马尔可夫性A A A B B B G G G S S S A , B A,B A , B S S S X A X_A X A X B X_B X B X S X_S X S X S X_S X S X A X_A X A X B X_B X B P ( X A , X B ∣ X S ) = P ( X A ∣ X S ) P ( X B ∣ X S ) P(X_A,X_B|X_S)=P(X_A|X_S)P(X_B|X_S) P ( X A , X B ∣ X S ) = P ( X A ∣ X S ) P ( X B ∣ X S ) X A ⊥ X B ∣ X S X_A\perp X_B|X_S X A ⊥ X B ∣ X S
实际上，如果联合概率分布P ( X ) P(X) P ( X )
由此可以得到概率无向图模型（或马尔可夫随机场）的定义：如果联合概率分布P ( X ) P(X) P ( X )
因子分解
对给定的概率无向图模型，我们希望将整体的联合概率写成若干子联合概率的乘积的形式，也就是对联合概率进行因子分解，这样便于模型的学习与计算。
先定义概率无向图中的团与最大团：
对于无向图G G G
若C C C G G G G G G C C C
将概率无向图模型的联合概率分布表示为其最大团上的严格正函数的乘积除以一个归一化因子的操作，即为概率无向图模型的因子分解。
具体而言，联合概率分布P ( X ) P(X) P ( X ) C C C Ψ C ( X C ) \Psi_C(X_C) Ψ C ( X C ) P ( X ) = 1 Z ∏ C Ψ C ( X C ) P(X)=\frac{1}{Z}\prod_C\Psi_C(X_C) P ( X ) = Z 1 C ∏ Ψ C ( X C ) Z = ∑ X ∏ C Ψ C ( X C ) \displaystyle Z=\sum_{X}\prod_C\Psi_C(X_C) Z = X ∑ C ∏ Ψ C ( X C ) Ψ C ( X C ) \Psi_C(X_C) Ψ C ( X C ) Ψ C ( X C ) = e − E ( X C ) \Psi_C(X_C)=e^{-E(X_C)} Ψ C ( X C ) = e − E ( X C ) E ( X C ) E(X_C) E ( X C )
概率无向图模型因子分解的存在性由Hammersley-Clifford定理保证。【其证明可参照链接 】
条件随机场
基本概念
条件随机场（conditional random field，CRF）的定义如下：设X X X Y Y Y P ( Y ∣ X ) P(Y|X) P ( Y ∣ X ) X X X Y Y Y Y Y Y G = ( V , E ) G=(V,E) G = ( V , E ) P ( Y v ∣ X , Y w , w ≠ v ) = P ( Y v ∣ X , Y w , w ∼ v ) P(Y_v|X,Y_w,w\not = v)=P(Y_v|X,Y_w,w\sim v) P ( Y v ∣ X , Y w , w = v ) = P ( Y v ∣ X , Y w , w ∼ v ) u u u X X X P ( Y ∣ X ) P(Y|X) P ( Y ∣ X )
由定义可知，条件随机场属于判别模型。而对于随机变量X X X G G G
而在NLP领域中，最常见的CRF就是线性链条件随机场，主要用于序列标注。此时P ( y ∣ x ) P(\mathbf{y}|\mathbf{x}) P ( y ∣ x ) y \mathbf{y} y x \mathbf{x} x
设x = x 1 , x 2 , ⋯ , x T , y = y 1 , y 2 , ⋯ , y T \mathbf{x}=x_1,x_2,\cdots,x_T,\mathbf{y}=y_1,y_2,\cdots,y_T x = x 1 , x 2 , ⋯ , x T , y = y 1 , y 2 , ⋯ , y T P ( y t ∣ x , y 1 , … , y t − 1 , y t + 1 , ⋯ , y T ) = P ( y t ∣ x , y t − 1 , y t + 1 ) , t = 1 , 2 , ⋯ , T P(y_t|\mathbf{x},y_1,…,y_{t-1},y_{t+1},\cdots,y_T)=P(y_t|\mathbf{x},y_{t-1},y_{t+1}),\quad t=1,2,\cdots,T P ( y t ∣ x , y 1 , … , y t − 1 , y t + 1 , ⋯ , y T ) = P ( y t ∣ x , y t − 1 , y t + 1 ) , t = 1 , 2 , ⋯ , T y 0 y_0 y 0 y T + 1 y_{T+1} y T + 1
线性链条件随机场具有以下三种主要形式：
基本形式{ y t , y t + 1 } \{y_t,y_{t+1}\} { y t , y t + 1 } P ( y ∣ x ) = 1 Z ( x ) ∏ t = 1 T + 1 Ψ t ( y t − 1 , y t , x ) P(\mathbf{y}|\mathbf{x}) = \frac{1}{Z(\mathbf{x})} \prod_{t=1}^{T+1} \Psi_t(y_{t-1}, y_t, \mathbf{x}) P ( y ∣ x ) = Z ( x ) 1 t = 1 ∏ T + 1 Ψ t ( y t − 1 , y t , x ) Z ( x ) = ∑ y ∏ t = 1 T + 1 Ψ t ( y t − 1 , y t , x ) \displaystyle Z(\mathbf{x})=\sum_{\mathbf{y}}\prod_{t=1}^{T+1}\Psi_t(y_{t-1}, y_t, \mathbf{x}) Z ( x ) = y ∑ t = 1 ∏ T + 1 Ψ t ( y t − 1 , y t , x ) Ψ t ( y t − 1 , y t , x ) = exp ( ∑ j = 1 M + L λ j f j ( y t − 1 , y t , x , t ) + ∑ l = 1 L μ l g l ( y t , x , t ) ) \Psi_t(y_{t-1}, y_t, \mathbf{x}) = \exp\left(\sum_{j=1}^{M+L} \lambda_j f_j(y_{t-1}, y_t, \mathbf{x}, t) + \sum_{l=1}^L \mu_l g_l(y_t, \mathbf{x}, t)\right) Ψ t ( y t − 1 , y t , x ) = exp ( j = 1 ∑ M + L λ j f j ( y t − 1 , y t , x , t ) + l = 1 ∑ L μ l g l ( y t , x , t ) ) f j f_j f j g l g_l g l λ j \lambda_j λ j μ l \mu_l μ l
特征函数通常为指示函数，当满足特征条件时取值为1 1 1 0 0 0 x , t \mathbf{x},t x , t x t x_t x t
另一方面，由上面的基本形式可知，线性链条件随机场也属于对数线性模型，是Logistic回归/最大熵模型在序列数据上的推广。标记序列表示的类别数量会随着序列长度的增加而指数级增加。
实际上，上一讲中的隐马尔科夫模型的联合概率也可以转换为线性链条件随机场的形式：
P ( y , x ) = ∏ t = 1 T + 1 P ( y t ∣ y t − 1 ) ⋅ ∏ t = 1 T P ( x t ∣ y t ) ⟹ log P ( y , x ) = ∑ t = 1 T + 1 log P ( y t ∣ y t − 1 ) + ∑ t = 1 T log P ( x t ∣ y t ) = ∑ t = 1 T + 1 ∑ s i , s j I ( y t − 1 = s i ) I ( y t = s j ) ⋅ log P ( s j ∣ s i ) + ∑ t = 1 T ∑ s i , O k I ( y t = s i ) I ( x t = o k ) ⋅ log P ( o k ∣ s i ) ⟹ P ( y , x ) = exp ( ∑ t = 1 T + 1 ∑ s i , s j λ i j I ( y t − 1 = s i ) I ( y t = s j ) + ∑ t = 1 T ∑ s i , o k μ i k I ( y t = s i ) I ( x t = o k ) ) \begin{aligned}
P(\mathbf{y},\mathbf{x}) &= \prod_{t=1}^{T+1} P(y_t|y_{t-1}) \cdot \prod_{t=1}^{T} P(x_t|y_t)\\
\Longrightarrow \log P(\mathbf{y}, \mathbf{x}) &= \sum_{t=1}^{T+1} \log P(y_t|y_{t-1}) + \sum_{t=1}^{T} \log P(x_t|y_t)\\
&=\sum_{t=1}^{T+1}\sum_{s_i, s_j} I(y_{t-1} = s_i) I(y_t = s_j) \cdot \log P(s_j|s_i)+\sum_{t=1}^T\sum_{s_i, O_k} I(y_t = s_i) I(x_t = o_k) \cdot \log P(o_k|s_i)\\
\Longrightarrow P(\mathbf{y},\mathbf{x})&=\exp \left( \sum_{t=1}^{T+1} \sum_{s_i, s_j} \lambda_{ij} I(y_{t-1} = s_i) I(y_t = s_j) + \sum_{t=1}^{T} \sum_{s_i, o_k} \mu_{ik} I(y_t = s_i) I(x_t = o_k) \right)
\end{aligned} P ( y , x ) ⟹ log P ( y , x ) ⟹ P ( y , x ) = t = 1 ∏ T + 1 P ( y t ∣ y t − 1 ) ⋅ t = 1 ∏ T P ( x t ∣ y t ) = t = 1 ∑ T + 1 log P ( y t ∣ y t − 1 ) + t = 1 ∑ T log P ( x t ∣ y t ) = t = 1 ∑ T + 1 s i , s j ∑ I ( y t − 1 = s i ) I ( y t = s j ) ⋅ log P ( s j ∣ s i ) + t = 1 ∑ T s i , O k ∑ I ( y t = s i ) I ( x t = o k ) ⋅ log P ( o k ∣ s i ) = exp t = 1 ∑ T + 1 s i , s j ∑ λ ij I ( y t − 1 = s i ) I ( y t = s j ) + t = 1 ∑ T s i , o k ∑ μ ik I ( y t = s i ) I ( x t = o k ) λ i j \lambda_{ij} λ ij μ i k \mu_{ik} μ ik
与HMM相比，线性链CRF作为判别模型，还可以利用转移特征和状态特征之外的其他特征进行序列标注，因而表现往往更好。
一般形式f j ( y t − 1 , y t , x , t ) = { f j ( y t − 1 , y t , x , t ) , j = 1 , 2 , ⋯ , M g l ( y t , x , t ) , j = M + 1 , M + 2 , ⋯ , M + L f_j(y_{t-1}, y_t, \mathbf{x}, t) =
\begin{cases}
f_j(y_{t-1}, y_t, \mathbf{x}, t), & j = 1, 2, \cdots, M \\
g_l(y_t, \mathbf{x}, t), & j = M + 1, M+2, \cdots, M+L
\end{cases} f j ( y t − 1 , y t , x , t ) = { f j ( y t − 1 , y t , x , t ) , g l ( y t , x , t ) , j = 1 , 2 , ⋯ , M j = M + 1 , M + 2 , ⋯ , M + L P ( y ∣ x ) = 1 Z ( x ) exp ( ∑ t = 1 T + 1 ∑ j = 1 M + L w j f j ( y t − 1 , y t , x , t ) ) Z ( x ) = ∑ y exp ( ∑ t = 1 T + 1 ∑ j = 1 M + L w j f j ( y t − 1 , y t , x , t ) ) \begin{aligned}
P(y|\mathbf{x}) &= \frac{1}{Z(\mathbf{x})} \exp \left( \sum_{t=1}^{T+1} \sum_{j=1}^{M+L} w_j f_j(y_{t-1}, y_t, \mathbf{x}, t) \right) \\
Z(\mathbf{x}) &= \sum_{\mathbf{y}} \exp \left( \sum_{t=1}^{T+1} \sum_{j=1}^{M+L} w_j f_j(y_{t-1}, y_t, \mathbf{x}, t) \right) \\
\end{aligned} P ( y ∣ x ) Z ( x ) = Z ( x ) 1 exp ( t = 1 ∑ T + 1 j = 1 ∑ M + L w j f j ( y t − 1 , y t , x , t ) ) = y ∑ exp ( t = 1 ∑ T + 1 j = 1 ∑ M + L w j f j ( y t − 1 , y t , x , t ) ) t t t P ( y ∣ x ) = 1 Z ( x ) exp ( ∑ j = 1 M + L w j f j ( y , x ) ) Z ( x ) = ∑ y exp ( ∑ j = 1 M + L w j f j ( y , x ) ) \begin{aligned}
P(\mathbf{y}|\mathbf{x}) &= \frac{1}{Z(\mathbf{x})} \exp \left( \sum_{j=1}^{M+L} w_j f_j(\mathbf{y}, \mathbf{x}) \right) \\
Z(\mathbf{x}) &= \sum_{\mathbf{y}} \exp \left( \sum_{j=1}^{M+L} w_j f_j(\mathbf{y}, \mathbf{x}) \right) \\
\end{aligned} P ( y ∣ x ) Z ( x ) = Z ( x ) 1 exp ( j = 1 ∑ M + L w j f j ( y , x ) ) = y ∑ exp ( j = 1 ∑ M + L w j f j ( y , x ) ) O ( T ⋅ I T ) O(T\cdot I^T) O ( T ⋅ I T ) I I I
矩阵形式x \mathbf{x} x t = 1 , 2 , ⋯ , T + 1 t = 1, 2, \cdots, T + 1 t = 1 , 2 , ⋯ , T + 1 I × I I \times I I × I M t ( x ) = [ Ψ t ( y t − 1 , y t , x ) ] I × I M_t(\mathbf{x}) = [\Psi_t(y_{t-1}, y_t, \mathbf{x})]_{I\times I} M t ( x ) = [ Ψ t ( y t − 1 , y t , x ) ] I × I Ψ t ( y t − 1 , y t , x ) = exp ( ∑ j = 1 M + L w j f j ( y t − 1 , y t , x , t ) ) \Psi_t(y_{t-1}, y_t, \mathbf{x}) = \exp \left( \sum_{j=1}^{M+L} w_j f_j(y_{t-1}, y_t, \mathbf{x}, t) \right) Ψ t ( y t − 1 , y t , x ) = exp ( j = 1 ∑ M + L w j f j ( y t − 1 , y t , x , t ) ) M 1 ( x ) M_1(\mathbf{x}) M 1 ( x ) 1 × I 1\times I 1 × I M T + 1 ( x ) M_{T+1}(\mathbf{x}) M T + 1 ( x ) I × 1 I\times 1 I × 1 P ( y ∣ x ) = 1 Z ( x ) ∏ i = 1 T + 1 Ψ ( y t − 1 , y t , x ) Z ( x ) = M 1 ( x ) M 2 ( x ) ⋯ M T ( x ) M T + 1 ( x ) \begin{aligned}
P(\mathbf{y}|\mathbf{x})&=\frac{1}{Z(\mathbf{x})}\prod_{i=1}^{T+1}\Psi(y_{t-1},y_t,\mathbf{x})\\
Z(\mathbf{x})&=M_1(\mathbf{x})M_2(\mathbf{x})\cdots M_{T}(\mathbf{x})M_{T+1}(\mathbf{x})
\end{aligned} P ( y ∣ x ) Z ( x ) = Z ( x ) 1 i = 1 ∏ T + 1 Ψ ( y t − 1 , y t , x ) = M 1 ( x ) M 2 ( x ) ⋯ M T ( x ) M T + 1 ( x ) O ( T ⋅ I 2 ) O(T\cdot I^2) O ( T ⋅ I 2 )
与HMM类似，线性链CRF同样主要用于处理三个基本问题（略，见上一讲 ），其中参数为w = { w 1 , ⋯ , w M + L } \mathbf{w}=\{w_1,\cdots,w_{M+L}\} w = { w 1 , ⋯ , w M + L }
概率计算算法
与HMM类似，线性链CRF概率如果直接计算会过于复杂，此时也有进行前向-后向算法简化计算。
首先定义前向向量（1 × I 1\times I 1 × I α t ( x ) = M 1 ( x ) M 2 ( x ) ⋯ M t ( x ) , t = 1 , 2 , ⋯ , T + 1 \alpha_t(\mathbf{x})=M_1(\mathbf{x})M_2(\mathbf{x})\cdots M_t(\mathbf{x}),\quad t=1,2,\cdots,T+1 α t ( x ) = M 1 ( x ) M 2 ( x ) ⋯ M t ( x ) , t = 1 , 2 , ⋯ , T + 1 α t + 1 ( x ) = α t ( x ) M t + 1 ( x ) \alpha_{t+1}(\mathbf{x})=\alpha_t(\mathbf{x})M_{t+1}(\mathbf{x}) α t + 1 ( x ) = α t ( x ) M t + 1 ( x ) α T + 1 ( x ) \alpha_{T+1}(\mathbf{x}) α T + 1 ( x ) Z ( x ) Z(\mathbf{x}) Z ( x )
然后定义后向向量（I × 1 I\times 1 I × 1 β t ( x ) = M t + 1 ( x ) M t + 2 ( x ) ⋯ M T + 1 ( x ) , t = T , T − 1 , ⋯ , 0 \beta_t(\mathbf{x})=M_{t+1}(\mathbf{x})M_{t+2}(\mathbf{x})\cdots M_{T+1}(\mathbf{x}),\quad t=T,T-1,\cdots,0 β t ( x ) = M t + 1 ( x ) M t + 2 ( x ) ⋯ M T + 1 ( x ) , t = T , T − 1 , ⋯ , 0 β t ( x ) = M t + 1 ( x ) β t + 1 ( x ) \beta_{t}(\mathbf{x})=M_{t+1}(\mathbf{x})\beta_{t+1}(\mathbf{x}) β t ( x ) = M t + 1 ( x ) β t + 1 ( x ) β 0 ( x ) = Z ( x ) \beta_{0}(\mathbf{x})=Z(\mathbf{x}) β 0 ( x ) = Z ( x )
结合前向向量与后向向量，就得到了归一化因子的前向-后向算法：
Z w ( x ) = α t ( x ) β t ( x ) = M 1 ( x ) M 2 ( x ) ⋯ M T + 1 ( x ) Z_\mathbf{w}(\mathbf{x}) = \alpha_t(\mathbf{x})\beta_t(\mathbf{x}) = M_1(\mathbf{x})M_2(\mathbf{x})\cdots M_{T+1}(\mathbf{x}) Z w ( x ) = α t ( x ) β t ( x ) = M 1 ( x ) M 2 ( x ) ⋯ M T + 1 ( x )
由前向-后向向量，我们可以得到特征函数的期望：
E P ( y ∣ x ) [ f j ] = ∑ y P ( y ∣ x ) f j ( y , x ) = ∑ y P ( y ∣ x ) ∑ t = 1 T + 1 f j ( y t − 1 , y t , x , t ) = ∑ t = 1 T + 1 ∑ y t − 1 , y t f j ( y t − 1 , y t , x , t ) α t − 1 ( y t − 1 ∣ x ) Ψ t ( y t − 1 , y t , x ) β t ( y t ∣ x ) Z ( x ) , j = 1 , 2 , ⋯ , M . E P ~ ( x , y ) [ f j ] = ∑ x , y P ~ ( x , y ) f j ( y , x ) = ∑ x P ~ ( x ) ∑ y P ( y ∣ x ) ∑ t = 1 T + 1 f j ( y t − 1 , y t , x , t ) = ∑ x P ~ ( x ) ∑ t = 1 T + 1 ∑ y t − 1 , y t f j ( y t − 1 , y t , x , t ) α t − 1 ( y t − 1 ∣ x ) Ψ t ( y t − 1 , y t , x ) β t ( y t ∣ x ) Z ( x ) , j = 1 , 2 , ⋯ , M . \begin{aligned}
\mathbb{E}_{P(\mathbf{y}|\mathbf{x})}[f_j]
&= \sum_y P(\mathbf{y}|\mathbf{x})f_j(\mathbf{y}, \mathbf{x}) \\
&= \sum_y P(\mathbf{y}|\mathbf{x}) \sum_{t=1}^{T+1} f_j(y_{t-1}, y_t, \mathbf{x}, t) \\
&= \sum_{t=1}^{T+1} \sum_{y_{t-1}, y_t} f_j(y_{t-1}, y_t, \mathbf{x}, t)
\frac{\alpha_{t-1}(y_{t-1}|\mathbf{x})\Psi_t(y_{t-1}, y_t,\mathbf{x})\beta_t(y_t|\mathbf{x})}{Z(\mathbf{x})},\quad j = 1, 2, \cdots, M.\\[20pt]
\mathbb{E}_{\tilde{P}(\mathbf{x}, \mathbf{y})}[f_j]&= \sum_{\mathbf{x}, \mathbf{y}} \tilde{P}(\mathbf{x}, \mathbf{y})f_j(\mathbf{y}, \mathbf{x}) \\
&= \sum_{\mathbf{x}} \tilde{P}(\mathbf{x}) \sum_{\mathbf{y}} P(\mathbf{y}|\mathbf{x}) \sum_{t=1}^{T+1} f_j(y_{t-1}, y_t, \mathbf{x}, t) \\
&= \sum_{\mathbf{x}} \tilde{P}(\mathbf{x})\sum_{t=1}^{T+1} \sum_{y_{t-1}, y_t} f_j(y_{t-1}, y_t, \mathbf{x}, t)
\frac{\alpha_{t-1}(y_{t-1}|\mathbf{x})\Psi_t(y_{t-1}, y_t,\mathbf{x})\beta_t(y_t|\mathbf{x})}{Z(\mathbf{x})}, \quad j = 1, 2, \cdots, M.
\end{aligned} E P ( y ∣ x ) [ f j ] E P ~ ( x , y ) [ f j ] = y ∑ P ( y ∣ x ) f j ( y , x ) = y ∑ P ( y ∣ x ) t = 1 ∑ T + 1 f j ( y t − 1 , y t , x , t ) = t = 1 ∑ T + 1 y t − 1 , y t ∑ f j ( y t − 1 , y t , x , t ) Z ( x ) α t − 1 ( y t − 1 ∣ x ) Ψ t ( y t − 1 , y t , x ) β t ( y t ∣ x ) , j = 1 , 2 , ⋯ , M . = x , y ∑ P ~ ( x , y ) f j ( y , x ) = x ∑ P ~ ( x ) y ∑ P ( y ∣ x ) t = 1 ∑ T + 1 f j ( y t − 1 , y t , x , t ) = x ∑ P ~ ( x ) t = 1 ∑ T + 1 y t − 1 , y t ∑ f j ( y t − 1 , y t , x , t ) Z ( x ) α t − 1 ( y t − 1 ∣ x ) Ψ t ( y t − 1 , y t , x ) β t ( y t ∣ x ) , j = 1 , 2 , ⋯ , M . Z ( x ) = α T + 1 ( x ) Z(\mathbf{x}) = \alpha_{T+1}(\mathbf{x}) Z ( x ) = α T + 1 ( x ) α t − 1 ( y t − 1 ∣ x ) \alpha_{t-1}(y_{t-1}|\mathbf{x}) α t − 1 ( y t − 1 ∣ x ) β t ( y t ∣ x ) \beta_t(y_t|\mathbf{x}) β t ( y t ∣ x ) y t − 1 y_{t-1} y t − 1 y t y_t y t
学习算法
与HMM类似，线性链CRF的学习算法同样有监督学习算法（极大似然估计法）：
对于观测序列与标记序列均一致的训练数据，其联合概率可表达为
P ~ ( x , y ) = P ~ ( x ) P w ( y ∣ x ) = P ~ ( x ) exp ( ∑ j = 1 M + L w j f j ( y , x ) ) ∑ y exp ( ∑ j = 1 M + L w j f j ( y , x ) ) \tilde{P}(\mathbf{x},\mathbf{y})=\tilde{P}(\mathbf{x})P_{\mathbf{w}}(\mathbf{y}|\mathbf{x})=\tilde{P}(\mathbf{x})\frac{\displaystyle\exp \left( \sum_{j=1}^{M+L} w_j f_j(\mathbf{y}, \mathbf{x}) \right) }{\displaystyle\sum_{\mathbf{y}} \exp \left( \sum_{j=1}^{M+L} w_j f_j(\mathbf{y}, \mathbf{x}) \right)} P ~ ( x , y ) = P ~ ( x ) P w ( y ∣ x ) = P ~ ( x ) y ∑ exp ( j = 1 ∑ M + L w j f j ( y , x ) ) exp ( j = 1 ∑ M + L w j f j ( y , x ) ) L ( w ) = − ∑ x , y P ~ ( x , y ) log P w ( y ∣ x ) = ∑ x P ~ ( x ) log ∑ y exp ( ∑ j = 1 M + L w j f j ( y , x ) ) − ∑ x , y P ~ ( x , y ) ∑ j = 1 M + L w j f j ( y , x ) \begin{aligned}
L(\mathbf{w}) &= -\sum_{\mathbf{x},\mathbf{y}} \tilde{P}(\mathbf{x}, \mathbf{y}) \log P_{\mathbf{w}}(\mathbf{y}|\mathbf{x}) \\
&= \sum_{\mathbf{x}} \tilde{P}(\mathbf{x}) \log \sum_{\mathbf{y}} \exp \left( \sum_{j=1}^{M+L} w_j f_j(\mathbf{y}, \mathbf{x}) \right) - \sum_{\mathbf{x},\mathbf{y}} \tilde{P}(\mathbf{x}, \mathbf{y}) \sum_{j=1}^{M+L} w_j f_j(\mathbf{y}, \mathbf{x})
\end{aligned} L ( w ) = − x , y ∑ P ~ ( x , y ) log P w ( y ∣ x ) = x ∑ P ~ ( x ) log y ∑ exp ( j = 1 ∑ M + L w j f j ( y , x ) ) − x , y ∑ P ~ ( x , y ) j = 1 ∑ M + L w j f j ( y , x ) ∂ L ∂ w j = ∑ x , y P ~ ( x ) P w ( y ∣ x ) f j ( y , x ) − E P ~ ( x , y ) [ f j ] , = ∑ x , y P ~ ( x ) ⋅ E P ( y ∣ x ) [ f j ] − E P ~ ( x , y ) [ f j ] , j = 1 , 2 , ⋯ , M \begin{aligned}
\frac{\partial L}{\partial w_j} &= \sum_{\mathbf{x},\mathbf{y}} \tilde{P}(\mathbf{x}) P_{\mathbf{w}}(\mathbf{y}|\mathbf{x}) f_j(\mathbf{y},\mathbf{x}) - \mathbb{E}_{\tilde{P}(\mathbf{x}, \mathbf{y})}[f_j], \\
&=\sum_{\mathbf{x},\mathbf{y}} \tilde{P}(\mathbf{x})\cdot \mathbb{E}_{P(\mathbf{y}|\mathbf{x})}[f_j]- \mathbb{E}_{\tilde{P}(\mathbf{x}, \mathbf{y})}[f_j], \quad j = 1, 2, \cdots, M
\end{aligned} ∂ w j ∂ L = x , y ∑ P ~ ( x ) P w ( y ∣ x ) f j ( y , x ) − E P ~ ( x , y ) [ f j ] , = x , y ∑ P ~ ( x ) ⋅ E P ( y ∣ x ) [ f j ] − E P ~ ( x , y ) [ f j ] , j = 1 , 2 , ⋯ , M
当然，作为无约束最优化问题，也可以使用迭代尺度法IIS、梯度下降法以及拟牛顿法（如BFGS）等进行计算，此处作略（可能在CS127中会涉及）
预测问题
与HMM类似，线性链CRF的预测问题同样可使用维特比算法解决。首先将预测问题转化为优化问题：
arg max y [ log P w ( y ∣ x ) ] = arg max y { log [ 1 Z ( x ) exp ( ∑ j = 1 M + L w j f j ( y , x ) ) ] } = arg max y { log [ 1 Z ( x ) exp ( ∑ t = 1 T + 1 ∑ j = 1 M + L w j f j ( y t − 1 , y t , x , t ) ) ] } = arg max y 1 ⋯ y T { ∑ t = 1 T + 1 ∑ j = 1 M + L w j f j ( y t − 1 , y t , x , t ) } \begin{aligned}
\argmax_{\mathbf{y}} \left[ \log P_w(\mathbf{y} | \mathbf{x}) \right]
&= \argmax_{\mathbf{y}} \left\{ \log \left[ \frac{1}{Z(\mathbf{x})} \exp \left( \sum_{j=1}^{M+L} w_j f_j(\mathbf{y}, \mathbf{x}) \right) \right] \right\} \\
&= \argmax_{\mathbf{y}} \left\{ \log \left[ \frac{1}{Z(\mathbf{x})} \exp \left( \sum_{t=1}^{T+1} \sum_{j=1}^{M+L} w_j f_j(y_{t-1}, y_t, \mathbf{x}, t) \right) \right] \right\} \\
&= \argmax_{y_1\cdots y_T} \left\{ \sum_{t=1}^{T+1} \sum_{j=1}^{M+L} w_j f_j(y_{t-1}, y_t, \mathbf{x}, t) \right\}
\end{aligned} y arg max [ log P w ( y ∣ x ) ] = y arg max { log [ Z ( x ) 1 exp ( j = 1 ∑ M + L w j f j ( y , x ) ) ] } = y arg max { log [ Z ( x ) 1 exp ( t = 1 ∑ T + 1 j = 1 ∑ M + L w j f j ( y t − 1 , y t , x , t ) ) ] } = y 1 ⋯ y T arg max { t = 1 ∑ T + 1 j = 1 ∑ M + L w j f j ( y t − 1 , y t , x , t ) } { 1 , 2 , ⋯ , I } \{1,2,\cdots,I\} { 1 , 2 , ⋯ , I } 1 1 1 t t t y t y_t y t δ t ( y t ) = max y 1 ⋯ y t − 1 ∑ t ′ = 1 t ∑ j = 1 M + L w j f j ( y t ′ − 1 , y t ′ , x , t ′ ) \delta_t(y_t) = \max_{y_1\cdots y_{t-1}} \sum_{t'=1}^t \sum_{j=1}^{M+L} w_j f_j(y_{t'-1}, y_{t'}, \mathbf{x}, t') δ t ( y t ) = y 1 ⋯ y t − 1 max t ′ = 1 ∑ t j = 1 ∑ M + L w j f j ( y t ′ − 1 , y t ′ , x , t ′ ) δ t ( y t ) = max y t − 1 [ δ t − 1 ( y t − 1 ) + ∑ j = 1 M + L w j f j ( y t − 1 , y t , x , t ) ] ϕ t ( y t ) = arg max y t − 1 [ δ t − 1 ( y t − 1 ) + ∑ j = 1 M + L w j f j ( y t − 1 , y t , x , t ) ] \begin{aligned}
\delta_t(y_t) &= \max_{y_{t-1}} \left[ \delta_{t-1}(y_{t-1}) + \sum_{j=1}^{M+L} w_j f_j(y_{t-1}, y_t, \mathbf{x}, t) \right] \\
\phi_t(y_t) &= \argmax_{y_{t-1}} \left[ \delta_{t-1}(y_{t-1}) + \sum_{j=1}^{M+L} w_j f_j(y_{t-1}, y_t, \mathbf{x}, t) \right]
\end{aligned} δ t ( y t ) ϕ t ( y t ) = y t − 1 max [ δ t − 1 ( y t − 1 ) + j = 1 ∑ M + L w j f j ( y t − 1 , y t , x , t ) ] = y t − 1 arg max [ δ t − 1 ( y t − 1 ) + j = 1 ∑ M + L w j f j ( y t − 1 , y t , x , t ) ] t = T t=T t = T δ T ∗ = max y T δ ( y T ) y T ∗ = arg max y T δ ( y T ) \begin{aligned}
\delta^*_T&=\max_{y_T}\delta(y_T)\\
y_T^*&=\argmax_{y_T}\delta(y_T)
\end{aligned} δ T ∗ y T ∗ = y T max δ ( y T ) = y T arg max δ ( y T ) y t − 1 ∗ = ϕ t ( y t ∗ ) , t = T , T − 1 , … , 1 y_{t-1}^* = \phi_t(y_t^*), \quad t = T, T-1, \dots, 1 y t − 1 ∗ = ϕ t ( y t ∗ ) , t = T , T − 1 , … , 1 y ∗ = y 1 ∗ y 2 ∗ ⋯ y T ∗ \mathbf{y}^* = y_1^* y_2^* \cdots y_T^* y ∗ = y 1 ∗ y 2 ∗ ⋯ y T ∗
最后我们梳理一下HMM和CRF相关模型算法提出的时间线：
模型/算法
提出者
提出时间
隐马尔可夫模型（HMM）
Leonard Baum，Ted Petrie等
1966年
维特比算法
Andrew Viterbi
1967年
Baum-Welch算法（前向-后向算法）
Leonard Baum 与 Lloyd Welch
1972年
最大熵马尔可夫模型（MEMM）
Andrew McCallum，Dayne Freitag 与 Fernando Pereira
2000年
条件随机场（CRF）
John Lafferty，Andrew McCallum 和 Fernando Pereira
2001年
注：MEMM可看作HMM与CRF中间的过渡形态，也属于判别模型，直接借鉴了最大熵模型，引入了特征函数，与CRF的主要区别在于使用局部归一化因子，这会导致标注偏置问题。
p.s. 笔者在看李航《机器学习方法》的这一章内容的时候发现有不少笔误，令人忍俊不禁（
ok，这样我们就基本将监督学习方法梳理完成了，下面进行简单的归纳总结：
按照学习问题与模型策略分类
按照模型属性分类
学习策略
学习算法
下面正式开启无监督学习篇章！
