確率的勾配降下法

前述のように、古典的な確率的勾配降下法は一般的に学習率ηに敏感です。高速な収束には大きな学習率が必要ですが、これは数値的不安定性を引き起こす可能性があります。この問題は、現在の反復ではなく次の反復で確率的勾配を評価する 暗黙的更新を考慮することで、ほぼ解決できます^{[ 29 ] 。}$${\displaystyle w^{\text{new}}:=w^{\text{old}}-\eta \,\nabla Q_{i}(w^{\text{new}}).}$$

この方程式は暗黙的であるため${\displaystyle w^{\text{new}}}$は等式の両辺に現れる。これは近接勾配法の確率的形式であり、更新式は次のようにも書ける。 $${\displaystyle w^{\text{new}}:=\arg \min _{w}\left\{Q_{i}(w)+{\frac {1}{2\eta }}\left\|w-w^{\text{old}}\right\|^{2}\right\}.}$$

例として、特徴量を用いた最小二乗法を考えてみましょう。${\displaystyle x_{1},\ldots ,x_{n}\in \mathbb {R} ^{p}}$そして観察結果 ${\displaystyle y_{1},\ldots ,y_{n}\in \mathbb {R} }$私たちは以下の問題を解決したいと考えています。 $${\displaystyle \min _{w}\sum _{j=1}^{n}\left(y_{j}-x_{j}'w\right)^{2},}$$ どこ${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p}}$ は内積を表します。${\displaystyle x}$切片を含む最初の要素として「1」を持つことができます。古典的な確率的勾配降下法は次のように進行します。 $${\displaystyle w^{\text{new}}=w^{\text{old}}+\eta \left(y_{i}-x_{i}'w^{\text{old}}\right)x_{i}}$$

どこ${\displaystyle i}$1から${\displaystyle n}$この手順の理論的な収束は比較的緩やかな仮定の下で起こるものの、実際にはこの手順は非常に不安定になる可能性がある。特に、${\displaystyle \eta }$誤って指定されているため、${\displaystyle I-\eta x_{i}x_{i}'}$絶対値が大きい固有値を持つ確率が高い場合、手順は数回の反復で数値的に発散する可能性があります。一方、暗黙的確率勾配降下法（ISGDと略記）は、次のように閉形式で解くことができます。 $${\displaystyle w^{\text{new}}=w^{\text{old}}+{\frac {\eta }{1+\eta \left\|x_{i}\right\|^{2}}}\left(y_{i}-x_{i}'w^{\text{old}}\right)x_{i}.}$$

この手順は、ほぼすべての場合において数値的に安定している。${\displaystyle \eta }$学習率が正規化されているため、このような最小二乗問題における古典的な確率的勾配降下法と暗黙的な確率的勾配降下法の比較は、最小平均二乗法 (LMS)と 正規化最小平均二乗フィルタ (NLMS)の比較と非常によく似ています。

