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

Tag

# 機械学習

# 解説

preferred

もう2月ですが、新年明けましておめでとうございます。徳永です。残り11ヶ月、頑張ってまいりましょう。

前回までで、劣微分を使った最適化手法として劣勾配法やFOBOS, Truncated Gradientを紹介しました。

更新式を見るとわかるのですが、FOBOS/Truncated Gradientでは、前半でよく出現する要素に対して厳しく正則化がかかる一方、後半でよく出現する要素に対してはあまり正則化がかかりません。極端な例として、データの特徴となる要素が1回だけしか出てこない場合を考えましょう。ある要素が最初の1回にしかでてこなかった場合と、最後の1回にしか出てこなかった場合で、その重みを比較してみるとどうなるでしょうか？

この結果を考えてみると、最初の1回にしか出てこなかった場合、ほぼ確実にその重みは0になってしまいますが、最後の1回に出てきた場合にはそこそこ大きな重みが残ることがわかります。しかし、出現順序と正則化のペナルティ量とは、本来は無関係であるべきでしょう。

そこで今回紹介するのが、Stochastic Gradient Descent Training for L1-regularized Log-linear Models with Cumulative Penalty (Tsuruoka, Tsujii and Ananiadou, ACL2009) です。第二著者の辻井先生は、東大を早期退官されてMRSAへ行かれるということがつい最近業界では話題になっていましたね。

Cumulative Penalty

論文の方では提案手法にアルゴリズムの名前は明示的につけてはいませんが、実験のセクションではCumulative Penaltyと呼んでいるので、このエントリでもCumulative Penaltyと呼ぶことにします。

さて、Cumulative Penaltyの考えた方は非常にシンプルです。FOBOSやTruncated Gradientでは最初の方に初めて出てきた要素に対しては、その重みが0になるまで常に正則化をかけつづけますが、最後の方に出てきた要素に対しては正則化をかけきることができない場合があります。そこで、最初の方に出てきた要素と同じだけの正則化を最後の方にでてきた要素に対してもかけてやろう、というのがCumulative Penaltyの考え方です。

具体的には、

現在までに与えたペナルティの総量\(u\)
i番目の要素がそこまでに受けてきたペナルティ\(q_i\)

を用意して、正則化の時には\(\max(0, w_i – (u + q_i))\)で正則化を計算します。（\(w_i > 0\)の場合。\(w_i < 0\)だと全部符号が逆になります。）他のところはFOBOS/Truncated Gradientと特に変わりありません。以下にCumulative Penaltyを利用した場合の正則化についての疑似コードを示します。

def regularize_cp(w)

  for i in 0 .. w.length
    z = w[i]
    if w[i]
      w[i] = max(w[i] - (u + q[i]), 0)
    else if w[i] < 0
      w[i] = min(w[i] + (u - q[i]), 0)

    q[i] = q[i] + (w[i] - z)

なお、\(u\)は\(u = u + \eta C\) という式で徐々に増加していきます。

この他、論文の方では学習率の値を指数的に減少させることで収束が速くなりますよという工夫も書いてありますが、どちらかというとこのCumulative Penaltyの方にオリジナリティがあるのかなと思います。タイトルにもCumulative Penaltyと書いてありますしね。

連載の終わりに

FOBOSは非常に実装が簡単で、かついい感じの性能が出るのでぜひ紹介したい、と思って全2回ぐらいでさくっと紹介するつもりで書き始めた一連のエントリなのですが、一個一個を書くのが予想以上に重く、かつ連載自体も全5回に及ぶという、当初の想定からすると圧倒的に巨大なボリュームになってしまいました。今回で、劣微分関連のエントリは一旦終わりにしたいと思います。

最適化関係は面白いのですが、どんどんと新しいものが出てくるので追いかけるのがなかなか大変です。去年のNIPSなんかにもまた新しい手法が出てきていたりするので、またそのうち新しい手法の紹介なんかもできたらいいなと考えています。

さて、連載は終わりますが、最終回の掲載が前回の掲載から1ヶ月以上も間があいてしまいましたし、内容を忘れてしまった方は、下のリンクからぜひもう一度読んでいただければと思います。