CRF原理初探

語言: CN / TW / HK

寫在前面:本人剛剛入門NLP三個月,希望通過記錄部落格來鞏固自己的知識,增進對知識的理解。

本人在進行序列標註(sequence tagging)方面的學習時,最先接觸到兩個經典的統計學習方法:一個是HMM(隱馬爾可夫模型),一個是CRF(條件隨機場)。在查閱CRF有關的文章時,發現大體分為兩類:一類硬核解析,從公式出發;一類重視概念,從原理出發。很多博文都寫的很好,不過本人認為,理解CRF,數學與概念都要重視,才能見效。希望這篇膚淺的文章能夠幫助像我一樣剛入門的NLPer掃去一些疑惑。

一、序列標註 Sequence tagging

瞭解CRF之前,先從序列標註開始講起。

序列標註問題是NLP中的基本問題,簡單來說就是對一段序列進行標註或者說打標籤。許多經典的NLP任務,像詞性標註、分詞、命名實體識別、拼音輸入法等等,本質上都是對句子中的元素進行標籤預測。序列標註也是很多更高層次NLP任務的前驅,因為最近做的是分詞任務,所以簡單說明一下常見的標註方式,便於讀者後續閱讀:

  1. BIO標註:B-Beginning 一個詞的開始;I-Inside 一個詞之中;O-Outside 獨立的字。(常見於命名實體識別,B-Name等等形式)
  2. BMES標註:B-Begin 一個詞的開始;E-End 一個詞的結束;M-Middle 一個詞的中間;S-Single 獨立的字。(常用於中文分詞)
  3. BIOES標註:和1、2中字母含義相同。

接下來,一起來看看CRF吧!

二、為什麼需要CRF?

先說個人結論:CRF能在訓練語料中學習到更多資訊,表徵出更多特徵。

我看過一個很有趣的例子,原文在這兒翻譯在這兒,大概思想就是,你手頭有一組圖片,圖片順序展示了一個人一天的生活。現在,需要你對這一組圖片進行標註,註明這個人在做什麼事情,你會怎麼去做?

一般來說,我們會一張一張地看,有時候還需要藉助前後照片進行推理。因為這組圖片是具有時空順序關係的,上一張圖片如果在吃飯下一張圖片不可能會在做飯。

CRF的核心思想也是這樣,通過對某一時刻與相鄰時刻之間的特徵進行學習,來獲得更好的預測效果。其實如果是之前有了解神經網路的朋友的話,看到這裡也一定會想到LSTM模型吧?LSTM模型也很適用於解決序列型別問題,因此,像模型Bi-LSTM會後接CRF層來獲得更豐富的標籤之間的特徵資訊。

為了顯示CRF在分詞時對訓練資料更強的學習能力,展示一個例子(拿HMM作比較):

對於訓練資料中出現過的句子(BMES標註): [為/S 本/S 單/B 位/E 服/B 務/E 的/S 地/B 震/E 監/B 測/E 臺/B 網/E]

對應的分詞結果應該為: ['為', '本', '單位', '服務', '的', '地震', '監測', '臺網']

HMM預測結果:

CRF預測結果:

CRF的分詞結果

可以看出,CRF在遇到訓練資料中出現過的序列,能體現出自身學習到的資訊進行標註,對於訓練資料提供的潛藏資訊的表徵能力更強。

接下來,讓我們更進一步地瞭解CRF的性質與不同之處。

三、判別式(Discriminative)模型與生成式(Generative)模型

這兩個概念是經常容易碰到的概念,也是我覺得比較基礎不能混淆的知識。

先放一張直觀的圖:

  1. 什麼是判別式?

顧名思義,判別式就是,根據xx判斷xx。對於輸入X,預測標記Y,即條件概率P(Y|X)。所以在我的理解中,判別式其實是在訓練中學習得到一個邊界條件,或者說分裂面,對於模型的輸入,可以直接通過這個判斷標準來進行分類。像上圖中的左半部分,其實得到的是兩個類別的不同點,因此判別式在分類預測任務中有著非常不錯的表現。

  1. 什麼是生成式?

顧名思義,生成式就是,根據訓練資料生成多個種類的“模型”,而不是像判別式一樣去學習各個種類之間的分界。因此,這種方式計算的是一種聯合概率P(X,Y),對於輸入X,計算多個聯合概率,取最大的作為最有可能的情況。像上圖中的右圖所示,生成式會學習出比較完整的這一整個類的邊界,而不是僅僅關注類之間的關係。

  1. 舉個栗子

