条件随机场CRF(三) 模型学习与维特比算法解码1. linear-CRF模型参数学习思路2. linear-CRF模型参数学习之梯度下降法求解3. linear-CRF模型维特比算法解码思路4. linear-CRF模型维特比算法流程5. linear-CRF模型维特比算法实例6.linear-CRF vs HMM

　　　　在linear-CRF模型参数学习问题中，我们给定训练数据集XX和对应的标记序列YY，KK个特征函数fk(x,y)fk(x,y)，需要学习linear-CRF的模型参数wkwk和条件概率Pw(y|x)Pw(y|x)，其中条件概率Pw(y|x)Pw(y|x)和模型参数wkwk满足一下关系：

Pw(y|x)=P(y|x)=1Zw(x)exp∑k=1Kwkfk(x,y)=exp∑k=1Kwkfk(x,y)∑yexp∑k=1Kwkfk(x,y)Pw(y|x)=P(y|x)=1Zw(x)exp∑k=1Kwkfk(x,y)=exp∑k=1Kwkfk(x,y)∑yexp∑k=1Kwkfk(x,y)

　　　　所以我们的目标就是求出所有的模型参数wkwk，这样条件概率Pw(y|x)Pw(y|x)可以从上式计算出来。

　　　　下面我们只简要介绍用梯度下降法的求解思路。

　　　　在使用梯度下降法求解模型参数之前，我们需要定义我们的优化函数，一般极大化条件分布Pw(y|x)Pw(y|x)的对数似然函数如下：

L(w)=log∏x,yPw(y|x)P¯¯¯¯(x,y)=∑x,yP¯¯¯¯(x,y)logPw(y|x)L(w)=log∏x,yPw(y|x)P¯(x,y)=∑x,yP¯(x,y)logPw(y|x)

　　　　其中P¯¯¯¯(x,y)P¯(x,y)为经验分布，可以从先验知识和训练集样本中得到,这点和最大熵模型类似。为了使用梯度下降法，我们现在极小化f(w)=−L(Pw)f(w)=−L(Pw)如下：

f(w)=−∑x,yP¯¯¯¯(x,y)logPw(y|x)=∑x,yP¯¯¯¯(x,y)logZw(x)−∑x,yP¯¯¯¯(x,y)∑k=1Kwkfk(x,y)=∑xP¯¯¯¯(x)logZw(x)−∑x,yP¯¯¯¯(x,y)∑k=1Kwkfk(x,y)=∑xP¯¯¯¯(x)log∑yexp∑k=1Kwkfk(x,y)−∑x,yP¯¯¯¯(x,y)∑k=1Kwkfk(x,y)(1)(2)(3)(4)(1)f(w)=−∑x,yP¯(x,y)logPw(y|x)(2)=∑x,yP¯(x,y)logZw(x)−∑x,yP¯(x,y)∑k=1Kwkfk(x,y)(3)=∑xP¯(x)logZw(x)−∑x,yP¯(x,y)∑k=1Kwkfk(x,y)(4)=∑xP¯(x)log∑yexp∑k=1Kwkfk(x,y)−∑x,yP¯(x,y)∑k=1Kwkfk(x,y)

　　　　对ww求导可以得到：

∂f(w)∂w=∑x,yP¯¯¯¯(x)Pw(y|x)f(x,y)−∑x,yP¯¯¯¯(x,y)f(x,y)∂f(w)∂w=∑x,yP¯(x)Pw(y|x)f(x,y)−∑x,yP¯(x,y)f(x,y)

　　　　有了ww的导数表达书，就可以用梯度下降法来迭代求解最优的ww了。注意在迭代过程中，每次更新ww后，需要同步更新Pw(x,y)Pw(x,y),以用于下一次迭代的梯度计算。

　　　　现在我们来看linear-CRF的第三个问题：解码。在这个问题中，给定条件随机场的条件概率P(y|x)P(y|x)和一个观测序列xx,要求出满足P(y|x)P(y|x)最大的序列yy。

