自然語言處理常用模型解析

自然語言處理常用模型解析

一、N元模型

思想：

如果用變量W代表一個文本中順序排列的n個詞，即W = W1W2…Wn ，則統(tǒng)計語言 模型的任務是給出任意詞序列W 在文本中出現(xiàn)的概率P（W）。利用概率的乘積公式，P（W）可展開為：P（W） = P（w1）P（w2|w1）P（w3| w1 w2）…P（wn|w1 w2…wn-1），不難看出，為了預測詞Wn的出現(xiàn)概率，必須已知它前面所有詞的出現(xiàn)概率。從計算上來看，這太復雜了。如果任意一個詞Wi的出現(xiàn)概率只同它前面的N-1個詞有關，問題就可以得到很大的簡化。 這時的語言模型叫做N元模型 （N-gram），即P（W） = P（w1）P（w2|w1）P（w3| w1 w2）…P（wi|wi-N+1…wi-1）…實際使用的通常是N=2 或N=3的二元模型（bi-gram）或三元模型（tri-gram）。以三元模型為例，近似認為任意詞Wi的出現(xiàn)概率只同它緊接的前面的兩個詞有關。重要的是這些概率參數(shù)都是可以通過大規(guī)模語料庫來估值的。比如三元概率有P（wi|wi-2wi-1） ≈ count（wi-2 wi-1… wi） / count（wi-2 wi-1）式中count（…） 表示一個特定詞序列在整個語料庫中出現(xiàn)的累計次數(shù)。統(tǒng)計語言模型有點像天氣預報的方法。用來估計概率參數(shù)的大規(guī)模語料庫好比是一個地區(qū)歷年積累起來的氣象紀錄，而用三元模型來做天氣預報，就像是根據(jù)前兩天的天氣情況來預測今天的天氣。天氣預報當然不可能百分之百正確。這也算是概率統(tǒng)計方法的一個特點吧。（摘自黃昌寧論文《中文信息處理的主流技術是什么？》）

條件： 該模型基于這樣一種假設，第n個詞的出現(xiàn)只與前面N-1個詞相關，而與其 它任何詞都不相關，整句的概率就是各個詞出現(xiàn)概率的乘積。這些概率可以通過直接從語料中統(tǒng)計N個詞同時出現(xiàn)的次數(shù)得到。常用的是二元的Bi-Gram和三元的Tri-Gram。

問題：

雖然我們知道元模型中， n越大約束力越強，但由于計算機容量和速度的限制 及數(shù)據(jù)的稀疏，很難進行大n的統(tǒng)計。

二、馬爾可夫模型以及隱馬爾可夫模型

? ? ? ? 思想： 馬爾可夫模型實際上是個有限狀態(tài)機，兩兩狀態(tài)間有轉移概率；隱馬爾可夫模型中狀態(tài)不可見，我們只能看到輸出序列，也就是每次狀態(tài)轉移會拋出個觀測值；當我們觀察到觀測序列后，要找到最佳的狀態(tài)序列。隱馬爾科夫模型是一種用參數(shù)表示的用于描述隨機過程統(tǒng)計特性的概率模型，是一個雙重隨機過程，由兩個部分組成：馬爾科夫鏈和一般隨機過程。其中馬爾科夫鏈用來描述狀態(tài)的轉移，用轉移概率描述。一般隨機過程用來描述狀態(tài)與觀察序列之間的關系，用觀察值概率描述。因此，隱馬爾可夫模型可以看成是能夠隨機進行狀態(tài)轉移并輸出符號的有限狀態(tài)自動機，它通過定義觀察序列和狀態(tài)序列的聯(lián)合概率對隨機生成過程進行建模。每一個觀察序列可以看成是由一個狀態(tài)轉移序列生成，狀態(tài)轉移過程是依據(jù)初始狀態(tài)概率分布隨機選擇一個初始狀態(tài)開始，輸出一個觀察值后再根據(jù)狀態(tài)轉移概率矩陣隨機轉移到下一狀態(tài)，直到到達某一預先指定的結束狀態(tài)為止，在每一個狀態(tài)將根據(jù)輸出概率矩陣隨機輸出一個觀察序列的元素。

