1. linear-CRF模型参数学习思路
在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)的表达式和最大熵模型原理小结中的模型一样，也可以使用最大熵模型中使用的改进的迭代尺度法(improved iterative scaling, IIS)来求解。
下面我们只简要介绍用梯度下降法的求解思路。
2. linear-CRF模型参数学习之梯度下降法求解
在使用梯度下降法求解模型参数之前，我们需要定义我们的优化函数，一般极大化条件分布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),以用于下一次迭代的梯度计算。
梯度下降法的过程这里就不累述了，如果不熟悉梯度下降算法过程建议阅读之前写的梯度下降（Gradient Descent）小结。以上就是linear-CRF模型参数学习之梯度下降法求解思路总结。
3. linear-CRF模型维特比算法解码思路
现在我们来看linear-CRF的第三个问题：解码。在这个问题中，给定条件随机场的条件概率P(y|x)P(y|x)和一个观测序列xx,要求出满足P(y|x)P(y|x)最大的序列yy。
这个解码算法最常用的还是和HMM解码类似的维特比算法。到目前为止，我已经在三个地方讲到了维特比算法，第一个是文本挖掘的分词原理中用于中文分词，第二个是隐马尔科夫模型HMM（四）维特比算法解码隐藏状态序列中用于HMM解码。第三个就是这一篇了。
维特比算法本身是一个动态规划算法，利用了两个局部状态和对应的递推公式，从局部递推到整体，进而得解。对于具体不同的问题，仅仅是这两个局部状态的定义和对应的递推公式不同而已。由于在之前已详述维特比算法，这里就是做一个简略的流程描述。
对于我们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
4. linear-CRF模型维特比算法流程
现在我们总结下 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,进行递推：
δ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
Ψ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
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∗)
5. linear-CRF模型维特比算法实例
下面用一个具体的例子来描述 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),即标记为(名词，动词，名词)。
6.linear-CRF vs HMM
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，如需转载请自行联系原作者
