HOWTO use CRF++

使用方法

Training 和 Test 的檔案格式

Training 和 test 檔都必須以特定的格式來編碼好讓 CRF++ 能正常運作。一般來說，training 和 test 檔必須由多個 token 所組成。此外，一個 token 是由多個（但是是固定數量的）的 column 所組成。依據不同的 task 可能會有不同的 token 定義，然而，在大多數的情形下，它們相當於 word。每一個 token 必須被宣告於一列中，每一個 column 藉由空白字元（或是 tab 字元）加以區隔。一連串的 token 構成一個 sentence。要辨識每個 sentence 之間的界線，是利用一個空白列加以區分。

我們可以加入任意數目的 cloumn，但是加入的 column 數目在所有的 token 中必須一樣。此外，有一些 semantics 會存在於 column 之間，比如，第一個 column 代表‘word’，第二個 column 是‘POS tag’，第三個是‘sub-category of POS’，依此類推。

最後一個 column 代表的是一個 true answer tag，它會被 CRF 用來 train。

下面是一個範例：

He        PRP  B-NP
reckons   VBZ  B-VP
the       DT   B-NP
current   JJ   I-NP
account   NN   I-NP
deficit   NN   I-NP
will      MD   B-VP
narrow    VB   I-VP
to        TO   B-PP
only      RB   B-NP
#         #    I-NP
1.8       CD   I-NP
billion   CD   I-NP
in        IN   B-PP
September NNP  B-NP
.         .    O

He        PRP  B-NP
reckons   VBZ  B-VP
..

每一個 token 有三個 column：

• 字本身（比如 reckons）；
• 該字的詞性（比如 VBZ）；
• Chunk（answer）tag；以 IOB2 格式來表示；

下面的資料是無效的，因為第二個和第三個的 column 為 2（它們沒有 POS column）。column 的數目必須是固定的。

He        PRP  B-NP
reckons   B-VP
the       B-NP
current   JJ   I-NP
account   NN   I-NP
..

準備 feature template

因為 CRF++ 設計成為一個泛用的工具，使用者必須事先指定 feature template。該檔描述了在 training 和 testing 時會用到的 feature，

Template basic 和 macro

在 template 檔中的每一列，代表的是一個 template。在每一個 template 中，%x[row,col] 這種特殊的 macro 會被用來指定在輸入資料中的某一個 token。row 指明了相對於目前 token 的位置，而 col 則指定了 column 的絕對位置。

下面是一個例子：

輸入的資料：

He        PRP  B-NP
reckons   VBZ  B-VP
the       DT   B-NP << 目前的 token
current   JJ   I-NP
account   NN   I-NP

template	expanded feature
%x[0,0]	the
%x[0,1]	DT
%x[-1,0]	rokens
%x[-2,1]	PRP
%x[0,0]/%x[0,1]	the/DT
ABC%x[0,0]123	ABCthe123

Template 類型

要注意的是，template 有兩種類型，使用者必須指定所有的 template 的類型。template 的第一個字元說明了該 template 是哪種類行。

Unigram template：第一個字元是‘U’

用來描述 unigram feature 的 template。當你指定一個 template：“U01:%x[0,1]”，CRF++ 自動產生一組 feature function（func1 ... funcN）：

func1 = if (output = B-NP and feature="U01:DT") return 1 else return 0
func2 = if (output = I-NP and feature="U01:DT") return 1 else return 0
func3 = if (output = O and feature="U01:DT") return 1  else return 0
....
funcXX = if (output = B-NP and feature="U01:NN") return 1  else return 0
funcXY = if (output = O and feature="U01:NN") return 1  else return 0
...

template 產生的 feature function 數目是 (L * N)，其中 L 是輸出的 class 數目，N 是從指定的 template 中 expand 的 unique string 。

Bigram template：第一個字元為‘B’

用來描述 bigram feature 的 template。藉由這個 template，最自動產生目前的輸出 token 和 前一個輸出 token（bigram）的結合。這種類型的 template 會產生總共 (L * L * N) 不同的 feature，L 是輸出的 class 數目，N 是被這個 template 產生的 unique feature 總數。當 class 的數量越大，這種 template 會產生大量的不同 feature，因此可能造成在 training 和 testing 上的效能低落。

