[DL輪読会]A Bayesian Perspective on Generalization and Stochastic Gradient Descent

DEEP LEARNING JP [DL Papers] A Bayesian Perspective on Generalization and Stochastic Gradient Descent Masahiro Suzuki, Matsuo Lab http://deeplearning.jp/ 1

• http://deeplearning.jp/

本輪読発表について • A Bayesian Perspective on Generalization and Stochastic Gradient Descent – Samuel L. Smith, Quoc V. Le • arXiv:1710.06451（11/6現在ICLR投稿中） • ちなみにSmith氏はICLRにこれともう1本出している模様 – Don't Decay the Learning Rate, Increase the Batch Size – 元のタイトルはUnderstanding Generalization and Stochastic Gradient Descent（redditでディスられてたから変えた？） • 深層学習における汎化の疑問に，ベイジアンの観点から考える． • 合わせて，深層学習と汎化に関する話題について簡単にまとめました． – もっと知りたい方がいる場合は完全版作ります 2

目次 • • • • 機械学習と汎化 深層学習と汎化 Flat minimaとsharp minima ベイズ的観点からの汎化とSGD 3

機械学習と汎化 4

機械学習と汎化 • 機械学習で重要なのは汎化能力！ – 汎化：訓練集合で学習した後に，未知のデータ（テスト集合）について予測 できる能力のこと – 「最適化」と機械「学習」の違いはここにある． • 問題設定（教師あり学習）： – データ分布： (x, y) ⇠ D – 仮説（識別関数，モデル）： f : x ! y ，f 2 F – 損失関数： l(ŷ, y) • やりたいこと： – 期待損失（テスト誤差）R[f ] = ED [l(f (x), y)] を最小化すること – しかしデータ分布は未知なので，直接期待損失を求めることができない！！ 5

汎化ギャップ • 直接データ分布を求められないので，代わりにデータ分布からのサン プルを利用する． – データ集合（訓練集合）： Dn = (x1 , y1 ), ..., (xn , yn ) n 1X – 経験損失（訓練誤差）： R̂n[f ] = n l(f (xi), y1) i=1 – データ集合Dn からアルゴリズム A によって得た仮説を fA(Dn ) とする． • 予測損失の代わりに，経験損失を最小化することにする． – このとき，以下の汎化ギャップを抑えるようにしたい． Rn [fA(Dn ) ] R̂[fA(Dn ) ] – 式のとおり，このギャップは，仮説集合，データ集合，アルゴリズム，損失関 数に依存する． – 統計的学習理論はこれを色々考える分野． 6

汎化ギャップと仮説集合の大きさ • 汎化ギャップは，仮説集合の大きさに依存する． – 仮説集合（モデル容量）が大きいと，ギャップは大きくなる． [Goodfellow+ 16]より • 損失は，バイアス（近似誤差）とバリアンス（推定誤差）に分解する ことができる． – 仮説集合が大きくなると，バイアスが小さくなりバリアンスが大きくなる – 仮説集合が小さくなると，バイアスが大きくなりバリアンスが小さくなる 7

汎化ギャップの評価 • 汎化ギャップは直接求められないが，なんらかの形で評価したい． Rn [fA(Dn ) ] R̂[fA(Dn ) ] • 統計的学習理論では，以下のようなアプローチがある． – 複雑度 – 一様安定性（話さない） – ロバスト性（話さない） • 基本的には，汎化ギャップの上界を求める． 8

仮説集合の複雑度 • PAC学習では，仮説集合の複雑度を考えることで，確率的な上界を 求めることができる． – 複雑度の指標としては，VC次元とラデマッハ複雑度がある． n • 経験ラデマッハ複雑度： 1X R̂(F ) = E [sup ( f 2F n i=1 i f (xi ))] ただし， 1 , ..., n は+1と-1を等確率にとる独立な確率変数． – ランダムなラベル付けに対する，関数集合Fの適合度を表す． • 任意の 2 (0, 1) に対して，1 以上の確率で次式が成り立つ． sup Rn [f ] − R̂[f ]  2R̂(F ) + 3 f 2F s log 2 2n – ラデマッハ複雑度によって，汎化ギャップの上界が求められるようになった！ 9

