AdaGrad

AdaGrad（Adaptive Gradientの略）は、機械学習および深層学習で使用される最適化アルゴリズムであり、各パラメータごとに学習率を個別に適応させる。すべてのパラメータに単一の学習率を適用する標準的な確率的勾配降下法とは異なり、AdaGradは各パラメータの履歴上の二乗勾配に基づいて、そのパラメータの更新をスケーリングする。このパラメータごとの適応により、アルゴリズムは頻度の低いパラメータに対してより大きな更新を行い、頻度の高いパラメータに対してより小さな更新を行うことができ、これは特にスパースデータの設定で有用である。AdaGradは2011年にJohn Duchi、Elad Hazan、Yoram Singerによって導入され、その後のRMSPropやAdamなどの適応的最適化手法の開発における基礎的な手法となった。

AdaGradの核心的なアイデアは、各パラメータについて過去の勾配の二乗の累積和を維持することである。各反復において、パラメータの学習率はこの累積和の平方根で除算される。これは、履歴上の勾配が大きいパラメータは実効学習率が小さくなり、勾配が小さいまたは頻度の低いパラメータは実効学習率が大きくなることを意味する。二乗勾配の累積は単調に増加するため、実効学習率は時間とともに減衰する。この特性は凸設定における収束に有益であるが、非凸問題では過度に積極的な減衰につながる可能性があり、この制限が後のアルゴリズムの動機となった。

背景

機械学習における最適化は、しばしば各サンプルの損失関数の和である目的関数を最小化することを伴う。n個のサンプルからなるトレーニングセットの場合、経験リスクはQ(w) = (1/n) Σ Q_i(w)で与えられる。ここで、wはパラメータベクトル、Q_iはi番目のサンプルの損失である。標準的な勾配降下法では、各ステップで全和の勾配を計算するため、nが大きい場合に計算コストが高くなる。確率的勾配降下法（SGD）は、代わりに単一のサンプルまたはミニバッチを用いて勾配を近似し、反復あたりの計算コストを削減するが、ノイズを導入する。1950年代のRobbins-Monroアルゴリズムは確率近似の基礎を築き、SGDは大規模データセットでの効率性から機械学習の主流となった。

SGDでは、更新規則はw := w - η ∇Q_i(w)であり、ηは学習率である。固定学習率の選択はしばしば最適ではなく、大きすぎる学習率は発散を引き起こし、小さすぎる学習率は収束を遅らせる。AdaGradのような適応的手法は、最適化のランドスケープの幾何学に基づいて学習率を調整することで、この問題に対処することを目的とする。AdaGradの動機は、特にスパースな特徴を持つ問題において、パラメータがまれにしか更新されない場合、異なるパラメータが異なるステップサイズを必要とするという観察から来ている。

アルゴリズム

AdaGradは、対角行列G_tを維持することでSGDの更新を変更する。ここで、各対角要素は対応するパラメータの過去の勾配の二乗和である。時刻tにおけるパラメータw_iの更新は以下の通りである：

w_i := w_i - (η / sqrt(G_{t,ii} + ε)) ∇Q_i(w_i)、

ここで、εはゼロ除算を避けるための小さな定数（例：1e-8）である。累積された勾配の二乗G_{t,ii} = Σ_{τ=1}^{t} (∇Q_i(w_τ))^2である。これはベクトル形式で次のように書ける：

w := w - η * diag(G_t + εI)^{-1/2} ∇Q(w)。

実際には、このアルゴリズムはミニバッチに適用されることが多く、勾配はトレーニングサンプルのサブセット上で計算される。パラメータごとの学習率はη_t,i = η / sqrt(G_{t,ii} + ε)となる。G_tは時間とともに増加するため、実効学習率は減少し、アルゴリズムが進むにつれて小さなステップを取る。これは、一貫した方向に勾配を蓄積して加速するモメンタム付きSGDとは対照的である。

数学的性質

AdaGradはもともと凸最適化の文脈で分析された。著者らは、凸関数に対してAdaGradがオンライン学習における後悔の上限を漸近的に最適に達成することを示した。具体的には、アルゴリズムの損失と事後的に最良の固定パラメータとの累積差を測定する後悔が、O(√T)で増加し、オンライン学習の下限と一致する。これは固定学習率を持つ標準SGDよりも改善であり、学習率スケジュールの慎重な調整を必要としない。

しかし、二乗勾配の累積は単調に増加するため、学習率は時間とともにゼロに減衰する。非凸問題、特に深層ニューラルネットワークのトレーニングでは、これが学習の早期停止を引き起こす可能性がある。この制限が、二乗勾配の和ではなく移動平均を使用するRMSPropや、適応学習率とモメンタムを組み合わせたAdamなどの開発につながった。

数学的特性

AdaGradはもともと凸最適化の文脈で分析された。凸関数に対して、AdaGradはオンライン学習の漸近的に最適なリグレット境界を達成することが示された。具体的には、リグレット（アルゴリズムの損失と最良の固定パラメータの損失との累積差）はAdaGradでO(√T)となり、オンライン凸最適化の下界と一致する。これは、固定学習率を使用するSGDよりも改善されており、学習率の調整が不要な点で優れている。