ISGDの閉形式解は最小二乗法でのみ可能であるが、この手順は幅広いモデルで効率的に実装できる。具体的には、${\displaystyle Q_{i}(w)}$に依存する${\displaystyle w}$特徴との線形結合によってのみ${\displaystyle x_{i}}$そうすれば、${\displaystyle \nabla _{w}Q_{i}(w)=-q(x_{i}'w)x_{i}}$、 どこ${\displaystyle q()\in \mathbb {R} }$依存する可能性がある${\displaystyle x_{i},y_{i}}$同様だが、${\displaystyle w}$例外的に${\displaystyle x_{i}'w}$最小二乗法はこの規則に従い、ロジスティック回帰やほとんどの一般化線形モデルも同様です。たとえば、最小二乗法では、${\displaystyle q(x_{i}'w)=y_{i}-x_{i}'w}$、そしてロジスティック回帰では${\displaystyle q(x_{i}'w)=y_{i}-S(x_{i}'w)}$、 どこ${\displaystyle S(u)=e^{u}/(1+e^{u})}$はロジスティック関数です。ポアソン回帰では、${\displaystyle q(x_{i}'w)=y_{i}-e^{x_{i}'w}}$、 等々。

このような設定では、ISGDは単純に以下のように実装されます。${\displaystyle f(\xi )=\eta q(x_{i}'w^{\text{old}}+\xi \|x_{i}\|^{2})}$、 どこ${\displaystyle \xi }$はスカラーです。すると、ISGDは以下と同等になります。 $${\displaystyle w^{\text{new}}=w^{\text{old}}+\xi ^{\ast }x_{i},~{\text{where}}~\xi ^{\ast }=f(\xi ^{\ast }).}$$

スケーリング係数${\displaystyle \xi ^{\ast }\in \mathbb {R} }$は、前述の一般化線形モデルなどのほとんどの通常のモデルでは関数が二分法によって見つけることができるため、${\displaystyle q()}$は減少しており、したがって、${\displaystyle \xi ^{\ast }}$は${\displaystyle [\min(0,f(0)),\max(0,f(0))]}$。

さらに提案されている方法としては、モーメンタム法やヘビーボール法があり、これらは機械学習の文脈では、バックプロパゲーション学習に関するRumelhart、Hinton、Williamsの論文^{[ 30 ]に登場し、ソ連の数学者 Boris Polyak の 1964 年の関数方程式の解法に関する論文[ 31 ]}からアイデアを借用している。モーメンタム付き確率的勾配降下法は、各反復で更新Δ wを記憶し、勾配と前の更新の線形結合として次の更新を決定する。 ^{[ 32 ] [ 33 ]}$${\displaystyle \Delta w:=\alpha \Delta w-\eta \,\nabla Q_{i}(w)}$$$${\displaystyle w:=w+\Delta w}$$ それは以下のことにつながる： $${\displaystyle w:=w-\eta \,\nabla Q_{i}(w)+\alpha \Delta w}$$

パラメータ​${\displaystyle w}$これにより最小化されます${\displaystyle Q(w)}$推定される、${\displaystyle \eta }$ステップサイズ（機械学習では学習率と呼ばれることもある）であり、${\displaystyle \alpha }$は、0から1の間の指数関数的減衰係数であり、現在の勾配と以前の勾配が重みの変化にどれだけ寄与するかを決定します。

「運動量」という名称は、物理学における運動量、すなわち重力ベクトルとの類推に由来する。${\displaystyle w}$^{パラメータ空間を移動する粒子として考えられる運動量法は}、損失の勾配から加速（「力」）を受けます。古典的な確率的勾配降下法とは異なり、同じ方向に移動し続ける傾向があり、振動を防ぎます。運動量法は、数十年にわたり、コンピュータ科学者によって人工ニューラルネットワークのトレーニングに成功裏に使用されてきました。^{[ 34 ]} 運動量法は、減衰不足のランジュバン動力学 と密接に関連しており、シミュレーテッドアニーリングと組み合わせることができます。^{[ 35 ]}

1980年代半ばに、この方法はユーリ・ネステロフによって次の点で予測される勾配を使用するように修正され、その結果として生まれたいわゆるネステロフ加速勾配法は、2010年代の機械学習で時折使用された。^{[ 36 ]}

平均化確率勾配降下法は、1980年代後半にRuppertとPolyakによって独立に発明されたもので、時間の経過に伴うパラメータベクトルの平均を記録する通常の確率勾配降下法です。つまり、更新は通常の確率勾配降下法と同じですが、アルゴリズムは^{[ 37 ]も追跡します。}

$${\displaystyle {\bar {w}}={\frac {1}{t}}\sum _{i=0}^{t-1}w_{i}.}$$最適化が完了すると、この平均化されたパラメータベクトルがwの代わりになります。

AdaGrad（適応勾配アルゴリズム）は、パラメータごとの学習率を持つ修正された確率的勾配降下アルゴリズムで、2011年に初めて発表されました。^{[ 38 ]}非公式には、これは疎なパラメータの学習率を増加させ、疎でないパラメータの学習率を減少させます。この戦略は、データが疎で疎なパラメータがより多くの情報を提供する設定では、標準的な確率的勾配降下よりも収束性能を向上させることがよくあります。このようなアプリケーションの例としては、自然言語処理や画像認識などがあります。^{[ 38 ]}

基本学習率ηは依然として存在するが、これは外積行列の対角要素であるベクトル{ Gj _{, j} }の要素と乗算される_。

$${\displaystyle G=\sum _{\tau =1}^{t}g_{\tau }g_{\tau }^{\mathsf {T}}}$$

どこ${\displaystyle g_{\tau }=\nabla Q_{i}(w)}$、反復τにおける勾配。対角成分は次式で与えられる。

$${\displaystyle G_{j,j}=\sum _{\tau =1}^{t}g_{\tau ,j}^{2}.}$$このベクトルは基本的に次元ごとの勾配二乗の履歴合計を格納し、各反復後に更新されます。更新の式は^{[ a ]です。}$${\displaystyle w:=w-\eta \,\mathrm {diag} (G)^{-{\frac {1}{2}}}\odot g}$$ または、パラメータごとの更新として記述すると、 $${\displaystyle w_{j}:=w_{j}-{\frac {\eta }{\sqrt {G_{j,j}}}}g_{j}.}$$ 各{ G _{( i , i )} }は、単一のパラメータw _iに適用される学習率のスケーリング係数を生み出します。この係数の分母は、${\textstyle {\sqrt {G_{i}}}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2}}}}$は以前の導関数のℓ ₂ノルムであり、極端なパラメータ更新は抑制され、更新が少ないまたは小さいパラメータはより高い学習率を受け取ります。^{[ 34 ]}

AdaGradは凸問題向けに設計されているが、非凸最適化にも適用されて成功している。^{[ 39 ]}

RMSProp（Root Mean Square Propagation の略）は、2012 年に、当時ジェフリー・ヒントン研究室の博士課程学生であったジェームズ・マーテンスとイリヤ・サツケバーによって考案された手法で、Adagrad と同様に、各パラメータに対して学習率が調整されます。そのアイデアは、重みの学習率を、その重みの最近の勾配の大きさの移動平均で割ることです。^{[ 40 ]}珍しいことに、論文として発表されたのではなく、Coursera の講義で説明されただけです。^{[ 41 ] [ 42 ]}

まず、移動平均は平均二乗の観点から計算されます。

$${\displaystyle v(w,t):=\gamma v(w,t-1)+\left(1-\gamma \right)\left(\nabla Q_{i}(w)\right)^{2}}$$

どこ、${\displaystyle \gamma }$忘却係数は、過去の勾配を二乗和として保存するという概念をAdagradから借用したものですが、古いデータの影響を徐々に減少させることで、非凸問題におけるAdagradの学習率低下の問題を解決するために「忘却」が導入されています。

そして、パラメータは次のように更新されます。

$${\displaystyle w:=w-{\frac {\eta }{\sqrt {v(w,t)}}}\nabla Q_{i}(w)}$$

RMSPropは、さまざまなアプリケーションで学習率の良好な適応性を示しています。RMSPropはRpropの一般化と見なすことができ、フルバッチだけでなくミニバッチでも動作可能です。^{[ 40 ]}

Adam ^{[ 43 ]} (Adaptive Moment Estimation の略) は、RMSPropオプティマイザの 2014 年の更新版で、モーメンタム法の主要機能と組み合わせたものです。^{[ 44 ]}この最適化アルゴリズムでは、勾配と勾配の 2 次モーメントの両方について、指数忘却を伴う移動平均が使用されます。${\displaystyle w^{(t)}}$そして損失関数${\displaystyle L^{(t)}}$、 どこ${\displaystyle t}$現在のトレーニング反復をインデックスします（インデックスは${\displaystyle 1}$) Adamのパラメータ更新は次のように与えられます。

