勾配降下法

勾配降下法は、制約のない数理最適化のための手法です。これは、微分可能な多変数関数を最小化するための一次反復アルゴリズムです。

この手法の基本的な考え方は、現在の点における関数の勾配（または近似勾配）とは逆方向に繰り返しステップを踏むことです。これは、最も急な降下方向だからです。逆に、勾配の方向にステップを踏むと、その関数を最大化する軌跡が得られます。この手順は勾配上昇法と呼ばれます。勾配降下法は、どちらも最適化のための反復手法ではありますが、局所探索アルゴリズムと混同してはいけません。

勾配降下法は、機械学習や人工知能において、コスト関数や損失関数を最小化するのに特に有用である。^{[ 1 ]}

勾配降下法は一般的に、1847 年に最初に提案したオーギュスタン＝ルイ・コーシーに帰せられる。 ^{[ 2 ]}ジャック・アダマールは1907 年に同様の方法を独自に提案した。^{[ 3 ] [ 4 ]}非線形最適化問題に対するその収束特性は、 1944 年にハスケル・カリーによって初めて研究され、^{[ 5 ]}その後数十年にわたってこの方法はますます研究され、使用されるようになった。^{[ 6 ] [ 7 ]}

勾配降下法の単純な拡張である確率的勾配降下法は、今日ほとんどの深層ネットワークの学習に用いられる最も基本的なアルゴリズムである。

勾配降下法は、多変数関数が${\displaystyle f(\mathbf {x} )}$点近傍で定義され微分可能である${\displaystyle \mathbf {a} }$、 それから${\displaystyle f(\mathbf {x} )}$から始めると最も速く減少する${\displaystyle \mathbf {a} }$負の勾配の方向に${\displaystyle f}$で${\displaystyle \mathbf {a} 、つまり-\nabla f(\mathbf {a} )}$ならば、

${\displaystyle \mathbf {a} _{n+1}=\mathbf {a} _{n}-\eta \nabla f(\mathbf {a} _{n})}$

十分小さなステップサイズまたは学習率の場合$\displaystyle \eta \in \mathbb {R} _{+}}$、 それから ${\displaystyle f(\mathbf {a_{n}} )\geq f(\mathbf {a_{n+1}} )}$言い換えれば、その用語は${\displaystyle \eta \nabla f(\mathbf {a} )}$から差し引かれる${\displaystyle \mathbf {a} }$なぜなら、我々は勾配に逆らって局所最小値に向かって進みたいからである。この観察を念頭に置いて、まず推測から始める。$\displaystyle \mathbf {x} _{0}}$局所的な最小値の場合${\displaystyle f}$、そしてシーケンスを考慮する${\displaystyle \mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots }$そのため

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\eta _{n}\nabla f(\mathbf {x} _{n}),\ n\geq 0.}$

単調数列があります

${\displaystyle f(\mathbf {x} _{0})\geq f(\mathbf {x} _{1})\geq f(\mathbf {x} _{2})\geq \cdots ,}$

つまり、シーケンスは${\displaystyle (\mathbf {x} _{n})}$目的の局所最小値に収束します。ステップサイズの値は${\displaystyle \eta }$各反復処理において変更が許容される。

関数に関する特定の仮定の下では、局所最小値への収束を保証することが可能です。${\displaystyle f}$（例えば、${\displaystyle f}$凸型で${\displaystyle \nabla f}$リプシッツ）と特定の選択${\displaystyle \eta }$それらには次のシーケンスが含まれます。

${\displaystyle \eta _{n}={\frac {\left|\left(\mathbf {x} _{n}-\mathbf {x} _{n-1}\right)^{\top }\left[\nabla f(\mathbf {x} _{n})-\nabla f(\mathbf {x} _{n-1})\right]\right|}{\left\|\nabla f(\mathbf {x} _{n})-\nabla f(\mathbf {x} _{n-1})\right\|^{2}}}}$

