確率的勾配降下法

ミニバッチを使い上下に行ったり来たりしながら目的関数の値が減少していく例

確率的勾配降下法（かくりつてきこうばいこうかほう、英: stochastic gradient descent, SGD）は、連続最適化問題に対する勾配法の乱択アルゴリズム。バッチ学習である最急降下法をオンライン学習に改良したアルゴリズムである。目的関数が微分可能な和の形であることを必要とする。

背景

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

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

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

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

和の最小化問題は経験損失最小化（英語版）の問題にも現れる。${\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回の反復の計算量を小さくする事ができる。これは大規模な機械学習の問題で効果的である^[2]。

反復法

確率的勾配降下法（オンライン学習）では、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を有効活用でき計算を高速化できる。また、複数の訓練データを使うので収束がよりなめらかになる事もある。

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

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

学習率の調整方法および変種

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

確率的近似法

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

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

Nesterovの加速勾配降下法

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

${\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年にデビッド・ラメルハートらがバックプロパゲーションと共に提案した方法^[8]。

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

平均化法

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

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

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

Truncated Gradient

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

正則化双対平均化法（Regularized Dual Averaging Method）

2009年に Lin Xiao が発表した方法^[11][12]。目的関数が下記のように汎化能力を高めるために 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}}}$

AdaGrad

2011年に John Duchi らが発表した方法^[13]。${\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年に出ている^[12]。

${\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}}}$

RMSProp

2012年に Tijmen Tieleman らが発表した方法^[14]。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}}}$

AdaDelta

2012年に Matthew D. Zeiler が発表した方法^[15]。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}}}$

Sum of Functions Optimizer

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

Adam

2015年に Diederik P. Kingma らが発表した方法^[17]。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}}}$

AdaBound

2019年のICLRでLiangchen Luoらが発表した方法^[18]。 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}$ の初期値はなんらかの確率分布からランダムに選ぶ。どの確率分布を使うかは、最小値の近傍に収束する確率に影響がある。しかし、何が適切な確率分布かはモデル次第である。ニューラルネットワークの場合についてはバックプロパゲーションの項目を参照。

平均・分散の調整

確率的勾配降下法は入力の値に極端に平均・分散が異なる物が混じると、うまく行かなくなる確率が上がる。よって、モデル自体に線形変換をかけるなどして、訓練データの正規化をして、平均0分散1になるように調整する方が良い。

正規化オンライン学習

学習データがリアルタイムで手に入るなど、事前に平均0分散1に調整できない場合のために、2013年に Stephane Ross らが正規化オンライン学習を発表している^[19]。データの絶対値の最大値を追跡して、それを元に調整する。

脚注

1. Ferguson, Thomas S. (1982). “An inconsistent maximum likelihood estimate”. Journal of the American Statistical Association 77 (380): 831–834. doi:10.1080/01621459.1982.10477894. JSTOR 2287314. 
2. Bottou, Léon; Bousquet, Olivier (2008). The Tradeoffs of Large Scale Learning. Advances in Neural Information Processing Systems. Vol. 20. pp. 161–168.
3. Bottou, Léon (1998). “Online Algorithms and Stochastic Approximations”. Online Learning and Neural Networks. Cambridge University Press. ISBN 978-0-521-65263-6. http://leon.bottou.org/papers/bottou-98x 
4. Kiwiel, Krzysztof C. (2001年). “Convergence and efficiency of subgradient methods for quasiconvex minimization”. Mathematical Programming (Series A) (Berlin, Heidelberg: Springer) 90 (1): pp. 1–25. doi:10.1007/PL00011414. ISSN 0025-5610 
5. Robbins, Herbert; Siegmund, David O. (1971). “A convergence theorem for non negative almost supermartingales and some applications”. In Rustagi, Jagdish S.. Optimizing Methods in Statistics. Academic Press 
6. Herbert Robbins; Sutton Monro (1951). “A Stochastic Approximation Method”. Ann. Math. Statist. 22 (3): 400-407. doi:10.1214/aoms/1177729586. 
7. Yurii Nestero (1983). “A method of solving a convex programming problem with convergence rate O(1/k²)”. Soviet Mathematics Doklady 27: 372–376. 
8. Rumelhart, David E.; Hinton, Geoffrey E.; Williams, Ronald J. (8 October 1986). “Learning representations by back-propagating errors”. Nature 323 (6088): 533–536. doi:10.1038/323533a0. 
9. David Ruppert (1988). “Efficient estimations from a slowly convergent Robbins-Monro process”. Technical Report (Cornell University Operations Research and Industrial Engineering) 781. https://ecommons.cornell.edu/handle/1813/8664. 
10. John Langford; Lihong Li; Tong Zhang (2009). “Sparse Online Learning via Truncated Gradient”. Journal of Machine Learning Research 10: 777-801. http://www.jmlr.org/papers/volume10/langford09a/langford09a.pdf. 
11. Lin Xiao (2009). “Dual Averaging Method for Regularized Stochastic Learning and Online Optimization”. In Advances in Neural Information Processing Systems 23. http://papers.nips.cc/paper/3882-dual-averaging-method-for-regularized-stochastic-learning-and-online-optimization.pdf. 
12. ^ Perla, Joseph (2013). Notes on AdaGrad. http://www.ark.cs.cmu.edu/cdyer/adagrad.pdf. 
13. John Duchi; Elad Hazan; Yoram Singer (2011). “Adaptive Subgradient Methods for Online Learning and Stochastic Optimization”. The Journal of Machine Learning Research 12: 2121-2159. http://jmlr.org/papers/v12/duchi11a.html. 
14. Tijmen Tieleman; G. Hinton (2012). Lecture 6.5 - rmsprop, COURSERA: Neural Networks for Machine Learning. 
15. Matthew D. Zeiler (2012). ADADELTA: An Adaptive Learning Rate Method. https://arxiv.org/abs/1212.5701. 
16. Jascha Sohl-Dickstein; Ben Poole; Surya Ganguli (2014). “Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods”. Proceedings of the 31 st International Conference on Machine Learning 32. https://arxiv.org/abs/1311.2115. 
17. Diederik Kingma; Jimmy Ba (2015). “Adam: A Method for Stochastic Optimization”. Proceedings of the 3rd International Conference for Learning Representations, San Diego. https://arxiv.org/abs/1412.6980. 
18. Luo, Liangchen and Xiong, Yuanhao and Liu, Yan and Sun, Xu (2019). “Adaptive Gradient Methods with Dynamic Bound of Learning Rate”. Proceedings of the 7th International Conference on Learning Representations, New Orleans, Louisiana. https://www.luolc.com/publications/adabound/. 
19. Stephane Ross; Paul Mineiro; John Langford (2013). “Normalized Online Learning”. Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence. https://arxiv.org/abs/1305.6646. 

関連項目

• 最適化問題
• 最急降下法
• 甘利俊一