2011年6月25日土曜日

間違ってるかもしれないCRFの説明



TokyoNLP で話す内容を貼っておきます。
きっと後で訂正が入るんだろうな。。

2011年6月12日日曜日

実数素性テンプレートの使える CRF

この間記事で書いた実数素性テンプレートを使える CRF を作ってみました。
google code

面倒くさかったのでだいぶコピペの目立つコードになってますが、その辺は勘弁。

  • テンプレートが文字列を扱うバイナリな値を取る場合(%x マクロを使うもの)ならば、素性関数 f_k(y_{i-1},y_i,X) は 1 or 0 を取る。
  • テンプレートが実数を扱う場合(%r や SUM, MAX, Value, etc. )ならば、素性関数 f_k(y_{i-1},y_i,X) はテンプレートに書かれた演算結果の値 or 0 を取る。
と、実数素性を使わない CRF からの変更点はそれだけです。


以下は動作確認のためだけのコード。

# include "rtcrflearn.hpp"
# include "rtcrftagger.hpp"

using namespace RtCrf;
using namespace std;

int main(int argc, char **argv)
{
Crflearn learner(*(argv+1),*(argv+2),1000000);
learner.init();

learner.learn(5,0);
learner.save("test.model");

Crftagger tagger(*(argv+1),1000000);
tagger.read("test.model");
tagger.tagging(*(argv+2));
return 0;
}


下が動かしたときの出力。

# ./test template ../data/train.txt
labels: 2
bound: 3
ufeatures: 17
bfeatures: 1
instance: 1
uparameters: 34
bparameters: 8
model parameters: 42
epoch: 0 err:0.500000(2/4)
epoch: 1 err:0.000000(0/4)
epoch: 2 err:0.000000(0/4)
epoch: 3 err:0.000000(0/4)
epoch: 4 err:0.000000(0/4)
a b c 1.0 -1.0 L_A L_A
d e f -1.0 1.0 L_B L_B
p e f -0.5 0.1 L_B L_B
g b c 0.3 -0.1 L_A L_A

実数素性を使えそうな公開データとかあればそれで試してみたいですけど、とりあえず今日の所はここまで。

Tagger クラスの出力に予測時のスコアを出すようにすれば、1段目の CRF の出力を2段目の CRF の学習素性に使うというようなスタッキングも出来るようになるかなと思う次第。
そのうち CNF とかと一緒にまとめて API を変えとこうかな。

2011年6月8日水曜日

実数素性テンプレートを作ろう。

まだ生きてます。

ここしばらくはちと研究のまねごとなどを会社でしている事もあって、あんまりブログに書ける事も無い日々です。
とりあえず対外的に問題ない範囲だと、去年の11月にACMLという会議でポスター発表をしてみました。
ポスターはアブストの提出だけだったのですが、参考文献が後で見直したら壊れていたという大失敗。

後、同じ11月にNL研でクエリの訂正手法についての発表をしてきました。
広島のお好み焼きはおいしかったです。

あと、 NetWalker を活用するべくいくつか実装したものもあるのですが、そちらはまだしばらく非公開。

とりあえず生存報告はこんな所。
最近忙しいですが何となく以前よりは楽しく過ごせている気がします。

で、久しぶりに書いた記事がこれで終わりというのもなんなので、近々 TokyoNLP で発表しようかなと思っている CRF の素性テンプレート周りの話に関連して少々追記。

素性テンプレートが使える CRF というと、CRF++ や crfsgd がありますが、基本的にこれらの素性テンプレートは文字列を素性とするタイプで、素性関数は f_k(y,x) = 1 or 0 というようにバイナリの値を取るようになっています。
これはある素性関数は特定の y と x のペアが観測された時に 1 を返して、それ以外のときは 0 を取るという意味で、素性がテキストの時は特に問題になる事はありません。
が、最近はクエリログとかを扱う機会も多くなってきた都合上、出来れば実数値も扱いたいなーと思う事がしばしばです。
例えば、クエリに含まれるトークンにタグ付けをする際には、トークンの尤度を言語モデルで求めて、それを素性として扱いたいとかがあると思うのですが、それは現状だと数値の範囲を表す様なテキストに変更して素性として扱うしかなさそうです。
ですが、この方法だとスコアの範囲ごとに素性が分かれるので、やっぱり元々の言語モデルで求めた尤度を直接素性として扱うのとは違いそうです。

なので、実数の扱える素性テンプレートを作ってみました。
http://code.google.com/p/cnf/source/browse/#hg%2Ftoys%2Frtcrf%2Fsrc
動作としては、 f_k(y,テキスト素性) = 1 or 0、 f_k(y,実数素性) = 素性の実数値 or 0 となります。