$${\displaystyle m_{w}^{(t)}:=\beta _{1}m_{w}^{(t-1)}+\left(1-\beta _{1}\right)\nabla _{w}L^{(t-1)}}$$$${\displaystyle v_{w}^{(t)}:=\beta _{2}v_{w}^{(t-1)}+\left(1-\beta _{2}\right)\left(\nabla _{w}L^{(t-1)}\right)^{2}}$$

$${\displaystyle {\hat {m}}_{w}^{(t)}={\frac {m_{w}^{(t)}}{1-\beta _{1}^{t}}}}$$$${\displaystyle {\hat {v}}_{w}^{(t)}={\frac {v_{w}^{(t)}}{1-\beta _{2}^{t}}}}$$

$${\displaystyle w^{(t)}:=w^{(t-1)}-\eta {\frac {{\hat {m}}_{w}^{(t)}}{{\sqrt {{\hat {v}}_{w}^{(t)}}}+\varepsilon }}}$$ どこ${\displaystyle \varepsilon }$は小さなスカラーです（例：${\displaystyle 10^{-8}}$）は、0による除算を防ぐために使用され、${\displaystyle \beta _{1}}$（例：0.9）${\displaystyle \beta _{2}}$（例えば0.999）は、それぞれ勾配と勾配の2次モーメントの忘却係数です。二乗と平方根は要素ごとに計算されます。

