確率的勾配降下法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
ミニバッチを使い上下に行ったり来たりしながら目的関数の値が減少していく例

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

背景[編集]

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

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

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

和の最小化問題は経験損失最小化の問題も引き起こす。 の値が i 番目の訓練データであるならば、Q(w) が経験損失である。

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

はステップサイズと呼ばれる。機械学習においては学習率とも呼ばれる。

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

反復法[編集]

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

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

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

パラメータ  と学習率  の初期値を選ぶ
while 収束するか所定の反復回数まで反復する do
    (訓練データ)をランダムにシャッフルする
    for each i = 1, 2, ..., n do
        

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

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

(訓練データ)がランダムにシャッフルされる事により、確率的に局所解にはまりにくくなる効果がある。

学習率の調整方法および変種[編集]

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

確率的近似法[編集]

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

Nesterovの加速勾配降下法[編集]

1983年に Yurii Nesterov が発表[7]

モメンタム法[編集]

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

平均化法[編集]

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

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

Truncated Gradient[編集]

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

正則化双対平均化法(Regularized Dual Averaging Method)[編集]

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

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

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

L1 正則化と L2 正則化を

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

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

AdaGrad[編集]

2011年に John Duchi らが発表した方法[13]アダマール積(要素ごとの積)。下記計算、全てパラメータごと(要素ごと)に計算する。 は無限大に発散させないための正の小さな定数。

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

RMSProp[編集]

2012年に Tijmen Tieleman らが発表した方法[14]。AdaGrad の変形。勾配の2乗の指数移動平均を取るように変更。 などを使用。

AdaDelta[編集]

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

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 よりも収束が速くなった。ハイパーパラメータは を推奨。イテレーション回数 t は 1 から始める。

パラメータの初期値[編集]

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

平均・分散の調整[編集]

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

正規化オンライン学習[編集]

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

関連項目[編集]

参照[編集]

  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”. 20. Advances in Neural Information Processing Systems. pp. 161–168. http://leon.bottou.org/papers/bottou-bousquet-2008 
  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/k2)”. 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. ^ a b 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. http://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. http://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. http://arxiv.org/abs/1412.6980. 
  18. ^ Stephane Ross; Paul Mineiro; John Langford (2013). “Normalized Online Learning”. Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence. http://arxiv.org/abs/1305.6646.