もちろん、素性テンプレートというからには観測された素性の組み合わせを扱えないと格好が悪いので、実数素性でも組み合わせ(素性どうしの各種演算等)が扱えるようにしました。

で、ついでに素性テンプレートが今まで学習器とセットで独立性が低かった点も見直してみました。

使える演算としては、
  • ( x )
  • x + x
  • x - x
  • x * x
  • x / x
  • x % x
  • -x
  • log x
  • sqrt x
  • exp x
  • max ( x,... )
  • min ( x,... )
  • sum ( x,... )
  • prod ( x,... )
  • x > x
  • x >= x
  • x < x
  • x <= x

をひとまず用意。
上の例だと x は変数に見えますが、別の演算を x の所に入れる事も出来るので、

(x_1+x_2)*x_3*max(max(...),min(...),x_4,log(x_5),...)

みたいな事も出来ます。

とりあえず実際に適当に書いてみたテンプレートの例が以下です。

# Unigram
U00:%x[-2,0]
U01:%x[-1,0]_%x[0,0]
U02:%x[-1,0]_%x[0,0]_%x[1,0]
U03:1.0-%r[0,3]
U04:%r[0,3]+%r[0,4]
U05:%r[0,3]-%r[0,4]
U06:%r[0,3]*-%r[0,4]
U07:%r[0,3]/-%r[0,4]
U08:%r[0,3]%-%r[0,4]
U09:SUM(%r[.,3])
U10:PROD(%r[.,4])
U11:MIN(%r[0,3],%r[0,4])
U12:MAX(%r[0,3],%r[0,4])
U13:MIN(%r[.,3])
U14:MAX(%r[.,4])
U15:MIN(%r[0,.])
U16:MAX(%r[0,.])
U17:MIN(MAX(%r[0,.],%r[.,3]),%r[.,4])
U18:%r[0,3]/MAX(%r[.,3])
U19:%r[0,3]/SUM(%r[.,3])
U20:MIN(%r[0,3]+%r[0,4],%r[0,3])

# Bigram
B

で、入力に使ったこれまた適当データが次。
a b c 1.0 -1.0 L_A 
d e f -1.0 1.0 L_B
p e f -0.5 0.1 L_B
g b c 0.3 -0.1 L_A

これに上のテンプレートを使って素性を展開すると、次のようになります。
U00:_B-2:1 U01:_B-1_a:1 U02:_B-1_a_d:1 U05:2 U06:1 U07:1 U09:-0.2 U10:0.01 U11:-1 U12:1 U13:-1 U14:1 U15:-1 U16:1 U17:-1 U18:1 U19:-5 B:1 
U00:_B-1:1 U01:a_d:1 U02:a_d_p:1 U03:2 U05:-2 U06:1 U07:1 U09:-0.2 U10:0.01 U11:-1 U12:1 U13:-1 U14:1 U15:-1 U16:1 U17:-1 U18:-1 U19:5 U20:-1 B:1
U00:a:1 U01:d_p:1 U02:d_p_g:1 U03:1.5 U04:-0.4 U05:-0.6 U06:0.05 U07:5 U08:-0.1 U09:-0.2 U10:0.01 U11:-0.5 U12:0.1 U13:-1 U14:1 U15:-0.5 U16:0.1 U17:-1 U18:-0.5 U19:2.5 U20:-0.5 B:1
U00:d:1 U01:p_g:1 U02:p_g__E+1:1 U03:0.7 U04:0.2 U05:0.4 U06:0.03 U07:3 U08:0.1 U09:-0.2 U10:0.01 U11:-0.1 U12:0.3 U13:-1 U14:1 U15:-0.1 U16:0.3 U17:-1 U18:0.3 U19:-1.5 U20:0.2 B:1

実装 は c++ で、 bison、 flex を使って作っています。
tsubosaka さんからはこのくらいの仕様なら bison、 flex なんて使わないでいいんじゃないの?というありがたいお言葉を頂いたのですが、残念ながら僕は 1 からパーザを書いた経験が無く、正直自信が無いためこれらを使っています。
ちなみに flex のバージョンが 2.5.35 、bison が 2.3 の環境で作っています。
bison は 2.1 以降なら c++ に対応しているので問題ないと思いますが、 flex の方は 2.5.35 だと yyFlexLexer::yywrap の実装がデフォルトで無いため、yywrap の実装を適当にソースコードの中に書いています。
これが 2.5.4 以降だと標準で実装されているので、多分コンパイル時に多重定義で怒られるんじゃないかなぁという気がします。

今週はきっとこれ使った CRF 実装してます。