乾貨 | 條件隨機場詳解之模型篇

微信公眾號

關鍵字

全網搜索最新排名

【機器學習演算法】：排名第一

【機器學習】：排名第二

【Python】：排名第三

【演算法】：排名第四

條件隨機場部分分為兩篇講解，今天這一篇主要簡單的講述什麼是條件隨機場以及在這之前的概率無向圖模型，下一次將從優化演算法的層面上論述如何優化這個問題。（理解本篇文章需要對數理統計和圖論有一定的基礎）

條件隨機場

（Conditional Random Fields），簡稱

CRF

，是一種

判別式

的概率圖模型。條件隨機場是在給定隨機變數X條件下，隨機變數Y的馬爾科夫隨機場。原則上，條件隨機場的圖模型布局是可以任意給定的，但比較常用的是定義在線性鏈上的特殊的條件隨機場，稱為

線性鏈條件隨機場

。因為其不論在訓練、推論或是解碼上，都存在效率較高的演算法可供演算。

CRF最早由John D. Lafferty等在2001年提出，結合了最大熵模型和隱馬爾可夫模型（生成式模型）的特點，是一種概率無向圖模型。它常用於

序列標註、詞性標註，語義分析等自然語言處理問題

，比如可以用於分詞（Segmentation）、詞性標註（Part of Speech）和命名實體識別（Named Entity Recognition）任務。一般序列分類問題常常採用隱馬爾可夫模型（HMM），但隱馬爾可夫模型中存在兩個假設：輸出獨立性假設和馬爾可夫性假設。其中，輸出獨立性假設要求序列數據嚴格相互獨立才能保證推導的正確性，而事實上大多數序列數據不能被表示成一系列獨立事件。而條件隨機場則使用一種概率圖模型，具有表達長距離依賴性和交疊性特徵的能力，能夠較好地解決標註（分類）偏置等問題的優點，而且所有特徵可以進行全局歸一化，能夠求得全局的最優解。

概率無向圖模型

由於條件隨機場是在給定一組輸入隨機變數條件下，另一組輸出隨機變數的條件概率分布模型，其特點是假設輸出隨機變數構成馬爾科夫隨機場。因此在本節首先介紹馬爾科夫隨機場，即概率無向圖模型。

概率無向圖模型定義

圖是由結點及連接結點的邊組成的集合。結點和邊分別記作v和e，結點和邊的集合分別記作V和E，圖記作G=（V,E）。無向圖是指圖的邊是沒有方向的。

概率圖模型是由圖表示的概率分布。

設有聯合概率分布P(Y)，Y∈Y是一組隨機變數。由無向圖G=（V,E）表示概率分布P(Y)，即在圖G中，結點v∈V表示一個隨機變數Yv，Y=(Yv)v∈V;邊e∈E表示隨機變數之間的概率依賴關係。

給定一個聯合概率分布P(Y)和表示它的無向圖G.首先定義無向圖表示的隨機變數之間存在的

成對馬爾科夫性、局部馬爾科夫興和全句馬爾科夫性

。

概率無向圖模型的定義：

設有聯合概率分布P(Y)，由無向圖G=(V,E)表示，在圖G中，結點表示隨機變數，邊表示隨機變數之間的依賴關係。如果聯合概率分布P(Y)滿足成對、局部或全局馬爾科夫性，就稱此聯合概率分布為概率無向圖模型或馬爾科夫隨機場模型。

概率無向圖模型的因子分解

團與最大團：

無向圖G中 任何兩個結點均有邊連接的結點子集稱為團。若C是無向圖G的一個團，並且不能再加進任何一個G的結點使其稱為一個更大的團，則稱此C為最大團。

將概率無向圖模型的聯合概率分布表示為其最大團上的隨機變數的函數的乘積形式的操作，稱為概率無向圖模型的因子分解。給定概率 模型，捨棄無向圖為G，C表示G上的最大團，Yc表示C對應的隨機變數。那麼概率無向圖模型的聯合概率分布P(Y)可寫作圖中所有最大團上的函數的乘積形式，即

其中，Z是規範化因子，由下式給出：

規範化因子保證P(Y)構成了一個概率分布。這裡要求勢函數是嚴格正的，通常定義為指數函數：

條件隨機場