Barzilai-Borwein法[ ^{8 ] [ 9 ]}やシーケンス^のように$\displaystyle \eta _{n}}$ウルフ条件を満たす（これは線探索によって見つけることができる）。関数が${\displaystyle f}$が凸関​​数である場合、すべての局所最小値は同時に全体最小値でもあるため、この場合、勾配降下法は全体解に収束することができます。

このプロセスは隣の図に示されています。ここで、${\displaystyle f}$は平面上で定義され、そのグラフは椀型をしていると仮定する。青い曲線は等高線、つまり の値が である領域である。${\displaystyle f}$は一定です。ある点から始まる赤い矢印は、その点における負の勾配の方向を示しています。ある点における（負の）勾配は、その点を通る等高線に直交することに注意してください。勾配降下法は、ボウルの底、つまり関数の値が一定になる点に到達することがわかります。${\displaystyle f}$最小限です。

勾配降下法を理解するためのアナロジー

勾配降下の基本的な考え方は、架空のシナリオで説明できます。人々が山で立ち往生し、下山しようとしています（つまり、全体的な最小値を見つけようとしています）。濃い霧のため視界は極めて悪く、山を下る道が見えないため、最小値を見つけるには局所的な情報を使用する必要があります。彼らは勾配降下法を使用できます。これは、現在の位置での丘の傾斜を見て、最も急な下り坂の方向に進むというものです。もし彼らが山の頂上（つまり、最大値）を探そうとしているなら、最も急な上り坂の方向に進みます。この方法を使用すると、最終的には山を下る道を見つけるか、山の湖のような穴（局所的な最小値または鞍点）で立ち往生する可能性があります。ただし、丘の傾斜は単純な観察ではすぐには明らかにならず、測定するには高度な機器が必要であり、人々はたまたまその機器を持っていると仮定します。この計測器で丘の傾斜を測定するにはかなりの時間がかかる。そのため、日没前に山を下りたいのであれば、計測器の使用を最小限に抑える必要がある。そうなると、コースから外れないように、どのくらいの頻度で傾斜を測定すべきかという問題が生じる。

この例えでは、人々はアルゴリズムを表し、山を下る道はアルゴリズムが探索するパラメータ設定のシーケンスを表します。丘の傾斜は、その地点における関数の傾きを表します。傾斜を測定するために使用される手段は微分です。彼らが進む方向は、その地点における関数の勾配と一致します。次の測定を行うまでの移動時間は、ステップサイズです。

勾配降下法は連立一次方程式を解くために使用できる。

${\displaystyle \mathbf {A} \mathbf {x} -\mathbf {b} =0}$

二次最小化問題として再定式化される。システム行列が${\displaystyle \mathbf {A} }$は実対称かつ正定値であり、目的関数は、最小化される二次関数として定義される。

${\displaystyle f(\mathbf {x} )=\mathbf {x} ^{\top }\mathbf {A} \mathbf {x} -2\mathbf {x} ^{\top }\mathbf {b} ,}$

となることによって

${\displaystyle \nabla f(\mathbf {x} )=2(\mathbf {A} \mathbf {x} -\mathbf {b} ).}$

一般的な実数行列の場合${\displaystyle \mathbf {A} }$線形最小二乗法は、

${\displaystyle f(\mathbf {x} )=\left\|\mathbf {A} \mathbf {x} -\mathbf {b} \right\|^{2}.}$

実数に対する従来の線形最小二乗法では${\displaystyle \mathbf {A} }$そして${\displaystyle \mathbf {b} }$ユークリッドノルムが使用される場合、

${\displaystyle \nabla f(\mathbf {x} )=2\mathbf {A} ^{\top }(\mathbf {A} \mathbf {x} -\mathbf {b} ).}$

線探索最小化、局所的に最適なステップサイズを見つける${\displaystyle \eta }$各反復において、二次関数については解析的に実行でき、局所最適解の明示的な式が得られる。${\displaystyle \eta }$知られている。^{[ 6 ] [ 13 ]}

例えば、実対称かつ正定値行列の場合${\displaystyle \mathbf {A} }$、簡単なアルゴリズムは次のようになります。^{[ 6 ]}

