條件随機場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，如需轉載請自行聯系原作者