2010年2月28日日曜日

Conditional Neural Fields on Google Code

CNF の著者の Jian Peng 氏に特許について質問をしてみたところ、問題ないということでしたので Google Code にプロジェクトを作成してコードを公開しました。

http://code.google.com/p/cnf/

あまりちゃんとした実装ではないので、使用は自己責任でお願いします。
間違ってるかもしれないので、間違いがあれば教えてくれると嬉しいです。

mercurial で管理しているので、以下のコマンドで落としてきて使用できます。

$ hg clone https://cnf.googlecode.com/hg/ cnf
$ cd cnf
$ make
$ ./src/cnflearn src/template data/conll2000/train.txt test.save
$ ./src/cnftagger src/template test.save data/conll2000/test.txt

cnflearn_main.cpp と cnftagger_main.cpp を見てもらえば分かる通り、実行用のプログラムはむちゃくちゃ手抜です。

logsumexp の計算部分には、NAIST の浅原先生の資料にあるコードを使わせて頂きました。

2010年2月16日火曜日

Conditional Neural Fields

年越ししてから既に2ヶ月が過ぎ、2月も終わりが見えかけてきた今日この頃です。
生存報告をかねて、少しだけ最近やっていた事を書いておきます。

去年の年末くらいに、面白そうな論文を見つけたのでそれを読みつつ、実装していました。
NIPS2009 で発表された論文です。

その名も Conditional Neural Fields 。
http://books.nips.cc/papers/files/nips22/NIPS2009_0935.pdf

名前から何か感じるところの有る人もいそうですが、これはCRFに隠れ層を加えて、非線形にした物になります。

自分のメモ用に、先に簡単に CRF についておきます。
--
CRF の説明はNLP2006のチュートリアル資料が割と分かりやすいです。
http://nlp.dse.ibaraki.ac.jp/~shinnou/lecture/nl/NLP2006.pdf

私はオンライン学習器でしかCRFを作った事が無いので、ここではそのつもりで書きます。
CRF では素性関数に対応するパラメータを学習するわけですが、その式は大雑把に書くと次のようになります。

Λ_t+1 = Λ_t + η * (正解の素性関数ベクトル - 期待素性関数ベクトル)

η は学習率、Λ は素性関数に対応するパラメータベクトルです。
正解の素性関数ベクトルは入力系列が与えられれば素性と正解のラベルのペアを取り出すだけで作れます。
要はどの素性とラベルのペアが何個有ったか、どのラベルとラベルの遷移が何回あったか、をカウントしてベクトルにしています。

期待素性関数ベクトルはちょっと計算が面倒ですが、現在のパラメータΛのもとで、入力系列から生起しうる全てのラベル系列を考えます。
各ラベル系列が生起した際の、各素性関数の期待値を計算し足し合わせた物が期待素性関数ベクトルです。
まともに全てのラベル系列を生成して試すともの凄い計算量になるので、これは Forward-Backward アルゴリズムを用いて計算するのが一般的です。
--

前置きが長くなりましたが、 CNF について書きます。
ちなみに間違ってるかもしれません。あまり期待しては行けません。
この記事は後でこっそり修正されてる可能性もあります。

CRF との違いは、観測素性の扱いになります。
CRF では、素性関数 f(x,y) は素性xとラベルy のペアを観測した際に1になるような関数です。

これが CNF では、f(h(X,t),y) になります。

数式は元論文のままだと比較しにくいので変えてます。
関数h はロジスティック関数で、X に対して非線形な値を取ります。
t は系列のカレントの位置を表しています。

f(h(X,t),y) は組み合わせ素性xとラベルy のペアを観測した際に、h(X,t)を返す関数と思ってください。
X が大文字になっている理由は、CNF では入力系列に対して隠れ層で組み合わせ素性を取り出すためです。
素性関数 f(h(X),y) は入力系列 X に対して、位置tに置ける組み合わせ素性 x とラベル y のペアに対して、h(X,t) を返します。

h(X,t) は中で何をしているのかと言うと、入力系列 X とパラメータθベクトルの内積を計算して、その値をロジスティック関数に乗せて非線形な値にしています。

こうする事で、単純に組み合わせ素性が観測されたというだけではなく、その素性に対して非線形な重みを与えています。

次に、パラメータの最適化ですが、実は素性関数が非線形になっているという事を無視すると、観測素性についてのパラメータと、遷移素性についてのパラメータの更新の式は一緒になります。

ただし、正解の素性関数ベクトルはどの素性とラベルのペアが何個有ったか、どのラベルとラベルの遷移が何回あったか、ではなく、素性に対して非線形な重みを計算し足し合わせたものになります。ラベルとラベルの遷移は相変わらずただのカウントです。
要は、カウントの仕方が1ずつ足していたのが、実数値ずつ足すようになった物です。

