劣微分を用いた最適化手法について(4)

Tag

# 機械学習

# 解説

preferred

徳永です。進撃の巨人3巻が発売される頃までにはこのエントリを公開するつもりだったのですが、無理でした。

前回は、劣勾配法を紹介し、前々回で紹介した確率的勾配降下法と劣勾配法を比較した場合、劣勾配法を用いることによって微分不可能な点があっても最適化が可能になるけれど、解の品質には依然として問題がある場合があり、特にL1正則化に付いてはあまり良い結果が得られない、というところまでお話しました。

今回は劣勾配法の改良に当たる論文として、FOBOSと呼ばれる手法を紹介します。ここから先はしばらく退屈な話が続くかもしれないので、あらかじめ、これらの手法がどうすごいかを語っておきましょう。私がこれらの手法がすごいと感じているところは、コードが非常に短く書けるところです。学習のコアの部分は、正則化を入れても15行とか20行ぐらいで十分に書けます。それでいて学習は十分に高速であり、実用的に使えるのです。

FOBOS

今回紹介する論文はEfficient Online and Batch Learning Using Forward Backward Splitting John Duchi, Yoram Singer; Journal of Machine Learning Research 10(Dec):2899−2934, 2009. です。この論文はジャーナルなので長いですが、2009年のNIPSに投稿された短いバージョンもあります。お好きな方をお読みください。

この論文の主眼は、劣勾配法を使ってL1正則化を行った際に（汎用的に使える手法であるという主張ですが、やはり実用的な観点からはL1正則化が一番大きなポイントだと思います）劣勾配法よりも大幅に効率的に解を求められる、という点でしょう。この提案手法をFOBOSと言います。昔はFOLOSという名前でしたが、FOBOSに変わりました。

FOBOSは劣勾配法に似たオンライン学習アルゴリズムです。特徴として、各サンプルでのパラメーター更新を2ステップに分けているところが挙げられます。すなわち、

損失項の劣勾配法による処理
正則化項の閉じた形での最適解の計算

の2つのステップです。劣勾配法では、損失項と正則化項の両方の勾配を一気に計算していましたが、その2つを分離した訳です。

t番目のサンプルを見る際に使うパラメーターを\(\textbf{w}_t\)とした時に、勾配方向へまず移動したものを\(\textbf{v}\)とし、正則化の処理まで終わったものを\(\textbf{w}_{t+1}\)とします。なんでいきなり文字が\(\textbf{v}\)に変わるのかと疑問に思われるかもしれませんが、元の表記法もちょっとタイミングは違うけどそうなるから、WordPressで複雑な数式を書くと読みにくい、などの理由によります。

まず、損失項（損失関数）の劣勾配の部分の処理に関しては、\(f(\textbf{x})\)の劣勾配を計算し、その方向に進みます。劣勾配がわからない人は前回を参照してください。

次に、正則化を行ないます。この正則化がFOBOSのポイントで、正則化項を以下の式の結果として処理すると、閉じた形で解が計算できます。更新後のパラメーター\(\textbf{w}_{t+1}\)は

\(\textbf{w}_{t+1} = \arg \max_{\textbf{w}} \frac{1}{2} || \textbf{w} – \textbf{v} || ^2 + \hat{\lambda} r(\textbf{w})\)

として求めます。ややしつこいですが、\(\textbf{v}\)は勾配方向へと少しだけ\(\textbf{w}_t\)を動かしたものです。また、\(\hat{\lambda}\)は、学習率とかをいい感じに考慮した定数であると考えてください。（前回ではこのパラメーターに相当する部分にはcという定数を使っていましたが、今回はFOBOSの式に合わせました。）

計算式の導出は面倒ですし誰も読まなさそうなので省略することにして、概略だけざっと書いておきます。\(\textbf{w}_{t+1}\)を求める際の目的関数の値は非負の数の和であり、かつそれぞれの項は独立しているという特徴があります。このため、それぞれの項に関して最適な値を計算すれば、それが\(\textbf{w}\)に関しての最適解になっています。それぞれの項に関する最適な値の計算は、ラグランジュの未定乗数法を使えば簡単に計算できます。論文の方ではL1正則化、L2正則化、Berhu正則化（L1とL2をミックスしたような正則化です）などに対して式を導出していますが、ここではL1正則化に付いてのみ紹介しておくことにします。\(r(\textbf{w})\)としてL1正則化を当てはめて計算してやると、\(\textbf{w}_{t+1}\)のi番目の値は、

