CRF基礎知識學習

2017-10-24條件隨機場

ConditionalRandomFields

內容隱馬爾可夫模型最大熵模型條件隨機場模型

隱馬爾可夫模型隱馬爾可夫模型(HiddenMarkovModel，HMM)是統(tǒng)計模型，它用來描述一個含有隱含未知參數(shù)的馬爾可夫過程。其難點是從可觀察的參數(shù)中確定該過程的隱含參數(shù)。然后利用這些參數(shù)來作進一步分析，例如模式識別。

離散馬爾可夫過程設有N個不同狀態(tài)的隨機過程，令t=1,2,…表示不同的時間點，表示時刻隨機過程所處的狀態(tài)，表示狀態(tài)到的轉移概率。當隨機過程滿足：當前所處的狀態(tài)僅與它之前的一個狀態(tài)有關，即時，該隨機過程為馬爾可夫隨機過程。隱馬爾可夫模型一個完整的隱馬爾可夫模型要求兩個具體的模型參數(shù)N和M，和三個概率矩陣A,B,π，也即隱馬爾可夫模型可形式化定義為一個五元組(N,M,A,B,π)。1〕模型中的狀態(tài)數(shù)N。模型中的各個狀態(tài)是相互連結的，任何狀態(tài)能從其它狀態(tài)到達。用S表示各個狀態(tài)的集合，，表示t時刻的狀態(tài)。2〕模型中各狀態(tài)不同的觀察符號，即輸出字符個數(shù)M。V表示各字符集合，。3〕狀態(tài)轉移概率分布A。，其中，，當從狀態(tài)經(jīng)一步到達時，。4〕觀察字符在狀態(tài)j時的概率分布B，，其中。，。5〕初始狀態(tài)分布π，，其中，。給定N，M，A，B，π，HMMs能輸出一個觀察字符的序列，其中，T是觀察序列的字符個數(shù)。隱馬爾可夫模型隱馬可爾可夫模型是一個生成模型，給定一個觀察序列，HMMs模型隱含一個與觀察序列對應的狀態(tài)序列。以下圖為隱馬爾可夫模型：上圖表示出HMMs內部的條件獨立關系，HMMs有三個獨立性假設：一是t時刻的狀態(tài)只依賴于t?1時刻的狀態(tài)，即。二是t時刻生成的值只依賴于t時刻的狀態(tài)，即。三是狀態(tài)與具體時間無關，即對任意的i和j都有。隱馬爾可夫模型HMMs的三個根本問題1〕給定一個模型λ=(N,M,A,B,π)，如何高效計算某輸出字符序列的概率P(O|λ)。2〕給定一個模型λ=(N,M,A,B,π)和一個輸出字符序列，如何找到產生這一序列概率最大的狀態(tài)序列。3〕給定一個模型λ=(N,M,A,B,π)和一個輸出字符序列，如何調整模型的參數(shù)使得產生這一序列的概率最大。隱馬爾可夫模型HMMs的三個根本解決方法問題1是一個評價問題，即給定一個模型λ和一個觀察序列，如何計算由模型產生這一觀察序列的概率P(O|λ)，可采用forward-backward算法解決。forward-backward過程：定義forward變量為,即對于模型λ，在t時刻，狀態(tài)為時的局部觀察序列的概率記為為局部觀察序列和t時刻的狀態(tài)的聯(lián)合分布概率，那么可遞歸得到。終結：遞歸：定義前向變量：初始化：forward算法：隱馬爾可夫模型隱馬爾可夫模型HMMs的三個根本解決方法由各個觀察字符的輸出狀態(tài)相互獨立，下面給出的遞推過程：隱馬爾可夫模型HMMs的三個根本解決方法那么觀察序列所有可能的狀態(tài)序列的概率為，以下圖說明了在t時刻從N個狀態(tài)，到達t+1時刻的狀態(tài)的forward過程，隱馬爾可夫模型HMMs的三個根本解決方法