　　　　维特比算法本身是一个动态规划算法，利用了两个局部状态和对应的递推公式，从局部递推到整体，进而得解。对于具体不同的问题，仅仅是这两个局部状态的定义和对应的递推公式不同而已。由于在之前已详述维特比算法，这里就是做一个简略的流程描述。

　　　　对于我们linear-CRF中的维特比算法，我们的第一个局部状态定义为δi(l)δi(l),表示在位置ii标记ll各个可能取值(1,2...m)对应的非规范化概率的最大值。之所以用非规范化概率是，规范化因子Z(x)Z(x)不影响最大值的比较。根据δi(l)δi(l)的定义，我们递推在位置i+1i+1标记ll的表达式为：

δi+1(l)=max1≤j≤m{δi(j)+∑k=1Kwkfk(yi=j,yi+1=l,x,i)},l=1,2,...mδi+1(l)=max1≤j≤m{δi(j)+∑k=1Kwkfk(yi=j,yi+1=l,x,i)},l=1,2,...m

　　　　和HMM的维特比算法类似，我们需要用另一个局部状态Ψi+1(l)Ψi+1(l)来记录使δi+1(l)δi+1(l)达到最大的位置ii的标记取值,这个值用来最终回溯最优解，Ψi+1(l)Ψi+1(l)的递推表达式为：

Ψi+1(l)=argmax1≤j≤m{δi(j)+∑k=1Kwkfk(yi=j,yi+1=l,x,i)},l=1,2,...mΨi+1(l)=argmax1≤j≤m{δi(j)+∑k=1Kwkfk(yi=j,yi+1=l,x,i)},l=1,2,...m

　　　　现在我们总结下 linear-CRF模型维特比算法流程：

　　　　输入：模型的KK个特征函数，和对应的K个权重。观测序列x=(x1,x2,...xn)x=(x1,x2,...xn),可能的标记个数mm

　　　　输出：最优标记序列y∗=(y∗1,y∗2,...y∗n)y∗=(y1∗,y2∗,...yn∗)

　　　　1) 初始化：

δ1(l)=∑k=1Kwkfk(y0=start,y1=l,x,i)},l=1,2,...mδ1(l)=∑k=1Kwkfk(y0=start,y1=l,x,i)},l=1,2,...m

Ψ1(l)=start,l=1,2,...mΨ1(l)=start,l=1,2,...m

　　　　2) 对于i=1,2...n−1i=1,2...n−1,进行递推：

　　　　3) 终止：

y∗n=argmax1≤j≤mδn(j)yn∗=argmax1≤j≤mδn(j)

　　　　4)回溯：

y∗i=Ψi+1(y∗i+1),i=n−1,n−2,...1yi∗=Ψi+1(yi+1∗),i=n−1,n−2,...1

　　　　最终得到最优标记序列y∗=(y∗1,y∗2,...y∗n)y∗=(y1∗,y2∗,...yn∗)

　　　　下面用一个具体的例子来描述 linear-CRF模型维特比算法，例子的模型和CRF系列第一篇中一样，都来源于《统计学习方法》。

　　　　假设输入的都是三个词的句子，即X=(X1,X2,X3)X=(X1,X2,X3),输出的词性标记为Y=(Y1,Y2,Y3)Y=(Y1,Y2,Y3),其中Y∈{1(名词)，2(动词)}Y∈{1(名词)，2(动词)}

　　　　这里只标记出取值为1的特征函数如下：

t1=t1(yi−1=1,yi=2,x,i),i=2,3,λ1=1t1=t1(yi−1=1,yi=2,x,i),i=2,3,λ1=1

t2=t2(y1=1,y2=1,x,2)λ2=0.6t2=t2(y1=1,y2=1,x,2)λ2=0.6

t3=t3(y2=2,y3=1,x,3)λ3=1t3=t3(y2=2,y3=1,x,3)λ3=1

t4=t4(y1=2,y2=1,x,2)λ4=1t4=t4(y1=2,y2=1,x,2)λ4=1

t5=t5(y2=2,y3=2,x,3)λ5=0.2t5=t5(y2=2,y3=2,x,3)λ5=0.2

s1=s1(y1=1,x,1)μ1=1s1=s1(y1=1,x,1)μ1=1

