« gboost | メイン | Yahoo!の形態素解析をMeCabで無理やり再現してみる »
2007年06月21日
L1-regularized CRFを実装してみた
hillbigさんのブログで 紹介されていた "Scalable Training of L1-regularized Log-linear Models", G. Andrew and J. Gao., ICML 2007. をCRF++上に実装してみました。現在の CRF++ の実装、そしてオリジナルも含めた多くの実装は L2-regularized log-linear model です。hillbig さんのプレゼンにもありますが、L2は若干高性能だけど、全パラメータが非0になって、最終的なモデルがデカく なってしまうのですが、L1だと不必要･冗長なパラメータを完全に0にする効果があり、モデルをコンパクトにします。
3年前のmecabに関する論文では、L2 と L1 の CRF を比較して、L2のほうが若干高性能ということを確認していました。
L1-regularized の場合は、パラメータが0の点でgradientが計算できない問題が発生するため、既存の最適化 アルゴリズムはうまく適用できません。3年前は、box-constraintで定式化していましたが、パラメータ空間が2倍になるという問題がありました。それが CRF++への導入を遅らせていました。
前置きが長くなりましたが、件の論文は、L1-reguralized log linear を既存の LBFGS を使って高速に導出しようというお話です。結論から言ってしまえば、論文にあるとおり、LBFGSを30行ぐらいいじるだけで実装できます。 (実際の diff はこちらなど)。基本的なアイデアは次の4つです
1. Reguralizer から導出される gradient の影響は hessianの計算には使わない
2. 0点でのgradientは二つ候補があるが、目的関数が小さくなるほうを選ぶ
3. 現在の gradient と更新方向の sign は異なる。一緒の場合は変化させない
2. 負->正 もしくは 正->負になるようなパラメータ更新は認めない。そうなった場合は強制的に0
Conll2000の小規模データで実験すると、非0のパラメータが 1/10ぐらいになって、モデルが劇的に圧縮されることが確認できました。
投稿者 taku : 2007年06月21日 01:42
トラックバック
このエントリーのトラックバックURL:
http://chasen.org/~taku/blog/mt-tb.cgi/228