深層学習と汎化 10

深層学習と仮説集合の大きさ • 深層学習はパラメータが膨大になる． – つまり仮説集合の大きさはかなり大きい->汎化ギャップも大きいはず – パラメータが増えるほど，汎化ギャップはさらに大きくなるはず 0.1 MNIST 0.09 CIFAR-10 Training Test (at convergence) Test (early stopping) 0.08 0.5 0.07 Error Error 0.06 0.05 0.04 0.03 0.4 0.3 0.2 0.02 0.1 0.01 0 Training Test (at convergence) Test (early stopping) 0.6 4 8 16 32 64 128 H 256 512 1K 2K 4K 0 4 8 16 32 64 128 H 256 512 1K 2K 4K 仮説集合の大きさ • しかし実験的には，パラメータが増えるほど汎化性能が良くなること が知られている[Neyshabur+ 17]． – しかも，経験損失が下がりきっても，予測損失は下がっている． 11

深層学習と汎化ギャップ • つまりこういうことになっている． Deep learning なんで？？？ 12

既存の学習理論では説明できない現象 • 従来の統計的学習理論で汎化について説明することはできないか？ – モデルの複雑度（ラデマッハ複雑度）を計測すればよい． • Zhangらによる実験[Zhang+ 17]： – ランダムなラベル付けをした訓練集合で学習 sup Rn [f ] − R̂[f ]  2R̂(F ) + 3 s f 2F log 2 2n • 深層モデルは，これを完全に学習した． • ラデマッハ複雑度は1（max）となり，汎化ギャップの上界が緩くなることを意味する． – モデルに様々な正則化を行って学習 • あまり大きな違いはなかった． • 正則化は仮説集合の大きさを小さくする効果がある． • つまり，仮説集合の大きさを抑える->汎化性能の向上，とは限らない． • 従来の学習理論では説明できないことが，DNNでは起こってい る？？ 13

視点の転換：最適解の形 • 深層モデルの損失関数は非凸 – 局所的最適解などが沢山ある． – それだけではなく，大域的最適解もいくつかある． -> 最適解の「形」にも注目すべきでは？？ • Sharp minimaとflat（broad）minima sharp flat（broad） 14

Flat minimaと汎化性能 • Flat minimaが良い汎化となることが，経験的に指摘されていた [Hochreiter & Schmidhuber+ 97]． – Chaudhariらは，この仮説を元にEntropy-SGDを提案している[Chaudhari+ 17]． • Sharp minimaに行かないような，局所エントロピーに基づく手法． • また，ランダムなラベルで訓練すると，ヘッセ行列の最大固有値が大 きくなる（=sharp minima）ことが確認された[Krueger+ 17] – その他にも，ランダムラベルを学習するためには，モデル容量が大きい必要が あることを確認． • しかし，汎化性能を変えずに，sharp minimaを持つ損失関数に再 パラメータ化できることも示された[Dinh+ 17]． ->良い汎化ならばflat minima，ではない！ 15

バッチサイズとflat minima • Keskarは，大規模なバッチサイズがsharp minimaに落ちることを 実験的に示した[Keskar+ 16]． – 小規模なバッチサイズだとflat minimaに落ちることも確認． • 一方，Hofferは，大規模なバッチサイズがsharp minimaに落ちる のは，反復回数が足りないだけと主張[Hoffer+ 17]． – Flat minimaに行くには時間がかかる． – 異なるバッチサイズで反復回数を同じになるように学習率を調節すると，汎化 ギャップがなくなっていることを確認． – （ただし，一様安定性の観点からは，反復回数を増やさないほうがSGDは安定 する[Hardt+ 16]） 16

ベイズ的観点からの汎化とSGD 17

ベイズ的観点からの汎化とSGD • A Bayesian Perspective on Generalization and Stochastic Gradient Decent[Smith+ 17] – この論文では，汎化とSGDについて次の2つの問題に取り組んでいる． • 訓練で獲得した局所解が汎化するかどうか． • なぜSGDは汎化性能の高い局所解を獲得するのか． – ベイズ的な視点で検証するといろいろわかってくる． 18

