CRF++の自分用メモetc - yasuhisa's blog

論文読んだりしているけど、実際にCRFを動かしたことがなかったり...ということで動かしてみる。動かすためにいくつか理解しないといけないことがあるので自分用メモ。

CRF++: Yet Another CRF toolkit

素性テンプレート

Unigram

まず簡単そうなところから。学習用の入力データがこんな感じになってるとして、3行目を今中心に見ているとしよう。

Input: Data
He        PRP  B-NP
reckons   VBZ  B-VP
the       DT   B-NP << CURRENT 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,1]	123ABCDT123

論文とかで書かれている形と対応させたほうが分かりやすい気がするので、対応させることを考えてみる。 $f_v(X, y_t)$ は例えば

|%x[0,0]|the|

だと $X_t$ が"the"かつ $Y_t$ が"B-NP"ならば1という素性に展開されるということを表わしている。ここで注意したほうがいいこととしては、 $f_v(X_t, y_t)$ ではなく $f_v(X, y_t)$ であるということだ。(HMMや)MEMMでは $f_v(X_t, y_t)$ となっていたが、これではlabel biasなどの問題が起こってしまうので、CRFでは $f_v(X, y_t)$ というものを考えている。これによって、Xのほうは見ているところに限定されず

|%x[-1,0]|rokens|

のように一個前を見ることもできるし、一個に限らず3個前とか10個後とか見ることもできる。ただ、遠くになると影響が小さくなるし、なんでもかんでも入れすぎると素性の数が無闇に増えてしまうので、前後二つとかが一般的なようだ。そして、Xのほうは自由に前後を見れるだけではなく、2個ペアで見ることもできる。つまり

U05:%x[-1,0]/%x[0,0]
U06:%x[0,0]/%x[1,0]

というような書き方をすることによって、Xのほうのバイグラムを考えることができる(もちろんこっちも $Y_t$ のほうも展開されることに注意)。別に単語自身のバイグラムだけではなく、品詞のほうについて考えることもできて、かつトライグラムのようなこともできる。次のような例はまさにそれだ。

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

This is a template to describe bigram features. With this template, a combination of the current output token and previous output token (bigram) is automatically generated. Note that this type of template generates a total of (L * L * N) distinct features, where L is the number of output classes and N is the number of unique features generated by the templates. When the number of classes is large, this type of templates would produce a tons of distinct features that would cause inefficiency both in training/testing.
http://crfpp.sourceforge.net/

とあって、UnigramだけだとN個の素性だけだが、Bigramになるとoutputのほうのbigramを見るので、 $L^2$ 倍素性関数が増えてるということになる。この場合、X(の部分集合)がなんとかというのもあるのだが、「 $y_{t-1} = A$ かつ $y_t = B$ 」のようなことを考えるので、ラベルの二乗に比例した数の素性関数ができる、ということである。"Here, unigram and bigram features mean uni/bigrams of output tags."と書いてあって、Bigramをかを見るのはword-levelのBigramではなく、output tagsに関してのBigramである。Bigramを考えると素性の数は結構増えてくるので、注意が必要。こういうこともあって、CRFとかMEMMでは素性マイニングと呼ばれる泥くさい作業が必要不可欠?