使用 CRF 做中文分詞

概要

簡述 CRF
問題描述（中文分詞任務）
建構特征函數
CRF 學習算法（改進的疊代尺度法）
CRF 預測算法（維特比算法）

注：以上實作隻針對中文分詞任務。

1. 簡述 CRF

注，以下内容需要一定的學習成本，如有不适請跳至下一節（實戰中學習）。但，建議先大概學一下理論！

學習 CRF 的路線：

大概了解 機率圖模型 （将機率用圖的方式表示出來，節點表事件，邊代表事件間的聯系，這樣便于計算聯合機率）；
- 機率有向圖模型 --> 貝葉斯網絡
- 機率無向圖模型 --> 馬爾科夫随機場
  - 機率無向圖模型的因子分解（考慮如何表示聯合機率），不求證明但求了解
- 資料
  - 從零學習Belief Propagation算法1
  - 從零學習Belief Propagation算法2
大概學習 邏輯斯蒂回歸 & 最大熵模型
- 邏輯斯蒂回歸 非常簡單，它能讓我們了解什麼是對數線性模型(CRF也是哦)
- 最大熵模型
  - 本質，模型的學習過程就是求解最大熵模型的過程
  - 也就是，在滿足所有限制條件下，模型最後學到的是熵最大的，最公平的
  - 最後，學習使用改進的疊代尺度法優化ME（後面 CRF 的學習也使用這個方法）
- 資料
  - 《統計學習方法》第六章
了解 HMM & MEMM
- 從三個點學習 HMM （其實 CRF MEM 類似）–> 學習過程中一定要牢記這三點
  - 機率問題（數學問題）
  - 學習問題（學習模型）
  - 預測問題（利用模型）–> 維特比算法
- HMM 的兩個假設
  - 馬爾科夫性假設
  - 觀測獨立性假設：任意時刻的觀測隻依賴該時刻的狀态，與其他觀測以及狀态無關（☆，注意與 CRF MEMM 的不同）
- MEMM 的問題 --> 标注偏執（CRF，解決了此問題）
- 資料
  - 《統計學習方法》第十章
  - 【中文分詞】最大熵馬爾可夫模型MEMM
再回看 機率圖模型
- 重點回顧 馬爾科夫随機場
- 資料
  - 從零學習Belief Propagation算法2
最後便可很輕松地學習 CRF （下面 CRF ，特指線性鍊CRF）
- CRF 通俗的說，就是條件機率分布構成一個馬爾科夫随機場；
- CRF 參數化形式，由它的定義結合機率無向圖的因子分解可得；
  - 可能會發現其與 ME 的形式，有幾分相似，但它們的思想不一樣（CRF 做序列标注，ME 做分類）；
- 接下來從三個點學習 CRF
  - 機率問題（重點關注求期望，在學習算法要用到）
  - 學習問題（已學，改進的疊代尺度法）
  - 解碼問題（已學，維特比算法）
- 資料
  - 《統計學習方法》第十一章
  - 【中文分詞】條件随機場CRF

學習過程中可能對一些符合表示産生歧義，後面的中文分詞應用會有解釋。

學完後，可能還有點迷糊，不要緊，通過下面做中文分詞的應用便能完全懂了！

2. 問題描述

我們的目标是：中文分詞！OK，接下來分析此任務。

白	B           // 第一列，等待分詞的輸入序列；第二列，标記序列（即分詞結果）
菜	E
清	B           // B，表示詞的開始
炖	E           // M，表示詞的中間
白	B           // E，表示詞的結束
蘿	M           // S, 表示單字成詞
蔔	E
是	S
什	B
麼	E
味	B
道	E
？	S

這裡，把中文分詞視為序列标注問題。即，給每個字打上标簽，由這些标簽描述了分詞結果。上面是“白菜清炖白蘿蔔是什麼味道？”的分詞結果。從注釋中可以看到，一共有 4 個标簽。