ベイズの定理と事後分布
• モデルをM，パラメータをω とすると，パラメータの事後分布は，
{ }
i 1

P (!|{y}, {x}; M )

=

P ({y}|!, {x}; M )P (!; M )
P ({y}|{x}; M )

/

P ({y}|!, {x}; M )P (!; M ).

– 尤度をone-hotのクロスエントロピーとすると，
Q
{ } )
(y |
)
i P
Q
−H(!;M )
H(!;
M
)
=
ln
(P
(y
|!,
xi ; M )).
i
P ({y}|!, {x}; M ) = i PP
(yi |!, xi ; M ) = e
i
，p
(
)
( (p |
))
−λ! /2
P
(!;
M
)
=
λ/2⇡e
– 事前分布は，ガウス分布
．
2

2

• したがって事後分布は，
P (!|{y}, {x}; M ) /

p

λ/2⇡e−C(!;M ) , where C(!; M ) = H(!; M ) + λ! 2 /2

•
は正則化パラメータ
• これはL2正則化クロスエントロピーコスト関数となる
19

予測分布 • 予測分布は，パラメータを周辺化して P (yt |xt , {x}, {y}; M ) = = Z R d! P (yt |!, xt ; M )P (!|{y}, {x}; M ) d! P (yt |!, xt ; M )e−C(!;M ) R . d! e−C(!;M ) P (yt |!, xt ; M ) が滑らかだと , – ここで，パラメータの積分のほとんどが !0の領域で， ( ) , すると，コスト関数Cを最小化してパラメータ !0を求めて，予測分布を y g P (yt |xt ; M ) ⇡ P (yt |!0 , xt ; M ) と近似できる． 20

ベイズ的モデル比較 • 学習したモデル選択のために，2つのモデルM1とM2のエビデンス （周辺尤度）を比較する． P (M1 |{y}, {x}) P ({y}|{x}; M1 ) P (M1 ) = P (M2 |{y}, {x}) P ({y}|{x}; M2 ) P (M2 ) – この設定では，エビデンスは次のように計算できる． ( P 1X P ({y}|{x}; M ) ⇡ exp − C(!0 ) + ln(λi /λ) 2 i=1 !) / ただし， P はモデルパラメータ数， i はヘッセ行列の固有値． • オッカムの剃刀：2つのモデルが同じ精度ならば，より単純なモデル を選択すべきという指標． – 第2項は，オッカム係数． – 曲率の小さい（=flat minima）最小値のほうが，パラメータをデータに合わせ る必要がないので単純になる． 21

ランダムラベルとの比較 • この研究では，ラベルが完全にランダムで，各クラスに等しい確率を 割り当てるモデルとしてnullモデルを考えて，比較する． P ({y}|{x}; N U LL) = (1/n)N = e h b f i i l b l h h N ln (n) id – nはモデルクラス数，Nはラベル数 • エビデンスの比は， P ({y}|{x}; M ) =e P ({y}|{x}; N U LL) ただし E(!0 ) = C(!0 ) + (1/2) P i ln(λi /λ) E(!0 ) , N ln(n) i – この比が0より小さければ，予測モデルが信頼できないことになる． • [Dinh+ 17]と違い，モデルのパラメータ化に依存しない． – [Dinh+ 17]では，ヘッセ行列の固有値 i を変更してパラメータ化を変えていた が，正則化パラメータ も変える必要があった． – 一方，本手法では ln( i / )となっているので，オッカム係数は変わらない． 22

深層学習とヘッセ行列の計算 • 深層モデルでは，パラメータ数が数百万にもなるので，ヘッセ行列を 求めて，エビデンスを計算できない！ • また，多くの同等の最小値があることも考慮する必要． – 隠れユニットの入れ替えで，同値の表現を作れるため． 23

単純なラベルでのランダムラベル問題 • [Zhang+ 17]では，DNNのように仮説集合の大きい場合に，ランダ ムラベルを完全に記憶してしまう問題があった． -> 本研究では，はるかに単純なモデル，ロジスティック回帰で試す． • データセット：各要素をガウス分布からサンプリングした200次元ベ クトルの入力 x – 2つのタスクで実験： • ランダムに0，1を割り当て（ランダムラベルの場合） • 要素の和が1より大きいなら1，そうでなければ0（ラベルを正しく割り当てた場合） 24