現在我的訓練資料裡有可口可樂與百事可樂,然後我向訓練好的機器輸入一張含有易拉罐的圖片。

假如是判別式模型:先對圖片提取出特徵資訊,判別式模型通過一些顯著的區分特徵(顏色、LOGO等等),直接可以給出是可口可樂的概率和是百事可樂的概率。

假如是生成式模型:先對圖片提取出特徵資訊,再通過訓練時已經對可口可樂和百事可樂建立好的模型,逐個傳入圖片特徵進行計算,最後概率最高的那個就是預測得到的種類。

  1. 和CRF有什麼關係?

HMM是生成式模型,CRF是判別式模型。為什麼?因為HMM的訓練過程是對所有樣本建立一個統計學的概率密度模型,這個模型是通過HMM當中的轉移矩陣和發射矩陣實現的。而CRF不同,CRF計算的是條件概率,直接對訓練資料中獲取的分類規則進行建模,例如前後位置資料與當前位置資料之間的關係等等。CRF更注重的是通過特徵函式學習到序列的特徵特點,以及序列之中的約束條件。這也就是為什麼CRF不會出現第二點中HMM出現的問題,因為HMM只對一個字以及它的下一個字是什麼做了概率估計,並沒有真正關注到整句話裡的前後特徵。

事實上,判別式模型與生成式模型是有一定的轉化關係的。邏輯上可以理解為,生成式模型對各個種類建立模型之後,其實也得到了各個模型的邊界,提供了轉化為判別式的前提條件。對HMM有所瞭解的讀者也可以思考一個問題,HMM與CRF是否存在一定的轉化關係?

四、從馬爾可夫到CRF

  1. 隨機場

在一個樣本空間中,各個點的值是根據某種分佈隨即賦予的。

  1. 馬爾可夫隨機場

隨機場+馬爾可夫性,即隨機場中某個位置只與其相鄰位置的值有關,與不相鄰位置的值無關。

  1. 條件隨機場

特殊的馬爾科夫隨機場,Y滿足馬爾可夫性。隨機場中每一個位置下還有一個觀測值X(observation),本質上,就是給定了觀測值X的隨機場,這個場中有X和Y兩種隨機變數,且Y滿足馬爾可夫性。

  1. 線性鏈條件隨機場 Linear-CRF

最常見的CRF的形式,特點是X和Y都具有相同的結構,並且滿足馬爾可夫性,即隨機場中某個位置只與其相鄰位置的值有關,與不相鄰位置的值無關。

Linear-CRF示意圖:

五、最大熵模型與CRF

  1. 最大熵 MaxEnt

最大熵模型不僅僅應用在序列標註任務上,該模型最偉大的地方在於,引入了特徵函式以及其相對應的引數來對輸入的整體特徵進行學習。數學公式就不搬上來了,其實整體上與CRF最後的結果很相似。

個人理解中,特徵函式的引入是為了引導模型去學習我們認為對於任務有幫助的一些特徵。 通過這種方式建立起對條件概率的計算,成為了判別式模型。而單純的生成式模型不含有特徵函式,直接對整個資料的分佈進行相應的學習。

  1. 最大熵馬爾可夫模型 MEMM

MEMM相比於HMM模型進步的地方在於,學習了MaxEnt的方法來計算條件概率。但是它的侷限性在於,MEMM是在每個區域性節點進行計算的基礎上,再合併起來。這樣做的問題在於,每一步的最大熵模型得到的條件概率僅基於與這一點相關的兩點的資訊,並且也只是在這個區域性進行歸一化,缺乏全域性性。

MEMM的進步之處在於,引入了判別式的方法,又基於HMM的性質在區域性進行運算,速度也很快。

  1. CRF中的特徵函式

CRF更像是以上幾種方法的結晶。

CRF中不可或缺的概念就是特徵函式。一開始在我看CRF的時候,突然蹦出兩個特徵函式搞得我一頭霧水,後來我才發現原來都是在前人不斷地研究和試錯中慢慢摸索出來的模型,respect。特徵函式其實是人為定義的,比如在分詞任務中,我不希望動詞後面會加形容詞或者動詞,那麼我可以通過設定特徵函式來明確這一點,給機器一個調整的方向。

CRF的特徵函式有兩種:

① 節點上的狀態特徵函式: $ s_l(y_i,x,i),i=1,2,...,L $

表示出節點上觀察序列與對應狀態之間的特徵。

② 節點之間的轉移特徵函式: $ t_k(y_{i-1},y_i,x,i),k=1,2,...,K $

表現出節點之間(這裡是前一個節點與當前節點)的特徵關係。