一個 HMM有 5個組成部分，通常記為一個五元組{S，K， π，A，B}，有時簡寫為一個三元組{π ，A，B}，其中：①S是模型的狀態(tài)集，模型共有 N個狀態(tài)，記為 S={s1，s2， ?，sN}；②K是模型中狀態(tài)輸出符號的集合，符號數(shù)為 M，符號集記為K={k1，k2，?，kM}；③是初始狀態(tài)概率分布，記為 ={ 1， 2，?， N}，其中 i是狀態(tài) Si作為初始狀態(tài)的概率；④A是狀態(tài)轉移概率矩陣，記為A={aij}，1≤i≤N，1≤j≤N。其中 aij是從狀態(tài) Si轉移到狀態(tài) Sj的概率；⑤B是符號輸出概率矩陣，記為B={bik}，1≤i≤N，1≤k≤M。其中 bik是狀態(tài) Si輸出 Vk的概率。要用HMM解決實際問題，首先需要解決如下 3個基本問題：①給定一個觀察序列 O=O1O2?OT和模型{ π，A，B}，如何高效率地計算概率P（O|λ），也就是在給定模型的情況下觀察序列O的概率；②給定一個觀察序列 O=O1O2?OT和模型{ π，A，B}，如何快速地選擇在一定意義下“最優(yōu)”的狀態(tài)序列Q=q1q2?qT，使得該狀態(tài)序列“最好地解釋”觀察序列；③給定一個觀察序列 O=O1O2?OT，以及可能的模型空間，如何來估計模型參數(shù)，也就是說，如何調(diào)節(jié)模型{π，A，B}的參數(shù)，使得 P（O|λ）最大。

問題：

隱馬模型中存在兩個假設：輸出獨立性假設和馬爾可夫性假設。其中，輸出獨立性假設要求序列數(shù)據(jù)嚴格相互獨立才能保證推導的正確性，而事實上大多數(shù)序列數(shù)據(jù)不能被表示成一系列獨立事件。 三、最大熵模型 最大熵原理原本是熱力學中一個非常重要的原理，后來被廣泛應用于自然語言處理方面。其基本原理很簡單：對所有的已知事實建模，對未知不做任何假設。也就是建模時選擇這樣一個統(tǒng)計概率模型，在滿足約束的模型中選擇熵最大的概率模型。若將詞性標注或者其他自然語言處理任務看作一個隨機過程，最大熵模型就是從所有符合條件的分布中，選擇最均勻的分布，此時熵值最大。 求解最大熵模型，可以采用拉格朗日乘數(shù)法，其計算公式為：

?

為歸一化因子 ，是對應特征的權重，表示一個特征。每個特征對詞性選擇的影響大小由特征權重決定，而這些權值可由GIS或IIS 學習算法自動得到。

三、支持向量機

原理：支持向量機的主要思想可以概括為兩點： （1） 它是針對線性可分情況進行分析，對于線性不可分的情況， 通過使用非線性映射算法將低維輸入空間線性不可分的樣本轉化為高維特征空間使其線性可分，從而使得高維特征空間采用線性算法對樣本的非線性特征進行線性分析成為可能; （2） 它基于結構風險最小化理論之上在特征空間中建構最優(yōu)分割超平面，使得學習器得到全局最優(yōu)化，并且在整個樣本空間的期望風險以某個概率滿足一定上界。 支持向量機的目標就是要根據(jù)結構風險最小化原理，構造一個目標函數(shù)將兩類模式盡可能地區(qū)分開來， 通常分為兩類情況來討論，：（1） 線性可分；（2） 線性不可分。

線性可分情況 在線性可分的情況下，就會存在一個超平面使得訓練樣本完全分開，該超平面可描述為： w ·x + b = 0 （1） 其中，“·”是點積， w 是n 維向量， b 為偏移量。

最優(yōu)超平面是使得每一類數(shù)據(jù)與超平面距離最近的向量與超平面之間的距離最大的這樣的平面。

最優(yōu)超平面可以通過解下面的二次優(yōu)化問題來獲得：

?

滿足約束條件：?

在特征數(shù)目特別大的情況，可以將此二次規(guī)劃問題轉化為其對偶問題：

滿足約束條件：

線性不可分的情況 對于線性不可分的情況，可以把樣本X 映射到一個高維特征空間H，并在此空間中運用原空間的函 數(shù)來實現(xiàn)內(nèi)積運算，這樣將非線性問題轉換成另一空間的線性問題來獲得一個樣本的歸屬。 根據(jù)泛函的有關理論，只要一種核函數(shù)滿足Mercer 條件，它就對應某一空間中的內(nèi)積，因此只要在最優(yōu)分類面上采用適當?shù)膬?nèi)積函數(shù)就可以實現(xiàn)這種線性不可分的分類問題。 此時的目標函數(shù)為：圖十二

特點：

