確率的勾配降下法

下記の和の形の目的関数を最小化する問題を扱う。

${\displaystyle Q(w)=\sum _{i=1}^{n}Q_{i}(w)}$

パラメータ ${\displaystyle w^{*}}$ はQ(w) を最小化するように推定する。典型的には、${\displaystyle Q_{i}}$ は i 番目の訓練データ。

古典的な統計学において、和の最小化問題は、最小二乗問題や最尤推定問題などにあらわれる。一般的なケースでは、和を最小化する推定量はM推定量と呼ぶ。しかしながら、Thomas S. Fergusonの例^[3]などで示されるように、いくつかの最尤推定の問題において、最小解ではなく局所解を要求するだけでも制限が厳しすぎると長い間認識され続けてきた。それゆえ、現代の統計理論家は最尤関数の停留点(微分がゼロになる点)を考慮する事が多くなった。

和の最小化問題は経験損失最小化（英語版）の問題にも現れる。${\displaystyle Q_{i}(w)}$ の値が i 番目の訓練データであるならば、Q(w) が経験損失である。

上記の関数 Q を最小化する際、標準的な最急降下法（バッチ学習）では、下記の反復を繰り返す。

${\displaystyle w:=w-\eta \nabla Q(w)=w-\eta \sum _{i=1}^{n}\nabla Q_{i}(w)}$

${\displaystyle \eta }$ はステップサイズと呼ばれる。機械学習においては学習率（英語版）とも呼ばれる。

確率分布がパラメータが一つの指数型分布族などで、勾配の総和の計算が、小さな計算量で出来てしまう事もあるが、一つ一つの勾配を計算して総和を取らないといけない事も多い。そのような場合、和の全体ではなく、和の一部分だけを計算する事で、1回の反復の計算量を小さくする事ができる。これは大規模な機械学習の問題で効果的である^[4]。

確率的勾配降下法（オンライン学習）では、Q(w) の勾配は、1つの訓練データから計算した勾配で近似する。

上記の更新を1つ1つの訓練データで行い、訓練データ集合を一周する。収束するまで訓練データ集合を何周もする。一周するたびに訓練データはランダムにシャッフルする。AdaGrad などの適応学習率のアルゴリズムを使用すると収束が速くなる。

擬似コードでは、確率的勾配降下法は下記になる。

パラメータ ${\displaystyle w}$ と学習率 ${\displaystyle \eta }$ の初期値を選ぶ
while 収束するか所定の反復回数まで反復する do
    ${\displaystyle Q_{i}}$（訓練データ）をランダムにシャッフルする
    for each i = 1, 2, ..., n do
        ${\displaystyle \!w:=w-\eta \nabla Q_{i}(w)}$

全てではないが複数の訓練データで勾配を計算する方法をミニバッチと言う。この方法は、コンピュータのSIMDを有効活用でき計算を高速化できる。また、複数の訓練データを使うので収束がよりなめらかになる事もある。

確率的勾配降下法の収束性は凸最適化と確率近似の理論を使い解析されている。目的関数が凸関数もしくは疑似凸関数であり、学習率が適切な速度で減衰し、さらに、比較的緩い制約条件を付ければ、確率的勾配降下法はほとんど確実に最小解に収束する。目的関数が凸関数でない場合でも、ほとんど確実に局所解に収束する^[5][6]。これは Robbins-Siegmund の定理による^[7]。

${\displaystyle Q_{i}}$（訓練データ）がランダムにシャッフルされる事により、確率的に局所解にはまりにくくなる効果がある。

Summarize Timeline Top Qs Fact Check

基本的な確率的勾配降下法に対して多くの改良が提案されている。特に、機械学習において、ステップサイズ（学習率）の調整は重要問題として認識されている。学習率を大きくしすぎると発散し、小さくしすぎると収束まで遅くなる。

1951年に Herbert Robbins と Sutton Monro が発表^[8]。学習率をイテレーション回数の逆数で減衰させる方法。Robbins-Monro法とも言われる。

${\displaystyle \eta _{t}={\frac {\eta _{0}}{t}}}$

1983年に Yurii Nesterov が発表^[9]。

${\displaystyle {\begin{aligned}x_{0}&=w_{0}\\x_{t}&=w_{t-1}-\eta \nabla Q_{i}(w_{t-1})\\w_{t}&=x_{t}+{\frac {t-1}{t+2}}(x_{t}-x_{t-1})\end{aligned}}}$