通常，我們稱等待分詞的語句輸入序列（或稱為觀測序列）；而稱分詞結果為輸出序列（或稱為标記序列、狀态序列）。是以，我們的目标（中文分詞）可以描述為：在給定觀測序列 X X X 下，找到機率最大的标記序列 Y Y Y。

怎麼解決呢？CRF的思想是：首先，假設條件分布 P ( Y ∣ X ) P(Y|X) P(Y∣X) 可構成馬爾科夫随機場（即每個狀态隻受相鄰狀态或輸入序列的影響）；然後，我們通過訓練（統計）可以确定此分布；最後，序列标注問題（如中文分詞）是在給定條件随機場 P ( Y ∣ X ) P(Y|X) P(Y∣X) 和輸入序列 X X X 求條件機率最大的标記序列 Y ∗ Y^{*} Y∗。可以看到，最後變為一個動态規劃問題（DP）。

在我們繼續進行下去之前，需要線性鍊CRF的參數化形式（想要了解如何得到的該形式，請參考機率無向圖的因子分解）

P ( Y ∣ X ) = 1 Z ( X ) e x p ( ∑ i , k λ k t k ( y i − 1 , y i , X , i ) + ∑ i , l μ l s l ( y i , x , i ) ) 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)) P(Y∣X)=Z(X)1exp(i,k∑λktk(yi−1,yi,X,i)+i,l∑μlsl(yi,x,i))

其中， t k t_k tk s l s_l sl 分别為轉移特征、狀态特征，而 λ k \lambda_k λk μ l \mu_l μl 為它們對應的權重（學習問題就是去學習這些權重）。而 Z ( X ) Z(X) Z(X) 是規範化因子，求和是在所有可能的輸出序列上進行（如何了解這句話，其實就是周遊 Y Y Y 的全排列，比如這裡一共有 4 句子長度 4^{句子長度} 4句子長度個可能）

Z ( X ) = ∑ Y e x p ( ∑ i , k λ k t k ( y i − 1 , y i , X , i ) + ∑ i , l μ l s l ( y i , x , i ) ) Z(X) = \sum_Yexp(\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)=Y∑exp(i,k∑λktk(yi−1,yi,X,i)+i,l∑μlsl(yi,x,i))

可以看到， Z ( X ) Z(X) Z(X) 起到的是全局歸一化，而在 MEMM 中隻使用了局部歸一化，是以出現局部偏執問題。

在下一節，我們将關注狀态特征與轉移特征。

3. 建構特征函數

線上性鍊CRF參數化形式中，未知的隻有特征與對應參數（或稱為權重），而參數是在學習問題中關注的，是以隻剩下特征了。怎樣定義或建構特征呢？

我們的目标是：中文分詞！是以，針對中文分詞任務我們有獨特的特征構造方式（借鑒于

CRF++

）。首先，明确特征函數的含義：它描述是否滿足指定特征，滿足傳回1否則傳回0；再來看特征模闆

# Unigram      --> 構造狀态特征的模闆
U00:%x[-2,0]
U01:%x[-1,0]
U02:%x[0,0]
U03:%x[1,0]
U04:%x[2,0]
U05:%x[-2,0]/%x[-1,0]/%x[0,0]
U06:%x[-1,0]/%x[0,0]/%x[1,0]
U07:%x[0,0]/%x[1,0]/%x[2,0]
U08:%x[-1,0]/%x[0,0]
U09:%x[0,0]/%x[1,0]

# Bigram    --> 構造轉移特征的模闆
B

我們的特征有兩種形式：狀态特征 & 轉移特征。下面結合特征模闆分别介紹這兩種特征。

狀态特征函數 s l ( y i , X , i ) ) s_l(y_i,X,i)) sl(yi,X,i)) ，它的輸入為目前狀态、整個觀測序列以及目前位置。上面特征模闆中

U01～U09

用于生成狀态特征。以

U00:%x[-2,0]

為例，-2 代表取觀測序列中相對目前位置的倒數第2個，0 在此處無意義。是以，用

U00～U09

做模闆在我愛我的祖國。第3個位置下可建構的狀态特征為

