1. 導入
私達が実際に機械学習で行っていることは誤差関数を最小にすることや尤度関数を最大にするパラメータを求めることですが、関数の最小点を見つけることを「最適化」とすると、関数によっては最適化はとても難しいものとなり、単なる行列計算では求めることができない場合があります( むしろそのような場合がほとんどです ).
その際に勾配を用いたアプローチが効果的とされています.
2. 勾配降下法
関数の勾配を用いて、最適化を図る手法を勾配降下法( Gradient Descent: GD )と呼びます.
横軸を重み\( w \)、縦軸を誤差\( E(w) \)とした時、誤差が最小となる重みを\( w^{opt} \)とし、現在の重みを\( w^{old} \)とします. 学習によって最適な重み\( w^{opt} \)へ近づくように重みの更新を行うのですが、その際知りたいのは重みをどの方向へ動かせば良いのかということで、それには\( w^{old} \)上での傾き(勾配)を用いることで解決されます. よって、\( w^{old} \)の地点の傾きから、変化量 \( \Delta w \)を求め、新たな重み\( w^{new} \)を求めます.
$$w^{new}\; =\; w^{old}\; +\; \Delta w \tag{1}$$
このとき傾きは重み\( w \)のみで\( E(w) \)を微分したものとして、\( \frac{\partial E}{\partial w} \)と表すことができます.
図のように傾きが正のとき\( w \)を減少させ、負のときは\( w \)を増加させます. したがって、変化量\( \Delta w \)は関数が確実かつ最も急に減らすため、学習係数\( \eta \)を用いて
$$\Delta w\; =\; -\eta \frac{\partial E}{\partial w} \tag{2}$$
と表すことができます. 勾配降下法はこれを繰り返すことで、\( w^{opt} \)に近づいていきます.
2.1 学習係数\( \eta \)について
\( E(w + \Delta w) < E(w) \)が成り立つためには、学習係数\( \eta \)は正の小さな値でなければなりません.
目的関数\( E(w) \)について、例えば一変数の関数では以下のように近似できます.
$$E\left( w +\Delta w \right)\; \approx \; E\left( w \right)\; +\; \Delta w\frac{d E\left( w \right)}{d w} ( \Delta w は小さい値) \tag{3}$$
このとき\( \Delta w\;=\;-\eta \frac{d E(w)}{d w} \)にとると
$$E\left( w +\Delta w \right)\; \approx \; E\left( w \right)\; -\; \eta \left( \frac{d E\left( w \right)}{d w} \right)^{2}\; <\; E\left( w \right) \tag{4}$$
が成立し、\( E(w + \Delta w) < E(w) \)と言えます.
そのため、関数の値を確実に減らすには
$$E\left( w +\Delta w \right)\; \approx \; E\left( w \right)\; +\; \Delta w\frac{d E\left( w \right)}{d w} ( \Delta w は小さい値)$$
が成り立たなければならないため、\( \eta \)は正の小さい値である必要があります.
2.2 勾配降下法の問題点
勾配降下法はデータ量が多いとその分の計算量も非常に大きなものになってしまいます.
例えば目的関数\( E(\boldsymbol{x}) \)を以下のものとします( 機械学習の目的関数は大体がこの形をとると思います ). $$E\left( \boldsymbol{w} \right)\; =\; \sum^{N}{y\left( \boldsymbol{x}_n \right)} \tag{5}$$
このとき目的関数を勾配降下法で解くために重み\( w \)で微分を求めても、\( N \)の分だけの和をとる形になってしまいます.
$$\frac{\partial E\left( \boldsymbol{w} \right)}{\partial \boldsymbol{w}}=\; \sum^{N}{\frac{y\left( \boldsymbol{x}_n \right)}{\partial \boldsymbol{w}}} \tag{6}$$
$$\boldsymbol{w}=\boldsymbol{w} -\eta \sum^{N}{\frac{y\left( \boldsymbol{x}_n \right)}{\partial \boldsymbol{w}}} \tag{7}$$
つまり、勾配降下法でパラメータを更新するにはこの微分を毎回求める必要があるため、その回数分\( \frac{\partial \; y\left( \boldsymbol{x}_n \right)}{\partial \boldsymbol{w}} \)を計算しなければなりません.
3. 確率的勾配降下法
勾配降下法の問題を解決する新たにかわる手法として確率的勾配降下法( Stochastic Gradient Descent: SGD )です.
単純に1つのデータごとに \( \frac{\partial y\left( \boldsymbol{x}_{n} \right)}{\partial \boldsymbol{w}} \) を計算し、重み\( w \)を更新する手法なのですが、勾配降下法よりも正確さや速度において優れていると言われています. 勾配降下法同様、こちらもデータ全体を何周かまわす必要がありますが、勾配降下法の1回分と同じ計算量でN回移動できるため、非常に高速に解にたどり着くことが可能です.
$$\boldsymbol{w}=\boldsymbol{w} -\eta \frac{\partial E_n\left( \boldsymbol{w} \right)}{\partial \boldsymbol{w}} \tag{8}$$
また確率的勾配降下法は勾配降下法と比べ、以下のような利点があります.
- 局所最適解にトラップしにくい（勾配法の初期値依存問題への解決）
- 冗長な学習データがある場合，勾配法よりも学習が高速
- 学習データを収集しながら逐次的に学習可能
ちなみに、ここでの「確率的」とは学習するデータの順番がランダムであり、実行するたびに結果が変わること示すものです.
3.1 ミニバッチ
確率的勾配降下法について、データを全て見るのではなく計算できるある程度の固まり単位で勾配を計算していく方法をミニバッチ(Minibatch)と言います.
サンプルの数を\( m \)としたとき、それが十分なサイズならば\( \nabla E\)について
$$\nabla E \approx \frac{\sum^{M}{E_{j}}}{m} \tag{9}$$
と近似することができます. このときのパラメータの更新は以下のようになります.
$$\boldsymbol{w} = \boldsymbol{w} - \frac{\eta }{M}\sum_{j}^{M}{\frac{\partial E}{\partial \boldsymbol{w}}} \tag{10}$$
$$(Mはミニバッチのサイズ)$$
3.2 オンライン学習とバッチ学習
勾配降下法と確率的勾配降下法について説明しましたが、これらの決定的な違いは勾配の使い方であり、この記事のテーマである確率的勾配降下法はオンライン学習、勾配降下法はバッチ学習と分けて考えることができます.
オンライン学習とはデータを１つ見たらパラメータを更新するという作業を繰り返しことを指し、対してバッチ学習はデータを全部読み込んでからパラメータを更新するという作業を繰り返すことを指します.
それぞれの欠点としては、オンライン学習の方がパラメータの収束が不安定で、データによっては学習率をうまい具合に設定しないと収束しません. またバッチ学習は計算コストが大きく、使用するメモリの量も多くなる傾向があります.
4. ロジスティック回帰の学習
１次元のロジスティック回帰の学習を確率的勾配降下法を使って導きます.
\( f\left( \boldsymbol{x} \right)\;=\;\boldsymbol{w}^{T}\boldsymbol{x}\; +\; b \)によって1次元に写像された\( m \)次元ベクトルであるデータ\( \boldsymbol{x} \)にラベル\( d \in { 0, 1} \)が対応しているとき、事後分布は\( p\left( d | \boldsymbol{x} \right)\; =\; y\left( \boldsymbol{x} \right)^{d}\left( 1\; -\; y\left( \boldsymbol{x} \right) \right)^{1-d} \)と表現することができます.
このとき入力からラベルを推定するために重み\( \boldsymbol{w} \)について最尤推定を行うとき、対数をとって和の形で表し、符号を反転させ最小化を考える場合の目的関数( 損失関数 )は以下のようになります.
$$E(\boldsymbol{w}) = -\sum^{N}{\left[dn\log y(\boldsymbol{x}n) +(1-dn)\log\{1-y(\boldsymbol{x}n)\}\right]} ( 原因不明のエラーのためd_n は dnと表記 )$$
4.1 \( \frac{\partial E}{\partial \boldsymbol{w}} \)の導出
※ 都合により\(d_n\)などの下付き文字を\(dn\)と表記します.
対数尤度関数\(E\)は
$$E(\boldsymbol{w}) = -\sum^{N}{\left[dn\log y(\boldsymbol{x}n) +(1-dn)\log\{1-y(\boldsymbol{x}n)\}\right]} \tag{11}$$
ここで、
$$\begin{align} \log\{1-y\left( \boldsymbol{x}n \right)\} & = \log\left[ 1-\frac{1}{1+\exp \left\{ -(\boldsymbol{w}^{T}\boldsymbol{x}+b) \right\}}\right] \tag{12} \\ & = \log\left[ \frac{\exp \left\{ -(\boldsymbol{w}^{T}\boldsymbol{x}+b) \right\}}{1+\exp \left\{ -(\boldsymbol{w}^{T}\boldsymbol{x}+b) \right\}} \right] \tag{13} \\ & = \log\left[\exp \left\{ -(\boldsymbol{w}^{T}\boldsymbol{x}+b) \right\}y\left( \boldsymbol{x}n \right)\right] \tag{14} \\ & = \log\left[\exp \left\{ -(\boldsymbol{w}^{T}\boldsymbol{x}+b) \right\}\right] + \log y\left( \boldsymbol{x}n \right) \tag{15} \\ & = -(\boldsymbol{w}^{T}\boldsymbol{x}+b) + y\left( \boldsymbol{x}n \right) \tag{16} \end{align}$$
より、
$$\begin{align} E(\boldsymbol{w}) & = -\sum^{N}{\left[dn\log y(\boldsymbol{x}n) +(1-dn)\{ -(\boldsymbol{w}^{T}\boldsymbol{x}+b) + \log y\left( \boldsymbol{x}n \right) \}\right]} \tag{17} \\ & = -\sum^{N}{\left[\log y(\boldsymbol{x}n) +(1-dn)\{ -(\boldsymbol{w}^{T}\boldsymbol{x}+b)\}\right]} \tag{18} \\ & = \sum^{N}{\left[\log \left[1+\exp \left\{ -(\boldsymbol{w}^{T}\boldsymbol{x}+b) \right\}\right] +(1-dn)\{ -(\boldsymbol{w}^{T}\boldsymbol{x}+b)\}\right]} \tag{19} \end{align}$$
ここで\(w\)に対して微分すると、
$$\begin{align} \frac{\partial E}{\partial \boldsymbol{w}} & = \sum^{N}{\left[\frac{y\left( \boldsymbol{x}n \right) \left[ 1+\exp \left\{ -(\boldsymbol{w}^{T}\boldsymbol{x}+b)\right\} -1\right]}{1+\exp \left\{ -(\boldsymbol{w}^{T}\boldsymbol{x}+b) \right\}} + (1-dn)(-0 -\boldsymbol{x}n)\right]} \tag{20} \\ & = \sum^{N}{\left[\{\boldsymbol{x}n - \boldsymbol{x}n \cdot y\left( \boldsymbol{x}n \right)\} - (\boldsymbol{x}n - dn \cdot \boldsymbol{x}n)\right]} \tag{21} \\ & = -\sum^{N}{\{ dn - y\left( \boldsymbol{x}n \right)\}\boldsymbol{x}n}\tag{22} \end{align}$$
となります. よって、
$$\frac{\partial E}{\partial \boldsymbol{w}} = -\sum^{N}{\{ dn - y\left( \boldsymbol{x}n \right)\}\boldsymbol{x}n} \tag{23} $$
4.2 \( \frac{\partial E}{\partial b} \)の導出
\(b\)についても同様に計算すると
$$\frac{\partial E}{\partial b} = -\sum^{N}{\{ dn - y\left( \boldsymbol{x}n \right)\}} \tag{24} $$
4.3 パラメータの更新
このように求めた勾配を用いて、以下のようにして\(\boldsymbol{w}, b\)を更新し、目的関数\(E\)の最小化を行います.
$$\boldsymbol{w}\; =\; \boldsymbol{w}\; -\; \eta \frac{\partial E}{\partial \boldsymbol{w}}$$
$$b\; =\; b\; -\; \eta \frac{\partial E}{\partial b}$$
5. Pythonで実装
5.1 データの生成
0または1でラベル付けされた2種類のデータ集合を生成し、それらをランダムに並べ替えます.
def main():
m, N = 2, 10000
x1, x2 = np.random.randn(N, m), np.random.randn(N, m) + np.array([5, 5])
x = np.vstack((x1, x2))
d1, d2 = np.zeros(N), np.ones(N)
d = np.hstack((d1, d2))
dataset = np.column_stack((x, d))
np.random.shuffle(dataset)
x, d = dataset[:, :2], dataset[:, 2]
w, b = np.random.rand(m), np.random.random()>>> import numpy as np
>>> m, N = 2, 1000
>>> x1, x2 = np.random.randn(N, m), np.random.randn(N, m) + np.array([5, 5])
>>> x = np.vstack((x1, x2))
>>> d1, d2 = np.zeros(N), np.ones(N)
>>> d = np.hstack((d1, d2))
>>> dataset = np.column_stack((x, d))
>>> np.random.shuffle(dataset)
>>> x, d = dataset[:, :2], dataset[:, 2]
>>> x
array([[ 1.89631613, -0.36255756],
[ 0.12282228, 1.12186762],
[ 5.55456376, 3.58391658],
...,
[-0.2250628 , -1.09651331],
[-2.26790372, -0.06684712],
[-0.15449889, 0.34766331]])
>>> d
array([ 0., 0., 1., ..., 0., 0., 0.])5.2 勾配の計算
$$\frac{\partial E}{\partial \boldsymbol{w}} = -\sum^{N}{\{ dn - y\left( \boldsymbol{x}n \right)\}\boldsymbol{x}n} \tag{23}$$
$$\frac{\partial E}{\partial b} = -\sum^{N}{\{ dn - y\left( \boldsymbol{x}n \right)\}} \tag{24}$$
def p_y_given_x(x, w, b):
def sigmoid(a):
return 1.0 / (1.0 + np.exp(-a))
return sigmoid(np.dot(x, w) + b)
def grad(x, d, w, b):
error = d - p_y_given_x(x, w, b)
w_grad = -np.mean(x.T * error, axis=1)
b_grad = -np.mean(error)
return w_grad, b_grad5.3 確率的勾配降下法
$$\boldsymbol{w} = \boldsymbol{w} - \frac{\eta }{M}\sum_{j}^{M}{\frac{\partial E}{\partial \boldsymbol{w}}} \tag{10}$$
$$\boldsymbol{b} = \boldsymbol{b} - \frac{\eta }{M}\sum_{j}^{M}{\frac{\partial E}{\partial b}} \tag{25}$$
def SGD(x, d, w, b, e, eta=0.10, iteration=5, minibatch_size=10):
for _ in range(iteration):
for index in range(0, x.shape[0], minibatch_size):
_x = x[index:index + minibatch_size]
_d = d[index:index + minibatch_size]
w_grad, b_grad = grad(_x, _d, w, b)
w -= eta * w_grad
b -= eta * b_grad
e.append(np.mean(np.abs(d - p_y_given_x(x, w, b))))
return e, w, b5.4 出力結果 - イテレーション毎の誤差(SGD)
5.5 出力結果 - 学習されたパラメータによる\( \boldsymbol{w}^{T}\boldsymbol{x} + b = 0 \)
6. 正則化
モデルの過学習を防ぎ、汎化能力を高めるために追加の項を導入する手法を正則化( Regularization )と言います. 過学習は既知のデータに対する間違い(経験損失)と未知のデータに対する間違い(期待損失、汎化誤差)が離れている状態を指します. 誤解を恐れずに言うと学習データ専用のパラメータになってしまった状態です.
正則化によりもたらされることはモデルに重みを追加することへの罰則です.具体的には、目的関数に正則化項を入れることにより、パラメータの値が大きくなることを抑制しようとします.
正則化にはいくつか種類があり、その中でもL1正則化とL2正則化は代表的でよく使用されます.
L1正則化(Lasso)
- 大小に関わらず同等の罰則
- 多くの重みが0になるため小さなモデルが学習可能
L2正則化(Ridge)
- 大きな重みに対して大きな罰則を与え、小さな重みに対して小さな罰則を与える
- 精度が少々高い
正則化は機械学習において非常に重要であるため、機会があればまとめたいと思います.
7. おまけ
7.1 モメンタム
勾配降下法の収束性能を向上させる手法として、モメンタム( momentum )があります. 勾配のブレが大きいとなかなか収束しないため、それを低減させるために重みの修正量に前回の重みの修正量をいくらか加算する方法です.
def SGD_momentum(x, d, w, b, e, eta=0.10, mu=0.65, iteration=50, minibatch_size=10):
wlist, blist = [w], [b]
def momentum(mu, list):
return mu * (list[1] - list[0])
for _ in range(iteration):
for index in range(0, x.shape[0], minibatch_size):
_x = x[index:index + minibatch_size]
_d = d[index:index + minibatch_size]
w_grad, b_grad = grad(_x, _d, w, b)
if len(wlist) > 1:
w -= eta * w_grad + momentum(mu, wlist)
b -= eta * b_grad + momentum(mu, blist)
wlist.pop(0)
blist.pop(0)
else:
w -= eta * w_grad
b -= eta * b_grad
wlist.append(w)
blist.append(b)
e.append(np.mean(np.abs(d - p_y_given_x(x, w, b))))
return e, w, b7.2 AdaGrad
学習係数を自動的に決定する手法の一つにAdaGradがあります. 過去すべての勾配の2乗和の平方根の逆数を利用します.
def SGD_adagrad(x, d, w, b, e, eta=0.10, iteration=50, minibatch_size=10):
wgrad2sum = np.zeros(x.shape[1])
bgrad2sum = 0
for _ in range(iteration):
for index in range(0, x.shape[0], minibatch_size):
_x = x[index:index + minibatch_size]
_d = d[index:index + minibatch_size]
w_grad, b_grad = grad(_x, _d, w, b)
wgrad2sum += np.power(w_grad, 2)
bgrad2sum += np.power(b_grad, 2)
w -= (eta/np.sqrt(wgrad2sum)) * w_grad
b -= (eta/np.sqrt(bgrad2sum)) * b_grad
e.append(np.mean(np.abs(d - p_y_given_x(x, w, b))))
return e, w, bStochastic Average Gradientなんてのも提案されているみたいですね. 速いらしいです.