任意の学習率の式に対する効率的なL1正則化の計算方法

Tag

preferred

今回はaveraged FOBOSの導出をしてみたのでその話を書こうかと思ったのですが、導出途中に平均化劣勾配法の場合と大差ないと気付いてしまってテンションが下がってしまいました。というわけで、ちょっとネタを変えて、学習率をいい感じに減衰させながら学習するためにはどうしたらいいのか、ありがちな実装テクニックについて書いてみます。

前提知識

前提知識として最適化問題をどう解くかを知っている必要があります。これについては以前に入門記事を書きましたので適宜ご参照下さい。文字数制限の関係で4回目と5回目のみリンクしておきます。

劣微分を用いた最適化手法について(4) やっとFOBOSが出てくる第4回
劣微分を用いた最適化手法について(完) 感動の最終回

問題提起

最近のオンライン学習において重要なテクニックの1つとして、パラメーター更新の遅延（lazy update）があります。これは、正則化の計算を必要になるまで遅延することで学習を高速化するものです。データが高次元かつスパースであるような場合には100倍程度の高速化が得られることも稀ではありません。

lazy updateのキモは、データ側で有効になっていない素性については、wの方ではどんな値になっていても計算結果に関わらないという点です。そのため、正則化は遅延できます。

\(k\)番目の要素\(w_k\)に対する正則化の計算は、L1 FOBOSにおいては以下のようなコードとなります。

# w_k ：wのk番目の要素の値
# c：更新幅
def regularize_w_k(w_k, c)
    return max(abs(w_k) - c, 0) * sign(w_k)

def sign(w_k)
   if w_k > 0
      return 1
   else
      return -1

コードを解説しましょう。absとsignは符号を気にしているだけなので、w_kが正の実数値の場合、正則化の式は結局max(w_k – c, 0) となります。つまり、w_kからcを引いた値が負の値になってしまう場合は0に、負にならない場合はw_k – cをそのまま採用する、ということになります。

学習率が一定の場合、cの値は簡単に計算できます。tを最後に\(w_k\)が更新されたラウンド（これまでのループの回数）とし、t+nを現在のラウンドとすると、c = \(\eta\) (t+n – t) = \(\eta\) n となります。より正確には比例定数を入れるべきですが、計算の難易度は変わらないので簡単のために省略しています。

学習率が一定ではない場合、cの計算は以下のようになります。

\(\sum_{t}^{t+n} \eta_i\)

これが効率よく計算できるかどうかは場合によります。今回は、Leon Bottouの sgd 2.0 （http://leon.bottou.org/projects/sgd）で用いられている以下の式について考えます。

\(\eta_i = eta_0 / (1 + \lambda \eta_0 t) 0.75\)

実はこれは閉形式で書けない

上の式を私は数時間かけて計算してみたのですが、どうもうまくいかず、最終的にWolfram Alpha先生に計算をお願いしてみました。以下がその画像です。

！？

なにやら想定外に難しそうな式が出てきてしまいました。実は、\(\zeta\)はHurwitz zeta functionという関数で、Wikipediaで調べたところ、閉じた形では計算できないようです。という訳で閉じた形に変形できないのは当たり前でした。

→Wolfram Alphaで数式を見る

効率的な計算は可能である

しかし、効率的な計算は実は可能です。まず、あらかじめ\(\Lambda_{t}\)というものを計算しておきます。\(\Lambda_{t}\)は以下で定義されるものとします。

\(\Lambda_{t} = \sum_{i=1}^{t} \eta_i\)

これらの\(\Lambda\)はメモリ上に保存しておくものとします。この\(\Lambda\)を使うと、

\(\sum_{i=t}^{t+n} \eta_i = \Lambda_{t+n} – \Lambda_{t}\)

と書くことができます。展開してみると合っていることが確認できます。ということで、任意の学習率に於いてL1正則化を効率よく計算できることが示せました。

さて、この方式の問題点は、すべての\(t\)に対して\(\Lambda_{t}\)を保存しておかなければいけない点です。この問題には単純な解決策があり、例えば10,000ラウンドに1回、正則化の計算を強制的に行うコードを入れておけば、\(\Lambda_{t}\)を保存しておくために必要なデータは長さ10,000の配列で充分保存できるようになります。もともと、すべての次元に対してすべてのラウンドで正則化の計算をするのが重たい、ということでlazy updateが生み出されたわけですが、10,000回に1回ぐらいであれば、正則化項の計算もそれほど大きな負担にはなりません。

このテクニックを用いることにより、正則化の計算コストを大幅に下げつつ、自由な学習率を用いることが可能になります。これを使って実験してみたかったのですが、年末進行等によりそこまでの時間が取れないので、また後日項を改めます。

Tag

# 機械学習