一般的條件隨機場定義：設X與Y是隨機變數，P(X|Y)是在給定X的條件下Y的條件概率分布。若隨機變數Y構成一個由 G=(V,E)表示的馬爾科夫隨機場，即

P(Yv|X,Yw,w≠v) = P(Yv|Yw,w－v)，對任意的節點v成立，則稱條件概率分布P(Y|X)為條件隨機場。式中w—v表示在圖G中與結點v有變連接的所有節點w，w≠v表示節點v以外的所有結點，Yv，Yu與Yw為結點v,u,與w對應的隨機變數。在定義中並沒有要求X與Y具有相同的結構。但是在實際中，一般假設X和Y具有相同的圖結構。

下面主要介紹一種特殊的條件隨機場模型，即無向圖為如圖1所示的線性鏈的情況。即G=(V={1,2,…,n}, E={(i,i+1)}), i=1,2,…,n-1.在此情況下，X=(X1,X2,…,Xn) , Y=(Y1,Y2,…,Yn),最大團是相鄰兩個結點的集合。線性鏈條件隨機場有下面的定義。

線性鏈條件隨機場：

設X=(X1,X2,…,Xn),Y=(Y1,Y2,…,Yn)均為線性鏈表示的隨機變數序列，若在給定隨機變數序列X的條件下，隨機變數序列Y的條件概率分布P(Y|X)構成條件隨機場，即滿足馬爾科夫性P(Yi|X,Y1,…,Yi-1,Yi+1,…,Yn)=P(Yi|X,Yi-1,Yi+1), i=1,2,…n,(在i=1和n時只考慮單邊)。則稱P(Y|X)為線性鏈條件隨機場。在標註問題中，X表示輸入觀測序列，Y表示對應的輸出標記序列或狀態序列。

參數化形式

設P(Y|X)為線性鏈條件隨機場，則在隨機變數X取值為x的條件下，隨機變數Y取值為y的條件概率具有如下的形式：

其中

式中，tk和sl是特徵函數，λk和μl是對應的權值。Z(X)是規範因子，求和是在所有可能的輸出序列上進行的。上面的兩個式子是線性鏈條件隨機場模型的基本形式，表示給定輸入序列x，對輸出序列y預測的條件率。tk是定義在邊上的特徵函數，稱為

轉移特徵

。

依賴於當前和前一個位置

。sl是定義在結點上的特徵函數，稱為

狀態特徵，依賴於當前位置

。tk和sl都依賴於位置，是局部特徵函數。通常，特徵函數tk和sl取值為1和0；當滿足特徵條件時取值為1，否則為0.條件隨機場完全由特徵函數tk，sl和對應的權值λk和μl確定。線性鏈條件隨機場也是對數線性模型。

條件隨機場的對數模型可以做相應的簡化，以使它的形式看起來比較簡潔。設有K1個轉移特徵，K2個狀態特徵，K=K1+K2，記

然後對轉移與狀態特徵在各個位置i求和，記作：

用wk表示特徵fk(y,x)的權值，即

於是條件隨機場可以表示為:

其中

若以w表示權值向量，即

F(y,x)表示全局特徵向量,即

則，條件隨機場可以寫成向量w與F(y,x)的內積形式：

其中，

為了以後計算方便，下面將給出條件隨機場的矩陣形式。引入特殊的起點和y0=start，yn-1=stop，這時pw(y|x)可以通過矩陣形式表示。對於觀測序列x的每一個位置i=1,2,…,n+1，定義一個m階矩陣（m是標記yi取值的個數）。

這樣，給定觀測序列x，標記序列y的非規範化概率可以通過n+1個矩陣的乘積表示，於是，條件概率Pw(y|x)是

其中

投稿、商業合作

請發郵件到：357062955@qq.com

為答謝各位對本公眾號的關注，

在【機器學習演算法與Python】與大會官方不謝努力的協商下爭取到了5張優惠券

，這個優惠券優惠每日減少50，今天是1350，明天是減少1300的金額後天減1250。也就是說，您購買門票使用優惠碼越早折扣越大~然後現在團購票：4人5000，10人1萬。（

需要優惠碼的請給我留言

）

大會詳情請點解閱讀原文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！

本站內容充實豐富，博大精深，小編精選每日熱門資訊，隨時更新，點擊「搶先收到最新資訊」瀏覽吧！