L1-SGD

Stochastic Gradient Descent Training for L1-regularized Log-linear Models with Cumulative Penalty
Yoshimasa Tsuruoka, Jun’ichi Tsujii and Sophia Ananiadou, ACL2009.

論文紹介．鶴岡さんのL1正則化付き確率的勾配降下法（Stochastic Gradient Descent，SGD）．L1正則化はコンパクトなモデルパラメタになってくれるので，実用上はとてもうれしい．しかし，0の点で微分できないので面倒だった．提案手法は実装が超簡単（擬似コードで20行くらい），超高速で，収束も早いし，性能もいい，いいこと尽くめ．初めての人にもお勧めできる簡単さで，しかもそのまま実用品になります．

L1正則化は目的関数に重みベクトルのL1 normをたした，f(w)+C|w|を最小化しましょうというはなし．L2と違って，0の付近で最小になりやすいので，ほとんどのパラメタが0になって学習結果がコンパクトになりやすいため，実用上重要です．
ところが，この性質，つまり|w|は0の付近でとがっていることが最適化の上では問題．このまま計算すると，0を境にして振動するだけで，なかなか0に近づいてくれません．そこで，更新時に符号が変わるときは（0を飛び越えるときは）一度wの値を0にしてしまいます．これがclipping（で，これがFOLOS）．
しかし，ここまでやってもまだ真の最適解のスパース性に及びません．この原因はオンラインアルゴリズム特有の，最後にやってきたデータに強く引っ張られすぎるという問題のせいです．パラメタは対応する素性を含む学習データが出現すると，勾配が大きいので0から抜け出して，その後L1のペナルティだけがかさんでまた0に戻ります．この途中過程で打ち切られてしまうため，疎な解になりにくいのです（figure 1，下の追記参照）．ということは，L1のペナルティをためておいて，その素性を含む学習データがきたときに，ためておいたペナルティと，学習データによる抜け出す力（勾配）で力比べをして，ペナルティが勝ったらやっぱり0だった，学習データが勝ったら0から抜け出せばよさそう．これがcumulative．ため込んだペナルティと比較するので簡単には0から抜けません．ここで特に実用上大事なのは，L1のペナルティの絶対値はパラメタの現在の値に依存しないため，反復ごとに全体で1回足し算するだけ（これがu）．
実装は非常に簡単です．しかも，式見てわかるとおり各更新は素性の非ゼロ要素だけでよいので，ものすごく速いです．

追記（2010/2/19）
twitter上で，@tkngさんと@uchumikさんにFOLOS（@slaさんによると，最近FOBOSに改名したらしい．改名って・・・）との違いを教えていただきました．多謝！

Efficient Learning using Forward-Backward Splitting
John Duchi and Yoram Singer, NIPS2009.

5章にlazy updateについて書かれています．これは，鶴岡さんの論文でも言及されています．上の私の説明で，一度0から抜け出してから0に戻る途中で打ち切られるのが原因と書きましたが，これはちょっと間違い．lazy updateを使えばこの問題はなくなりますが，やはりcumulativeほど疎な解になりません．
一見lazy updateとcumulativeは同じに見えますが実は違います．lazy updateは前回の更新から，次の更新までの間のペナルティを一気にかけます．つまり，長いこと勾配が0で，次に立て続けに勾配が非0だと0から抜け出せます．一方で，cumulativeは最初から現在までのペナルティの総和を持っているので，勾配の総和がこれを超えてくれないと抜け出せません．なので，長いこと勾配が0だと，そのあと立て続けに勾配が非0でも，その間のペナルティがかさんでいるのでやっぱり0から抜けられません．
給料日（勾配が非0）のたびに取立て（L1ペナルティ）に来ますが，FOBOSは前回の取立て日からの日数分だけ，cumulativeは過去までさかのぼって今までのツケを要求します．人生後半で（学習の後半で）再就職すると（非0が続くと），FOBOSなら貯蓄ができますが（0から抜ける），cumulativeは今までのツケの返済に回されてやはり所持金0です．気に入ったんですが，別にわかりやすくないなw

さて，どっちがいいのかという話ですが，FOBOSは後半の出現に強く依存する点で，cumulativeの方がいいのかなという気がしました．バッチの場合は全データの勾配を足して，ペナルティも足すわけですから，出現順に依存してペナルティの総和の変わるFOBOSよりcumulativeの方が近いのかな，という直感．理論的な考察とかもありそうですね．