|
論文リンク: https://arxiv.org/abs/1706.10207 概要: この論文では、機械学習への最適化手法の適用に関する主要なモデル、アルゴリズム、およびいくつかの未解決の問題を紹介することを目的としています。この論文は、ある程度の知識を持つ読者、特に基本的な最適化アルゴリズムには精通しているが機械学習には精通していない読者を対象に書かれています。まず、教師あり学習問題の定式化を導出し、それがコンテキストと基礎となる仮定に応じてさまざまな最適化問題を引き起こす仕組みを示します。次に、ロジスティック回帰とディープニューラルネットワークトレーニングのケースに焦点を当てて、これらの最適化問題のいくつかの顕著な特徴について説明します。記事の後半では、凸ロジスティック回帰から始めて、いくつかの最適化アルゴリズムに焦点を当て、確率的勾配降下法 (SGD)、分散低減確率法、および 2 次法の使用を含む 1 次法について説明します。最後に、これらの手法をディープ ニューラル ネットワークのトレーニングにどのように適用できるかについて説明し、これらのモデルの複雑な非凸構造によって生じる困難に焦点を当てます。 1 はじめに過去 20 年間にわたり、機械学習という魅力的なアルゴリズム分野が、ほぼ前例のないペースで発展してきました。機械学習は統計学とコンピューターサイエンスに基づいており、数学的な最適化手法がその中核となっています。実際、最適化手法の分野における最近の理論的および実践的な進歩の多くは、機械学習やその他のデータ駆動型の分野の影響を受けています。しかし、このようなつながりがあっても、統計学、コンピューター サイエンス、機械学習に関連する問題の最適化手法の研究の間には、依然として多くの障壁が残っています。したがって、この論文では、機械学習アルゴリズムの概要を説明することで、この障壁を打ち破ろうとしています。 この論文の目的は、機械学習の分野に関連するいくつかの重要な問題と研究課題の概要を示すことです。オペレーションズ リサーチの分野における知識の関与を考慮して、読者は最適化手法の基本理論に精通していることを前提としていますが、オペレーションズ リサーチの専門家と他の貢献分野の人々との間のコミュニケーションを促進することを期待して、機械学習の一般的な分野で使用される関連用語と概念を紹介します。この目標を達成するために、この論文で紹介され使用される最も重要な用語を用語集 1 にリストします。 1.1 動機を明確にする
1.2 学習と最適化の問題
1.3 学習境界、過剰適合、正則化2 ロジスティック回帰問題を解くための最適化手法（浅いモデルのための最適化手法） Lとrがwの任意の凸関数である場合、このセクションで説明した方法は問題(11)を解くのに使用できます。 このカテゴリには、サポートベクターマシン、Lasso (最小絶対収縮および選択演算子)、スパース逆共分散選択など、多くの機械学習モデルが含まれます。これらのモデルの詳細については[86]およびその中の参考文献を参照してください。各ステップを具体的にするために、バイナリ正規化ロジスティック回帰を例として取り上げます。例の表記を簡略化するために、一般性を失うことなく仮定し、 とします。 （バイアス項 b0 はここでは省略されていますが、この省略は、常に 1 である 1 次元の固有値を入力ベクトルに追加することで補正できます。） w と x が両方とも d 次元の場合、特殊な凸最適化問題として定式化できます。 この種の問題では、正規化項が不可欠であることは言及する価値があります。なぜそれが重要であるかを考えるために、すべてのi∈{1,...,n}に対して、yi(wT*xi) > 0となるパラメータベクトルwが存在し、無限光線{θw:θ> 0}が存在すると仮定します。すると問題は非常に明確になります。この例では、θ →∞のとき、 つまり、関数（式12）は最小値を取ることができない。一方、（強制）正則化関数rを追加することで、問題（12）が最適解を持つことが保証される。 正規化関数rについては、一般的な選択肢を参照し、r(w) = ||w||1とします。しかし、簡単にするために、通常は前者を選択します。前者では、式 12 がすべての因子に関して連続的に微分可能になるからです。対照的に、r(w) = ||w||1 は滑らかでない問題につながり、関数の最小化にはより複雑なアルゴリズムが必要になります。 2.1 一次法まず、問題(12)を解くための一次法について議論する。ここで「一次」とは、関数Fのパラメータの最初の偏導関数を取る数学的手法を指す。 2.1.1 勾配降下法概念的には、滑らかな凸目的関数を最小化する最も簡単な方法は勾配降下法である。詳細な分析については[62]を参照。この方法では、初期推定値 w0 から始めて、次の式を使用して重み推定値が反復的に更新されます。 ここで、αk > 0 はステップサイズパラメータです。ステップサイズシーケンス{αk}の選択は、このアルゴリズムのパフォーマンスを直接決定します。最適化研究の分野では、線形探索を使用して各反復で {αk } を決定すると、さまざまな種類の問題を解決するための優れたアルゴリズムが見つかると広く信じられています。ただし、関数 F の計算ごとにデータセット全体を渡す必要があるため、この操作は機械学習アプリケーションにとってはコストがかかり、n が大きすぎると (トレーニング) コストが高くなる可能性があります。 幸いなことに、各 αk が正の定数 α に設定され、それが十分に小さい固定値である場合、理論的な分析から、アルゴリズムの収束は依然として保証されます。 （固定ステップサイズ定数は機械学習の分野では学習率と呼ばれます。しかし、定数でなくても、αK またはシーケンス全体 {αK } を学習率と呼ぶ人もいます）。アルゴリズムの収束速度は、関数 f が強凸関数であるか弱凸関数であるかによって異なります。 L1 ノルム正則化によるロジスティック回帰問題を解決するための勾配降下法と加速勾配降下法の拡張は、それぞれ ISTA と FISTA と呼ばれます。この場合、λ > 0 であっても、目的関数は強く凸ではないことがわかります。 ISTAとFISTAは、目的関数が凸関数である場合にのみ、対応する滑らかな関数と同じ線形収束率を持ちます[5]。 ML トレーニング プロセスにおける勾配降下法の重要な機能は、各反復で関数 F の勾配を解く計算コストを計算することです。 MLトレーニングでは、1回の勾配計算のコストは通常O(ND)であり、これは例えば、正規化項がのとき、関数Fの各特定のwに対する勾配は 2.1.2 確率的勾配法確率的勾配法は、オペレーションズ リサーチの分野では確率的目的関数の最小化に使用されることでよく知られており、ML コミュニティでは機能最適化アルゴリズムとしても使用されています。このアルゴリズムはもともと、ランダム方程式系を解くためにロビンスとモンロー[67]によって提案されました。このアルゴリズムは、良好な収束性でランダム目的関数を最小化するために使用でき、各反復の計算量はO(nd)（勾配降下法の計算量）ではなくO(d)のみである点が注目に値します。 各反復で、確率的勾配法は勾配 F(Wk) の不偏推定値 GK を計算します。この推定値は低コストで計算できる。例えば、式（12）の場合、ある反復における確率勾配は次のように解くことができる。 ここで、Sk はミニバッチと呼ばれ、そのすべての要素は均一分布に従ってデータセット全体 {1,...,n} から選択されます。次の操作は勾配降下法に似ています。 間違いなく、このアルゴリズムの鍵はステップサイズシーケンス {αk} の選択にあります。勾配降下法とは異なり、固定ステップ サイズ (つまり、学習率) では、アルゴリズムが強凸関数 F の最小値に収束することは保証されませんが、最小値の近傍への収束のみが保証されます。 SGD は勾配降下法よりも収束が遅くなります。特に、関数Fが強凸関数である場合、このアルゴリズムは、k ≥ O(1/ε)の場合にのみ、期待される精度の解（すなわち、E[F(wk)]-F(w) ≤ εを満たす解）が得られることを保証する。関数Fが単なる凸関数である場合、上記の解はk ≥ O(1/ε^2)の場合にのみ保証される[11]。 一方、前述のように、Sk が定数 (n または k とは無関係) で制限されている場合、SGD の各反復コストは勾配降下法の 0(n) 倍小さくなります。 しかし、実際のアプリケーションでは、標準 SGD は必ずしも機械学習の最適化問題を解決するための最も効果的な方法ではありません。実際、機械学習や最適化アルゴリズムの分野では、SGD の改良や代替手段の開発に向けた活発な研究が数多く行われています。次の 2 つのセクションでは、分散削減法と 2 次法という 2 種類の方法について説明します。しかし、これら 2 つの方法以外にも多くの方法があります。たとえば、モメンタム付き SGD は SGD の拡張であり、実際には標準の SGD よりもパフォーマンスが優れていることがわかっています。下記のアルゴリズム1を参照 2.1.3 分散低減法問題(11)を考慮すると、単純な凸関数項と結合したn個の関数の有限和としての目的関数Fの構造を利用することでSGD法を改善できることがわかった。 SAG [74]、SAGA [22]、SDCA [76]、SVRG [44]などいくつかの方法が研究されている。 参照しやすいように、SVRG アルゴリズム 2 と呼びます。アルゴリズムは、各外側の反復で完全な勾配計算を実行し、その後、完全な勾配のランダムな修正であるランダムな方向にさらに L ステップ反復します。内側のループステップサイズLは収束を確実にするために特定の条件を満たす必要がある[44]。 SVRG は Stochastic Variance Reducing Gradient の略で、アルゴリズムが SGD (具体的には有限和最小化) の分散削減バリアントとして見ることができることからその名前が付けられています。 研究者たちはSVRGとSAGAのアイデアをいくつか組み合わせて、SARAHと呼ばれる新しい方法を提案した。 SVRGと異なるのは内部反復ステップサイズのみです。SARAHの式は次のようになります。 この変更により、SARAH のステップ サイズは不偏勾配推定に基づかなくなります。ただし、SVRG に比べて収束特性が向上します。 表2: 強凸関数を最小化する一次法の計算複雑度 表3: 一般凸関数を最小化する一次法の計算複雑度 2.2 2次法と準ニュートン法決定論的最適化における数十年にわたる研究に触発され、ML 最適化における最も活発な研究分野の 1 つは、2 次導関数 (つまり、曲率) 情報を使用してトレーニングを高速化する方法に関するものです。 残念ながら、n または d が大きい場合、機械学習アプリケーションではヘッセ行列の計算と保存に非常にコストがかかります。 (21)のようなモデルに基づく別のタイプのアルゴリズムは準ニュートン法である。 興味深いことに、これらの方法では明示的な 2 次導関数を計算するのではなく、各反復で低ランク更新を適用することによって、完全に 1 次導関数で構成されるヘッセ近似行列を構築します。たとえば、最も人気のある準ニュートン法である Broyden-Fletcher-Goldfarb-Shanno (BFGS) 法について簡単に紹介しましょう。このアプローチでは、まず(21)の最小値は であることがわかり、さらに逆ヘッセ近似を計算するのが実際には便利であることがわかります。ステップサイズsk = w_k+1 − wk、変位yk = ∇F(wk+1) − ∇F(wk)であるため、セカント方程式sk = (B^-1)ykを満たすように最小化することを選択します。慎重に選択された標準記法を用いると、この問題の解析的定式化は次のように明示的に記述できる。 それらの違いは、単なる 2 次行列として表すことができます。 参照しやすいように、完全な古典的な BFGS アルゴリズムはアルゴリズム 3 と呼ばれます。 2 次情報があっても、不一致の削減なしの確率的最適化手法では、部分線形よりも速く収束を達成することはできません。ただし、ヘッセ行列近似行列がヘッセ行列の真の解に収束する場合、収束率の定数を減らし、悪条件の影響も減らすことができるため、2 次情報を使用することは良い考えです。 残念ながら、実用的な効率性の向上は確認されているものの、理論的にそのような向上を達成できる真の二次的方法は存在しません。これまでのところ、ほとんどの実用的な方法では、ヘッセ行列（近似行列）が適切に動作している限り、SGD の収束（速度）特性を保証することしかできません。たとえば、シーケンス {Bk} (必ずしも BFGS 更新によって生成されるわけではない) がすべての k に対して次を満たす場合: 現時点では、SGD と同じ収束率特性を持ちます。これらの仮定が適切に正当化されている限り、これらの制限が上で説明した方法に適用されると想定するのは合理的です。ただし、確率的勾配推定がヘッセ近似に関係する可能性がある準ニュートン法のコンテキストでは注意が必要です。 3 ディープラーニングこの方向における大きな進歩としては、ディープ ニューラル ネットワーク (DNN) の使用が挙げられます。機械学習の対応する分野はディープラーニング（または階層学習）と呼ばれ、連続した線形および非線形変換からなる複数の層を持つ深いグラフを使用してデータから高レベルの抽象化を構築しようとするアルゴリズムのクラスを表します[6、51、73、37、38、23]。近年、科学者たちは、完全結合ニューラルネットワーク（FNN）[84、28]、畳み込みニューラルネットワーク（CNN）[50]、再帰型ニューラルネットワーク（RNN）[41、57、52]など、さまざまな種類のニューラルネットワークを研究してきました。ここでは、主に最初の 2 種類のニューラル ネットワークに焦点を当てながら、他のニューラル ネットワークにも注目していきます。 3.1 問題の定式化
3.2 確率的勾配降下法DNN のトレーニングに最適化アルゴリズムを適用することに対する混乱した反応を強調するために、次のことを引用します。まず、例えば[11]では、非凸目的関数（常に入力×出力空間から抽出される）を最小化するためにSGDを適用することにより、期待される勾配リスクが少なくとも部分列にわたって消失することが保証されることが示されている。この結論は、SGD が他の最先端の勾配ベースの最適化アルゴリズムと同様の収束保証を達成できることを示唆しており、安心できるものです。しかし、文献にはさまざまな保証があるにもかかわらず、限界があります。結局のところ、多くの勾配ベースの最適化アルゴリズムは目的関数が単調減少することを保証しますが、SG はこのように計算されません。では、部分列が固定点に収束する場合、この点が鞍点、誤差のある局所最小値、または目標値が初期点よりも悪くなる最大値ではないことをどのように確認できるでしょうか。実際のところ、確信は持てません。つまり、SGD メソッドは一般に、グローバル最小値よりもローカル最小値を見つけるのが得意です。一方、SGD は固定値の周りにゆっくりと収束する傾向があるため、ディープ ニューラル ネットワークでの開発を妨げる可能性があります。 一般に、非凸問題の場合、SGDの収束率は[29, 30]で文書化されていますが、それらは非常に限られており、特に§1.3の議論には適用できません。したがって、機械学習における非凸最適化問題に対して SGD が最善のアプローチであると主張することはできません。さらに、以下の 多くの DNN および CNN では、ニューラル ネットワークによって生成される分類の複雑さ C がトレーニング例の数 n よりもはるかに大きいため、 の学習境界は役に立ちません。実際、[90]では、ニューラルネットワークが典型的なタイプのデータセットよりも簡単に優れた性能を発揮できるのは、これらのセット内のデータがランダムに乱されたときだけであることが経験的に示されました。 3.3 ヘッセフリー法このようなヘッセ行列とベクトルの積は方向微分として見ることができるため、DNNの逆伝播アルゴリズムを修正して計算できることが判明した[65]。この積の計算は、勾配の計算よりも定数倍だけ複雑です。結果として得られるメソッドのクラスは、ヘッセ情報がアクセスされて使用されるときにヘッセ行列が明示的に保存されないため、ヘッセフリー最適化メソッドと呼ばれることがよくあります。 DNN の場合、目的関数の非凸性により、真のヘッセ行列が正定値ではない可能性があるという追加の問題が発生します。一般的に言えば、決定論的最適化では、この問題に対処するための 2 つの方法は、ヘッセ行列を変更することと、信頼領域法を適用することです。どちらのアプローチもDNNのトレーニングの文脈で検討されてきた。例えば、[54,55]では、(11)の関数Fのヘッセ行列の式の最初の項をヘッセ行列で近似するガウス・ニュートン法が提案されている（正則化項は省略）。 ここで、は損失関数l(·, ·)の最初のパラメータに関するヘッセ行列、∇p(w, xi)はdy次元関数p(w, x)の重みwに関するヤコビ行列、∇^2 [pj (w, xi)]（すべてのj∈{1, . . . , dy}について）はwに関する要素ごとのヘッセ行列です。 3.4 サブサンプルヘッセ行列法最近、一連の論文（3、15、34）で、研究者は非常に一般的な確率モデルのフレームワークを使用して、凸の場合と非凸の場合の両方で信頼領域、直線探索、および適応型3次正則化法を分析しました。この研究では、確率的に不正確な勾配とヘッセ情報を使用した標準的な最適化手法は、勾配とヘッセ推定値が正の確率で十分に正確である限り、収束率を維持できることが示されています。 機械学習とヘッセ行列および勾配のサンプリングの場合、結果には、アルゴリズムによって実行されるステップの長さに対して十分に大きい |SK| を選択する必要があることだけが必要です。例えば[3,34]では、|SK|の大きさは信頼領域の半径に関連しています。重要なのは、サンプリングされたヘッセ行列にはサンプリングされた勾配よりもはるかに大きなサンプル セットが必要であることです。そのため、正確な勾配のヘッセ推定を使用するというアイデアは、強力な理論的サポートと優れた実用効率を備えた強力なアルゴリズムにつながっています。 | 
