L1正則化の累積更新
L1正則化を累積更新するというTsuruoka氏の手法を、先日のNLP2010で岡野原さんが紹介されていたので該当論文を読んでみた。どういう事を書いているのかざっとメモ。ほんとに概要だけなので詳しくは↓をよむべし。
Stochastic Gradient Descent Training for L1-regularized Log-linear Models with Cumulative Penalty
はじめに。L1正則化というのは正則化の一種。で、正則化というのは何かと言うと識別器を学習させる際に過学習を抑制させるためにペナルティを与えること。
正則化には主にL1とL2の二つがあるのだが、このうちL1は不要なパラメータをごっそりゼロにする(つまりパラメータ数を減らせるので省メモリ化できる)という利点がある。L1は正則化の式が滑らかでないので(つまり微分すると非連続点がでてしまうので)、あまり使われていなかったのだがFOBOSという画期的な手法が提案されたため、最近良く使われるようになった。FOBOSについては以下を参照。
で、FOBOSなのだが、オンライン学習に適用すると問題がある場合がある。どういう事かというと、FOBOSでは正則化項によってデータが与えられる度にじわじわと不要な重みを削っていくのだが、データが偏っていると十分に重みが削り取れないことがある。
たとえば本来なら「カレー」という単語は素性として重要でないのでカレーの重みはL1正則化によってゼロになり消滅するべきだったとする。ところが運悪く学習データの終りの方に集中してカレーという単語がでてくると、十分に重みが削がれないうちにデータがなくなってしまい学習終了になる。
このように学習データが偏っていると、実は不要なのに重みゼロで消滅してくれない素性がたくさんでてくる。これではL1の特徴が生かせない。
これに対して、Tsuruoka氏は、正則化によって削られるぶんの重みを保持しておいて、素性が出現したときに、もしそれまでに出現していたら削られていたであろう重みをごそっと引いてしまう方法でこれを解決したよ、という話。
ここまでに述べたことは論文のFigure1をみるとイメージしやすい。というかこの図にすべてが集約されている。感想としてはシンプルだが賢い方法だなと思った。それほど複雑な式は出てこないので数式など詳細は実際に論文を見るとよいかも。