概括括地說，支持向量機就是首先通過內(nèi)積函數(shù)定義的非線性變換將輸入空間變換到另一個高維空間，在這個空間中求最優(yōu)分類面。SVM分類函數(shù)形式上類似于一個神經(jīng)網(wǎng)絡，輸出是中間節(jié)點的線性組合，每個中間節(jié)點對應一個輸入樣本與一個支持向量的內(nèi)積，因此也叫做支持向量網(wǎng)絡。 SVM方法的特點： ① 非線性映射是SVM方法的理論基礎，SVM利用內(nèi)積核函數(shù)代替向高維空間的非線性映射; ② 對特征空間劃分的最優(yōu)超平面是SVM的目標，最大化分類邊際的思想是SVM方法的核心; ③ 支持向量是SVM的訓練結果，在SVM分類決策中起決定作用的是支持向量。 SVM 是一種有堅實理論基礎的新穎的小樣本學習方法。它基本上不涉及概率測度及大數(shù)定律等，因此不同于現(xiàn)有的統(tǒng)計方法。從本質上看，它避開了從歸納到演繹的傳統(tǒng)過程，實現(xiàn)了高效的從訓練樣本到預報樣本的“轉導推理”，大大簡化了通常的分類和回歸等問題。 SVM 的最終決策函數(shù)只由少數(shù)的支持向量所確定，計算的復雜性取決于支持向量的數(shù)目，而不是樣本空間的維數(shù)，這在某種意義上避免了“維數(shù)災難”。少數(shù)支持向量決定了最終結果，這不但可以幫助我們抓住關鍵樣本、“剔除”大量冗余樣本，而且注定了該方法不但算法簡單，而且具有較好的“魯棒”性。這種 “魯棒”性主要體現(xiàn)在：

①增、刪非支持向量樣本對模型沒有影響; ②支持向量樣本集具有一定的魯棒性; ③有些成功的應用中，SVM 方法對核的選取不敏感

四、條件隨機場 原理： 條件隨機場（CRFs）是一種基于統(tǒng)計的序列標記識別模型，由John Lafferty等人在2001年首次提出。它是一種無向圖模型，對于指定的節(jié)點輸入值，它能夠計算指定的節(jié)點輸出值上的條件概率，其訓練目標是使得條件概率最大化。線性鏈是CRFs中常見的特定圖結構之一，它由指定的輸出節(jié)點順序鏈接而成。一個線性鏈與一個有限狀態(tài)機相對應，可用于解決序列數(shù)據(jù)的標注問題。在多數(shù)情況下，CRFs均指線性的CRFs。用x=（x1，x2，…，xn）表示要進行標注的數(shù)據(jù)序列，y=（y1，y2，…，yn）表示對應的結果序列。例如對于中文詞性標注任務，x可以表示一個中文句子x=（上海，浦東，開發(fā)，與，法制，建設，同步），y則表示該句子中每個詞的詞性序列y=（NR，NR，NN，CC，NN，NN，VV）。 對于（X，Y），C由局部特征向量f和對應的權重向量λ確定。對于輸入數(shù)據(jù)序列x和標注結果序列y，條件隨機場C的全局特征表示為

?

CRFs模型的參數(shù)估計通常采用L—BFGS算法實現(xiàn)，CRFs解碼過程，也就是求解未知串標注的過程，需要搜索計算該串上的一個最大聯(lián)合概率，解碼過程采用Viterbi算法來完成。 CRFs具有很強的推理能力，能夠充分地利用上下文信息作為特征，還可以任意地添加其他外部特征，使得模型能夠獲取的信息非常豐富。CRFs通過僅使用一個指數(shù)模型作為在給定觀測序列條件下整個標記序列的聯(lián)合概率，使得該模型中不同狀態(tài)下的不同特征權值可以彼此交替，從而有效地解決了其他非生成有向圖模型所產(chǎn)生的標注偏置的問題。這些特點，使得CRFs從理論上講，非常適合中文詞性標注。

總結

?首先，CRF，HMM（隱馬模型）都常用來做序列標注的建模，像詞性標注，True casing。但隱馬模型一個最大的缺點就是由于其輸出獨立性假設，導致其不能考慮上下文的特征，限制了特征的選擇，而另外一種稱為最大熵隱馬模型則解決了這一問題，可以任意的選擇特征，但由于其在每一節(jié)點都要進行歸一化，所以只能找到局部的最優(yōu)值，同時也帶來了標記偏見的問題（label bias），即凡是訓練語料中未出現(xiàn)的情況全都忽略掉，而條件隨機場則很好的解決了這一問題，他并不在每一個節(jié)點進行歸一化，而是所有特征進行全局歸一化，因此可以求得全局的最優(yōu)值。目前，條件隨機場的訓練和解碼的開源工具還只支持鏈式的序列，復雜的尚不支持，而且訓練時間很長，但效果還可以。最大熵隱馬模型的局限性在于其利用訓練的局部模型去做全局預測。其最優(yōu)預測序列只是通過viterbi算法將局部的最大熵模型結合而成的。 條件隨機場，隱馬模型，最大熵隱馬模型這三個模型都可以用來做序列標注模型。但是其各自有自身的特點，HMM模型是對轉移概率和表現(xiàn)概率直接建模，統(tǒng)計共現(xiàn)概率。而最大熵隱馬模型是對轉移概率和表現(xiàn)概率建立聯(lián)合概率，統(tǒng)計時統(tǒng)計的是條件概率。

中，統(tǒng)計了全局概率，在 做歸一化時，考慮了數(shù)據(jù)在全局的分布，而不是僅僅在局部歸一化，這樣就解決了MEMM中的標記偏置的問題。