終結：遞歸：定義前向變量：初始化：backward算法：隱馬爾可夫模型隱馬爾可夫模型HMMs的三個根本解決方法

隱馬爾可夫模型HMMs的三個根本解決方法

隱馬爾可夫模型HMMs的三個根本解決方法問題2是一個解碼問題，給定一個模型λ=(N,M,A,B,π)和一個輸出字符序列，如何找到產生這一序列概率最大的狀態(tài)序列，即從個可能的狀態(tài)序列中找到一個“最優(yōu)”的狀態(tài)序列，其中N是HMMs模型中狀態(tài)的個數(shù)，T是觀察序列的長度。對于問題2根據(jù)不同的“最優(yōu)”標準，可以有假設干個解決方案，所以給定觀察序列，找出“最優(yōu)”狀態(tài)序列的困難是最優(yōu)狀態(tài)序列的定義，即最優(yōu)標準的選擇。一個有效的查找最優(yōu)路徑的算法是Viterbi算法，它基于動態(tài)規(guī)劃方法。隱馬爾可夫模型HMMs的三個根本解決方法Viterbi算法：給定觀察序列，利用Viterbi算法可以有效率的找到一個最優(yōu)的狀態(tài)序列，計算量為，我們定義表示t時刻狀態(tài)時的最優(yōu)狀態(tài)序列和前t個觀察序列的聯(lián)合概率：

由t時刻狀態(tài)時的最優(yōu)狀態(tài)序列和前t個觀察序列的聯(lián)合概率可遞推得到時刻狀態(tài)時的最優(yōu)狀態(tài)序列和前t+1個觀察序列的聯(lián)合概率：隱馬爾可夫模型HMMs的三個根本解決方法Viterbi算法：初始化遞歸結束得到最優(yōu)路徑隱馬爾可夫模型HMMs的三個根本解決方法問題3是模型參數(shù)估計問題。給定觀察序列Ο，調整模型的參數(shù)使得在給定模型λ的條件下該觀察序列的概率P(Ο|λ)最大，可以用Baum-Welch方法〔等價于EM(Expectation-Modification)方法〕或者用梯度技術，通過不斷循環(huán)迭代更新參數(shù)的方法，設法使P(Ο|λ)到達最優(yōu)。Baum-Welch方法是EM算法的一種實現(xiàn)，因采用爬山法往往得到的是局部最優(yōu)。隱馬爾可夫模型HMMs的三個根本解決方法解題思想：給定一個模型和輸出字符序列，任意設定初始參數(shù)值，通過不斷循環(huán)更新參數(shù)的方法，設法到達最優(yōu)。算法步驟：2.基于λ0以及觀察值序列X，訓練新模型λ；1.初始模型〔待訓練模型〕λ0,3.如果log

