平均化パーセプトロンの効率的な計算

概要

パーセプトロンは学習事例を受け取り重みベクトルを更新する、という処理を反復した後に重みベクトルを出力する
平均化パーセプトロンは過去の反復で学習した重みベクトルの平均を出力する
平均化パーセプトロンは実装が簡単でありながら、良い予測精度が出ることが多い
素直に平均化パーセプトロンの出力を計算しようとすると各反復における重みベクトルを保持する必要がありメモリ的に学習が非効率であるため、実際には今回メモする方法で実装されることが多い

準備

パーセプトロンを学習するにあたって利用する表記は以下のとおり。

N: 素性の数
x: 学習事例。実数値のN次元ベクトル
y: 学習事例に対するラベル。 {-1, 1}
D: N個の学習事例からなる学習データ {(x_i, y_i)} (1 <= i <= K)
w: 重みベクトル。実数値のN次元ベクトル
dot(a, b): 二つのベクトルの内積を返す
sign(x): 1 if x >= 0 else -1

パーセプトロン

パーセプトロンの学習の擬似コードは次の通り。学習事例を受け取り、予測ラベルが正解ラベルと一致しなかった場合に、重みベクトルを更新する。

w = [0, ..., 0] ### N次元
for (x_i, y_i) in D
  y = sign(dot(x_i, w))
  if y != y_i
    u = y_i * x_i ### x_iの要素に対してy_iを掛ける
    w += u
return w

平均化パーセプトロン

平均化パーセプトロンの効率的な学習の擬似コードは以下の通り。パーセプトロンと違うところは、更新回数を覚えておくこと、またパラメータとしてw_all、w_avgが増えていること。このw_avgが"過去の反復で学習した重みベクトルの平均"となっている。

w = [0, ..., 0] ### N次元
w_all = [0, ..., 0] ### N次元
t = 1 ### 更新回数
for (x_i, y_i) in D
  y = sign(dot(x_i, w))
  if y != y_i
    u = y_i * x_i ### x_iの要素に対してy_iを掛ける
    w += u
    w_all += t * u ### uの要素に対してtを掛ける
    t += 1
w_avg = w - w_all / t ### w_allの要素に対してTで割る
return w_avg

では、なぜこのようにしてw_avgが計算されるのかを考えてみる。ここで、u_tをt回目の更新における重みの更新幅とすると、各更新の重みベクトルは次のような関係にある。

$$ \begin{eqnarray} \mathbf{w}_1 &=& \mathbf{0} \\
\mathbf{w}_2 &=& \mathbf{w}_1 + \mathbf{u}_1\\
\mathbf{w}_3 &=& \mathbf{w}_2 + \mathbf{u}_2\\
\mathbf{w}_4 &=& \mathbf{w}_3 + \mathbf{u}_3\\
\end{eqnarray} $$

このことから、例えばt=4のときのw_avgは次のように計算することができる。

$$ \begin{eqnarray} \mathbf{ w}_{avg} &=& \frac{(\mathbf{w}_1 + \mathbf{w}_2 + \mathbf{w}_3 + \mathbf{w}_4)}{4} \\
&=& \frac{(\mathbf{w}_1 + (\mathbf{w}_1 + \mathbf{u}_1) + (\mathbf{w}_2 + \mathbf{u}_2) + (\mathbf{w}_3 + \mathbf{u}_3))}{4} \\
&=& \frac{(\mathbf{w}_1 + (\mathbf{w}_1 + \mathbf{u}_1) + (\mathbf{w}_1 + \mathbf{u}_1 + \mathbf{u}_2) + (\mathbf{w}_2 + \mathbf{u}_2 + \mathbf{u}_3))}{4} \\
&=& \frac{(\mathbf{w}_1 + (\mathbf{w}_1 + \mathbf{u}_1) + (\mathbf{w}_1 + \mathbf{u}_1 + \mathbf{u}_2) + (\mathbf{w}_1 + \mathbf{u}_1 + \mathbf{u}_2 + \mathbf{u}_3))}{4} \\
&=& \frac{(\mathbf{0} + (\mathbf{0} + \mathbf{u}_1) + (\mathbf{0} + \mathbf{u}_1 + \mathbf{u}_2) + (\mathbf{0} + \mathbf{u}_1 + \mathbf{u}_2 + \mathbf{u}_3))}{4} \\
&=& \frac{(3 \mathbf{u}_1 + 2 \mathbf{u}_2 + \mathbf{u}_3)}{4} \\
&=& \frac{4 (\mathbf{u}_1 + \mathbf{u}_2 + \mathbf{u}_3)}{4} - \frac{(\mathbf{u}_1 + 2 \mathbf{u}_2 + 3 \mathbf{u}_3)}{4} \\
&=& \mathbf{w}_4 - \frac{(\mathbf{u}_1 + 2 \mathbf{u}_2 + 3 \mathbf{u}_3)}{4} \end{eqnarray} $$

単純に毎回wをw_allに足しこんでいって、最後に更新回数で割っても同様の結果になるが、更新された要素のみを保持する方が足し込む数が減るので、計算が効率的。