実装が簡単で高性能な線形識別器、AdaGrad+RDAの解説

機械学習では、データがどのクラスに属するかを識別するという問題が基本的です。
この識別問題は線形識別器というモデルを使うことで解くことができます。
この記事では、実装が簡単で高性能な線形識別器、AdaGrad+RDAの解説を行います。

AdaGrad+RDAの詳細な解説は以下の論文を参考にしてください。
http://www.magicbroom.info/Papers/DuchiHaSi10.pdf

こちらはAdaGrad+RDAの実装例です。
http://d.hatena.ne.jp/echizen_tm/20140726/1406376207


識別問題は、通常データを2つのクラスに分類します。どうやって分類するかというと、線形識別器が正の値を返したか、負の値を返したかでクラスを分けます。
具体的には、線形識別器は以下の形式をしています。

y = Σ(x_i * w_i)

データを表すベクトル: x = {x_1, x_2, ..., x_i, ...}
重みを表すベクトル: w = {w_1, w_2, ..., w_i, ...}

要するに、データベクトルと重みベクトルの内積の値を返すのが線形識別器です。この内積の値が正か負かで、2つのクラスに分類します。
ここで必要なのは、データが適切に分類されるように重みベクトルを決定することです。この重みベクトルを決める良い方法がAdaGrad+RDAです。


AdaGrad+RDAはオンライン学習のアルゴリズムです。オンライン学習はデータを1つ与えるごとに重みを良い方向に更新していきます。一度の処理で扱うデータが1つであることと、新しいデータを得るごとに重みを更新できることで、近年の大規模データを扱うのに非常に適しています。
具体的にはAdaGrad+RDAは以下の最適化問題を解きます。

f(x, w) = 任意の損失関数
g_i = Σgrad_i(f(x_t, w_t))  # 損失関数の勾配の要素の和
h_i = Σ(grad_i(f(x_t, w_t)) * grad_i(f(x_t, w_t)))  # 損失関数の勾配の要素の二乗の和

min (Σ(g_i * w_i)/t + Σ(h_i * w_i^2)/(2t) + λ|w|)


ちょっとわかりにくいので、細かく見ていきます。
f(x, w)は任意の損失関数です。損失関数というのは、データの分類に失敗するような重みを持っているほど大きな値をとる関数です。例えば、ヒンジ損失関数というのが一般的です。これは以下の形をしています。

f(x, w) = max(0, -yΣ(x_i * w_i))

y = {1, -1}
1か-1かでxが属するクラスを表す

Σ(x_i * w_i)は記事の最初のほうで述べた線形識別器です。なので線形識別器が返す符号と正解(y)の符号が同じ場合には、-yΣ(x_i * w_i)は負の値になるのでヒンジ損失関数は0を返します(=線形識別器の返す答えと正解が一致したので損失がない)。逆に線形識別器の返す符号と正解(y)の符号が違う場合には、そのまま線形識別器の返す値の絶対値がヒンジ損失関数の値になります。
このヒンジ損失関数の勾配を計算します。勾配というのは関数をベクトルxの要素それぞれで微分したものを並べたベクトルです。
線形識別器が正解した場合は損失がないので以下ではf(x, w) = -yΣ(x_i * w_i)について考えます。

grad_i(f(x, w))  # 勾配のi番目の要素 = 損失関数fをw_iで偏微分したもの
= ∂-yΣ(x_i * w_i) / ∂w_i = -y * x_i

AdaGrad+RDAにおいては、損失関数はなんでも良いのですが、イメージがつかみにくい場合は上記のヒンジ損失を入れて考えてみてください。


さて、g_i = Σgrad_i(f(x_t, w_t))ですが、これはx_t(t番目のデータ)とw_t(t-1番目のデータまで学習したあとの重み)を使って計算した勾配の要素の合計です。
同様に、h_i = Σ(grad_i(f(x_t, w_t)) * grad_i(f(x_t, w_t))) は勾配の要素の二乗の合計です。


gとhの説明が済んだので、min (Σ(g_i * w_i)/t + Σ(h_i * w_i^2)/(2t) + λ|w|)の説明をします。この式はRegret損失と呼ばれるものを最小化するようになっているのですが、Regret損失の説明は面倒なのでパスします。とにかくこの式を最小化するといい感じの重みが出来ると考えてください。
第1項Σ(g_i * w_i)/tは勾配の要素の和と(現時点での)重みの内積を(現時点での)データ数で割ったものです。詳細は省きますが、通常の損失関数の最小化に該当する部分です。
第2項Σ(h_i * w_i^2)/(2t)は勾配の要素の二乗の和と(現時点での)重みの要素の二乗の内積を(現時点での)データ数*2で割ったものです。proximal term(和訳は不明)と呼ばれているもので、この項によってAROWのような適応的な重みの更新を可能にしています。
第3項はL1正則化のregularization term(正則化項)というもので、これを入れることで過学習(学習用のデータは分類できるが未知のデータはうまく分類できないような、良くない学習)を抑制します。λは適当な正の実数の係数で、自由に決めて良いのですが、この値が大きいほど正則化が強く効きます。


上記の最適化問題を解くと以下の式が得られます。

|g_i/t| < λの場合:
w_i = 0

g_i/t > λの場合:
w_i = t(-g_i/t + λ)/h_i

g_i/t < -λの場合:
w_i = t(-g_i/t - λ)/h_i

この式を用いることで、例えばヒンジ損失関数を使う場合、以下のような学習ができます。

1: 重みベクトルを0で初期化するw = {0, 0, ...}

2: データ(y_1, x_1)が入力される。
y_1 = 1
x_1 = {x_11, x_12, ...}

3: データ数(t)を1つ増やす。
t += 1

4: ヒンジ損失関数の勾配を計算する。
grad_i(f(x_1, w)) = - y_1 * x_1i

5: g_iを計算する。
g_i += grad_i(f(x_1, w))

6: h_iを計算する。
h_i += (grad_i(f(x_1, w)) * grad_i(f(x_1, w)))

7: g_i/tとλを比較して以下のどれかをする。
w_i = 0
w_i = t(-g_i/t + λ)/h_i
w_i = t(-g_i/t - λ)/h_i

8: データ(y_2, x_2)が入力される。
(2:以降の処理と同じ。以下、データが無くなるまで繰り返し)

この処理を行うことで最適な重みベクトル(w)を計算することが出来ます。
AdaGrad+RDAは上記のように、自由に損失関数を選ぶことが出来るという利点があります。また、regularization term(L1正則化)によって、更新される重みgの大きさがλぶん引かれている(重みがλ以下の場合は0になる)のと、proximal termに含まれるhによって更新される重みの大きさが適応的になっている(勾配の大きな事例は更新量が小さくなる)のが特徴です。