六、CRF公式淺析

進入公式環節,在此之前,還要先補充一點方便理解的知識:

  1. 概率無向圖

實際上,如果聯合概率分佈滿足成對,區域性或全域性馬爾可夫性,就稱此聯合概率分佈為概率無向圖模型。這個定義和上面馬爾可夫場的定義是相似的。也就是說,可以把馬爾科夫場看作一個概率無向圖,點是隨機變數,邊是變數間關係。而條件隨機場又可以看作是特殊的馬爾科夫隨機場,故而可以用概率無向圖來進行表示。

在概率無向圖中,還有一個很重要的概念,叫做最大團。

感謝這篇文章,這組圖片說明的很清楚。其實很簡單,極大團中是全連線的一組節點,再多一個節點就會破壞這種全連線的條件限制。最大團就是極大團中節點數最多的極大團。

那我們為什麼需要最大團呢?因為根據一個很數學的定理(Hammersley-Clifford 定理),概率無向圖模型的聯合概率分佈P(Y)可由最大團得到:

$ P(Y) = \frac{1}{Z}\sum_{Y}\psi_c(Y_c) $

$ Z = \sum_Y \prod_c\psi_c(Y_c) $

$ \psi_c(Y_c) = e^{-E(Y_c)} $

$ E(x_c) = \sum_{u,v\in C,u \neq v}\alpha_{u,v}t_{u,v}(u,v) + \sum_{v \in C}\beta_v s_v(v) $

第一條公式裡的c,就是無向圖的最大團。${Y_c}$代表了節點上的隨機變數,${\psi_c}$是一個嚴格正函式,Z是歸一化因子。

第二條公式是歸一化因子的計算公式。與第一條公式相同,只不過增加了對所有最大團的連乘。

第三和第四條公式是對${\psi}$函式,或者說,勢函式的進一步解釋。但實際上,並沒有規定${\psi}$函式一定是這樣。 因為這裡的定義與物理中的玻爾茲曼分佈有關,所以一般這樣設定勢函式。這裡的${\alpha}$與${\beta}$都是引數,t()與s()是特徵函式。 還有一個細節,這裡的特徵函式t()是關於極大團中兩個節點之間的關係,而s()是關於節點單獨的。這與CRF中特徵函式的定義很相似。

公式沒有看得很明白也沒有關係,讀者是否發現,第四條公式非常的眼熟?讓我們繼續來觀察一下CRF的公式。

  1. CRF公式

為了便於說明,以線性條件隨機場為例。

CRF的引數化定義是這樣的: $ P(y|x) = \frac{1}{Z(x)}exp(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i) + \sum_{i,l}\mu_ls_l(y_i,x,i)) $

$ Z(x) = \sum_y exp(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i) + \sum_{i,l}\mu_ls_l(y_i,x,i)) $

是不是很眼熟?其實就是把概率無向圖中的公式整合了一下嘛!λμ都是可學習的引數,特徵函式也和我們前面定義的一樣。其實,MEMM最大熵的計算公式也和這個結果非常相似,因為資訊熵的定義和設計本身就與這裡的勢函式有一些相似之處。但是它與CRF不同的地方主要在於,歸一化因子的計算不同。MEMM計算的歸一化因子是各個節點上歸一化因子連乘得到(個人觀察,不一定正確);CRF直接計算全域性的歸一化因子,因此全域性性更強。

看到這裡,是不是大概明白CRF的公式來源於哪裡了?

為了表達方便,一般會對公式進行簡化如下:

$ P(y|x) = \frac{1}{Z(x)}exp(\sum_{k}\omega_kf_k(y,x)) $

$ Z(x) = \sum_Y exp(\sum_{k}\omega_kf_k(y,x)) $

ω來代替表示兩個引數,用 f() 來代替表示兩個特徵函式。用了這個公式之後,其實我們能發現CRF的一些工作原理。滿足特徵函式數量越多,相應的條件概率值就會越大(不將ω考慮進來,將ω考慮進來的話應該加一個前提:在我們希望學習的特徵情況下。)

至此,就可以通過一些演算法(梯度下降、L-BFGS等等)進行學習,得到引數了。

七、總結

個人認為,CRF最核心的點莫過於引入全域性性。上面的例子講的是Linear-CRF的情況,實際上,CRF可以複雜得多,這一切都由你的特徵函式來確定。CRF的這種設計方式使得它能挖掘出更多的標籤之間的約束關係和資訊,但是缺點也比較明顯,就是訓練速度會比較慢。 最後,感謝俊毅哥還有KNLP組中其他的小夥伴們!!