s2=s2(yi=2,x,i),i=1,2,μ2=0.5s2=s2(yi=2,x,i),i=1,2,μ2=0.5

s3=s3(yi=1,x,i),i=2,3,μ3=0.8s3=s3(yi=1,x,i),i=2,3,μ3=0.8

s4=s4(y3=2,x,3)μ4=0.5s4=s4(y3=2,x,3)μ4=0.5

　　　　求标记(1,2,2)的最可能的标记序列。

　　　　首先初始化:

δ1(1)=μ1s1=1δ1(2)=μ2s2=0.5Ψ1(1)=Ψ1(2)=startδ1(1)=μ1s1=1δ1(2)=μ2s2=0.5Ψ1(1)=Ψ1(2)=start

　　　　接下来开始递推，先看位置2的：

δ2(1)=max{δ1(1)+t2λ2+μ3s3,δ1(2)+t4λ4+μ3s3}=max{1+0.6+0.8,0.5+1+0.8}=2.4Ψ2(1)=1δ2(1)=max{δ1(1)+t2λ2+μ3s3,δ1(2)+t4λ4+μ3s3}=max{1+0.6+0.8,0.5+1+0.8}=2.4Ψ2(1)=1

δ2(2)=max{δ1(1)+t1λ1+μ2s2,δ1(2)+μ2s2}=max{1+1+0.5,0.5+0.5}=2.5Ψ2(2)=1δ2(2)=max{δ1(1)+t1λ1+μ2s2,δ1(2)+μ2s2}=max{1+1+0.5,0.5+0.5}=2.5Ψ2(2)=1

　　　　再看位置3的：

δ3(1)=max{δ2(1)+μ3s3,δ2(2)+t3λ3+μ3s3}=max{2.4+0.8,2.5+1+0.8}=4.3δ3(1)=max{δ2(1)+μ3s3,δ2(2)+t3λ3+μ3s3}=max{2.4+0.8,2.5+1+0.8}=4.3

Ψ3(1)=2Ψ3(1)=2

δ3(2)=max{δ2(1)+t1λ1+μ4s4,δ2(2)+t5λ5+μ4s4}=max{2.4+1+0.5,2.5+0.2+0.5}=3.9δ3(2)=max{δ2(1)+t1λ1+μ4s4,δ2(2)+t5λ5+μ4s4}=max{2.4+1+0.5,2.5+0.2+0.5}=3.9

Ψ3(2)=1Ψ3(2)=1

　　　　最终得到y∗3=argmax{δ3(1),δ3(2)}y3∗=argmax{δ3(1),δ3(2)},递推回去，得到：

y∗2=Ψ3(1)=2y∗1=Ψ2(2)=1y2∗=Ψ3(1)=2y1∗=Ψ2(2)=1

　　　　即最终的结果为(1,2,1)(1,2,1),即标记为(名词，动词，名词)。

　　　　linear-CRF模型和HMM模型有很多相似之处，尤其是其三个典型问题非常类似，除了模型参数学习的问题求解方法不同以外，概率估计问题和解码问题使用的算法思想基本也是相同的。同时，两者都可以用于序列模型，因此都广泛用于自然语言处理的各个方面。

　　　　现在来看看两者的不同点。最大的不同点是linear-CRF模型是判别模型，而HMM是生成模型，即linear-CRF模型要优化求解的是条件概率P(y|x)P(y|x),则HMM要求解的是联合分布P(x,y)P(x,y)。第二，linear-CRF是利用最大熵模型的思路去建立条件概率模型，对于观测序列并没有做马尔科夫假设。而HMM是在对观测序列做了马尔科夫假设的前提下建立联合分布的模型。

　　　　最后想说的是，只有linear-CRF模型和HMM模型才是可以比较讨论的。但是linear-CRF是CRF的一个特例，CRF本身是一个可以适用于很复杂条件概率的模型，因此理论上CRF的使用范围要比HMM广泛的多。

　　　　以上就是CRF系列的所有内容。

本文转自刘建平Pinard博客园博客，原文链接：http://www.cnblogs.com/pinard/p/7068574.html，如需转载请自行联系原作者