期待素性関数ベクトルも同じ要領です。 入力系列から生成されうる全てのラベル系列を考えて、各ラベル系列が生起した際の各素性関数の期待値を計算して足し合わせます。 ただし期待値を計算する際には素性に対して、これまで有った/無かったで済ませていたところにh関数の値が入ります。

パラメータ推定での1つ大きな違いは、これに加えて隠れ層のパラメータθについても更新することです。

θの更新は、次の式で行われます。
θt+1 = θt + Σt w_yt,g * ∂h/∂θ - E (Σt w_yt^,g * ∂h/∂θ)

wは素性関数に対応した重みパラメータです。
重みパラメータΛ = (W, U, θ) と思ってください。
Wは観測素性に対応する重みパラメータ
Uは遷移素性に対応する重みパラメータ
θは隠れ層のパラメータ
E は期待値です。

かなりやっつけな式なので詳しくは元論文を読んだ方が良いです。
要は、正解系列中の観測素性の重みベクトルと、入力系列から生成されうる全ラベル系列を考えた時の各観測素性の期待値ベクトルの差をなくすようにθを更新しています。

という事で、実装してみました。
実装は sgd + FOLOS です。

コード公開したいんだけど、権利関係やら何やら良く分からない。
論文の著者にメールして特許についてとか聞いといた方が良いと言われているのですが、そこで停止中。

--
ちなみに、CNF は組み合わせ素性、CRF は組み合わせ無し、のような印象を受けますが、CRF++やCrfSgdを使った事が有る方は分かると思いますが、CRF でも素性テンプレートを使って組み合わせ素性を扱えます。

素性テンプレートを使った組み合わせ素性の抽出はまさに CNF で言うところの中間層だと思っています。
なので、CNF と CRF の違いは実際のところロジスティック関数による非線形な値を観測素性に与えているところと、θの学習が入っているところだというのが私の理解です。

私の実装もそのまんまで、「ロジスティック関数による非線形な値を観測素性に与えているところと、θの学習を入れた」素性テンプレートを使える CRF です。

--
conll2000 のチャンキングで比較をしてみたので一応載せておきます。
一応素性テンプレートは揃えてありますが、内部での処理が微妙に違うため素性数は厳密に一緒ではありません。

まあ、見ての通りだと思いますが、恐らくロジスティック関数による非線形な値云々よりも、組み合わせ素性を使えるかどうかの方が重要で、CRF でもそれが出来れば問題ないんだろうなという感じでした。

元々Kernelなどを用いた非線形な分類の実体は、素性の組み合わせを考慮してより高次元空間へ写像して、その空間で線形分離しているわけで、素性テンプレートを使って組み合わせ素性を扱っている以上、あんま変わんない結果が出たとしても別段驚く事じゃない気もしますね。

* CrfSgd
[Epoch 50] -- wnorm: 9273.81 total time: 1664.69 seconds
Training perf: sentences: 8936 loss: 4473.67 objective*n: 9110.58
misclassifications: 794(0.375011%)
accuracy: 99.62%; precision: 99.32%; recall: 99.18%; FB1: 99.25
Testing perf: sentences: 2012 loss: 4429.27 objective*n: 5473.3
misclassifications: 1893(3.99561%)
accuracy: 96.00%; precision: 93.84%; recall: 93.62%; FB1: 93.73
Saving model file model.gz.
Done! 1664.69 seconds.

* CNF
epoch: 49 err:0.002985(632/211727)
./cnflearn template data/conll2000/train.txt testbb.save 3728.58s user 200.56s system 69% cpu 1:34:54.39 total

./cnftagger template testbb.save data/conll2000/test.txt | ./conlleval
processed 47377 tokens with 23852 phrases; found: 23718 phrases; correct: 22293.
accuracy: 96.02%; precision: 93.99%; recall: 93.46%; FB1: 93.73
ADJP: precision: 81.08%; recall: 75.34%; FB1: 78.11 407
ADVP: precision: 83.71%; recall: 80.72%; FB1: 82.19 835
CONJP: precision: 55.56%; recall: 55.56%; FB1: 55.56 9
INTJ: precision: 100.00%; recall: 50.00%; FB1: 66.67 1
LST: precision: 0.00%; recall: 0.00%; FB1: 0.00 0
NP: precision: 94.39%; recall: 93.88%; FB1: 94.14 12355
PP: precision: 96.81%; recall: 97.78%; FB1: 97.29 4859
PRT: precision: 83.15%; recall: 69.81%; FB1: 75.90 89
SBAR: precision: 87.72%; recall: 85.42%; FB1: 86.55 521
VP: precision: 93.95%; recall: 93.62%; FB1: 93.78 4642