我
愛
我  <-- 目前處于此位置
的
祖
國
# 下面為生成的狀态特征
U00:我
U01:愛
U02:我
U03:的
U04:祖
U05:我/愛/我
U06:愛/我/的
U07:我/的/祖
U08:愛/我
U09:我/的
注：每行代表 4 個狀态特征，因為這裡有 4 标簽（BMES）。是以，這裡一共産生 40 個狀态特征。
注：請注意，這隻是在第 3 個位置下産生的。

轉移特征 t k ( y i − 1 , y i , X , i ) t_k(y_{i-1},y_i,X,i) tk(yi−1,yi,X,i)，它的輸入為上一狀态、目前狀态、整個觀測序列以及目前位置。上面特征模闆中，

表示生成所有的轉移特征。因而，一共可産生 16 種轉移特征（無視觀測序列）。它們為

BB  --> 表示從上一個狀态 B 轉移到目前狀态 B
BM
BE
BS
MB
MM
ME
MS
EB
EM
EE
ES
SB
SM
SE
SS

OK，了解了這兩種特征的構造過程，我們便可以通過掃描訓練集來建構大量的特征（注意，轉移特征固定為16個）。我的 25M 訓練集下，大約可以生成 560w+ 個特征函數（隻取頻率大于等于3的）。

下面看程式中如何定義特征，首先看

Feature

類

import java.io.Serializable;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @author iwant
 * @date 19-6-13 09:31
 * @desc 特征函數
 */
public class Feature implements Serializable, Cloneable {

    // 特征函數數字辨別
    private int id;
    // 特征函數辨別（含特征函數的内容） --> 比如，featureId="U00:我"
    private String featureId;           
    // 出現頻率     --> 數組大小為 4 ,從這裡可以看出一個該類對象對應 4 個狀态特征
    private AtomicInteger[] freqs = new AtomicInteger[4];

    // 權重         --> 數組大小為 4 ,從這裡可以看出一個該類對象對應 4 個狀态特征
    // 注：對應四個标記（BMES）
    private double[] weights = new double[4];

    public Feature(int id, String featureId) {
        this.id = id;
        this.featureId = featureId;
        for (int i = 0; i < weights.length; i++)
            this.freqs[i] = new AtomicInteger();
    }

    public Feature(String featureId) {
        this(-1, featureId);
    }

}

從注釋中我們可以看到，一個

Feature

對象包含 4 個狀态特征。

我們把所有的特征放在一個

Map<String,Feature>

集合中，其中 key 即

featureId

便于後續查找某一特征，而 value 自然就是對應的

Feature

對象了。

注：因這裡的轉移特征無視觀測序列，是以在用

Feature

對象描述轉移特征時，一個對象對應一個轉移特征。因而此時規定對象中的數組隻有下标 0 處有意義。

這裡就不列出掃描訓練集構造所有特征函數的代碼，具體請在源碼中

Utils.java

中查找。

有了特征函數我們便可關注參數了，也就是下一節中學習算法做的事。

4. CRF 學習算法

首先，我們需要明确學習的是什麼。線上性鍊CRF的參數化形式中原有兩個未知，一個是特征函數另一個是參數（亦稱為權重）。在上一節，我們已經構造了所有的特征函數。是以現在隻剩下它們對應的參數就可以确定模型了。自然而然，CRF 學習的目标就是更新這些參數！

至于如何更新這些參數，是這一小節的重點。前面已經提到，我們将會使用改進的疊代尺度法來優化CRF。

可能你會問為什麼這麼學習。首先要明确我們已知訓練資料集，由此可知經驗機率分布 P ~ ( X , Y ) \tilde{P}(X,Y) P~(X,Y) （統計學習的最基本假設）。現在求條件分布，便可以通過極大化訓練資料的對數似然函數來求模型參數。改進的疊代尺度法通過疊代的方法不斷優化對數似然函數改變量的下界，達到極大化對數似然函數的目的。通俗地講，為了求條件分布，數學家給我們提供了一個NB的工具 – 極大化對數似然函數，這樣就變成了優化問題。針對該優化問題呢，數學家經過對原函數不斷放縮、求導給我們推導出了許多優化算法，改進的疊代尺度法（IIS）便是其中一個，其他的還有拟牛頓法梯度下降法等等。(注：這裡不再詳述推導過程。感興趣的，可以參考《統計學習方法》第六章)

