您的位置: 首页  >  文章  >  条件随机场(CRF)笔记

条件随机场(CRF)笔记

分类: 文章 • 2025-02-11 10:53:22

目录

Prerequisite

  • Markov随机场
  • 好天气

HMM（隐马尔科夫模型）

定义：

我们从一个模型，二个假设，三个问题去简单认识下HMM。
条件随机场(CRF)笔记
其中Y=(y1,y2,⋯ ,yT)TY=(y_1,y_2,\cdots,y_T)^T为隐变量（状态），X=(x1,x2,⋯ ,xT)TX=(x_1,x_2,\cdots,x_T)^T为观测变量（输出）。
一个模型：
是指HMM是由参数集合λ=(π,A,B)\lambda=(\pi, A,B)决定的。其中π\pi是指p(yi)p(y_i)，即是初始状态的概率向量。AA为状态转移矩阵，即是Aij=p(yt+1=qj∣yt=qi)A_{ij}=p(y_{t+1}=q_j\vert y_{t}=q_i)。B为发射矩阵B为发射矩阵，即是Bij=p(xi=vj∣yi=qi)B_{ij}=p(x_i=v_j\vert y_i=q_i)。其中q,vq,v分别是yi和xiy_i和x_i的取值集合。
二个假设：
1.齐次马尔科夫假设：
即是说，任意状态yiy_i只会与前一状态yi−1y_{i-1}有关，说：
P(yi∣x1,x2,⋯ ,xi−1,y1,y2,⋯ ,yi−1)=P(yi∣yi−1)P(y_i\vert x_1,x_2,\cdots,x_{i-1},y_1,y_2,\cdots,y_{i-1})=P(y_i\vert y_{i-1})
2.观测独立性假设：
即是说，任意观测（输出）只依赖于该时刻的状态，说：
P(xi∣x1,x2,⋯ ,xi−1,y1,y2,⋯ ,yi−1,yi)=P(xi∣yi)P(x_i\vert x_1,x_2,\cdots,x_{i-1},y_1,y_2,\cdots,y_{i-1},y_i)=P(x_i\vert y_i)
三个问题：
1.概率计算：P(X∣λ)P(X\vert \lambda)
2.学习问题：计算出λ\lambda
3.预测问题：P(Y∣X,λ)P(Y\vert X,\lambda)

存在的问题：

如果是在词性标注问题中，那么HMM的假设就过于严格了，因为显然词性应该和整个文本都有关系。因此CRF就弥补了这一点。

CRF

条件随机场(CRF)笔记
其中Y=(y1,y2,⋯ ,yT)TY=(y_1,y_2,\cdots,y_T)^T为隐变量（状态），X=(x1,x2,⋯ ,xT)TX=(x_1,x_2,\cdots,x_T)^T为观测变量（输入）。

定义：

CRF是指给定随机变量集合X的条件下，Y随机变量集合构成马尔科夫随机场，由其性质即是有：
P(Yv∣X,Yw,w≠v)=P(YV∣X,Yw,w∼v)P(Y_v\vert X,Y_w,w\ne v)=P(Y_V\vert X,Y_w,w\sim v)
其中v，w指随机变量集合的第v,w个元素，w∼v表示与v有边相连其中v，w指随机变量集合的第v,w个元素，w\sim v表示与v有边相连
等式的含义是，YvY_v只与给定XX和与vv有边相连的节点ww有关。

因子分解：

表示：

Markov随机场的因子分解通式为：
P(Y)=1Z∏i=1Nϕci(Yci)Z=∑Y∏i=1Nϕci(Yci)P(Y)=\frac{1}{Z}\prod_{i=1}^N\phi_{c_i}(Y_{c_i})\\ Z=\sum_Y\prod_{i=1}^N\phi_{c_i}(Y_{c_i})
其中，ci表示第i个最大团，Yci表示第i个最大团的随机变量集合。Z是归一化因子，使得∑YP(Y)=1其中，c_i表示第i个最大团，Y_{c_i}表示第i个最大团的随机变量集合。Z是归一化因子，\\使得\sum_YP(Y)=1。
条件随机场(CRF)笔记