${\displaystyle {\begin{aligned}&{\text{repeat in the loop:}}\\&\qquad \mathbf {r}$ :=\mathbf {b} -\mathbf {Ax} \\&\qquad \eta  :={\mathbf {r} ^{\top }\mathbf {r} }/{\mathbf {r} ^{\top }\mathbf {Ar} }\\&\qquad \mathbf {x}  :=\mathbf {x} +\eta \mathbf {r} \\&\qquad {\hbox{if }}\mathbf {r} ^{\top }\mathbf {r} {\text{ が十分に小さい場合、ループを終了する}}\\&{\text{繰り返しループを終了する}}\\&{\text{結果として }}\mathbf {x} {\text{ を返す}}\end{aligned}}}

乗算を避けるため${\displaystyle \mathbf {A} }$反復ごとに２回、${\displaystyle \mathbf {x}$ :=\mathbf {x} +\eta \mathbf {r} } が意味するもの${\displaystyle \mathbf {r}$ :=\mathbf {r} -\eta \mathbf {Ar} } となり、従来のアルゴリズムが得られます。 ^{[ 14 ]}

${\displaystyle {\begin{aligned}&\mathbf {r}$ :=\mathbf {b} -\mathbf {Ax} \\&{\text{ループ内で繰り返す:}}\\&\qquad \eta  :={\mathbf {r} ^{\top }\mathbf {r} }/{\mathbf {r} ^{\top }\mathbf {Ar} }\\&\qquad \mathbf {x}  :=\mathbf {x} +\eta \mathbf {r} \\&\qquad {\hbox{\mathbf {r} ^{\top }\mathbf {r} {\text{が十分に小さい場合、ループを終了する}}\\&\qquad \mathbf {r}  :=\mathbf {r} -\eta \mathbf {Ar} \\&{\text{繰り返し終了}ループ}}\\&{\text{結果として }}\mathbf {x} {\text{ を返す}}\end{aligned}}}

この方法は線形方程式の解法にはほとんど用いられず、共役勾配法が最も一般的な代替法の一つである。勾配降下法の反復回数は、一般的にスペクトル条件数に比例する。${\displaystyle \kappa (\mathbf {A} )}$システム行列の${\displaystyle \mathbf {A} }$（最大固有値と最小固有値の比）${\displaystyle \mathbf {A} ^{\top }\mathbf {A} }$）一方、共役勾配法の収束は通常、条件数の平方根によって決定されるため、はるかに高速です。どちらの方法も前処理の恩恵を受けることができますが、勾配降下法では前処理器に関する仮定が少なくて済む場合があります。^{[ 14 ]}

勾配降下法は、非線形方程式系を解くためにも使用できます。以下に、勾配降下法を用いて3つの未知変数x ₁、x ₂、x ₃を求める方法を示す例を示します。この例では、勾配降下法の1回の反復処理を示しています。

非線形方程式系を考えてみましょう

${\displaystyle {\begin{cases}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}=0\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1=0\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}=0\end{cases}}}$

関連関数を導入しましょう

${\displaystyle G(\mathbf {x} )={\begin{bmatrix}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}\\\end{bmatrix}},}$

どこ

${\displaystyle \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\end{bmatrix}}.}$

ここで目的関数を定義する

${\displaystyle {\begin{aligned}f(\mathbf {x} )&={\frac {1}{2}}G^{\top }(\mathbf {x} )G(\mathbf {x} )\\&={\frac {1}{2}}\left[\left(3x_{1}-\cos(x_{2}x_{3})-{\frac {3}{2}}\right)^{2}+\left(4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\right)^{2}+\right.\\&{}\qquad \left.\left(\exp(-x_{1}x_{2})+20x_{3}+{\frac {10\pi -3}{3}}\right)^{2}\right],\end{aligned}}}$

我々はそれを最小限に抑えるよう努める。最初の推測として、

${\displaystyle \mathbf {x} ^{(0)}=\mathbf {0} ={\begin{bmatrix}0\\0\\0\\\end{bmatrix}}.}$

私たちは知っている

