早期終了タイミングを予測する:深層学習における確率勾配の分布の変化点検出
八島慶汰1 石川康太2 佐藤育郎2 野村哲弘1 横田理央1 松岡聡3,1
1: 東京工業大学, 2: デンソーアイティーラボラトリ, 3: 理化学研究所

Ⅰ. 貢献

Ⅲ.実験: 確率勾配のノルム分布の切り替わり

DNNのSGD学習の振る舞いと汎化性能の関係を実験的に調べるため，学習データ標本ごとの勾配ノルムの分布を毎イテレーション追跡し目的

・確率勾配のノルムの分布は学習初期では正規分布に近く，学習後期 (=過学習時) ではべき分布に近い

要領

結果

Ⅱ. 背景 (SGDの確率微分方程式による解釈)

i2B<latexit sha1_base64="zZ0y7Z7U/Em0Q/N0nY4X/w2qSQ8=">AAACPHicbVDPaxNBGJ1t/VHjj8Z69PJhEFLEsFsFBRFKevFY0TSFbFi+nXybDJmdXWa+FcN2/7Be+kd48+SlB0V67dlJmoO2Phh48973mPleWmrlOAy/Bxubt27fubt1r3X/wcNH2+3HO0euqKykgSx0YY9TdKSVoQEr1nRcWsI81TRM5wdLf/iFrFOF+cyLksY5To3KlET2UtL+NEzq+YuogfcwTObwEmJihFhTxl2IM4uyjpr6pH/SQOyqPKkVxMpA318Nphoh635N1LtleBdiq6Yz3k3anbAXrgA3SbQmHbHGYdL+Fk8KWeVkWGp0bhSFJY9rtKykpqYVV45KlHOc0shTgzm5cb1avoHnXplAVlh/DMNK/TtRY+7cIk/9ZI48c9e9pfg/b1Rx9nZcK1NWTEZePZRVGriAZZMwUZYk64UnKK3yfwU5Q98Y+75bvoTo+so3ydFeL3rV2/v4urPfX9exJZ6KZ6IrIvFG7IsP4lAMhBSn4of4KX4FZ8F58Du4uBrdCNaZJ+IfBJd/AGDoq9s=</latexit>!

ミニバッチ勾配 = 真の勾配 + 確率的ノイズ：
W =

⌘i2N

<latexit sha1_base64="xO53zeYMjm0AfiCRAunhJTNEiiA=">AAACpHicnVFdb9MwFHXC1yhfhT3ycqECdUKrkoEEEpo0FSR4QFMn6DqpLpHj3rTWHCeybxBV1l+2f7E3/g1ul4fR7YkrWT4+9xzZPjcttXIURX+C8NbtO3fvbd1vPXj46PGT9tNnx66orMShLHRhT1LhUCuDQ1Kk8aS0KPJU4yg9/bTqj36hdaowP2hR4iQXM6MyJQV5Kmmf88+oScAI9mGXo0dcY0Zd4JkVso6X9dnh2RK4q/KkVsCVgUN/NCLVArLu70R9hNEOvPk/2+4VfX9D379Bz62azWmn2ZJ2J+pF64LrIG5AhzU1SNoXfFrIKkdDUgvnxnFU0qQWlpTUuGzxymEp5KmY4dhDI3J0k3od8hJeeWYKWWH9MgRr9qqjFrlzizz1ylzQ3G32VuRNvXFF2YdJrUxZERp5eVFWaaACVhODqbIoSS88ENIq/1aQc+FjIz/Xlg8h3vzydXC814vf9vaO3nUO+k0cW+w5e8m6LGbv2QH7ygZsyGTwIvgSDIKj8HX4LfweDi+lYdB4ttk/Ff78C47rysM=</latexit>

1 X
rf (xi ; W )
|N |
i2N

真の勾配（フルバッチ）

1 X
rf (xi ; W )
|B|
i2B!!