为了表示方便，引入了start和stop。
条件随机场的因子分解：
这里，我们定义∏iNϕci(Yci)\prod_i^N\phi_{c_i}(Y_{c_i})为：
∏iNϕci(Yci)=exp⁡{∑t,kλktk(yt−1,yt,x,i)+∑t,lμlsl(yt,x,i)}\prod_i^N\phi_{c_i}(Y_{c_i})=\exp\{\sum_{t,k}\lambda_kt_k(y_{t-1},y_t,x,i)+\sum_{t,l}\mu_ls_l(y_t,x,i)\}
其中，tk,sl为特征函数，λk,μl为权值其中，t_k,s_l为特征函数，\lambda_k,\mu_l为权值
Z=∑Yexp⁡{∑t,kλktk(yt−1,yt,x,i)+∑t,lμlsl(yt,x,i)}Z=\sum_Y\exp\{\sum_{t,k}\lambda_kt_k(y_{t-1},y_t,x,i)+\sum_{t,l}\mu_ls_l(y_t,x,i)\}

化简(向量形式)：

exp{∑t,kλktk(yt−1,yt,x,i)+∑t,lμlsl(yt,x,i)}=exp{∑t(∑kKλktk(yt−1,yt,x,i)+∑tLμlsl(yt,x,i))}其中：λ=[λ1λ2⋅⋅⋅λk]t⃗=[t1t2⋅⋅⋅tk]μ=[μ1μ2⋅⋅⋅μl]s⃗=[s1s2⋅⋅⋅sl]∑t(∑kKλktk(yt−1,yt,x,i)+∑lLμlsl(yt,x,i))=∑tλTt⃗+μTs⃗其中，t⃗,s⃗为yi,yi−1的函数：=λT∑tt⃗+μT∑ts⃗令：θ=[λμ]H=[∑tt⃗∑ts⃗]则：P(Y)=1Zexp⁡{∑t,kλktk(yt−1,yt,x,i)+∑t,lμlsl(yt,x,i)}=1Zexp⁡(θTH)\begin{aligned}&exp\{\sum_{t,k}\lambda_kt_k(y_{t-1},y_t,x,i)+\sum_{t,l}\mu_ls_l(y_t,x,i)\}\\ &=exp\{\sum_{t}\big (\sum_{k}^K\lambda_kt_k(y_{t-1},y_t,x,i)+\sum_{t}^L\mu_ls_l(y_t,x,i)\big)\}\\ 其中：&\lambda=\begin{bmatrix}\lambda_1\\\lambda_2\\\cdot\\\cdot\\\cdot\\ \lambda_k \end{bmatrix}\vec t=\begin{bmatrix} t_1\\t_2\\\cdot\\\cdot\\\cdot\\ t_k\end{bmatrix}\mu=\begin{bmatrix} \mu_1\\\mu_2\\\cdot\\\cdot\\\cdot\\ \mu_l \end{bmatrix}\vec s=\begin{bmatrix} s_1\\s_2\\\cdot\\\cdot\\\cdot\\ s_l\end{bmatrix}\\ &\sum_t\big(\sum_{k}^K\lambda_kt_k(y_{t-1},y_t,x,i)+\sum_{l}^L\mu_ls_l(y_t,x,i)\big)\\ &=\sum_t\lambda^T\vec t+\mu^T\vec s\\ 其中，\vec t,\vec s为y_i,y_{i-1}的函数：\\ &=\lambda^T\sum_t\vec t+\mu^T\sum_t\vec s\\ &令：\theta=\begin{bmatrix}\lambda\\\mu\end{bmatrix} H=\begin{bmatrix} \sum_t\vec t\\ \sum_t\vec s\end{bmatrix}\\ 则：\\ \\P(Y)&=\frac{1}{Z}\exp\{\sum_{t,k}\lambda_kt_k(y_{t-1},y_t,x,i)+\sum_{t,l}\mu_ls_l(y_t,x,i)\}\\ &=\frac{1}{Z}\exp{(\theta^TH)}\\ \end{aligned}
Z=∑Yexp⁡(θTH)\qquad\qquad\qquad\qquad\qquad Z=\sum\limits_Y\exp(\theta^TH)

求解问题：

边缘概率求解