1986年にデビッド・ラメルハートらがバックプロパゲーションと共に提案した方法^[10]。

${\displaystyle {\begin{aligned}\Delta w&:=\eta \nabla Q_{i}(w)+\alpha \Delta w\\w&:=w-\Delta w\end{aligned}}}$

1988年に David Ruppert が提案した方法^[11]。

${\displaystyle {\bar {w}}={\frac {1}{t}}\sum _{i=1}^{t}w_{i}}$

を計算し、最終的にパラメータの平均値を学習結果とする。

2009年に John Langford らが発表した方法^[12]。L1 正則化を含む場合、確率的勾配降下法だとパラメータが 0 になりにくいが、K 回毎にパラメータの大きさが θ 以下であれば、0にする方法。

2009年に Lin Xiao が発表した方法^[13][14]。目的関数が下記のように汎化能力を高めるために L1 正則化を含む場合、確率的勾配降下法だとパラメータが 0 になりにくく、そのための対策をした方法。以下、この手法では Q(w) には ${\displaystyle \lambda \|w\|_{1}}$ を含めずに、L1 正則化の効果を実現する。

${\displaystyle Q(w)+\lambda \|w\|_{1}}$

まず、勾配の平均を計算する。

${\displaystyle {\overline {g}}_{t}={\frac {1}{t}}\sum _{t'=1}^{t}\nabla Q(w)_{t'}}$

その上で、パラメータの更新は以下の通り。ここでパラメータの初期値は0としている。

${\displaystyle w_{i}:={\begin{cases}0&{\text{if }}|{\overline {g}}_{t,i}|\leq \lambda ,\\-{\dfrac {\sqrt {t}}{\gamma }}\left({\overline {g}}_{t,i}-\lambda \operatorname {sgn}({\overline {g}}_{t,i})\right)&{\text{otherwise.}}\end{cases}}}$

L1 正則化と L2 正則化を

${\displaystyle Q(w)+\lambda \|w\|_{1}+{\frac {\sigma }{2}}\|w\|_{2}^{2}}$

の形で混ぜる場合は、このようになる。

${\displaystyle w_{i}:={\begin{cases}0&{\text{if }}|{\overline {g}}_{t,i}|\leq \lambda ,\\-{\dfrac {1}{\sigma }}\left({\overline {g}}_{t,i}-\lambda \operatorname {sgn}({\overline {g}}_{t,i})\right)&{\text{otherwise.}}\end{cases}}}$

以下のように、${\displaystyle \lambda }$ を少しずつ大きくしていくと、疎になる度合いを徐々に高めていける。

${\displaystyle \lambda =\lambda _{0}+\rho /{\sqrt {t}}}$

2011年に John Duchi らが発表した方法^[15]。${\displaystyle \circ }$ はアダマール積（要素ごとの積）。下記計算、全てパラメータごと（要素ごと）に計算する。${\displaystyle \epsilon }$ は無限大に発散させないための正の小さな定数。

${\displaystyle {\begin{aligned}r_{0}&=\epsilon \\r_{t}&=r_{t-1}+\nabla Q_{i}(w)\circ \nabla Q_{i}(w)\\\eta _{t}&={\frac {\eta _{0}}{\sqrt {r_{t}}}}\\w_{t+1}&=w_{t}-\eta _{t}\circ \nabla Q_{i}(w)\end{aligned}}}$

正則化双対平均化法と AdaGrad を組み合わせる方法が、AdaGrad の発表と共に2011年に出ている^[14]。

${\displaystyle {\begin{aligned}u&:=u+\nabla Q(w)\\r&:=r+\nabla Q_{i}(w)\circ \nabla Q_{i}(w)\\w_{i}&:={\begin{cases}0&{\text{if }}|u_{i}|/t\leq \lambda ,\\-\operatorname {sgn}(u_{i}){\dfrac {\eta t}{\sqrt {r_{i}}}}\left({\dfrac {|u_{i}|}{t}}-\lambda \right)&{\text{otherwise.}}\end{cases}}\end{aligned}}}$

2012年に Tijmen Tieleman らが発表した方法^[16]。AdaGrad の変形。勾配の2乗の指数移動平均を取るように変更。${\displaystyle \beta =0.9}$ などを使用。