\(sign(v_i) [|v_i| – \hat{\lambda}] \)

となります。ただし、sign関数は引数となる数の符号に応じて1, -1を返す関数で、[]は引数が0以上ならばその値を、0以下ならば0を返す関数です。

上の式はむりやり数式として表すよりも、コードで書いてしまったほうがわかり易いかもしれません。コードで書くとsignも[]もif文で書けます。以下にFOBOSによるSVMの最適化のコードを示します。

def learn_svm_fobos(x)
  diff = []

  # 損失による勾配
  if w.inner_prod(x) < 1
    w += eta * x

  # 正則化
  i = 0
  while i < w.length
    if w[i] > 0
      if w[i] - c > 0  # lambda_hatと書くと長いので代わりにcを使います
        w[i] -= c
      else
        w[i] = 0
    else 
      if w[i] + c > 0
        w[i] = 0
      else
        w[i] += c

正則化の部分について、\(w_i > 0\) の場合に絞って考えてみましょう。\(w_i > 0\)の場合、正則化ではさらに\(w_i \)が\(c\)より大きいかどうかをチェックし、大きければその定数を引きます。それが成り立っていない場合は\(w_i\)の値を0にします。\(w_i < 0[/latex]のときも同様です。このコードのL1正則化の部分では結局、

基本的にパラメーターそれぞれを定数分だけ0に近づける
0を超えて符号が変わってしまう場合には0で止める

ということをしています。一つめの部分によって使われないパラメーターはどんどんと0に近づいてゆき、二つめの部分によってあまり重要でないパラメーターは0に固定される可能性が高くなります。劣勾配法と比べた場合、二つめの部分が特に重要です。この操作をクリッピングと呼びます。

正則化の計算の高速化

FOBOSでは、素直に実装すると、正則化のためにはパラメーターの次元と同じ回数のループを回さなければなりません。パラメーターが高次元になってくるとこの計算コストは重たくのしかかります。ここで、ちょっとした工夫によって高速化が行なうことができます。

正則化の計算は遅延することができます。FOBOSによる最適化では損失項と正則化項の処理に分かれる訳ですが、損失項の処理でやることと言えば劣勾配を計算することであり、劣勾配の計算ではパラメーターの一部分、具体的には入力ベクトルにおいて0になっていない部分のみが使われるからです。そのため、使われない部分のパラメーターの正則化は、そのパラメーターが使われる直前まで遅延することができます。この際、あるパラメーターに対して最後に正則化の処理を行ったのは何回目のループか、という情報を別のベクターに保存しておく必要があり、このためメモリ使用量が増えてしまいますが、増やすだけの価値があるほどの高速化です。

自然言語処理などの分野では、パラメーターは高次元であり、かつ1回のデータで有効になるパラメーターの数はそれほど多くないため、この工夫の効果は非常に大きいです。

実際にこの工夫まで適用した実装して、ここでは以前私が書いたmicterという単語分割器のSVMでの学習部分を挙げておきます。C++で書いたためにL1正則化のところとかちょっと汚くなっていますが、雰囲気はおわかり頂けるかと思います。

Truncated Gradient

次に、Truncated Gradientについて簡単に紹介しましょう。Truncated GradientはJohn Langfordらが提案した手法であり、FOBOSと非常に似ています。Truncated GradientではL1正則化のみを提案している点、正則化を数回に1度にする事を提案している点などが相違点もありますが、ほぼFOLOSと同じであると言ってしまっても良いだろう、というぐらいに似ています。ただ、彼らのモチベーションは、大規模データに対するL1正則化つきの学習を高速に行う、というところにあり、出発点は少し違うようです。劣勾配法の提案からだいぶ時間が経過した2009年に、似たような手法が独立に出てきたというところは少し面白いですね。

また、彼らのグループは、素性の組み合わせで新しい素性を作る、というようなことも実験しています。これは線形識別器を事実上非線形に拡張しているようなものです。つまり、[latex]x_i\)と\(x_j\)を組み合わせて新しい入力\(x_i x_j\)を作る、というようなことができます。これはVowpal Wabbitと呼ばれる学習器に実装されています。

参考文献など

Efficient Online and Batch Learning Using Forward Backward Splitting John Duchi, Yoram Singer; Journal of Machine Learning Research 10(Dec):2899−2934, 2009.