# 勾配降下法 ## 定義 勾配降下法(gradient descent, GD)とは、目的関数の値を小さくするパラメータを、勾配情報を使って逐次的に更新していく最適化手法である。目的関数 $L(\theta)$ が解析的に解けない場合(非線形モデルを使う場合や、解析的に解けても計算量が大きすぎる場合)に用いる。$\theta$ に関する勾配 $v=\frac{\partial L(\theta)}{\partial \theta}$ は関数の値が最も急激に増加する方向を表すベクトルであり、その逆向き $-v$ が関数の値を最も急激に下げる方向に対応する。勾配降下法は現在のパラメータでの勾配 $v$ を求め、$\theta=\theta-\alpha v$ と更新する。ここで $\alpha>0$ は学習率と呼ばれるハイパーパラメータ(勾配法で直接最適化できず、学習時に前もって決める必要があるパラメータ)である。これをあらかじめ決めた回数、または目的関数の改善幅が閾値を下回るなどの条件を満たすまで繰り返す。勾配方向は必ずしも最適解の方向を向いているとは限らず、目的関数の等高線が楕円のように歪んでいる場合はジグザグに収束する。(Source: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.6) 勾配降下法はすべてのパラメータをまとめて更新できるため効率が良いが、訓練事例数が大きい場合、勾配 $v=\frac1N\sum_{i=1}^N\frac{\partial l(x^{(i)},y^{(i)};\theta)}{\partial\theta}$ を求めるために毎回全訓練データを走査する必要があり、計算コストが大きくなる。(Source: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.6) ## 確率的勾配降下法(SGD) 確率的勾配降下法(stochastic gradient descent, SGD)は、訓練データ全体から $B$ 個をサンプリングしたミニバッチ(mini-batch) $\{(x^{(j)},y^{(j)})\}_{j=1}^B$ を使って勾配の近似値 $\hat v=\frac1B\sum_{i=1}^B\frac{\partial l(x^{(i)},y^{(i)};\theta)}{\partial\theta}$ を求め、$\theta=\theta-\alpha\hat v$ と更新する手法である。ミニバッチのサンプリングにより勾配は確率変数となり、その期待値は真の勾配と一致する。SGDは不正確な勾配を使うため収束までの回数(収束回数)は勾配降下法より多く必要になるが、1回あたりの勾配計算時間が短くなるため、全体の計算量を大きな訓練データセットで数百〜数万倍の規模で削減できる。(Source: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.6) ## SGDの効果: 高速化と暗黙の正則化 確率的勾配降下法は更新時に適当なノイズが入ることで、悪い局所解から脱出できるだけでなく、当初は想定していなかった汎化性能を上げる「正則化効果」を持つことがわかっている。フラットな解(損失地形が平坦な極小点)はそうでない解に比べて汎化性能が高いことが知られており、SGDはこのようなフラットな解に到達しやすくしていると考えられている。詳細は[[暗黙的正則化]]・[[深層学習の汎化]]を参照。(Source: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.6) ## なぜ勾配が最も急速に値を下げる方向になるか 現在の位置から各次元を微小量 $v_i$ だけ動かしたときの目的関数の変化量は、偏微分の定理より $f(\theta_{cur}+v)-f(\theta_{cur})\simeq\langle g,v\rangle$ と近似できる(2次項以上の影響は微小量として無視できる)。内積は $\langle g,v\rangle=\|g\|\|v\|\cos\theta$ と表せるため、ノルムが固定なら $\cos\theta=1$(すなわち $v$ が $g$ と同じ方向)のとき内積が最大、$v$ が $g$ の反対方向のとき最小になる。よって最も値を急激に下げる方向は負の勾配方向 $-v$ となる。ただし現在の位置から離れると2次項以降の影響が無視できなくなるため、勾配を求めて少し進み、また勾配を求めて少し進む、という逐次的な更新が必要になる。(Source: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.6コラム「なぜ勾配が、値を最も急速に下げる方向になるのか」) ## なぜ0/1損失関数は学習に使えないか 損失関数として実際の分類結果をそのまま表す0/1損失関数は、微分がほとんどの位置で0になるため勾配降下法での学習に使えない。加えて0/1損失関数は凸関数ではないという問題もある。そこで学習時には、0/1損失関数と似た性質を持ちながら勾配が多くの点で0にならず、かつ凸であることが求められる**サロゲート損失関数(surrogate loss)**(クロスエントロピー損失など)を用いる。詳細は[[損失関数]]・[[凸最適化]]を参照。(Source: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.6コラム「なぜ0/1損失関数は『学習』に使われないのか」) ## 非凸最適化でありながら学習が成功する理由 『ディープラーニングを支える技術』第2章は勾配降下法・SGDの定式化を扱うのに対し、続編第1章は「なぜニューラルネットワークの非凸最適化問題で勾配降下法が(貪欲法であるにもかかわらず)学習に成功するのか」という問いを正面から扱う。ニューラルネットワークの目的関数には極小解・プラトー・鞍点が無数に存在し、以前は学習が不可能なくらい難しいと考えられていたが、幅の広いニューラルネットワークでは初期値から最適解まで単調に値が減少する経路(Star-convex Path)が存在しやすく、勾配降下法がこの経路をほとんど極小解・プラトー・鞍点に触れずに通っていけることが実験的・理論的にわかってきている。低ランク行列補間問題や線形ニューラルネットワークでは極小解がすべて最適解になることが証明されており、隠れ層が1層で幅が十分大きい場合には初期値から最適解まで単調減少するパスの存在が証明されている。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 1 ディープラーニングの最適化]] §1.1) さらに、勾配降下法の収束速度は目的関数を2次関数で近似したときの[[条件数]](最大固有値と最小固有値の比)に依存し、条件数が大きいほど等高線が細長い楕円になり収束がジグザグに遅くなる。モーメンタム法は勾配のノイズを除去し更新方向を安定化させるだけでなく、収束率の条件数への依存を $\kappa$ から $\sqrt\kappa$ に弱めることで、条件数が大きい(最適化が難しい)場合の収束を加速する。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 1 ディープラーニングの最適化]] §1.3) ## 横断的知見 - **前書と続編は、勾配降下法の「基本形の定式化」と「なぜそれが非凸最適化で成功するのか」という理論的説明を分担している**: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]]は勾配降下法・SGDの更新式と計算量のトレードオフを扱うにとどまり、ニューラルネットワークの目的関数が非凸であること自体には深く踏み込まない。一方 [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 1 ディープラーニングの最適化]]は、勾配降下法が貪欲法であり非凸最適化問題では最適解への到達が理論的に保証されないことを明示したうえで、幅の広いニューラルネットワーク・Star-convex Path・条件数といった概念を導入してこの保証の欠如を実験的・理論的にどう埋めているかを説明する。前書のSGDに関する「フラットな解への到達しやすさ」という記述(§2.6)は、続編第1章が「最適解は必ずしも汎化性能が高いとは限らず、フラットな極小解のほうが汎化性能が高い」と述べる部分と整合する。(Source: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.6, [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 1 ディープラーニングの最適化]] §1.1) - **2018年のSRE実務入門は、勾配降下法を最小構成のコード例(TensorFlow `GradientDescentOptimizer`)として提示し、収束理論には立ち入らない**: 『SREの探求』第18章は、単一ニューロンの重み($w=0.8$)を二乗損失($loss=(y-y\_)^2$)と学習率0.025の`GradientDescentOptimizer`で100ステップ最適化し、出力が目標値0.0へ単調に近づく様子(TensorBoardのグラフ)を示す。また脚注で「損失を最小化するために、トレーニング用データの条件に基づいて、モデルのパラメータに関する損失の勾配を計算する手法」と勾配降下法を定義する。本ページが積み増した『ディープラーニングを支える技術』の学習率・ミニバッチ・条件数・非凸最適化の理論的説明とは対照的に、SRE章は「動くコードを動かして損失が下がることを確認する」という体験ベースの導入にとどまり、局所解・鞍点・収束速度といった論点には触れない。同じ勾配降下法という手法が、専門書では非凸最適化の理論として、実務入門書では単一のスカラー損失を0に近づける最小デモとして提示されるという、対象読者に応じた抽象度の違いが確認できる。(Source: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.6, [[@2021__OReillyJapan__SREの探求 - Chapter 18 SREのための機械学習入門]] §18.6.2.4) - [[暗黙的正則化]]は既にjoisino2025・ESL第11章から「SGDの暗黙のバイアスが単純な解を選ぶ」という知見を蓄積しており、本ページが述べる「フラットな解への到達しやすさ」という説明と接続する余地がある(詳細は[[暗黙的正則化]]の横断的知見を参照)。 ## 未解決の問い - SGDのミニバッチサイズ $B$ は、収束速度・汎化性能・計算コストのトレードオフにどう影響するか。本章は定性的な説明にとどまり、$B$ の選び方の指針は示されていない。 - 学習率 $\alpha$(ハイパーパラメータ)の選び方は、目的関数の等高線の歪み(ジグザグ収束)にどう関係するか。 - 条件数κはニューラルネットワークの目的関数を局所的な2次近似で捉えた場合の指標だが、実際の学習の進行に伴って条件数がどう変化するか(層の深さ・幅・正規化層の有無との定量的な関係)は続編第1章の範囲外であり、[[条件数]]の未解決の問いとしても残っている。 ## 関連 - source: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] / [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 1 ディープラーニングの最適化]] / [[@2021__OReillyJapan__SREの探求 - Chapter 18 SREのための機械学習入門]] - concept: [[凸最適化]] / [[暗黙的正則化]] / [[経験リスク最小化]] / [[損失関数]] / [[深層学習の汎化]] / [[条件数]] ## 出典 - 岡野原大輔, 『ディープラーニングを支える技術』, 技術評論社, 2022, 第2章, §2.6. - 岡野原大輔, 『ディープラーニングを支える技術〈2〉 ニューラルネットワーク最大の謎』, 技術評論社, 2022, 第1章, §1.1, §1.3. - [[@2021__OReillyJapan__SREの探求 - Chapter 18 SREのための機械学習入門]] §18.6.2.4.