天天看点

条件随机场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,如需转载请自行联系原作者