条件随机场CRF

知识点

1. 有向图无向图
   
2. log linear model
   通用形式：
   $$P(y|x,w)=\frac{exp({\sum }_j{w}_j{F}_j(x,y))}{z(x,w)}$$
   F为feature function，有不同的构造方法。

• 逻辑回归(LR)
• 条件随机场(CRF)
  $$\begin{array}{rl}P(\bar{y}|\bar{x},w)& =\frac{1}{z_{(}\bar{x},w)}exp\sum _{j=1}^J{w}_j{F}_j(\bar{x},\bar{y})\\ & =\frac{1}{z_{(}\bar{x},w)}exp\sum _{j=1}^J{w}_j\sum _{i=2}^n{f}_j(y_{i-1},y_i,\bar{x},i)\end{array}$$

3. Inference
   y ^ = a r g m a x   P ( y ˉ ∣ x ˉ , w ) = a r g m a x   ∑ j = 1 J w j F j ( x ˉ , y ˉ ) = a r g m a x   ∑ j = 1 J w j ∑ i = 2 n f j ( y i − 1 , y i , x ˉ , i ) = a r g m a x   ∑ i = 2 n g i ( y i − 1 . y i ) g ( y i − 1 , y i ) = ∑ j = 1 J w j f j ( y i − 1 , y i , x ˉ , i )

   $$\begin{aligned} \hat{y} &= argmax \ P(\bar{y}|\bar{x},w)\\ &= argmax \ \sum_{j=1}^{J}w_{j}F_{j}(\bar{x},\bar{y})\\ &= argmax \ \sum_{j=1}^{J}w_{j}\sum_{i=2}^{n}f_{j}(y_{i-1},y_{i},\bar{x},i)\\ &= argmax \ \sum_{i=2}^{n}g_{i}(y_{i-1}.y_{i})\\ g(y_{i-1},y_{i}) &= \sum_{j=1}^{J}w_{j}f_{j}(y_{i-1},y_{i},\bar{x},i) \end{aligned}$$ y^​g(yi−1​,yi​)​=argmax P(yˉ​∣xˉ,w)=argmax j=1∑J​wj​Fj​(xˉ,yˉ​)=argmax j=1∑J​wj​i=2∑n​fj​(yi−1​,yi​,xˉ,i)=argmax i=2∑n​gi​(yi−1​.yi​)=j=1∑J​wj​fj​(yi−1​,yi​,xˉ,i)​
   求解使$\hat{y}$最大的$\bar{y}$，使用Viterbi算法求解。

4. w的参数估计
   ∂ ∂ w j log ⁡ P ( y ∣ x , w ) = ∂ ∂ w j [ ∑ j = 1 J w j F j ( x , y ) − log ⁡ z ( x , w ) ] = F j ( x , y ) − 1 z ( x , w ) ∂ ∂ w j z ( x , w ) = F j ( x , w ) − ∑ y ′ F j ( x , y ′ ) ⋅ P ( y ′ ∣ x , w ) = F j ( x , y ) − E ( F j ( x , y ′ ) ) E q u a t i o n 1

   $$\begin{aligned} \frac{\partial }{\partial w_{j}} \log P(y|x,w)&=\frac{\partial }{\partial w_{j}}[\sum_{j=1}^{J}w_{j}F_{j}(x,y)-\log z(x,w)]\\ &= F_{j}(x,y)-\frac{1}{z(x,w)}\frac{\partial }{\partial w_{j}}z(x,w)\\ &=F_{j}(x,w)-\sum_{y'}F_{j}(x,y')\cdot P(y'|x,w)\\ &=F_{j}(x,y)-E(F_{j}(x,y')) \quad \quad \quad Equation 1 \end{aligned}$$ ∂wj​∂​logP(y∣x,w)​=∂wj​∂​[j=1∑J​wj​Fj​(x,y)−logz(x,w)]=Fj​(x,y)−z(x,w)1​∂wj​∂​z(x,w)=Fj​(x,w)−y′∑​Fj​(x,y′)⋅P(y′∣x,w)=Fj​(x,y)−E(Fj​(x,y′))Equation1​
   $$P(y_k=u|\bar{x},w)=\frac{\alpha (k,u)\cdot \beta (u,k)}{z(\bar{x},w)}$$
   $$P(y_k=u,y_{k+1}=v|\bar{x},w)=\frac{\alpha (k,u)exp[g_{k+1}(u,v)]\beta (u,k)}{z(\bar{x},w)}Equation2$$
   $$\begin{array}{rl}\frac{\partial }{\partial w_j}\log P(\bar{y}|\bar{x},w)& =F_j(\bar{x},\bar{y})-E(F_j(x,y^{\prime }))\\ & =F_j(\bar{x},\bar{y})-E_{\bar{y}}[\sum _{i=2}^n{f}_j(y_{i-1},y_i,\bar{x},i)]\\ & =F_j(\bar{x},\bar{y})-E_{y_{i-1},y_i}[\sum _{i=2}^n{f}_j(y_{i-1},y_i,\bar{x},i)]\\ & =F_j(\bar{x},\bar{y})-\sum _{i=2}^n\sum _{y_{i-1}}\sum _{y_i}{f}_j(y_{i-1},y_i,\bar{x},i)\cdot P(y_i,y_{i-1}|\bar{x},w)\\ & =F_j(\bar{x},\bar{y})-\sum _{i=2}^n\sum _{y_{i-1}}\sum _{y_i}{f}_j(y_{i-1},y_i,\bar{x},i)\cdot \frac{\alpha (i-1,y_{i-1})exp[g_i(y_{i-1},y_i)]\beta (y_i,i)}{z(\bar{x},w)}\end{array}$$