Blog
まちがえて鋼の錬金術師の最終巻を2冊買ってしまいました。研究開発チームの徳永です。
前回は、線形識別器まで説明しました。今回はその続きからです。
まずはじめに、前回の内容を少しおさらいしておきましょう。線形識別器ではそれぞれの入力に対して重みがつき、その重みパラメーターを調節するのでした。この調節を最適化といいます。
パラメーターの最適化とは
パラメーターを調節する、といっても、どのようにして調節すればいいのでしょうか？調節して、パラメーターが良くなったということを、どうやって判断すればいいでしょうか？
例えば、パラメーターを調節することによって、間違いが減ったら、それはパラメーターがよくなった、と言えるでしょうか？まぁ、これはよくなったと言えそうですね。（実は、これはちょっと雑すぎる議論なのですが、それについては後で説明します。）
上の例のように、パラメーターを調節する際にはなんらかの目的となる数値があって、その数値を最小化する、もしくは最大化するということがパラメーターを最適化するということです。この基準値を計算する式を目的関数と呼びます。
例えば、機械学習による識別器の中でSVMという非常に有名なものがありますが、SVMの目的関数は以下のような式\(L(\textbf{w})\)であり、この値を最小化することで、正解率の高い識別器を作ることができます。（正確には、正則化項が抜けていますが…）
\(L(\textbf{w}) = \sum_i \max(1 – y_i \textbf{w} \cdot \textbf{x}_i, 0) \)
さて、最適化とは基準値を最小化もしくは最大化することであるということが説明できましたので、次に具体的にどうやって最小化/最大化を行うかを説明しましょう。
最適化をどうやって行うのか？
パラメーターを最適化する手法は原理的には3つぐらいあります。
- 閉じた形でデータから最適なパラメーターの値を求める
- 基準値の計算式を微分して勾配を求めて、勾配方向に進んでちょっとずつパラメーターを良くする
- 適当にパラメーターを変更して、よくなった値を採用する
上のリストは、上から効率的な順に並んでいます。
1.は一番効率的に最適化が行えます。例えば二乗誤差を最小にする場合などに利用できますが、より複雑な目的関数を利用した場合には一般にはこの手法は困難になります。
2.は山登り法とか呼ばれる方法で、基準値をよくできる方法に進んでいったらいいんじゃないの、みたいな感じです。山登りするときに、坂の斜面を登って行くとそのうち頂上につくよね、みたいなイメージ。
3.は例えば焼きなまし法やメトロポリス-ヘイスティングアルゴリズムなどで採用されている方法です。
今回は、2. 山登り法と呼ばれるタイプのパラメーター最適化手法について説明します。1, 3については扱いません。
オンライン型・バッチ型
勾配を使う方法にもいろいろあります。まず、バッチ型とオンライン型の2つの区別から説明を始めましょう。（厳密に区別するならば、オンライン型とストリーム型も区別する必要があるかもしれませんが、ここではそこまで細かい話はしません。）
バッチ型というのは、データを全部読み込んでから、パラメーターを1回更新する、というループを繰り返す手法です。それに対しオンライン型は、データを1つ見たらパラメーターを1回更新する、という作業を繰り返す手法です。
イメージ的には、ローソンとセブンイレブンとファミリーマートで肉まんを買って食べるのに、バッチ型ではローソン、セブンイレブン、ファミリーマートで肉まんを買って家に帰ってから食べるのに対し、オンライン型ではそれぞれの店で肉まんを買って、次の店に行くまでの間に食べてしまう感じです。肉まんを食べるという処理がパラメーター更新であり、パラメーター更新をどのタイミングで行うかという点が違いである、という私の頭の中のイメージですが、かえって分かりにくくなっていたらすみません。
バッチ型とオンライン型を比較すると、オンライン型の方がパラメーターの収束が不安定です。データによっては学習率をうまく設定しないと収束しない、というような場合もあります。一方、バッチ型の欠点としては、使用するメモリ量が多くなる傾向がある点が挙げられます。
その他、オンライン型のメリットを挙げると、一般的に実装がバッチ型よりも簡単です。また、近年の研究により、ステップ幅を適切に設定すると、オンライン学習の方が速い場合があることがわかってきました。
本エントリではバッチ型についてはニュートン法の話を少しだけ紹介するだけです。その後、オンライン型について少し詳しく説明します。
バッチ型：ニュートン法
バッチ型の最適化手法としては、ニュートン法、準ニュートン法などがあります。CRF（Conditional Random Fields）の最適化でL-BFGSというのを見たことのある人も多いと思いますが、あれは準ニュートン法の一種です。
ニュートン法の一族の欠点として、勾配を使うので、微分不可能な点を持つ関数に対しては使えないというものがあります。ただ、この欠点は広く認識されており、ものすごくたくさんの改良法が提案されています。”nonsmooth convex optimization”などで検索するといっぱい出てきます。例えば、A Quasi-Newton Approach to Nonsmooth Convex Optimization Problems in Machine Learning (Jin Yu, S.V.N. Vishwanathan, Simon Günter, Nicol N. Schraudolph; JMLR vol 11, pp1145−1200, 2010.) は図解入りでかなりわかりやすく書いてあります。今回説明したいのはバッチ型の手法ではないので、その詳細は省きます。
オンライン型：確率的勾配降下法
オンライン型最適化アルゴリズムの例として、ここでは確率的勾配降下法(Stochastic Gradient Descent, 以下SGD)について説明します。
さて、線形識別器fはどのような式だったのかを思い出しましょう。パラメーターベクトルを\(\textbf{w} \)、入力となる情報のベクトルを\(\textbf{x} \)とした時、線形識別器fは以下のような式で構成されます。
def f(x)
if w ・ x > 0
return 1
else
return -1
パラメーターはどんどん更新されるので、以下ではある時点tでの更新後の重みベクトルを\(\textbf{w}_{t+1}\)、更新前の重みベクトルを\(\textbf{w}_{t}\)で表すことにしましょう。また、i番目のデータを\(\textbf{x}_i\)で表すことにします。
詳しくは次回で説明しますが、SGDは微分不可能な点があると使えないので、ここで最大エントロピーモデルを使うことにします。最大エントロピーモデルの場合、最小化するべき式は、
\(L(\textbf{w}) = \sum_i – \log (1 / (1 + \exp(-y_i \textbf{w} \cdot \textbf{x}_i))) + r(\textbf{w})\)
となります。これは負の対数尤度の最小化になります。一般的に対数尤度の最大化として扱われることが多いですが、最小化にしたかったのでマイナス符号をつけてあります。\(r(\textbf{w})\)は正則化項というものですが、正則化項については後述することにして、とりあえず今は無視します。
\(r(\textbf{w})\)を無視すると、\(L(\textbf{w})\)は
\(L(\textbf{w}) = \sum_i – \log (1 / (1 + \exp(-y_i \textbf{w} \cdot \textbf{x}_i))) \)
となります。SGDではこの損失\(L(\textbf{w})\)を最小化するために、データを一つ読んでは勾配を計算し、勾配方向に適当に進みます。進む量を学習率と言い、\(\eta\)で表します。
だんだん疲れてきたのでここからは飛ばしていきます。SGDでは、データ全体を読んで勾配を計算する代わりに、データ一つ分での勾配を計算して、その方向にパラメーターを更新します。勾配を\(L'(\textbf{w}) \)とすると、式で書くと
\(\textbf{w}_{new} = \textbf{w}_{old} + \eta L'(\textbf{w})\)
となります。\(L'(\textbf{w})\)は\(L(\textbf{w})\)の\(\textbf{x}_i\)にだけ注目して\(\textbf{w}\)で微分すると求められ、
\(L'(\textbf{w}) = – y_i \exp(-y_i \textbf{w} \cdot \textbf{x}_i) / (1 + \exp(-y_i \textbf{w} \cdot \textbf{x}_i)) \textbf{x}_i \)
となります。一番右の\(\textbf{x}_i \)だけがベクトルで、ほかは計算結果は実数値になることに注意してください。この式を使って、データを1つよんで\(\textbf{w} \)を更新する、というのがSGDのアルゴリズムです。この例は2値の場合ですが、出力が多値の場合にも簡単に拡張できます。
なお、今回は確率の話はしていないので具体的な式は省きますが、この勾配の式は\(e / (1 + e) = 1 – 1 / (1 + e)\) を使って書き直すことができ、そうすると結局、間違えた確率の分だけ勾配が大きくなるということがわかります。
正則化
先ほどは無視しましたが、正則化は重要な概念ですので少し詳しく説明しておきましょう。
正則化はモデルの複雑さに対して与えるペナルティです。複雑なモデルはデータに対してものすごくフィットし、損失を0にすることもしばしば可能ですが、複雑過ぎるモデルは未知のデータに対して弱い、という事がよくあります。このような状態を過学習といいます。このような事態を避けるために、モデルの複雑さに対して与えるペナルティが正則化項です。
よく使われる正則化にはL1正則化とL2正則化があり、それぞれ、パラメータベクトルの要素の絶対値の和と、要素の二乗の和となります。式で書くとL1正則化は\(r(\textbf{w}) = c \sum_i |w_i| \)となり、L2正則化は\(r(\textbf{w}) = c \sum_i |w_i|^2 \)となります。
L2正則化の場合、\(w_i\)の値が0に近づけばペナルティはほぼ0になりますが、L1正則化の場合、ペナルティが0になるのは値が完全に0であるときのみです。そのため、L1の方がパラメータベクトルの非0の要素を減らす力が強く働きます。こう書くとL1正則化の方が良さそうですが、0のところで微分が不可能なため、一般的な数値最適化の手法を使うのが難しくなります。それで、L1正則化を実現するためのさまざまな研究が生まれました。
ちなみに、L0正則化とかL∞正則化とかもあります。
次回予告
いよいよ来週は劣微分が出てきます。乞う御期待！！！！！！！！！！！！！１