ノイズ項（分散 ∝ 1/|B|）dWt =<latexit sha1_base64="vhYRiT0n10QWXYqQGLRZatpBoNs=">AAACIXicbVBNS8NAEN34bf2qevSyWARFWhIV9CKIevCoYG2hqWGy2dTFzSbuToQS+le8+Fe8eFDEm/hn3NYetPpg4O17M+zMCzMpDLruhzM2PjE5NT0zW5qbX1hcKi+vXJk014zXWSpT3QzBcCkUr6NAyZuZ5pCEkjfC25O+37jn2ohUXWI34+0EOkrEggFaKSgfRI0A6SGt+gpCCTTetO8tGiHdpr6501j4IUe4Lqpej54OzB6NjgMMyhW35g5A/xJvSCpkiPOg/O5HKcsTrpBJMKbluRm2C9AomOS9kp8bngG7hQ5vWaog4aZdDC7s0Q2rRDROtS2FdKD+nCggMaabhLYzAbwxo15f/M9r5RgftAuhshy5Yt8fxbmkmNJ+XDQSmjOUXUuAaWF3pewGNDC0oZZsCN7oyX/J1U7N263tXOxVjo6HccyQNbJONolH9skROSPnpE4YeSBP5IW8Oo/Os/PmvH+3jjnDmVXyC87nFzMqoRc=</latexit>

rf (Wt )dt +:= (⌘/|B|)

1p変化点

(3)

(2) 変化点(尤度比＝1)(3) 過学習時

≃≃

正規分布

べき分布

Ⅳ.実験: 変化点と早期終了タイミングの関係
目的

正規分布とべき分布の尤度が等しくなる変化点と汎化最良となるタイミングの近さを評価する

要領

・Conv4層 + FC2層，第2Conv層を解析
次元数が少ないモデル(Slim)と4xのモデル(Fat)を使用

連続時間による近似 (η→0)

・Brownian motion [1, 2]

確率勾配のノルムは，初期値付近で正規分布の尤度が高く，過学習時でべき分布の尤度が高い(1) 初期値付近(Wk: 重み, xi: サンプル, f: ロス関数, η: 学習率, B: ミニバッチ)

1 X
rf (xi ; W ) +|N |(3)(1) (2)

ミニバッチSGD (確率的勾配降下) の学習則：⌘(1) (2)・正規分布，べき分布の尤度を測定ことを実験的に確認した．

Wk+1 = Wk

汎化最良・Conv4層 + FC2層，第2Conv層の勾配を解析
・CIFAR10データセット

・正規分布・べき分布の尤度が拮抗する
変化点の近くで汎化が最良となるX
1rf (xi ; Wk )|B|

初期値付近と過学習時での標本ごとの勾配ノルムの分
布形状の違いを調べる

・CIFAR10，CIFAR100データセット
・温度一定の下バッチサイズ (BS) を変化 (1〜4096)
1 D(W )dBtt

結果

若干の例を除き，変化点の近傍で汎化が最良となる: 逆温度

モデルサイズに対する傾向：大きいモデルではより両タイミングの一致性が高い

à 解の分布はエントロピーの高い状態をとる[3]データセットに対する傾向：

CIFAR10では相対的に変化点が早く、CIFAR100では遅い
バッチが大きいほど両タイミングが遅くなる<latexit sha1_base64="CyOqNZ1hA2SDX6hQaE6USzZUDJ0=">AAACEHicbVA9SwNBEN2LXzF+nVraLAZRC+OdCooghNhYRjAq5GLY28wlS/Y+2J0TwpmfYONfsbFQxNbSzn/jJqZQ44OBt+/NsDPPT6TQ6DifVm5icmp6Jj9bmJtfWFyyl1cudZwqDjUey1hd+0yDFBHUUKCE60QBC30JV373dOBf3YLSIo4usJdAI2TtSASCMzRS0970fEBGj0+oJyHALeoNnrv0rnJHPSXaHdy+yXbcftMuOiVnCDpO3BEpkhGqTfvDa8U8DSFCLpnWdddJsJExhYJL6Be8VEPCeJe1oW5oxELQjWx4UJ9uGKVFg1iZipAO1Z8TGQu17oW+6QwZdvRfbyD+59VTDI4amYiSFCHi3x8FqaQY00E6tCUUcJQ9QxhXwuxKeYcpxtFkWDAhuH9PHieXeyV3v7R3flAsV0Zx5MkaWSdbxCWHpEzOSJXUCCf35JE8kxfrwXqyXq2379acNZpZJb9gvX8BXAua6Q==</latexit>