說個題外話，再來談談為什麼CRF學習算法學習的是參數。我們還可以這麼了解，由不同的參數可以定義不同的模型。所有的參數可能構成了模型空間（或稱為模型集合）。學習算法的目的就是在模型空間中找尋最能拟合訓練資料的模型。

疊代尺度法的基本思想：我們有種方法能夠使得對數似然函數每次增加一點點，是以我們可以不斷地使用（疊代）該方法慢慢的增大對數似然函數。總有那麼一個時刻，它會收斂，于是達到了極大化對數似然函數的目的。

OK，是時候看算法描述

使用 CRF 做中文分詞使用 CRF 做中文分詞

下面将結合中文分詞任務解釋上面的算法描述。

可以看到算法的輸入有：轉移特征、狀态特征以及經驗分布（就是訓練樣本）。這裡需要說明的是每次訓練選取多少個樣本（機器學習中的 batch size 概念）。在中文分詞任務中，也就是考慮每次訓練使用多少個句子。實作時，我每次訓練使用 500 個句子。
再來看其中的步驟(a)，這一步便是上述疊代尺度法的基本思想中提到的每次能夠使對數似然函數增加一點點的方法。隻要我們求解出 δ k \delta_k δk 即可。可以看到公式 (11.41) (11.44) 給出了求解方法。後面再詳訴它們。
再來看其中的步驟(3)，這顯然就是那個疊代過程。但我們實作時需要考慮如何定義收斂（即疊代介紹的條件）。比如，在驗證集上的準确率不在提高。

不難發現整個算法中最難的就是步驟(a)中的方程求解。怎麼求，公式11.41、11.44已經說明了。下面以公式11.41為例來說明。

先要明确它是針對轉移特征的，且 δ k \delta_k δk 隻針對下标為 k k k 這一轉移特征；
再來看 S S S，它是一個常數，是一個足夠大的特征總數。這裡，我們每次訓練都要選一批句子，而每個句子都有個特征總數（即該句子滿足的狀态特征與轉移特征總數），足夠大的特征總數可以為這些特征總數中最大的那個。
再來看 E p ~ [ t k ] E_{\tilde{p}}[t_k] Ep~[tk] ，表示在經驗機率分布下 P ~ ( X , Y ) \tilde{P}(X,Y) P~(X,Y)，轉移特征函數 t k t_k tk 的期望值。聽起來很高大上，其實就是統計該特征函數在目前批量句子中出現的次數；
最後有 E p [ t k ] E_{p}[t_k] Ep[tk] ，表示特征函數在經驗分布為 P ~ ( X ) \tilde{P}(X) P~(X) 下關于聯合分布 P ( X , Y ) P(X,Y) P(X,Y) 的數學期望。公式 (11.42) 說明了怎麼求。但是相當繁瑣！我們需要知道 a l p h a alpha alpha M M M β \beta β。
- 先來解釋公式11.42，最外面的求和是針對所有的句子（比如，我實作時每次訓練要用 500 個句子）；從 1～n+1 的求和是周遊一個句子（注意一個句子的長度為 n）；最裡面的求和是針對所有的“前後狀态”（在中文分詞任務中，有4中标簽，是以一共有16個前後狀态）；
- M M M （參考《統計學習方法》公式11.23）
M i ( X ) = [ e x p ( ∑ k = 1 K ( ∑ i , k λ k t k ( y i − 1 , y i , X , i ) + ∑ i , l μ l s l ( y i , x , i ) ) ) ] M_i(X)=[exp(\sum_{k=1}^K(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,X,i)+\sum_{i,l}\mu_ls_l(y_i,x,i)))] Mi(X)=[exp(k=1∑K(i,k∑λktk(yi−1,yi,X,i)+i,l∑μlsl(yi,x,i)))]
- a l p h a alpha alpha （參考《統計學習方法》公式11.28）
α i T ( X ) = α i − 1 T ( X ) M i ( X ) \alpha_i^T(X)=\alpha_{i-1}^T(X)M_i(X) αiT(X)=αi−1T(X)Mi(X)
- b e t a beta beta （參考《統計學習方法》公式11.31）
β i ( X ) = M i + 1 ( X ) β i + 1 ( X ) \beta_i(X)=M_{i+1}(X)\beta_{i+1}(X) βi(X)=Mi+1(X)βi+1(X)
- 注意，在計算它們是要注意下标！每個句子都要計算 a l p h a alpha alpha M M M β \beta β 一次。

