bigram feature について。

twitter で @takeda25 さんが指摘されていたのですが, CRF で f(y_{i-1},y_{i},x_{i}) という観測素性とラベル bigram の組みまで考慮した素性関数があまり使われないのは, 素性数が増えるからというよりは計算に時間が掛かるためだろうか? という事を私なりに考えてみました.

CRF の1事例に対するパラメータ推定に掛かるオーダーはラベル数L, 系列長Tの時に, O(L^2T) です.
forward-backward でラティス中の位置 i, ラベル j のノードの alpha を計算する際には以下の logsumexp の計算を行います.

for (k = 0; k < L; ++k)
   alpha_{i,j} = logsumexp(alpha_{i,j}, alpha_{i-1,k}+cost)

この計算を全ての i, j について行います.

この時足し込んでいる cost が 観測素性+遷移素性のコストで, 観測素性 x に対してラベル bigram を考慮する場合, 遷移素性のコスト計算をする時に一緒に足す事になるため, 単純に観測された bigram 素性の数だけ加算回数が増えます.
ですが, logsumexp の呼び出し回数自体は変わりません. (最初この部分も定数倍になると勘違いしていました)

cost の加算部分だけが定数倍される程度なので, 計算時間にはそんなに影響が出ないのではないかと考えたのですが, 実は CNF だと結構影響が出ました...

CNF では cost の計算時に, logstic 関数による非線形な重み付けが必要になるため, exp の計算が入ります. exp の計算が素性数だけ増えるため, 試してみたら結構遅くなりました..

試してみたのは CoNLL2000 の学習データで, 使用したテンプレートは以下の通りです. 見事に全部 bigram テンプレートです.

# Bigram
B00:%x[-2,0,0]
B01:%x[-1,0,0]
B02:%x[0,0,0]
B03:%x[1,0,0]
B04:%x[2,0,0]
B05:%x[-1,0,0]/%x[0,0,0]
B06:%x[0,0,0]/%x[1,0,0]

B10:%x[-2,1,0]
B11:%x[-1,1,0]
B12:%x[0,1,0]
B13:%x[1,1,0]
B14:%x[2,1,0]
B15:%x[-2,1,0]/%x[-1,1,0]
B16:%x[-1,1,0]/%x[0,1,0]
B17:%x[0,1,0]/%x[1,1,0]
B18:%x[1,1,0]/%x[2,1,0]

B20:%x[-2,1,0]/%x[-1,1,0]/%x[0,1,0]
B21:%x[-1,1,0]/%x[0,1,0]/%x[1,1,0]
B22:%x[0,1,0]/%x[1,1,0]/%x[2,1,0]

B

これで学習を行ってみたところ, 次のようになりました.

* iter = 1

time ./src/learner --learner=cnf -t src/template -c data/conll2000/train.txt -s bigramtest.save --l2 --pool=1000000 --block=24 --lambda=2 --iter=1  
labels: 22
features: 338552
bound: 3
ufeatures: 0
bfeatures: 76329
instance: 8936
gate functions: 20
parameters of gate functions: 31
uparameters: 0
bparameters: 40301712
model parameters: 40301743
epoch:  0 err:0.069070(14624/211727)
./src/learner --learner=cnf -t src/template -c data/conll2000/train.txt -s     1323.90s user 41.84s system 96% cpu 23:40.72 total

ちなみに, テンプレートを元々の

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

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

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

# Bigram
B

にすると, iter = 1 の学習時間は以下の通り.

time ./src/learner --learner=cnf -t src/template -c data/conll2000/train.txt -s bigramtest.save --l2 --pool=1000000 --block=24 --lambda=2 --iter=1
labels: 22
features: 338552
bound: 3
ufeatures: 76328
bfeatures: 1
instance: 8936
gate functions: 20
parameters of gate functions: 31
uparameters: 1679216
bparameters: 528
model parameters: 1679775
epoch:  0 err:0.057314(12135/211727)
./src/learner --learner=cnf -t src/template -c data/conll2000/train.txt -s     67.23s user 5.61s system 92% cpu 1:18.67 total

だいたい bigram テンプレート数倍だけ遅くなりました..
exp の計算が bigram テンプレート数倍必要になるので, そこが影響したようです.

CRF の場合は logistic 関数の計算無しで加算のみになるため, ここまでの影響は出ないと考えられるので, bigram 素性を使ったとしてもそこまで遅くなるという事は無いのではないかと思います.

ちなみにオール bigram テンプレートを使った時の学習に必要なメモリは約 450 MB でした.

bigram 素性を使うとタグ付け時にトークンの文脈依存性を上手く学習できたりしそうですし, 意味の無い素性ではないと思うのですが, 何であまり使われていないんでしょうね.

ちなみに, CRFSuite では高速化の為にいろいろな工夫がされているそうで, その工夫の中にラベル bigram と観測素性の組み合わせは考慮しないという前提に基づいた手法があるのか, bigram 素性を扱うと高速化手法のどれかが使えなくなってしまうっぽい?
ソースコードを落としてきてちら見してみたのですが, 人のコードを読むのが苦手な私ではすぐには問題箇所が分からず, 「おー! コード超キレイ!」とそんな感想しか言えませんでした...

時間のある時にじっくり読んで勉強させてもらいます!