バッチサイズに対する傾向：・Levy motion [4]※ BS=4096, Slim, C100 のみ外れ値 Tequiv ' 4, 000<latexit sha1_base64="jG5ieut7r2IkWP8xsmocgZBcies=">AAAB/3icdVDJSgNBEO2JW4zbqODFS2MQPMgwkwQSb0EvHiNkg2QIPZ1K0qRnSXdPIIw5+CtePCji1d/w5t/YWQTXBwWP96qoqudFnEll2+9GamV1bX0jvZnZ2t7Z3TP3D+oyjAWFGg15KJoekcBZADXFFIdmJID4HoeGN7ya+Y0xCMnCoKomEbg+6QesxyhRWuqYR9VOAqOYjae4LZkPI1w4t227Y2ZtK39RKhVz+DdxLHuOLFqi0jHf2t2Qxj4EinIiZcuxI+UmRChGOUwz7VhCROiQ9KGlaUB8kG4yv3+KT7XSxb1Q6AoUnqtfJxLiSznxPd3pEzWQP72Z+JfXilWv5CYsiGIFAV0s6sUcqxDPwsBdJoAqPtGEUMH0rZgOiCBU6cgyOoTPT/H/pJ6znLyVuylky5fLONLoGJ2gM+SgIiqja1RBNUTRLbpHj+jJuDMejGfjZdGaMpYzh+gbjNcPC3uVeg==</latexit>

dWt =<latexit sha1_base64="++soaBm2e7Z330YOKEaZd40bUYw=">AAACNXicbVBNa9tAEF0lTZM6SeMmx16GmoJDsCMlgfRSCOmlBx9cqOOA5YjRamUvWa3E7qhghP9UL/0fOSWHHFpKr/0LXX8c8tEHC2/em2F2Xlwoacn377yV1RdrL9c3XtU2t7Zf79Tf7F7YvDRc9HiucnMZoxVKatEjSUpcFkZgFivRj68/zfz+N2GszPVXmhRimOFIy1RyJCdF9U7Sjwg+QivUGCuEtOnqfUgIDiCMBeFV1WqGqIoxQguCfTiERTWF0MpRhpB0IrpaaFG94bf9OeA5CZakwZboRvWbMMl5mQlNXKG1g8AvaFihIcmVmNbC0ooC+TWOxMBRjZmww2p+9RTeOyWBNDfuaYK5+nCiwszaSRa7zgxpbJ96M/F/3qCk9MOwkrooSWi+WJSWCiiHWYSQSCM4qYkjyI10fwU+RoOcXNA1F0Lw9OTn5OKoHRy3j76cNM7Ol3FssLfsHWuygJ2yM/aZdVmPcfad3bKf7Jf3w7v3fnt/Fq0r3nJmjz2C9/cfM0uoKg==</latexit>

rf (Wt )dt +(↵ 1)/↵↵dLt

à ヘビーテールな勾配ノイズによってNarrowminimaから抜け出しやすく，Wide minimaに留まりやすくなる[4]エラーバー：
Validation lossが最小値+5%のタイミング

ところが，• 実際は，過学習を避けるためvalidation setを用いた早期終了が必要• 早期終了時の確率勾配の性質は？？？
参考文献:
1. Li, Qianxiao+, “Stochastic modified equations and adaptive stochastic gradient algorithms.”, ICML 2017
2. Smith, Samuel L.+, "A bayesian perspective on generalization and stochastic gradient descent.”, ICLR 2018
3. Chaudhari, Pratik+, "Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks.”, ICLR 2018
4. Simsekli, Umut+. "A tail-index analysis of stochastic gradient noise in deep neural networks.”, ICML 2019