前向后向算法：
其主要思想就是找到关于势函数的递推式。
P(yt=a)=∑y0,y1⋯yt−1,yt+1,⋯ ,yT1Z∏iTϕci(Yci)=∑y0,y1⋯yt−1,yt+1,⋯ ,yT1Zϕc1(Yc1)ϕc2(Yc2)⋯ϕcN(YcN)其中：ϕci(Yci)=ϕci(yi−1,yi)=1Z∑yT∑yT−1ϕcT(yT−1,yT)⋯∑y2ϕc3(y2,y3)∑y1ϕc2(y1,y2)∑y0ϕc1(y0,y1)令：Δleft=∑yt−1ϕct(yt−1,yt)⋯∑y2ϕc3(y2,y3)∑y1ϕc2(y1,y2)∑y0ϕc1(y0,y1)αt(i)=∑yt−1ϕct(yt−1,yt=i)∑yt−2ϕct−1(yt−2,yt−1)⋯∑y2ϕc3(y2,y3)∑y1ϕc2(y1,y2)∑y0ϕc1(y0,y1)αt−1(j)=∑yt−2ϕct−1(yt−2,yt−1=j)⋯∑y2ϕc3(y2,y3)∑y1ϕc2(y1,y2)∑y0ϕc1(y0,y1)可以发现有：αt(i)=∑jϕci(yt−1=j,yt=i)αt−1(j)令:Δright=∑yT∑yT−1ϕcT(yT−1,yT)⋯∑yt+2ϕct+3(yt+2,yt+3)∑yt+1ϕct+2(yt+1,yt+2)ϕct+1(yt=i,yt+1)βt(i)=∑yt+1ϕct+1(yt=i,yt+1)∑yt+2ϕct+2(yt+1,yt+2)⋯∑yT−2ϕcT−2(yT−3,yT−2)∑yT−1ϕcT−1(yT−2,yT−1)∑yTϕcT(yT−1,yT)βt+1(j)=∑yt+2ϕct+2(yt+1=j,yt+2)⋯∑yT−2ϕcT−2(yT−3,yT−2)∑yT−1ϕcT−1(yT−2,yT−1)∑yTϕcT(yT−1,yT)可以发现有：βt(i)=∑jϕt+1(yt=i,yt+1=j)βt+1(j)综上有递推式:αt(i)=∑jϕci(yt−1=j,yt=i)αt−1(j)βt(i)=∑jϕt+1(yt=i,yt+1=j)βt+1(j)那么：P(yt=a)=1Zαt(a)βt(a)\begin{aligned}P(y_t=a)=&\sum_{y_0,y_1\cdots y_{t-1},y_{t+1},\cdots ,y_T}\frac{1}{Z}\prod_i^T\phi_{c_i}(Y_{c_i})\\ &=\sum_{y_0,y_1\cdots y_{t-1},y_{t+1},\cdots ,y_T}\frac{1}{Z}\phi_{c_1}(Y_{c_1})\phi_{c_2}(Y_{c_2})\cdots\phi_{c_N}(Y_{c_N})\\ 其中：\phi_{c_i}(Y_{c_i})=\phi_{c_i}(y_{i-1},y_i)\\ &=\frac{1}{Z}\sum_{y_T}\sum_{y_{T-1}}\phi_{c_T}(y_{T-1},y_T)\cdots\sum_{y_2}\phi_{c_3}(y_2,y_3)\sum_{y_1}\phi_{c_2}(y_1,y_2)\sum_{y_0}\phi_{c_1}(y_0,y_1)\\ 令：\\ &\Delta_{left}=\sum_{y_{t-1}}\phi_{c_{t}}(y_{t-1},y_t)\cdots\sum_{y_2}\phi_{c_3}(y_2,y_3)\sum_{y_1}\phi_{c_2}(y_1,y_2)\sum_{y_0}\phi_{c_1}(y_0,y_1)\\ &\alpha_t(i)=\sum_{y_{t-1}}\phi_{c_{t}}(y_{t-1},y_t=i)\sum_{y_{t-2}}\phi_{c_{t-1}}(y_{t-2},y_{t-1})\cdots\sum_{y_2}\phi_{c_3}(y_2,y_3)\sum_{y_1}\phi_{c_2}(y_1,y_2)\sum_{y_0}\phi_{c_1}(y_0,y_1)\\ &\alpha_{t-1}(j)=\sum_{y_{t-2}}\phi_{c_{t-1}}(y_{t-2},y_{t-1}=j)\cdots\sum_{y_2}\phi_{c_3}(y_2,y_3)\sum_{y_1}\phi_{c_2}(y_1,y_2)\sum_{y_0}\phi_{c_1}(y_0,y_1)\\ 可以发现有：\\ &\alpha_{t}(i)=\sum_j\phi_{c_i}(y_{t-1}=j,y_t=i)\alpha_{t-1}(j)\\ 令:\\ &\Delta_{right}=\sum_{y_{T}}\sum_{y_{T-1}}\phi_{c_T}(y_{T-1},y_T)\cdots\sum_{y_{t+2}}\phi_{c_{t+3}}(y_{t+2},y_{t+3})\sum_{y_{t+1}}\phi_{c_{t+2}}(y_{t+1},y_{t+2})\phi_{c_{t+1}}(y_t=i,y_{t+1})\\ &\beta_t(i)=\sum_{y_{t+1}}\phi_{c_{t+1}}(y_{t}=i,y_{t+1})\sum_{y_{t+2}}\phi_{c_{t+2}}(y_{t+1},y_{t+2})\cdots\sum_{y_{T-2}}\phi_{c_{T-2}}(y_{T-3},y_{T-2})\sum_{y_{T-1}}\phi_{c_{T-1}}(y_{T-2},y_{T-1})\sum_{y_{T}}\phi_{c_T}(y_{T-1},y_T)\\ &\beta_{t+1}(j)=\sum_{y_{t+2}}\phi_{c_{t+2}}(y_{t+1}=j,y_{t+2})\cdots\sum_{y_{T-2}}\phi_{c_{T-2}}(y_{T-3},y_{T-2})\sum_{y_{T-1}}\phi_{c_{T-1}}(y_{T-2},y_{T-1})\sum_{y_{T}}\phi_{c_T}(y_{T-1},y_T)\\ 可以发现有：\\ &\beta_t(i)=\sum_j\phi_{t+1}(y_t=i,y_{t+1}=j)\beta_{t+1}(j)\\ 综上有递推式:\\ &\alpha_{t}(i)=\sum_j\phi_{c_i}(y_{t-1}=j,y_t=i)\alpha_{t-1}(j)\\ &\beta_t(i)=\sum_j\phi_{t+1}(y_t=i,y_{t+1}=j)\beta_{t+1}(j)\\ 那么：\\ &P(y_t=a)=\frac{1}{Z}\alpha_t(a)\beta_t(a)\\ \end{aligned}