用來分辨相對位置的 identifier

當使用者要去辨識 token 的相對位置時，必須在 template 中放置一個 identifier。

下面的例子中，“%x[-2,1]”和“%x[1,1]” macro 會被替換成“DT”。但是它們代表不同的“DT”：

The       DT  B-NP
pen       NN  I-NP
is        VB  B-VP << CURRENT TOKEN
a         DT  B-NP

為了要區隔它們，我們會放置一個 unique identifier（U01: 或 U02:）在 template 中：

U01:%x[-2,1]
U02:%x[1,1]

在上面的例子中，這兩個 template 會被視為不同，因為它們會被 expand 成為不同的 feature，“U01:DT”和“U02:DT”。我們可以使用任何一種 identifier，但是最好使用數字來管理它們的命名，因為它們可以簡單的對應到 feature number。

假如你想使用“bag-of-words”feature，則不需要使用 identifier。

例子

下面是一個用於 CoNLL 2000 shared task 和 Base-NP chunking task 的 template 範例。只用到一個 bigram template（‘B’）。這表示只有前一個輸出 token 和目前的 token 的組合，才拿來當作 bigram feature。空白列或是以 # 起頭的列會被視為註解：

# Unigram
U00:%x[-2,0]
U01:%x[-1,0]
U02:%x[0,0]
U03:%x[1,0]
U04:%x[2,0]
U05:%x[-1,0]/%x[0,0]
U06:%x[0,0]/%x[1,0]

U10:%x[-2,1]
U11:%x[-1,1]
U12:%x[0,1]q
U13:%x[1,1]
U14:%x[2,1]
U15:%x[-2,1]/%x[-1,1]
U16:%x[-1,1]/%x[0,1]
U17:%x[0,1]/%x[1,1]
U18:%x[1,1]/%x[2,1]

U20:%x[-2,1]/%x[-1,1]/%x[0,1]
U21:%x[-1,1]/%x[0,1]/%x[1,1]
U22:%x[0,1]/%x[1,1]/%x[2,1]

# Bigram
B

若是寫成：

B01:%x[0,0]

則實際的 feature 數為：

（x[0,0] 的字元總數）×pre_label×cur_label

若是只寫：

B

則實際的 feature 數只有：

pre_label×cur_label

Training（encoding）

在命令列中：

crf_learn template_file train_file model_file

template_file 和 train_file 必須在事先準備好。crf_learn 會產生在 model_file 參數指定的檔案中產生 trained model。

一般來說，crf_learn 會在標準輸出中產生下列的資訊。另外，crf_learn 也會顯示每一次 LBFGS 程序的額外資訊。

C:> crf_learn template_file train_file model_file

CRF++: Yet Another CRF Tool Kit
Copyright (C) 2005 Taku Kudo, All rights reserved.

reading training data:
Done! 0.32 s

Number of sentences:          77
Number of features:           32856
Freq:                         1
eta:                          0.0001
C(sigma^2):                   10

iter=0 terr=0.7494725738 serr=1 obj=2082.968899 diff=1
iter=1 terr=0.1671940928 serr=0.8831168831 obj=1406.329356 diff=0.3248438053
iter=2 terr=0.1503164557 serr=0.8831168831 obj=626.9159973 diff=0.5542182244

• iter：處理多少 iteration
• terr：錯誤率（針對 tag）（錯誤的 tag 數/tag 總數）
• serr：針對 sentence 的錯誤率（錯誤的 sentence 數/sentence 總數）
• obj：目前的 object 值。當該值趨近於定點（fixed point），CRF++ 會停止該 iteration。
• diff：相對於前一個 object 值的差異。

有兩個主要的參數用來控制 training：

• -c float: 藉由這個選項，我們可以改變 CRF 的 hyper-parameter。越大的 C 值，CRF 越傾向去 overfit 指定的 training corpus。該參數控制了 overfitting 和 underfitting 之間的平衡。這個參數對產生的結果有很大的影響力。
• -f NUM： 這個參數設定 feature 的 cut-off threshold。CRF++ 在指定的 training 資料中使用這個參數不小於 NUM 次。預設值為 1。當套用 CRF++ 到大量的資料時，unique feature 的資料量將會很大，在這種情形下，這個參數很有用。