${\displaystyle \mathbf {x} ^{(1)}=\mathbf {0} -\eta _{0}\nabla f(\mathbf {0} )=\mathbf {0} -\eta _{0}J_{G}(\mathbf {0} )^{\top }G(\mathbf {0} ),}$

ここでヤコビ行列は${\displaystyle J_{G}}$は

${\displaystyle J_{G}(\mathbf {x} )={\begin{bmatrix}3&\sin(x_{2}x_{3})x_{3}&\sin(x_{2}x_{3})x_{2}\\8x_{1}&-1250x_{2}+2&0\\-x_{2}\exp {(-x_{1}x_{2})}&-x_{1}\exp(-x_{1}x_{2})&20\\\end{bmatrix}}.}$

計算結果：

${\displaystyle J_{G}(\mathbf {0} )={\begin{bmatrix}3&0&0\\0&2&0\\0&0&20\end{bmatrix}},\qquad G(\mathbf {0} )={\begin{bmatrix}-2.5\\-1\\10.472\end{bmatrix}}.}$

したがって

${\displaystyle \mathbf {x} ^{(1)}=\mathbf {0} -\eta _{0}{\begin{bmatrix}-7.5\\-2\\209.44\end{bmatrix}},}$

そして

${\displaystyle f(\mathbf {0} )=0.5\left((-2.5)^{2}+(-1)^{2}+(10.472)^{2}\right)=58.456.}$

さて、適切な${\displaystyle \eta _{0}}$は、

${\displaystyle f\left(\mathbf {x} ^{(1)}\right)\leq f\left(\mathbf {x} ^{(0)}\right)=f(\mathbf {0} ).}$

これは、さまざまな線探索アルゴリズムのいずれかを使用して行うことができます。あるいは、単純に推測することもできます。${\displaystyle \eta _{0}=0.001,}$これにより

${\displaystyle \mathbf {x} ^{(1)}={\begin{bmatrix}0.0075\\0.002\\-0.20944\\\end{bmatrix}}.}$

この値で目的関数を評価すると、次のようになります。

${\displaystyle f\left(\mathbf {x} ^{(1)}\right)=0.5\left((-2.48)^{2}+(-1.00)^{2}+(6.28)^{2}\right)=23.306.}$

減少${\displaystyle f(\mathbf {0} )=58.456}$次のステップの値へ

${\displaystyle f\left(\mathbf {x} ^{(1)}\right)=23.306}$

これは目的関数の大幅な減少を意味します。さらに手順を踏むと、システムの近似解が見つかるまで、その値はさらに減少します。

勾配降下法は、無限次元空間を含む任意の次元の空間で機能します。後者の場合、探索空間は通常関数空間であり、降下方向を決定するために最小化される汎関数のフレシェ微分を計算します。^{[ 7 ]}

勾配降下法が任意の次元数（少なくとも有限次元数）で機能することは、コーシー・シュワルツの不等式、すなわち、任意の次元の2つのベクトルの内積（ドット積）の大きさは、それらが共線である場合に最大になるという不等式の結果と見なすことができる。勾配降下法の場合、これは独立変数調整ベクトルが偏微分勾配ベクトルに比例する場合に該当する。

勾配降下法では、与えられた関数の曲率が方向によって大きく異なる場合、必要な精度で局所最小値を計算するのに多くの反復が必要になることがあります。このような関数に対しては、空間の形状を変更して関数レベルセットを同心円状にする前処理によって、収束の遅さを解消できます。ただし、前処理の構築と適用には計算コストがかかる場合があります。

勾配降下法は、モーメンタム^{[ 16 ]} ( Nesterov、Polyak、^{[ 17 ]}、Frank–Wolfe ^{[ 18 ]} ) およびヘビーボールパラメータ (指数移動平均^{[ 19 ]}および正負のモーメンタム^{[ 20 ]} ) によって変更できます。このような最適化ツールの主な例としては、Adam、DiffGrad、Yogi、AdaBelief などがあります。