実験1-1：簡単なモデルで問題が生じるか確認 – (a)：ランダムラベルの場合，(b)ラベルを正しく割り当てた場合 (a) (b) – ロジスティック回帰でも，ランダムラベルを完全に記憶してしまうことがわか る． • 正則化を高めても，モデルの性能は改善していない． • [Zhang+ 17]の指摘を簡単なモデル，データセットでも再現できた！ 25

実験1-2：ベイズ的エビデンスによる評価 • 対数エビデンス比の値をプロット – 評価を正解率からクロスエントロピーに変更 – (a)：ランダムラベルの場合，(b)ラベルを正しく割り当てた場合 (a) (b) – 訓練集合で評価しているにもかかわらず，対数エビデンス比は予測損失（テス ト誤差）とほぼ同じ傾向を示している． -> ベイズ的エビデンスが，この現象を説明している！ 26

SGDとベイズ推定と汎化 • 前述の結果から，深層ネットワークを訓練する場合は，損失関数では なく，エビデンスを最大にするように極小値をみつけるべきである． – ベイジアンは，ノイズを入れることでベイズ推定等を行っている． • SGDは，パラメータの近似ベイズ推定を行っているとみなせる [Mandt+ 17] – 一定の学習率を持つSGDは，定常分布を持つマルコフ連鎖をシミュレートして いる． • よって，SGDの「ノイズ」を調節することで，良い汎化とすること ができる． – 小規模なバッチは，より大きなノイズを与える． – ノイズによって，sharp minimaから遠ざかるようになる（[Keskar+ 16]の話と 一致）． 27 – つまり，勾配->深い最適値，ノイズ（ミニバッチ）->flat minima

隠れ層を持つモデルでの実験 • 線形モデルでは，単一の凸最適値しかないので，汎化ギャップを確認 できなかった． – ベイジアンの直感とも一致． • 800個の隠れユニットをもつ浅いニューラルネットワークで実験． – MNISTで学習（1000枚のみ） – モーメンタムSGD ->汎化ギャップを示す最も単純なモデル 28

実験2-1：バッチサイズによる予測損失の変化 • 大規模なバッチ（1000）と小規模なバッチ（30）での比較 – (a)：正解率，(b)クロスエントロピー (a) (b) – 小規模な方は時間がかかるものの，良い汎化性能となる． – ただし，L2正則化によって同じくらいとなった（図はappendix参照） 29

実験2-2：バッチサイズによる正解率の変化 • 1~1000のバッチサイズで実験 – (a)：各ステップの正解率，(b)10000ステップでのバッチサイズごとの正解率 (a) (b) – ベイズ推定で想定されるように，明確なバッチサイズのピークが存在する． • バッチサイズが10以下だとうまく学習できなくなる． 30

バッチサイズと各パラメータの関係 • 最適なバッチサイズが，学習率ε，訓練集合サイズN ，そしてモーメ ンタムの係数ωにどのように影響するかを調べる． !! • SGDは ! = ✏ dC + dĈ dC N – dC d! = PN dCi i=1 d! d! d! は真の勾配， dĈ d! d! = N B PB dCi i=1 d! はバッチの期待勾配 h d • 上の式を，確率的微分方程式の離散更新とみなす． dC d! = + ⌘(t) dt d! N • すると，最終的に g = ✏( B 1) ⇡ ✏N/B.というルールが得られる． fl i i – 式展開の詳細は，論文参照． – バッチサイズと，学習率，訓練集合サイズ ，モーメンタムの係数の関係を示 している． 31

実験3-1：最適バッチサイズと学習率の関係 • MNISTで学習 – (a)：バッチサイズと正解率，(b)学習率と最適バッチサイズ (a) (b) – ルールの通り，バッチサイズと学習率が比例関係になっている． Bopt / ✏ 32

実験3-2：最適バッチサイズと訓練集合サイズの関係 • MNISTで学習 – (a)：バッチサイズと正解率，(b)訓練集合サイズと最適バッチサイズ (a) (b) – ルールの通り，バッチサイズと訓練集合サイズが比例関係になっている． Bopt / N 33