重要な洞察は、AdaGradが特徴空間の幾何学に自動的に適応することである。スパース設定では、多くのサンプルでゼロとなる特徴の累積勾配は小さく保たれ、出現時により大きな更新が可能になる。これにより、自然言語処理やその他の高次元スパース入力を持つ領域で特に効果的となる。

ただし、二乗勾配の累積は単調に増加するため、実効学習率は時間とともにゼロに減衰する。深層ニューラルネットワークのような非凸問題では、これが学習の早期停止を引き起こす可能性がある。この制限が、二乗勾配の移動平均を使用するRMSPropや、適応学習率とモメンタムを組み合わせたAdamなどの開発につながった。

数学的性質

AdaGradはもともと凸最適化の文脈で分析された。凸関数に対して、AdaGradはオンライン学習における漸近的に最適なリグレット境界を達成する。具体的には、リグレット（アルゴリズムの累積損失と事後的に最良の固定パラメータとの差）はO(√T)で増加し、これはオンライン凸最適化の下界と一致する。これは、固定学習率の標準的なSGDに対する改善であり、学習率の慎重な調整を必要としない点で優れている。

重要な洞察は、AdaGradが特徴空間の幾何学に自動的に適応することである。スパースな設定では、多くのサンプルでゼロとなる特徴に対して、累積勾配は小さく保たれるため、それらの特徴が出現した際に大きな更新が可能になる。これにより、自然言語処理や高次元スパース入力を扱う他の領域で特に効果的である。

応用

AdaGradは、特にスパースデータを扱うタスクで応用されている。自然言語処理では、単語の袋表現やTF-IDFベクトルなど、高次元スパース入力を使用するモデルのトレーニングに使用されてきた。まれな単語は大きな更新を受け取り、頻繁な単語は小さな更新を受けるため、モデルはまれだが情報量の多い特徴から効果的に学習できる。

レコメンデーションシステムでは、AdaGradはユーザーとアイテムの埋め込みを更新するために使用されてきた。ユーザーとアイテムのペアの頻度は大きく異なるため、AdaGradのパラメータごとの学習率は、異なる頻度の特徴をバランスよく扱うのに役立つ。また、オンライン学習シナリオでは、データが逐次的に到着するため、AdaGradの適応的な性質が有効である。

限界

AdaGradの主な限界は、学習率の単調減少である。深層学習では、非凸の損失ランドスケープにより、この減少が早期の停滞を引き起こす可能性がある。累積二乗勾配が大きくなると、実効学習率が非常に小さくなり、モデルが十分に収束する前に学習が停止することがある。この問題に対処するため、以下のような変種が開発された：

• RMSProp: ジョフリー・ヒントンによって提案され、二乗勾配の指数減衰移動平均を使用することで、学習率がより柔軟に適応できるようにした。
• Adam: Diederik KingmaとJimmy Baによって2014年に提案され、移動平均とモメンタムを組み合わせ、適応学習率と慣性を両立させた。
• AdaDelta: Matthew Zeilerによって開発され、学習率ハイパーパラメータを不要にし、過去の勾配のウィンドウを使用する。

これらのアルゴリズムは、多くの深層学習アプリケーションでデフォルトの選択肢となっているが、すべてAdaGradのパラメータごとの学習率の概念にルーツを持つ。

限界と発展

AdaGradの主な限界は、累積二乗勾配が単調に増加するため、学習率が急速にゼロに近づくことである。深層学習では、これが訓練の初期段階で過度に小さな更新を引き起こし、収束が遅くなる可能性がある。この問題に対処するため、RMSPropは指数移動平均を使用して過去の勾配の影響を減衰させ、学習率が非増加ではなく適応的に変動できるようにした。Adamはさらに、一次モーメント（勾配の平均）と二次モーメント（二乗勾配の平均）の両方を維持し、バイアス補正を加えることで、スパース勾配とノイズの多い勾配の両方で安定した性能を発揮する。

また、AdaGradはバッチサイズや勾配クリッピングなどのハイパーパラメータと組み合わせて使用されることが多い。理論上の保証は凸問題に限定されるが、実践では多くの非凸問題でも良好な結果が得られることが示されている。ただし、深層学習の大規模モデルでは、Adamやその変種がより良い性能を示すことが一般的である。

応用

AdaGradは、スパースデータを扱うさまざまな機械学習タスクで応用されてきた。自然言語処理では、各ドキュメントがスパースベクトルで表現されるモデルのトレーニングに使用され、頻度の低い単語に対する更新が大きくなるため、語彙の学習が改善される。レコメンデーションシステムでは、ユーザーとアイテムのペアがスパースなインタラクションデータで表される行列因子分解モデルの最適化に使用され、まれなインタラクションに適応する能力が活用されている。

オンライン学習の設定でも、AdaGradは逐次到着するデータに対してモデルを更新する際に使用され、その適応的な学習率調整が有益である。また、テキスト分類やスパース線形モデルなど、特徴の頻度が大きく異なる問題で特に有効である。

AdaGradは、より高度な適応オプティマイザに取って代わられたものの、比較のベンチマークとして依然として重要であり、その理論的基盤は後の研究に影響を与え続けている。

関連項目

• stochastic gradient descent
• adam
• RMSProp
• learning rate
• convex optimization