勾配の指数移動平均として${\displaystyle m_{w}^{(t)}}$そして二乗勾配${\displaystyle v_{w}^{(t)}}$0のベクトルで初期化すると、最初のトレーニング反復でゼロへのバイアスが生じます。${\displaystyle {\tfrac {1}{1-\beta _{1/2}^{t}}}}$このバイアスを補正し、より正確な推定値を得るために導入された。${\displaystyle {\hat {m}}_{w}^{(t)}}$そして${\displaystyle {\hat {v}}_{w}^{(t)}}$。

Adam の収束を確立する最初の証明は不完全であり、その後の分析により、Adam はすべての凸目的関数に対して収束するわけではないことが明らかになった。^{[ 45 ] [ 46 ]}それにもかかわらず、Adam は実用上優れた性能を発揮するため、引き続き使用されている。^{[ 47 ]}

符号に基づく最適化は前述のRpropに遡りますが、2018 年に研究者たちは確率的勾配の大きさを考慮から外し、符号のみを考慮することで Adam を簡略化しようと試みました。^{[ 56 ] [ 57 ]}これにより、ワーカーからパラメータサーバーへの勾配転送の通信コストが大幅に削減されます。この意味で、勾配情報をより効率的に圧縮しつつ、標準的な SGD と同等の収束性を実現しています。^{[ 57 ]}

バックトラッキング線探索は、勾配降下法の別のバリアントです。以下はすべて、前述のリンクから引用しています。これは、Armijo–Goldstein条件として知られる条件に基づいています。どちらの方法も、各反復で学習率を変更できますが、変更方法は異なります。バックトラッキング線探索は、関数評価を使用してArmijo条件をチェックし、原則として、学習率を決定するためのアルゴリズムのループは長く、事前に不明になる可能性があります。適応型SGDは、学習率を決定するためにループを必要としません。一方、適応型SGDは、バックトラッキング線探索が持つ「降下特性」を保証しません。${\displaystyle f(x_{n+1})\leq f(x_{n})}$すべての n について。コスト関数の勾配がリプシッツ定数 L で大域的にリプシッツ連続であり、学習率が 1/L のオーダーで選択される場合、SGD の標準バージョンはバックトラッキング線探索の特殊なケースです。

標準的な（決定論的な）ニュートン・ラフソン法の確率的類似物（「2次」法）は、確率近似の設定において、漸近的に最適またはほぼ最適な反復最適化形式を提供する。経験的リスク関数の項のヘッセ行列を直接測定する方法は、Byrd、Hansen、Nocedal、およびSingerによって開発された。^{[ 58 ]}しかし、最適化に必要なヘッセ行列を直接決定することは、実際には不可能かもしれない。直接ヘッセ情報を必要としないSGDの2次バージョンの実用的かつ理論的に健全な方法は、Spallらによって示されている。^{[ 59 ] [ 60 ] [ 61 ]} (同時摂動ではなく有限差分に基づく効率の低い方法がRuppertによって提案されている。^{[ 62 ]} ) 近似ヘッセ行列への別のアプローチは、通常の勾配を自然勾配に変換するFisher情報行列で置き換えることである。^{[ 63 ]}直接ヘッセ情報を必要としないこれらの方法は、上記の経験的リスク関数の項の値、または項の勾配の値（すなわちSGD入力）のいずれかに基づいている。特に、経験的リスク関数の項のヘッセ行列を直接計算しなくても、漸近的に2次最適性を達成できる。目的が非線形最小二乗損失 である場合$${\displaystyle Q(w)={\frac {1}{n}}\sum _{i=1}^{n}Q_{i}(w)={\frac {1}{n}}\sum _{i=1}^{n}(m(w;x_{i})-y_{i})^{2},}$$ どこ${\displaystyle m(w;x_{i})}$予測モデル（例えば、深層ニューラルネットワーク）の場合、目的関数の構造を利用して、勾配のみを使用して2次情報を推定することができます。結果として得られる方法はシンプルで、多くの場合効果的です^{[ 64 ]。}