${\displaystyle {\begin{aligned}r_{t}&=\beta r_{t-1}+(1-\beta )\nabla Q_{i}(w)\circ \nabla Q_{i}(w)\\\eta _{t}&={\frac {\eta _{0}}{\sqrt {r_{t}+\epsilon }}}\\w_{t+1}&=w_{t}-\eta _{t}\circ \nabla Q_{i}(w)\end{aligned}}}$

2012年に Matthew D. Zeiler が発表した方法^[17]。AdaGrad や RMSProp の変形。初期学習率のハイパーパラメータがなくなっている。

${\displaystyle {\begin{aligned}r_{t}&=\beta r_{t-1}+(1-\beta )\nabla Q_{i}(w)\circ \nabla Q_{i}(w)\\v_{t}&={\frac {{\sqrt {s_{t}}}+\epsilon }{{\sqrt {r_{t}}}+\epsilon }}\circ \nabla Q_{i}(w)\\s_{t+1}&=\beta s_{t}+(1-\beta )v_{t}\circ v_{t}\\w_{t+1}&=w_{t}-v_{t}\end{aligned}}}$

2014年に Jascha Sohl-Dickstein らが発表した方法^[18]。確率的勾配降下法と記憶制限準ニュートン法の L-BFGS を組み合わせた方法。二次収束するようになり、収束が AdaGrad などよりも速くなった。

2015年に Diederik P. Kingma らが発表した方法^[19]。AdaGrad, RMSProp, AdaDelta の変形。AdaGrad や Sum of Functions Optimizer よりも収束が速くなった。ハイパーパラメータは ${\displaystyle \alpha =0.001,\beta _{1}=0.9,\beta _{2}=0.999,\epsilon =10^{-8}}$ を推奨。イテレーション回数 t は 1 から始める。

${\displaystyle {\begin{aligned}m_{0}&=v_{0}=0\\m_{t}&=\beta _{1}m_{t-1}+(1-\beta _{1})\nabla Q_{i}(w)\\v_{t}&=\beta _{2}v_{t-1}+(1-\beta _{2})\nabla Q_{i}(w)\circ \nabla Q_{i}(w)\\{\hat {m}}_{t}&={\frac {m_{t}}{1-\beta _{1}^{t}}}\\{\hat {v}}_{t}&={\frac {v_{t}}{1-\beta _{2}^{t}}}\\w_{t}&=w_{t-1}-\alpha {\frac {{\hat {m}}_{t}}{{\sqrt {{\hat {v}}_{t}}}+\epsilon }}\end{aligned}}}$

2019年のICLRでLiangchen Luoらが発表した方法^[20]。 Adamに学習率の制限(Bound)を加え、ステップごとにSGDへ連続的に変化させることによって、Adamの収束速度とSGDの汎化性能の両立を目指した。論文中でのハイパーパラメータと学習率の下限・上限は ${\displaystyle \alpha =0.001,\beta _{1}=0.9,\beta _{2}=0.999,\eta _{l}(t)=0.1-{\frac {0.1}{(1-\beta _{2})t+1}},\eta _{u}(t)=0.1+{\frac {0.1}{(1-\beta _{2})t}}}$であり、Adamと同様にt=1から始める。

${\displaystyle {\begin{aligned}m_{0}&=v_{0}=0\\g_{t}&=\nabla Q_{i}(w)\\m_{t}&=\beta _{1}m_{t-1}+(1-\beta _{1})g_{t}\\v_{t}&=\beta _{2}v_{t-1}+(1-\beta _{2})g_{t}^{2},{\text{and }}V_{t}={\text{diag}}(v_{t})\\{\hat {\eta }}_{t}&={\text{Clip}}({\frac {\alpha }{\sqrt {V_{t}}}},\eta _{l}(t),\eta _{u}(t))\\w_{t}&=w_{t-1}-{\frac {{\hat {\eta }}_{t}}{\sqrt {t}}}\circ m_{t}\end{aligned}}}$

パラメータ ${\displaystyle w}$ の初期値はなんらかの確率分布からランダムに選ぶ。どの確率分布を使うかは、最小値の近傍に収束する確率に影響がある。しかし、何が適切な確率分布かはモデル次第である。ニューラルネットワークの場合についてはバックプロパゲーションの項目を参照。