自 0.42 版起，CRF++ 開始支援平行處理！對於有兩個 CPU 以上的系統而言，這可以增進 training 的速度！要啟用該選項，請在命令列中加上下列參數：

• -p NUM：若是擁有多個 CPU，則藉由使用多執行緒處理，可以增進 training 的速度。NUM 是執行緒的數目。

下面是使用這兩個參數的例子：

% crf_learn -f 3 -c 1.5 template_file train_file model_file

Testing（decoding）

在命令列下：

crf_test -m model_file test_files ...

model_file 是被 crf_learn 產生的 model 檔。在測試時，不需要指定 template 檔，因為 model 檔有跟 template 一樣的資訊。test_file 是我們希望被指定連續 tag 的 test 資料。該檔的格式跟 training 檔的格式一樣。

下面是 crf_test 的輸出：

C:\ crf_test -m model test.data
Rockwell        NNP     B       B
International   NNP     I       I
Corp.   NNP     I       I
's      POS     B       B
Tulsa   NNP     I       I
unit    NN      I       I
..

最後一個 column 是經由 CRF++ 判斷的 tag。假如第三個 column 是正確答案的 tag，我們可以藉由比較第三和第四個 colume 的差異得到正確率。

verbose level

-v 選項設定 verbose level。預設值為 0。藉由增加 level，我們可以從 CRF++ 中取得額外的資訊。

level 1

可以取得每一個 tag 的邊緣可能性（marginal probability）（每個輸出的 tag 的信任度衡量），和輸出的可能性（整個輸出的可靠度衡量）。

C:\ crf_test -v1 -m model test.data| head
# 0.478113
Rockwell        NNP     B       B/0.992465
International   NNP     I       I/0.979089
Corp.   NNP     I       I/0.954883
's      POS     B       B/0.986396
Tulsa   NNP     I       I/0.991966
...

第一列“# 0.478113”顯示輸出的可靠度，另外每一個輸出的 tag 都有一個可靠度衡量輸出，像是“B/0.992465”。

level 2

顯示所有其它的可能性的邊緣可能性。

C:\ crf_test -v2 -m model test.data
# 0.478113
Rockwell        NNP     B       B/0.992465      B/0.992465      I/0.00144946    O/0.00608594
International   NNP     I       I/0.979089      B/0.0105273     I/0.979089      O/0.0103833
Corp.   NNP     I       I/0.954883      B/0.00477976    I/0.954883      O/0.040337
's      POS     B       B/0.986396      B/0.986396      I/0.00655976    O/0.00704426
Tulsa   NNP     I       I/0.991966      B/0.00787494    I/0.991966      O/0.00015949
unit    NN      I       I/0.996169      B/0.00283111    I/0.996169      O/0.000999975
..

N-best 輸出

藉由 -n 選項，使用者可以取得 N-best result。藉著啟用 n-best 輸出模式，CRF++ 首先會加入一個額外的列，該列會近似“# N prob”，其中 N 代表該輸出的 rank，其值是從 0 開始算；prob 表示該輸出的 conditional probability。

要注意的是，假如 CRF++ 無法找到任何候選時，將不會列舉出 N-best 結果。一個可能遇到這種情況的是將 CRF++ 應用於一個短的 sentence 時。

下面是一個 N-best 結果的例子：

C:\ crf_test -n 20 -m model test.data
# 0 0.478113
Rockwell        NNP     B       B
International   NNP     I       I
Corp.   NNP     I       I
's      POS     B       B
...

# 1 0.194335
Rockwell        NNP     B       B
International   NNP     I       I

CRF++ 0.3 跟 0.42 的比較

Comparison	CRF++ 0.3	CRF++ 0.42 (parallel) with -p=2
Server	iasl-64server1 (140.109.19.203) Windows 2003 Enterprise x64 Edition R2 10 G RAM
features	14791014	14791014
Thread	Default (1)	2
iteraction	155	159
reading training data times	164.02 s	135.82 s
Memory usage	2.82 G 2.85 G	3.04 G 3.21 G
CPU usage	1 CPU	2 CPU with 50-100% usage
Training time	1838.89 s	1313.00 s
Testing result (uncertainty)	F MEASURE: 0.952 TOTAL NCHANGE: 6887	F MEASURE: 0.952 TOTAL NCHANGE: 6881