P(X|λ)-log(P(X|λ0)<Delta，說明訓練已經(jīng)到達預期效果，算法結束。4.否那么，令λ0＝λ，繼續(xù)第2步工作隱馬爾可夫模型HMMs的三個根本解決方法Baum-Welch算法：

隱馬爾可夫模型HMMs的局限性

1.由于生成模型定義的是聯(lián)合概率，必須列舉所有觀察序列的可能值，這對多數(shù)領域來說是比較困難的。2.基于觀察序列中的每個元素都相互條件獨立。即在任何時刻觀察值僅僅與狀態(tài)〔即要標注的標簽〕有關。對于簡單的數(shù)據(jù)集，這個假設倒是合理。但大多數(shù)現(xiàn)實世界中的真實觀察序列是由多個相互作用的特征和觀察序列中較長范圍內的元素之間的依賴而形成的。最大熵模型

最大熵模型〔MEMs〕是基于最大熵理論的統(tǒng)計模型，廣泛應用于模式識別和統(tǒng)計評估中。最大熵原理的實質是，在局部知識前提下，關于未知分布最合理的推斷是符合知識的最不確定或最隨機的推斷。最大熵的原理可以概括為，將事件作為約束條件，求得可使熵最大化的概率分布作為正確的概率分布。熵的計算公式如下：

最大熵模型

熵有如下的性質：

其中|X|在離散分布時是隨機變量的個數(shù)。當X為確定值，即沒有變化的可能時上式左邊的等式成立。由條件：，對熵的計算公式求條件極值，可知當隨機變量X服從均勻分布時，成立，即均勻分布時熵最大。最大熵模型介紹最大熵模型的目的有兩個，一是得到條件概率的指數(shù)形式，二是說明求最大熵的實質是求對數(shù)似然函數(shù)的最大值。利用最大熵模型建模時，只需集中精力選擇特征，而不需要花費精力考慮如何使用這些特征。該模型的另一個優(yōu)點是特征選擇靈活，且不需要額外的獨立性假設或內在約束。但最大熵模型時空開銷大，存在嚴重的數(shù)據(jù)稀疏問題，需要進行平滑處理，且對語料庫的依賴性大。條件隨機場HMMs需要對觀察序列建模，且要求嚴格的輸出獨立性假設，導致其不能考慮上下文的特征，限制了特征的選擇。MEMs提出了一種條件模型，能夠把多種特征信息納入一個模型中，它用最大熵原理構造分布模型并利用對偶定理得出參數(shù)估計的實質是求最大對數(shù)似然估計。CRF〔conditionalrandomfield〕條件隨機場模型是一種典型的判別式模型。在觀測序列的根底上對目標序列進行建模，重點解決序列化標注的問題，CRF模型既具有判別式模型的優(yōu)點,又具有產生式模型考慮到上下文標記間的轉移概率，以序列化形式進行全局參數(shù)優(yōu)化和解碼的特點，解決了其他判別式模型(如最大熵、馬爾科夫模型)難以防止的標記偏置問題。條件隨機場隨機場可以看成是一組隨機變量的集合〔這組隨機變量對應同一個樣本空間〕,當給每一個位置按照某種分布隨機賦予一個值之后，其全體就叫做隨機場。馬爾可夫隨機場〔MRF〕對應一個無向圖。這個無向圖上的每一個節(jié)點對應一個隨機變量，節(jié)點之間的邊表示節(jié)點對應的隨機變量之間有概率依賴關系。因此，MRF的結構本質上反響了我們的先驗知識——哪些變量之間有依賴關系需要考慮，而哪些可以忽略。具有馬爾可夫性質：離當前因素比較遙遠(這個遙遠要根據(jù)具體情況自己定義〕的因素對當前因素的性質影響不大。如果給定的MRF中每個隨機變量下還有觀察值，要確定的是給定觀察集合下，這個MRF的分布，也就是條件分布，那么這個MRF就稱為CRF。它的條件分布形式完全類似于MRF的分布形式，只不過多了一個觀察集合x。CRF本質上是給定了觀察值(observations)集合的MRF。條件隨機場在以下的條件隨機場模型介紹中，隨機變量Χ表示需要標記的觀察序列集。隨機變量Y表示相應的表示標記序列集。所有的

被假設在一個大小為N的有限字符集內。隨機變量Χ和Y是聯(lián)合分布，但在判別式模型中我們構造一個關于觀察序列和標記序列的條件概率模型p(Y|X)和一個隱含的邊緣概率模型p(X)。下面給出條件隨機場定義：條件隨機場定義：令G=(V,E)表示一個無向圖，，Y中元素與無向圖G中的頂點一一對應。當在條件Χ下，隨機變量的條件概率分布服從圖的馬爾可夫屬性：，其中表示(v,w)是無向圖G的邊。這時我們稱(X,Y)是一個條件隨機場。條件隨機場關鍵問題1.特征函數(shù)的選擇2.參數(shù)估計3.模型推斷特征函數(shù)的選取直接關系模型的性能。從已經(jīng)標注好的訓練數(shù)據(jù)集學習條件隨機場模型的參數(shù)，即各特征函數(shù)的權重向量λ。在給定條件隨機場模型參數(shù)λ下，預測出最可能的狀態(tài)序列。條件隨機場1.特征函數(shù)的選擇CRFs模型中特征函數(shù)的形式定義：在定義特征函數(shù)的時候，首先構建觀察值上的真實特征b(x,i)的集合，即所有i時刻的觀察值x的真實特征，結合其對應的標注結果，就可以獲得模型的特征函數(shù)集。它是狀態(tài)特征函數(shù)和轉移特征函數(shù)的統(tǒng)一形式表示。特征函數(shù)通常是二值函數(shù)，取值要么為1要么為0。如果時刻i觀察值x是大寫開頭否則條件隨機場2.參數(shù)估計極大似然估計〔MaximumLikelihoodEstimation，MLE)假定對于訓練數(shù)據(jù)有一組樣本集合樣本是相互獨立的，為訓練樣本中(x,y)的經(jīng)驗概率，取對數(shù)形式：對于某個條件模型，訓練數(shù)據(jù)D的似然函數(shù)公式為：條件隨機場CRFs模型中極大似然函數(shù)：對求導：令上式等于0，求λ條件隨機場Lafferty提出兩個迭代縮放的算法用于估計條件隨機場的極大似然參數(shù)GIS算法〔GeneralisedIterativeScaling〕IIS算法〔ImprovedIterativeScaling〕迭代縮放是一種通過更新規(guī)那么以更新模型中的參數(shù)，通過迭代改善聯(lián)合或條件模型分布的方法。更新規(guī)那么如下：其中更新值使得新的值比原來的值更接近極大似然值。迭代縮放條件隨機場迭代縮放的根本原理假定我們有一個以為參數(shù)的模型并且要找到一組新的參數(shù)：使得在該參數(shù)條件下的模型具有更高的對數(shù)似然值。通過迭代，使之最終到達收斂。對于條件隨機場對數(shù)似然值的變化可以表示為：條件隨機場引入輔助函數(shù)：定義為在觀察序列和標記序列為(x,y)的條件下，特征值為1的特征的個數(shù)。根據(jù)尋找使最大化的?，使用迭代算法計算最大似然參數(shù)集。條件隨機場（A）將每個設初始值；（B）對于每個，計算，即迭代過程：應用更新規(guī)則，更新每個參數(shù)，直到收斂。條件隨機場GIS算法：GIS是迭代縮放的一種，為了確保參數(shù)收斂的結果達到全局最優(yōu)，GIS需要對特征集進行約束，即令每個訓練數(shù)據(jù)中的事件。定義了一個全局修正特征S(x,y)：其中C是訓練語料中所有的x和y情況下T(x,y)的最大值，即等于最大可能的特征個數(shù)，特征S(x,y)的參加確保了T(x,y)=C。假定對于所有的事件，條件隨機場選定的特征的總和是常量C。更新值按下式計算條件隨機場1.GIS算法的收斂速度由計算更新值的步長確定。C值越大，步長越小，收斂速度就越慢；反之C值越小，步長越大，收斂的速度也就越快。問題：2.GIS算法是依賴于一個額外的全局修正特征S(x,y)，以確保對于每個(x,y)對的有效特征的總和是一個常量。但是一旦參加這個新的特征，就認為這個特征和特征集中所有其他的特征之間是相互獨立的，并且它的參數(shù)也需要使用上式來更新。計算期望需要對所有可能的標記序列求和，這將是一個指數(shù)級的計算過程。條件隨機場IIS算法：重新定義：將每個對觀察序列和標記序列對(x,y)起作用的特征值的和近似等于對于觀察序列x的最大可能的觀察特征的和使用牛頓一拉夫森方法求解條件隨機場3.模型推斷第二個問題通過Viterbi算法解決。Viterbi算法是一種動態(tài)規(guī)劃算法，其思想精髓在于將全局最正確解的計算過程分解為階段最正確解的計算。二、對于未標記的序列，求其最可能的標記。常見的兩個問題：

一、在模型訓練中，求邊際分布和；第一個問題采用前向后向法解決；條件隨機場勢函數(shù)盡管在給定每個節(jié)點的條件下，分配給該節(jié)點一個條件概率是可能的，但條件隨機場的無向性很難保證每個節(jié)點在給定它的鄰接點條件下得到的條件概率和以圖中其它節(jié)點為條件得到的條件概率一致。因此導致我們不能用條件概率參數(shù)化表示聯(lián)合概率，而要從一組條件獨立的原那么中找出一系列局部函數(shù)的乘積來表示聯(lián)合概率。選擇局部函數(shù)時，必須保證能夠通過分解聯(lián)合概率使沒有邊的兩個節(jié)點不出現(xiàn)在同一局部函數(shù)中。最簡單的局部函數(shù)是定義在圖結構中的最大團(clique)上的勢函數(shù)(Potentialfunction)，并且是嚴格正實值的函數(shù)形式。但是一組正實數(shù)函數(shù)的乘積并不能滿足概率公理，那么必須引入一個歸一化因子Z，這樣可以確保勢函數(shù)的乘積滿足概率公理，且是G中節(jié)點所表示的隨機變量的聯(lián)合概率分布。其中C為最大團集合，利用Hammersley-Clifford定理，可以得到聯(lián)合概率公式如下：條件隨機場勢函數(shù)基于條件獨立的概念，條件隨機場的無向圖結構可以用來把關于的聯(lián)合分布因式化正的和實值的勢函數(shù)的乘積，每個勢函數(shù)操作在一個由G中頂點組成的隨機變量子集上。根據(jù)無向圖模型條件獨立的定義，如果兩個頂點間沒有邊，那么意味著這頂點這些頂點對應的隨機變量在給定圖中其它頂點條件下是條件獨立的。所以在因式化條件獨立的隨機變量聯(lián)合概率時，必須確保這些隨機變量不在同一個勢函數(shù)中。滿足這個要求的最容易的方法是要求每個勢函數(shù)操作在一個圖G的最大團上，這些最大團由隨機變量相應頂點組成。這確保了沒有邊的頂點在不同的勢函數(shù)中，在同一個最大團中的頂點都是有邊相連的。在無向圖中，任何一個全連通〔任意兩個頂點間都有邊相連〕的子圖稱為一個團(clique)，而稱不能被其它團所包含的才為最大團(maximalclique)。

條件隨機場勢函數(shù)理論上講，圖G的結構為任意，然而，在構造模型時，CRFs采用了最簡單和最重要的一階鏈式結構。如以下圖所示，條件隨機場(X,Y)以觀察序列Χ作為全局條件，并且不對Χ做任何假設。這種簡單結構可以被用來在標記序列上定義一個聯(lián)合概率分布p(y|x)，主要關心的是兩個序列和。條件隨機場概率模型的形式Lafferty對CRFs勢函數(shù)的選擇很大程度上受最大熵模型的影響。定義每個勢函數(shù)的形式如下：

其中y|c表示第c個團中的節(jié)點對應的隨機變量，是一個布爾型的特征函數(shù)，那么p(y|x)為：

其中Z(x)是歸一化因子，

在一階鏈式結構的圖G=(V,E)中，最大團僅包含相鄰的兩個節(jié)點，即是圖G中的邊。條件隨機場概率模型的形式對于一個最大團中的無向邊

，勢函數(shù)一般表達形式可擴展為：

其中

是整個觀察序列和相應標記序列在i?1和i時刻的特征，是一個轉移函數(shù)。而是在i時刻整個觀察序列和標記的特征，是一個狀態(tài)函數(shù)。聯(lián)合概率的表達形式可以寫為：其中，參數(shù)

和

可以由從訓練數(shù)據(jù)中估計，大的非負參數(shù)值意味著優(yōu)先選擇相應的特征事件，大的負值所對應的特征事件不太可能發(fā)生。條件隨機場概率模型的形式定義特征函數(shù)之前，先構造觀察序列的實數(shù)值特征b(x,i)集合來描述訓練數(shù)據(jù)的經(jīng)驗分布特征，這些特征與模型同分布。例如：

每個特征函數(shù)表示為觀察序列的實數(shù)值特征b(x,i)集合中的一個元素，如果當前狀態(tài)〔狀態(tài)函數(shù)〕或前一個狀態(tài)和當前狀態(tài)〔轉移函數(shù)〕具有特定的值，那么所有的特征函數(shù)都是實數(shù)值。例如轉移函數(shù)：為了統(tǒng)一轉移函數(shù)和狀態(tài)函數(shù)的表達形式，我們可以把狀態(tài)函數(shù)寫為下式：并用統(tǒng)一表示，可能是狀態(tài)函數(shù)或轉移函數(shù)，又令：從而結定觀察序列x條件下，相應的標記序列為y的概率可以寫為：其中Z(x)是歸一化因子。條件隨機場條件隨機場模型的參數(shù)估計以上的CRFs理論介紹給出了CRFs的概率形式公式，主要是基于最大熵理論，下面將介紹的是CRFs模型的參數(shù)估計，由最大熵模型可知參數(shù)估計的實質是對概率的對數(shù)最大似然函數(shù)求最值，即運用最優(yōu)化理論循環(huán)迭代，直到函數(shù)收斂或到達給定的迭代次數(shù)。假設給定訓練集，根據(jù)最大熵模型對參數(shù)λ估計采用最大似然估計法。條件概率p(y|x,λ)的對數(shù)似然函數(shù)形式為：條件概率p(y|x,λ)的形式化公式為：條件隨機場條件隨機場模型的參數(shù)估計對于該CRFs概率模型來說，對數(shù)最大似然參數(shù)估計的任務是從相互獨立的訓練數(shù)據(jù)中估計參數(shù)的值，那么對數(shù)似然函數(shù)可寫為下式：為了表達，假設鏈式結構的無向圖分別有一個特殊的起始節(jié)點和終止節(jié)點，分別用和表示。那么經(jīng)驗分布概率和由模型得到的概率的數(shù)學期望為：條件隨機場條件隨機場模型的參數(shù)估計我們根據(jù)對數(shù)似然函數(shù)對相應的參數(shù)

求一階偏導數(shù)：條件隨機場條件隨機場模型的參數(shù)估計通過梯度為零來求解參數(shù)λ并不一定總是得到一個近似解，因而需要利用一些迭代技術來選擇參數(shù)，使對數(shù)似然函數(shù)最大化。通常采用的方法是改進的迭代縮放ImprovedIterativeScaling,IIS〕或者基于梯度的方法來計算參數(shù)。以上的介紹中，我們給出了對數(shù)似然函數(shù)L(λ)梯度的計算表達形式，即的數(shù)學期望與由模型得到的條件概率p(y|x,λ)的數(shù)學期望的差。而經(jīng)驗分布的數(shù)學期望為訓練數(shù)據(jù)集中隨機變量(x,y)滿足特征約束的個數(shù)，模型的條件概率的數(shù)學期望的計算實質上是計算條件概率p(y|x,λ)，在下一節(jié)中我們將介紹條件概率的有效計算方法。條件隨機場條件概率的矩陣計算建立條件隨機場模型的主要任務是從訓練數(shù)據(jù)中估計特征的權重λ。下面主要對CRFs用到最大似然估計