参数估计

由上文可知，对任意样本YiY^i：
P(Yi)=1Z∏i=1Nϕci(Yci)=1Zexp{∑t,kλktk(yt−1,yt,x,i)+∑t,lμlsl(yt,x,i)}=1Z(λT∑tt⃗+μT∑ts⃗)θ=[λμ]H=[∑tt⃗∑ts⃗]=1Zexp⁡(θTH)且有λ,μ为参数\begin{aligned}P(Y^i)&=\frac{1}{Z}\prod_{i=1}^N\phi_{c_i}(Y_{c_i})\\ &=\frac{1}{Z}exp\{\sum_{t,k}\lambda_kt_k(y_{t-1},y_t,x,i)+\sum_{t,l}\mu_ls_l(y_t,x,i)\}\\ &=\frac{1}{Z}\big(\lambda^T\sum_t\vec t+\mu^T\sum_t\vec s\big) \\ &\theta=\begin{bmatrix}\lambda\\\mu\end{bmatrix} H=\begin{bmatrix} \sum_t\vec t\\ \sum_t\vec s\end{bmatrix}\\ &=\frac{1}{Z}\exp{(\theta^TH)}\\ 且有\lambda,\mu 为参数\\ \end{aligned}
那么很自然的，我们想到用极大似然去求解参数估计：
L(θ)=arg max⁡θ∏iP(Yi)L(\theta)=\argmax_\theta\prod_i P(Y^i)
此时问题就转化为参数θ\theta关于函数L(θ)L(\theta)的优化问题。
具体的算法有迭代尺度法，梯度下降，牛顿法等。
please jump: 参数估计

预测算法

预测的目标就是，求给定XX下，使得条件概率最大的YY。
please jump: 条件随机场CRF（预测算法详解）

条件随机场(CRF)笔记

参考书籍：
李航《统计学习方法第二版》

参考链接：
https://www.bilibili.com/video/BV1aE411o7qd?p=103
https://github.com/datawhalechina/team-learning/tree/master/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80

相关推荐