確率的勾配降下法

確率的勾配降下法（Stochastic Gradient Descent, SGD）

確率的勾配降下法（SGD）は、機械学習や深層学習で広く用いられる最適化アルゴリズムの一つです。特に、大規模なデータセットを扱う場合に、計算効率の高さから頻繁に利用されます。SGDは、目的関数を最小化するパラメータを反復的に更新することで、モデルの学習を進めます。

背景

機械学習では、多くの場合、以下の形式の目的関数を最小化することが目標となります。

Q(w) = Σ [Qi(w)] (i=1 to n)

ここで、`w`はモデルのパラメータ、`Qi(w)`は個々の訓練データに対する損失関数を表します。古典的な統計学では、このような和の形をした最小化問題は、最小二乗法や最尤推定などで現れます。

最急降下法（バッチ学習）では、目的関数全体の勾配を使ってパラメータを更新しますが、SGDでは、データの一部（または1つ）だけを用いて勾配を計算し、パラメータを更新します。このため、SGDはオンライン学習に適しており、大規模なデータセットでも効率的に学習を進めることができます。

反復法

SGDでは、以下の手順でパラメータを更新します。

1. 初期化: パラメータ`w`と学習率`η`を初期化します。
2. 反復: 以下の処理を収束するまで繰り返します。
- 訓練データをランダムにシャッフルします。
- 各訓練データに対して、以下のパラメータ更新を行います。

w := w - η∇Qi(w)

ここで、`∇Qi(w)`は、訓練データ`i`に対する損失関数の勾配を表します。

このプロセスを繰り返すことで、パラメータ`w`が目的関数を最小化する値に近づいていきます。通常、訓練データセットを複数回繰り返して学習を行い、各エポックごとに訓練データをシャッフルします。また、学習率`η`を適切に調整することで、収束速度や精度を向上させることが可能です。

ミニバッチ法

SGDの変種として、ミニバッチ法があります。ミニバッチ法では、一度に複数の訓練データを使って勾配を計算します。これにより、計算効率が向上するだけでなく、収束が安定する効果も期待できます。

収束性

SGDの収束性は、凸最適化と確率近似の理論を用いて解析されています。目的関数が凸関数である場合や、学習率が適切に減衰する場合には、SGDはほとんど確実に最小解に収束します。また、目的関数が非凸関数である場合でも、適切な条件の下で局所解に収束することが知られています。訓練データをランダムにシャッフルすることで、局所解にはまりにくくなる効果があります。

学習率の調整

SGDでは、学習率の調整が非常に重要です。学習率が大きすぎるとパラメータが発散し、小さすぎると収束が遅くなります。そのため、様々な学習率調整方法が提案されています。

確率的近似法

学習率をイテレーション回数の逆数で減衰させる方法です。Robbins-Monro法とも呼ばれます。

ηt = η0 / t

Nesterovの加速勾配降下法

パラメータの更新にモメンタムの概念を取り入れた方法です。

x0 = w0
xt = wt-1 - η∇Qi(wt-1)
wt = xt + (t-1)/(t+2) (xt - xt-1)

モメンタム法

パラメータ更新に過去の勾配の情報を加えることで、収束を加速させる方法です。

Δw := η∇Qi(w) + αΔw
w := w - Δw

平均化法

パラメータの平均値を学習結果とする方法です。

w_bar = (1/t) Σ [wi] (i=1 to t)

Truncated Gradient

L1正則化を含む場合に、パラメータが0になりにくいという問題に対処する方法です。パラメータの大きさが一定以下であれば、0に設定します。

正則化双対平均化法

L1正則化を効率的に行う方法です。勾配の平均を計算し、それに基づいてパラメータを更新します。L1正則化項を直接目的関数に含めずに、L1正則化の効果を実現します。

g_bar_t = (1/t) Σ[∇Q(w)t'] (t'=1 to t)
wi := 0 if |g_bar_t,i| <= λ
wi := -sqrt(t)/γ (g_bar_t,i - λsgn(g_bar_t,i)) otherwise

AdaGrad

学習率をパラメータごとに調整する方法です。勾配の二乗和を用いて学習率を調整します。

r0 = ϵ
rt = rt-1 + ∇Qi(w) ∘ ∇Qi(w)
ηt = η0 / sqrt(rt)
wt+1 = wt - ηt ∘ ∇Qi(w)

RMSProp

AdaGradの改良版です。勾配の二乗の指数移動平均を用いて学習率を調整します。

rt = βrt-1 + (1-β)∇Qi(w) ∘ ∇Qi(w)
ηt = η0 / sqrt(rt + ϵ)
wt+1 = wt - ηt ∘ ∇Qi(w)

AdaDelta

RMSPropの変形です。初期学習率のハイパーパラメータをなくしています。

rt = βrt-1 + (1-β)∇Qi(w) ∘ ∇Qi(w)
vt = sqrt(st) + ϵ / sqrt(rt) + ϵ ∘ ∇Qi(w)
st+1 = βst + (1-β)vt ∘ vt
wt+1 = wt - vt

Sum of Functions Optimizer

確率的勾配降下法と記憶制限準ニュートン法のL-BFGSを組み合わせた方法です。

Adam

AdaGrad, RMSProp, AdaDeltaの変形です。勾配の指数移動平均と二乗の指数移動平均を組み合わせて使用します。

m0 = v0 = 0
mt = β1mt-1 + (1-β1)∇Qi(w)
vt = β2vt-1 + (1-β2)∇Qi(w) ∘ ∇Qi(w)
m_hat_t = mt / (1 - β1^t)
v_hat_t = vt / (1 - β2^t)
wt = wt-1 - α * m_hat_t / (sqrt(v_hat_t) + ϵ)

AdaBound

Adamに学習率の制限(Bound)を加えた手法で、Adamの収束速度とSGDの汎化性能の両立を目指します。

m0 = v0 = 0
gt = ∇Qi(w)
mt = β1mt-1 + (1-β1)gt
vt = β2vt-1 + (1-β2)gt^2, and Vt = diag(vt)
η_hat_t = Clip(α / sqrt(Vt), ηl(t), ηu(t))
wt = wt-1 - η_hat_t / sqrt(t) ∘ mt

パラメータの初期値

パラメータ`w`の初期値は、何らかの確率分布からランダムに選ばれます。適切な確率分布を選択することは、学習の効率と精度に影響します。ニューラルネットワークの場合は、バックプロパゲーションの項目を参照するとよいでしょう。

平均・分散の調整

入力データの平均と分散が極端に異なる場合、SGDの学習がうまくいかないことがあります。そのため、訓練データの正規化を行い、平均0分散1になるように調整することが推奨されます。

正規化オンライン学習

学習データがリアルタイムで手に入り、事前に正規化できない場合に、データの絶対値の最大値を追跡して調整する方法が提案されています。

まとめ

確率的勾配降下法（SGD）は、機械学習において非常に重要な最適化アルゴリズムであり、その変種を含めると多岐にわたる手法が存在します。適切な学習率の調整や、データの正規化を行うことで、SGDの性能を最大限に引き出すことが可能です。

参考文献

もう一度検索