ニュートン法と共役勾配法を用いたヘッセ行列の逆行列に基づく方法は、より良い代替手段となり得る。^{[ 21 ] [ 22 ]}一般的に、このような方法はより少ない反復回数で収束するが、各反復のコストは高くなる。一例として、BFGS法がある。これは、各ステップで勾配ベクトルに掛ける行列を計算して「より良い」方向へ進むようにし、より洗練された線探索アルゴリズムと組み合わせて「最適」な値を見つけるものである。${\displaystyle \eta .}$コンピュータのメモリ容量の問題が支配的な極めて大規模な問題の場合、 BFGS法や最急降下法の代わりに、 L-BFGS法のようなメモリ容量を制限した手法を用いるべきである。

勾配降下法を局所探索アルゴリズムの代わりとして使用できる場合もあるが、勾配降下法は同じ系統のものではない。局所最適化のための反復法ではあるが、解空間を明示的に探索するのではなく、目的関数の勾配に依存するからである。

勾配降下法は、常微分方程式を解くためのオイラー法を応用したものと考えることができる。${\displaystyle x'(t)=-\nabla f(x(t))}$勾配流へ。この式は、制御システムの最適コントローラ^{[ 23 ]}として導出できる。${\displaystyle x'(t)=u(t)}$と${\displaystyle u(t)}$フィードバックフォームで提供${\displaystyle u(t)=-\nabla f(x(t))}$。

勾配降下法は局所最小値に収束し、鞍点の近傍では収束速度が低下する可能性がある。制約のない二次最小化問題であっても、勾配降下法では反復が進むにつれて反復値がジグザグパターンを描き、収束が遅くなる。これらの欠点を克服するために、勾配降下法の様々な改良法が提案されている。

勾配降下法は、制約集合への射影を含めることで、制約を扱うように拡張できます。この方法は、射影がコンピュータ上で効率的に計算できる場合にのみ実行可能です。適切な仮定の下では、この方法は収束します。この方法は、単調包含関係に対する前方後方アルゴリズム（凸計画法と変分不等式を含む）の特殊なケースです。^{[ 32 ]}

勾配降下法は、与えられたブレグマン発散として二乗ユークリッド距離を使用するミラー降下法の特殊なケースである。^{[ 33 ]}

勾配降下法の特性は、目的関数の特性と使用する勾配降下法のバリアント（例えば、直線探索ステップを使用するかどうか）に依存します。仮定は収束率や勾配降下法で証明できるその他の特性に影響を与えます。^{[ 34 ]}例えば、目的関数が強凸かつリプシッツ滑らかであると仮定すると、勾配降下法は固定ステップサイズで線形に収束します。^{[ 1 ]}仮定が緩いと、収束保証が弱くなるか、より洗練されたステップサイズの選択が必要になります。^{[ 34 ]}

• ヤン・ミルズ流
• ヤン・ミルズ・ヒッグス流
• ザイバーグ・ウィッテン流

• Boyd, Stephen ; Vandenberghe, Lieven (2004). "制約なし最小化" (PDF) .凸最適化. ニューヨーク: Cambridge University Press. pp. 457–520 . ISBN  0-521-83378-7。
• Chong, Edwin KP; Żak, Stanislaw H. (2013). "勾配法" .最適化入門（第4 版）. Hoboken: Wiley. pp. 131–160 . ISBN  978-1-118-27901-4。
• Himmelblau, David M. ( 1972). 「導関数を用いた制約なし最小化手順」『応用非線形計画法』ニューヨーク：McGraw-Hill、pp. 63–132。ISBN  0-07-028921-2。

• C++、Boost、UBLASを用いた線形回帰における勾配降下法の利用
• カーンアカデミーの動画シリーズでは、勾配上昇について解説しています。
• 深層ニューラルネットワークにおける勾配降下法を解説するオンライン書籍
• Ghostarchiveにアーカイブされていますそしてウェイバックマシン「勾配降下法、ニューラルネットワークの学習方法」。3Blue1Brown 。2017年10月16日– YouTube経由。
• ガリゴス、ギヨーム；ゴワー、ロバート M. (2023). 「(確率的)勾配法の収束定理ハンドブック」. arXiv : 2301.11235 [ math.OC ].