semi-crf は入力系列に対する最適なセグメンテーションを学習する学習器です。
crf が P(Y|X, W) を求めていたのに対して、semi-crf では P(S|X, W) を推定します。
文章で書くと、2つの違いは
* crf では入力系列 X に対して生成されうるすべてのラベル系列 Y' に対して、正解系列とそれ以外の系列を弁別するよう学習する
* semi-crf では入力系列 X に対して生成されうるすべてのセグメンテーション結果 S' に対して、正解のセグメンテーションとそれ以外のセグメンテーションを弁別するよう学習する
ということになります。
semi-crf では入力系列が与えられた際に、t_j , ... , u_j までを1つのセグメント s_j として、1つのラベルを割り当てます。
この時、t_j 、 u_j は常に以下を満たす必要があります。
1 <= t_j <= u_j <= |S| , t_{j+1} = u_j + 1
これは、セグメントの終了位置と次のセグメントの開始位置は一致するよということです。
で、crf で使われていた素性関数 f の代わりに segment feature function g ( g^k(y_j,y_{j-1},X,t_j,u_j) )を使います。
といっても、あまり大きく変わっているという事は無くて、crf の素性関数がトークン x_i とラベル y_i のペアに対して 1 or 0 を返していたのが、セグメント s_i とラベル y_i のペアに変わった程度です。
大きな違いは以上なのですが、パラメータ推定をする際のラティスの形が違います。
crf ではラティスはきれいな格子でしたが、semi-crf では各位置 i について、i で始まるセグメントと i で終了するセグメントのみ接続を許すため、結構複雑な形をしています。
ただ、これは形態素解析の物と同じなので 自然言語処理-基礎と応用- の1章、形態素解析の 1.1.5 節あたりを読むと分かりやすいと思います。
パラメータ推定は crf と同じ方法が使えます。
とりあえずここまで理解したところで、cnf で作ってみよう！ と考えて作り始めたのですが、いざ作ってみて失敗に気づきました。
semi-crf ではセグメント単位で同じラベルをふるため、ラベル付けは IOB とかじゃ無く、トークン列に対して AAA、BBB のようにつければ良いやと思っていたのですが、いざ動かす所で、正解の与え方ではまりました。
というのも、AA, AA, AA というラベル列を正解コーパスでつけたつもりでも、AAA, AAA、AAAAAA のどれとも区別が出来なくなってました。。
それで、方向を修正し、結局ラベル付けは IOB タグに限定する事にして（cnf ではそんな事はないのですが...セグメントの開始位置を区別しつつ、cnf と同じフォーマットのコーパスを入力に取れるようにする方法が他に思いつきませんでした。）、せっかく IOB を使うのだから、従来使えていた cnf と同じ素性も使えるようにしてみました。
IOB タグを使い、cnf で使っていたトークン素性を使えるようにするという事は、あるトークン x がセグメントの開始 B になりやすいだとか、また逆に B にはなりにくいという様な情報を学習できます。
さらに、 cnf では素性テンプレートを使い、カレントの位置 i の n 個前のトークンが何であったか等も素性として扱えるため、セグメントの外にあるトークンの情報も扱えるという利点があります。
まさにこれと同じ事をやっているっぽい論文
A Hybrid Markov/Semi-Markov Conditional Random Field for Sequence Segmentation
があったので、名前をお借りして a hybrid markov/semi-markov cnf と名付けてみました。
上の論文自体はまだちゃんと読んで理解したわけではないので、自信を持って同じとも違うとも言えないのですが、ちらっと読んだところ、私と同じくセグメント素性にトークン素性を追加したのではなく、セグメント素性をトークン素性の和で表しているように見えます。
そうするとコストの計算時に、トークン素性のコストを予め計算しておいて、各セグメントで共通する部分についてはキャッシュを使うという事が出来るようになります。
ちゃんと読んでからでないと断言はできませんが、あってたらそこが私の作った学習器との違いになりそうです。
とりあえず、コードは以前 cnf をアップした所にそのまま追加しました。
http://code.google.com/p/cnf/
semi* が追加部分です。
素性テンプレートは以下のようになっています。
# Unigram Segment
S:%s[15,0]
# Bigram Segment
T
# Unigram
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
トークン素性については以前と変わりありません。
# Unigram Segment
S:%s[15,0]
# Bigram Segment
T
の部分が追加したテンプレートの仕様で、
S:%s[ length , gate function に与える重みの初期値 ]
が unigram segment のテンプレート、
T:%s[ length , gate function に与える重みの初期値 ]
が bigram segment のテンプレートになります。
length は考慮するセグメントの最大長です。
S はセグメントの S ですが、 T は良い頭文字が思いつかなかったので、とりあえず T にしました。
トークン素性の bigram の B 同様、セグメントのラベル遷移だけを素性にする場合は T だけ書いておけば OK です。
ソースを落としてきたら、
# make
# ./src/semicnflearn src/semitemplate data/conll2000/train.txt semicnf.save
# ./src/semicnftagger src/semitemplate semicnf.save data/conll2000/test.txt
みたいにして使います。
コーパスは従来の系列ラベリングで使えた物は大抵使えるんじゃないかと思いますが、セグメンテーションに適した手法なのでどうせならちゃんとしたタスクのコーパスで評価したいところですね。
調べてみた所、公開されている semi-crf の実装もあまり無いようですし、素性テンプレートの使える semi-markov cnf はそこそこ貴重なのではないかと自分で思ってみたりしています。
今回から、学習器の学習率のスケジューリングとL1 正則化は
Stochastic Gradient Descent Training for L1-regularized Log-linear Models with Cumulative Penalty
の手法に変更しました。
@unnonouno さんのブログ
http://unnonouno.blogspot.com/2010/02/l1-sgd.html
で紹介されていた手法で、説明が秀逸ですw
[2010.7.21 追記]
template の仕様を変更しました。
以前の仕様では、unigram segment と bigram segment で各1つずつしかテンプレートを記述できなかったのですが、複数のテンプレートを記述できるようにしました。
それに伴って、
S:%s[ length , gate function に与える重みの初期値 ]
から、
S:%s[ length, col, 重みの初期値]
と、col を指定できるようにテンプレートのマクロも変更しています。
おまけで、新しい template の例を以下に。
# Unigram Segment
S01:%s[15,0,0]
S02:%s[15,1,0]
# Bigram Segment
T
# Unigram
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
投稿
0 件のコメント:
コメントを投稿