上面隻是了解計算過程，而在具體的實作中需要優秀的設計來提高性能。比如，我們的特征有幾百萬個，每次訓練要周遊這麼多特征？顯然，這樣行不通。我們能不能率先找出該批量句子中所含有的特征？再比如，考慮這一系列的計算過程那些能用多線程？

這些設計很吃個人的經驗，建議在先弄懂算法流程後，再設計，最後動手。大家先自己想想怎麼設計，看看有沒有奇淫技巧。如果沒想到，可以看看我的代碼（篇幅有限，就不再描述我是如何實作的了）。我的肯定不是最好的，但還能湊合。

5. CRF 預測算法

最後的預測算法，用于解決解碼問題，說白了就是能夠對輸入的句子進行分詞。

現在已經有條件随機場 P ( Y ∣ X ) P(Y|X) P(Y∣X)（由上面得到的）以及輸入序列（句子），要求條件機率最大的輸出序列（标記序列） Y ∗ Y^* Y∗。最後會發現這就是一個最優路徑問題，要用到動态規劃。此處便用的是著名的維特比算法。

具體過程不打算寫了。請參考《統計學習方法》中的 206 頁。很簡單的！書中已經給出遞歸公式，實作時按照公式來即可。

6. 結果

我是在人民日報語料（2014版）語料上做的實驗。模型大約訓練了一個半小時，最後的準确率為 94.20%。還算可以。

[INFO] 開始初始化！
[INFO] 開始解析特征模闆...
[INFO] 特征模闆解析完畢！
[INFO] 開始加載模型...
[INFO] 一共加載了 5656572 個特征！
[INFO] 初始化完畢！
[INFO] 評測使用的檔案：data/save/test.data !
[INFO] 結果将會儲存在：data/save/result.data !
[INFO] 分詞已結束，正在評估準确率...
[INFO] 評測結果如下：
	wTotal: 2042582
	sTotal: 47884
	wError: 118489, 5.80%   --> 94.20%
	sError: 29377, 61.35%

代碼(Github)

使用 CRF 做中文分詞使用 CRF 做中文分詞

使用 CRF 做中文分詞

概要

1. 簡述 CRF

2. 問題描述

3. 建構特征函數

4. CRF 學習算法

5. CRF 預測算法

6. 結果

繼續閱讀

Setup Factory 點選uninstall.exe Invalid start mode : archive filename

CSDN轉載他人部落格

Ant使用ProjectTargetTaskProperties特性路徑形式datatype

Eclipse出現不自動編譯的問題解決

GCC-Inline-Assembly-HOWTOGCC-Inline-Assembly-HOWTO

Apache Lucene 5.x 內建中文分詞庫 IKAnalyzer

other|2019最新PayPal二代支付接口Smart Payment Buttons開發

轉為utf8編碼的正确姿勢

一點項目查錯經驗之談（轉載）

SVN的安裝配置

git之安裝配置篇

Jenkins shell 工作自動化腳本

android xml中include标簽的使用

Cisco Switching Black Book

c#調用非托管函數的一個方法

Java程式員的職業生涯規劃建議