L1正則化について

先日L1正則化についての話をしてきました。 [ppt] [pdf]

ちょっと専門的な話ですが、L1正則化はパラメータ推定のときにパラメータw∈R^m に対し|w|_1 = |w_1| + |w_2| + ...+|w_m| のペナルティをかけるもので、機械学習だけでなく、compressed sensingやらいろいろな分野で出てくる手法です。

L1正則化を使うと、殆どのパラメータが0になりコンパクトな学習結果モデルが得られる上に、ノイズが大きい場合にはそれらを無視することができます（L2の場合はrepresenter theoremより、重みベクトルは訓練ベクトルの線形和としてしか表せないので、要らない素性の重みを0にするようなことは難しくなります）

さて、上の発表で話した中で今面白いのはL1-ball projectionという技術です。
"Efficient Projections onto the L1-Ball for Learning in High Dimensions", ICML 2008, J. Duchi, et. al. [pdf]

これはベクトルv∈R^mが与えられたら、w* = argmin_w |w-v|_2 , |v|_1 <= zを探す（|a|_ｎはnノルム）、つまり半径zのL1上の球で一番vに近い点を探すというものです。これができるとL1付の最適化もできます（|v|_1 < z の制約はラグランジュの未定乗数法でα(z - |v|_1) = -α|v|_1 + const.という効果）

この最適化は式を変形させていくと、現在のパラメータv_iを定数θ分だけ0に近づけて、もし符号が変わったら0にクリップするのが最適だということがわかります（θはその時のvに依存する）。式で書くと
w_i = sign(v_i) max(|v_i|-θ,0)
sign(v_i)はv_iの符号

つまりL1-ball projectionは各パラメータから定数の値をひくdiscountで実現できます
ということはL1正則化も結局のところ、discountによるスムージングということになります。
（L2-ball projectionだと、引くのではなく一定の値で割ることになる）

考えてみると当たり前のようなきもするけど、はっきりいわれるとすっきりしますね。

上の論文ではこのL1projectionを非常に効率的に行なう方法を提案しています（パラメータ数がmの時、平均O(m)時間、さらにアップデートで少数のパラメータしか変更しなくて続けてprojectionする場合は、変更があったパラメータ数がm'のときO(m' + log m)ぐらいでできるアルゴリズムも提案しされてます)。

実装も簡単そう。やってみるか。