スケーリングルールの効果 • 求めたルールによって，次の影響がある． – バッチサイズを大幅に増やすことができる． • 精度を落としたり，計算コストを上げなくても，学習率を調節することで，大幅に向上さ せられる． – 大きなサイズの商用データセットを利用できる． p • [Hoffer+ 17]では ✏ / Bopt . という方法が提案されている． h • しかし今回の実験では，[Hoffer+ 17]の方法では学習率が大きすぎて，逆に精度が下がる結 果となった． 34

実験3-3：最適バッチサイズとモーメンタム係数との関係 • MNISTで学習 – (a)：バッチサイズと正解率，(b)モーメンタム係数と最適バッチサイズ (a) (b) – ルールの通り，反比例の関係になっている． • 詳細はappendix 35

まとめ • 深層学習の汎化を考えると，従来の枠組みでは説明できない現象が発 生している． – 仮説集合が大きいほど，汎化ギャップが下がる． – 複雑度の指標だと汎化ギャップの上界を抑えられない． • Flat minimaに行けば，良さげになりそう． – ただし反例もある． – バッチサイズが関連してそう．ただしこれも反例あり． • ベイジアン的に汎化の問題を捉える． – という以前に，単純なモデルでもランダムラベルが学習される問題発生してる． – モデルエビデンスを比較することで，この問題の解釈が可能になった（ただし 多層はまだ） – SGDを近似ベイズ推定と考えると，ノイズがsharp minimaにはいることを避け ている．バッチサイズが小さいといいのもそのため． – バッチサイズと学習率やデータサイズなどとのルールが得られた． 36

感想 • 汎化ギャップを考えるには，モデルや損失関数だけではなく，アルゴ リズムやデータ集合についても考える必要がある（定義の通り）． – SGDはflat minimaの獲得に貢献している？ – データによる正則化（data augmentationとか）による違いは？ • この分野は，今くらいが楽しい時期かも． • 今回，発表時間的に断念した論文（おすすめ） – [Kawaguchi+ 17] Generalization in Deep Learning • 最初の定式化が素晴らしい（参考にしました）．まとめ方が博論っぽくてすごい． – [Neyshabur+ 17] Exploring Generalization in Deep Learning • この辺りの研究をずっとされているNeyshabur氏の論文． – [Wu+ 17] Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes • Flat minimaに落ちる理由に納得感がある説明． 37

参考資料（論文） • • • • • • • • • • • • [Dinh+ 17] Sharp Minima can Generalize for Deep Nets [Hardt+ 16] Train faster, generalize better: Stability of stochastic gradient descent [Hoffer+ 17] Train longer, generalize better: closing the generalization gap in large batch training of neural networks [Kawaguchi+ 17] Generalization in Deep Learning [Keskar+ 16] On large-batch training for deep learning: Generalization gap and sharp minima [Krueger+ 17] Deep Nets Don't Learn via Memorization [Mandt+ 17] Stochastic Gradient Descent as Approximate Bayesian Inference [Smith+ 17] A Bayesian Perspective on Generalization and Stochastic Gradient Decent [Neyshabur+ 17] Geometry of Optimization and Implicit Regularization in Deep Learning [Neyshabur+ 17] Exploring Generalization in Deep Learning [Wu+ 17] Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes [Zhang+ 16] Understanding deep learning requires rethinking generalization 38

参考資料（スライドや本等） • [Bousquet，17] Why Deep Learning works?（http://www.ds3-datasciencepolytechnique.fr/wp-content/uploads/2017/08/2017_08_31_16301730_Olivier_Bousquet_Understanding_Deep_Learning.pdf） • [Deng+ 14] Rademacher Complexity （http://web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/10_rade macher.pdf） • [Goodfellow+ 16] Deep Learning • [岡野原, 17] Deep Learning Practice and Theory （https://www.slideshare.net/pfi/deep-learning-practice-and-theory） • [金森，15] 統計的学習理論 (機械学習プロフェッショナルシリーズ) 39

• http://www.ds3-datascience-
• https://www.slideshare.net/pfi/deep-learning-practice-and-theory