[offconvex和訳]Is Optimization a Sufficient Language for Understanding Deep Learning?
最適化は深層学習を理解するのに十分な言語か？
Sanjeev Arora, Jun 3, 2019 (訳 Hiroki Naganuma, May 16th, 2020)
この記事は、下記の記事を翻訳したものです。直感的な理解を目的として、一部解説を加え意訳している箇所もあります。
また、このブログの内容は、 ICML2019において、Sanjeev Arora先生が講演を行っており、SlidesLiveが公開されています。
https://slideslive.com/38917765/is-optimization-a-sufficient-language-to-understand-deep-learning
現在の深層学習では、機械学習は通常、学習タスクに適した目的関数/コスト関数を定義し、その関数を勾配降下法(backpropagationを用いて実装されている)を用いて最適化することに集約されています。毎年何100本もの機械学習の論文が、最適化の様々な側面に向けられているのも不思議ではありません。このブログでは、深層学習を数学的に理解することが目的であるとすれば、最適化の視点は潜在的に不十分であることを示唆します。
Conventional View (CV) of Optimization(最適化の従来の見解): 目的関数の可能な限りの最小値の解をできるだけ速く求める。
先験的に、すべての学習が単一の目的関数を最適化することを含むべきかどうかは明らかではないことに留意してください。これが脳内での学習に当てはまるかどうかは、神経科学の分野における長年の未解決の問題となっています。脳の構成要素は、進化の様々な異変によって再利用されたり、組み合わされたりしてきたように見え、それら全ての集合体は、目的関数の最適化にまで要約されたと言えるかは未だわかっていません。詳細は、Marblestone+ 2016 を参照してください。
Sanjeev Aroraが提唱しているのは、深層学習アルゴリズムもまた、常に目的関数に反映されない重要な特性を持っているということです。現在の深層ネットワークは、過剰パラメータ化されており、複数の最適解を持っています。これらの過剰パラメータ化された深層ネットワークは、目的関数が、ほぼ0になるまで(つまり、最適に近くなるまで)学習され、このようにして発見された最適な(または最適に近い)モデルがunseen/held-out dataでも良好に動作する場合、学習は成功したと言われています(つまり、汎化します)。ここでの注意点は、目的関数の値が汎化について何も示唆しない場合があるということです(詳しくはZhang+ 2016を参照)。
ここで次のような疑問が想起されます: 「機械学習において最適化が最初の行程であるとすれば、汎化理論は、まさしく “第二の行程 “として、考え出されたのではなかったのか？」
例えば、この理論では、解が汎化することを保証にするため、学習する目的関数に正則化を追加する方法を示しています。もしくは、回帰のような単純な設定であっても、early stopping (すなわち、最適値に到達する前に停止)や勾配にノイズを加えること(例えば、バッチサイズや学習率を調整すること)は、完全な最適化よりも望ましい場合があることを示しています。
しかし、実際には明示的な正則化手法や noising tricks は、ランダムなラベルを持つデータであっても、深層ネットワークが低い値に到達してしまうことを防ぐことはできません (詳しくはZhang+ 2016を参照)。現在の汎化理論は、ある特定のモデルがなぜ汎化したのか、その場しのぎの説明を与えるような設計になっています。解がどのようにして得られたかを知ることは不可能であり、最適化のために正則化を推奨することを除けば、”prescriptive”ではありません。(以前のブログ記事で、descriptive 手法とprescriptiveな手法の区別や、汎化理論は主に descriptive であることを説明しています。ここで端的に説明すると、descriptiveは単に事象を説明をするのみで、prescriptiveは洞察に基づいて原因を洞察し事象を説明します)。根本的な謎として下記のものがあります。
Vanilaな勾配降下法(GD)でさえ、妥当な汎化性能を持つモデルを見つけることに長けています。さらに、勾配降下法を高速化する方法(例えば、加速化や適応的正則化)は時として汎化性能を劣化させることがあります。
言い換えれば、GDは元から汎化の良い解を見つけることにバイアスがかっているのです。このような “Magic” は勾配降下法の Trajectory に沿って起こるもので、目的関数の値自体では捉えられません。私たちは古い格言を思い出します。
The journey matters more than the destination.(行程は目的地よりも重要である)
単純ですが、示唆に富む2つの設定(1. Computing with Infinitely Wide Deep Nets, 2. Deep Matrix Factorization for solving Matrix Completion)で勾配降下法の新しい厳密な分析について概略を示し、この視点を説明したいと思います。
謝辞: このトピックに関する見解は、最初に勾配降下法のImplicit Bias に関するTTI Chicagoの優れた論文(Behnam Neyshabur 2017)によって形成され、その後も様々な共著者の貢献によって成り立っています。
Computing with Infinitely Wide Deep Nets
無限幅の深層ネットワークを用いた計算
過剰パラメータ化は深層ネットワークの性質をそこまで損なわないようなので、研究者たちは無限幅の過剰パラメータ化を行った状況を検討しています：CIFAR10のような学習データセットを用いて、AlexNetやVGG19のような幅を無限に増加させることができる古典的な深層ネットワークのアーキテクチャを学習します。ここでの幅とは、畳み込みフィルタのチャンネル数、全結合層の内部レイヤーのノード数です。
初期化(十分に小さなGaussian weightsを使用)と学習は、どのような有限の幅であっても意味があることに注意してください。出力のℓ2損失を仮定しています。無限幅の深層ネットを学習するには世界中の計算機をもってしても不十分であり、私たち理論家はすでに有限のネットを解くことで手一杯です。当然のことながら、このような問題は、絶望的で無意味なものと思われるかもしれません。しかし、数学/物理学の分野では、無限の極限において研究することで、問題に対する洞察を得ることがあります。ここで、無限深層ネットがCIFAR10のような有限データセットで学習している場合、最適解の数は無限にある中で、我々は勾配降下法が何をしているのかを理解しようとしています。過剰パラメータ化された深層ネットワークを用いることで、学習に関する証明可能な洞察が示されています(Zeyuan Allen-Zhu+ 2018(1), Zeyuan Allen-Zhu+ 2018(2), Simon S. Du+ 2018, Difan Zou+ 2018)。
幅が無限に近づくと、カーネル回帰問題のTrajectoryは、勾配降下法のTrajectoryに近づくが、問題のカーネルはいわゆるニューラルタンジェントカーネル(NTK)で、畳み込みニューラルネットワークの場合、カーネルはCNTKと呼ばれます。
このカーネルは、Arthur Jacot+ 2018で命名され、また、過剰パラメータ化された深層ネットワークに関する論文(例えば上述のSimon S. Du+ 2018)などで暗示されています。
このNTKの定義は、ランダムな初期化で無限幅のネットワークを使用します。2つの入力 x_i と x_j に対して、カーネル内積 K(x_i, x_j) は、パラメータに対する出力の勾配∇x の内積であり、それぞれ x=x_i, x=x_j で評価されます。ネットワーク幅が無限大に増加すると、このカーネルの内積は極限値に収束することが示されています。(極限の定義方法には技術的問題があり、一連の新しい論文はここでの形式的な記述を改良しています、 例えば Yang+ 2019 と以下の論文)。
Sanjeev Arora+ 2019では、動的計画法を用いてCNTKを効率的に計算できることが示しています。具体的には、無限幅の深層ネットワークを直接学習することはもちろん計算不可能ですが、学習されたネットワークの任意の入力に対する出力を効率的に計算する方法を提供しています。(余談:これまでの研究は、入力に一番近い層のみを学習し、それより下の層はランダムな初期化を行っています。そのため、Sanjeev Arora+ 2019での結果を、無限幅の深層ネットワークをカーネルやガウス過程と見なしているこれまでの研究と混同しないでください。詳細はSanjeev Arora+ 2019でのcitations/discussionを参照してください)。経験的に、この無限幅の深層ネットワーク(NTKに関するカーネル回帰)は、従来のカーネルよりもCIFAR10上でより良い性能を発揮することがわかっています。例えば、10層のCNNに対応するカーネルを用いた場合、CIFAR10で77.4%のTop-1 Accuracyを達成しています。
Deep Matrix Factorization for solving Matrix Completion
行列補完を解くための深層行列分解
推薦システムの設計に動機づけられた行列補完は、10年以上前からよく研究されています：ここで、行列のK個のランダムな成分が与えられた場合、未知の成分を補完したいと考えます。解は一般的に一意ではありません。しかし、補完する行列が低ランクまたは、ほぼ低ランクであり、いくつかのtechnicalな仮定(例えば、incoherence 条件と呼ばれる計画行列に関する条件)を満たす場合、様々なアルゴリズムが未知の成分を、ほとんどまたは正確に回復することができる。核ノルム/トレースノルムの最小化に基づく有名なアルゴリズムは次のとおり：すべての既知の観測値に適合し、最小の核ノルムを持つ行列を見つけます。(核ノルムはランクの凸緩和であることに注意してください。)
これを、Conventional View (CV)から必要とされる形式で、次のように単一の目的関数として書き下すことができます。S は明らかになった成分のインデックスの部分集合であり、λは乗数です。
ここで、Gunasekar+ 2017の提案をもちいて、核ノルムのpenalty項を無視します。その代わり(単純な勾配降下法/backpropagationを介して)、損失の最初の項において、2つの層を持つ線形ネットワークを単純に学習することによって、欠落した行列成分を補完しようとします。この線形ネットワーク(線形深層ネットワークについては、Nadav Cohen氏のブログ記事を参照してください)は、単なる2つのn×n行列の積なので、次式のとおりとなります。ただし、e_iはi番目が1、その他すべての成分が0であるベクトルとなっています。
添字(i,j)∈Sを用いて、学習の損失は、エンドツーエンドモデルM_2 x M_1が明らかになった成分にどれだけ適合しているかを表しています。Sはすべての 成分の中からランダムに選ばれるため、”汎化 “は、残りの成分を予測するのがうまくいっているということに正確に対応します。
経験的に、深層学習(すなわち、M_1,M_2を解くために勾配降下法を行い、低ランクを確保することを完全に忘れる)による行列を補完は、古典的なアルゴリズムと同様にうまく機能するため、次のような推測につながります。上記が真であれば、この場合の勾配降下法の暗黙的正則化(implicit regularization)効果は核ノルムによって正確に捕捉されることを意味します。
(Conjecture by Gunasekar+ 2017; Rough Statement)上記のように行列補完を深さ２の線形ネットワークを用いて解く場合、得られる解は核ノルム最小化によって得られる解と全く同じである。
上記は、あまりにも単純であり、Sanjeev Arora+ 2019では上記の推測が偽であることを示唆する新しい実験を報告しています。(Conjecture by Gunasekar+ 2017の記述には細かな但し書きがあり、決定的に反論するのはかなり難しいので”示唆”としておきます)
興味深いことに、層の数を2層から3層あるいはそれ以上に増やすことで、問題を過剰パラメータ化すると、Deep Matrix Factorizationと呼ばれます。これは、経験的に、核ノルム最小化よりも高い精度で行列補完を解くことができます。(Sanjeev Arora+ 2019では、核ノルム最小化アルゴリズムが行列を正確に回復するために必要な値よりも、S がわずかに小さい領域で実験を行っていることに注意してください。帰納的バイアスは、このようなデータの乏しい設定では、最も重要です。)
Sanjeev Arora+ 2019では、勾配降下法のtrajectoryを分析し、trajectory が低ランクの解を見つけることに強く偏り、この偏りは単純な核ノルムよりも強いことを示しています。上記に基づいて、深さN個のネットワークが過剰パラメータ化によって改善された性能の部分的な分析が示されています。さらに、このような低ランクな解への偏りは、核ノルムやエンドツーエンドの行列のSchatten準ノルムでは捕捉できないことが示唆されています。
注：経験的に、深層学習のための有名な高速な最適化手法であるadamは、最適化を大幅に高速化しますが、汎化をわずかに損ないます。これは、上で述べたConventional View (CV)では汎化を捉えるには不十分であるということに関連しています。
Conclusions/Takeways
上記の設定は単純ですが、深層学習を理解するためには、目的関数の値と収束率だけに注目した従来の最適化の見方Conventional View (CV)では不十分であることを示唆しています。
(1): 異なる最適化戦略 GD、SGD、Adam、AdaGradなどは、異なる学習アルゴリズムにつながります。これらの最適化戦略は、異なるTrajectoryへと誘導し、異なる汎化特性を持つ解を導く可能性があります。
(2) Trajectoryを論証するための新しいvocabulary (and mathematics)を開発する必要があります。これは、定常点、勾配ノルム、ヘシアンノルム、平滑性などの通常の“landscape view”の範囲を超えたものです。 ただし、Trajectoryは初期化に依存しています。
(3): 大学でODE(常微分方程式)/PDE(偏微分方程式)/力学系/ラグランジアンについて少し勉強しておくことは、Trajectoryを論証するために重要です。
