iwasawa_SLTH_slide

効率的な強い宝くじの探索アルゴリズムに関する検討 ○岩澤有祐，平川雅人，松尾豊 JSAI2023 [2A4-GS-2-04] 2023/06/07 @熊本城ホール ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO

■ 概要 強い宝くじを発見するアルゴリズムであるEdge-Popについて， 提案したDying Ratioという指標でその探索能力を分析し この問題を解決する手法を提案し，実験的に有効性を検証した ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 2

“The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks”, ICLR2019 ■背景 | 宝くじ仮説とIterative Pruning 宝くじ仮説：次のような実験的観察に基づく仮説 (1) 重みを普通に訓練し，値の小さい重みを削除（Magnitude Pruning）=> Net A (2) Prune後に残った重みだけを初期値に戻して再学習 => Net B のとき，Net BはNet Aと同等以上の性能を持つ． 刈込みと学習を繰り返す 実験 （Iterative Pruning） 結果 ことで，かなり小さい ネットでも上記が成立 過剰パラメータの良さは 示唆 くじ（重みと構造）をた くさん引いているから？ ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 3

“What's Hidden in a Randomly Weighted Neural Network?”, CVPR2020 ■背景 | 強い宝くじ仮説 (Strong Lottery Tickets Hypothesis; SLTH) 強い宝くじ仮説：目標ネットを𝑓とする．十分に大きいランダムネット𝑔に対しサ ブネット𝑔が存在し， ො 𝑔は𝑓と同等の性能を持つ（学習なしなので強い） ො 実験 結果 示唆 ・ 意義 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO ランダムなWideResNet50の中に ResNet34相当のNNが存在する [Ramanujan+2020] (1) DLにおける構造の重要性 （構造だけでも性能が出る） => Pruning Basedの 学習アルゴリズムの可能性 (2) よりスパースなNNの構築 4

“What's Hidden in a Randomly Weighted Neural Network?”, CVPR2020 ■背景 | Edge-Popアルゴリズム (EP) 本論文[Ramanujan+2019]で提案された強い宝くじを見つけるための手続き 下記2と3を繰り返す． 1. ランダムネットワークの各パラメータにスコアを割り当て 2. スコアがtop k%の重みを使用して順伝播 3. 損失に基づき逆伝播してスコアを更新（重みは更新しない） ※ Straight Through Estimatorを使う 1 2 3 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 5

■背景 | SLTHに関する既存研究 実験研究 理論研究 キーポイント：部分和近似（SubsetSum） 部分和近似 EPを使ったSLTの存在証明 • 画像認識 [1]，画像生成 [2] 部分和近似によるSLTの存在証明 • [5][6] など EPの改善手法 • IteRand [3]，PaB [4] より強い条件での証明 • Universal Lottery Ticket [7] 多くが存在証明．EPの挙動は明らかになっていない => 本研究で分析 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 6

SLTの学習過程の分析手法（分析指標）の提案 ■分析 | EPのDying Edge / Dying Ratioの分析 Dying Edge：EPの学習中に一度も選択されなかったエッジのこと． Dying Ratio：Dying Edgeの割合．DRと表記する．直感的には探索能力を表す． EPをCIFAR-10 / ResNet18に適用した際のDR (𝑘は刈り込み率， 𝑑 𝑇がdying ratio） 結果１：かなりの割合が一度も選ばれていない ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 結果２： どの刈り込み 率でも0.2程 度しか入れ替 わりがない 7

■分析 | Dying Ratio（横軸）と性能（縦軸）の関係 分析内容：学習率・バッチサイズ・Weight Decay・重み初期化・スコア初期化などを変更した 際のDRと精度の関係を可視化．※ DR以外の要素も入りうることに注意（例：学習のしやすさ） 結果 Conv8（左２つ，CIFAR-10とSVHN）: 負の相関が見られる ResNet18（右２つ，同上）:Inverse U-Shape ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 高すぎるDRは性能 に悪影響 8

■提案手法1/2 | Iterative Edge Pop iEP LTHで成功しているIterative Pruningを応用し，EPを 刈り込み率を上げながらKサイクル繰り返し行う． ②のプロセスをどうするかは選択肢がある （Rewinding; 巻き戻しと呼ばれる） 利点１：小さい刈り込み率の積で 目的の刈り込み率を達成できる 利点２：学習にランダムネスを加 えられる（バッチの順序に選ばれ るSLTはセンシティブ） ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 11

■提案手法2/2 | Soft Pruning vs. Hard Pruning Soft Hard（既存）: 各サイクルで下位のエッジを刈り取る． Pruning Soft（提案）: 各サイクルで下位のエッジを刈り取らない． スコアのみ引き継ぐ Hard Pruneだと必要なエッジも捨ててしまう可能性 がある（右図は入れ替わりを可視化したもの）． ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 12

■提案手法 | Iterative Edge Pop (iEP) with Soft Pruning iEP LTHで成功しているIterative Pruningを応用し，EPを 刈り込み率を上げながらKサイクル繰り返し行う． DRを下げる直感的理由１：小さい刈り込み率の積で目的の刈り込み率を達成できる DRを下げる直感的理由２：学習にランダムネスを加えられる （実際バッチの順序に選ばれるSLTはセンシティブ） Soft Hard（既存）: 各サイクルで下位のエッジを刈り取る． Pruning Soft（提案）: 各サイクルで下位のエッジを刈り取らない． DRを下げる直感的理由１：良い初期値を構成することで入れ替わりを促進している ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 13

■分析 | iEP w/ Soft PruningによるDying Ratioの変化 分析内容：CIFAR-10にそれぞれの手法を適用した際の刈り込み率ごとのDying Ratioの比較． 結果1 Soft iEPはDRを初期に抑制 - 50%くらいまではほぼDRが未発生 - 同じ刈り込み率のEPより低い Hard iEPは見かけ上DRが低い 結果2 が，最悪ケースはEPより悪い - 青点線：各サイクルのDR - 青実践：上に既に捨てたエッジをAdd ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 14

■実験 | ImageNetでの結果 iEPにより性能が改善 結果1 結果2 例: 20Mで性能をEPから3%改善 ※ 特にモデルサイズが大きい時顕著 全ての条件でSoft > Hard ※ 大体1%程度の改善 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 16

■実験 | ICIFAR-10, CIFAR-100での結果 Soft iEPが最もよい性能 結果1 - 図中赤線 - 大きい刈り込み率（>90%）で顕著 Fine Tune以外はiEPで性能↑ 結果2 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO - さまざまな巻き戻し方法を検討 （デフォルトは学習率のみ巻き戻す） - 学習率だけRewindするのが良い 17

■議論 | Dying Ratioと性能の関係 実験 結果 • iEP w/ Soft Pruningが複数のデータで良い性能 （特にベースモデルが大きい，刈り込み率が大で顕著な差） • 特にDying Ratioを初期で抑制できる 示唆 • 学習初期でDying Ratioを下げることで，良いサブネットの幹 が獲得され，効率よく全体が探索されたのではないか 課題 • 実際に測りたい探索効率はサブネットの探索効率 • Iterativeにやり直すのはコストが高い =>上記の知見を取り入れたより効率的なアルゴリズム開発 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 18

■議論 | 既存研究との関連 1 SLTHの理論との関連 • SubsetSumでの仮定とややそぐわない（ほぼ未使用）がそれ でもある程度性能が出るという意味で既存の説明に反する 2 EPの改善手法とDying Ratioとの関連 例１ IteRand | 学習途中で使われてないエッジの値を変更 例２ PaB | エッジの符号の反転のみ許す ※ 厳密にはEPではない 3 なぜIterative Pruningが効果的なのか？ • 通常のLTHでも諸説あり，明確な回答はない • 今回の結果は繰り返すことで良い探索ができていることを示唆 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 19

まとめ 強い宝くじを発見するアルゴリズムであるEdge-Popについて， 提案したDying Ratioという指標でその探索能力を分析し この問題を解決する手法を提案し，実験的に有効性を検証した 結果１ EPは著しく高いDRを持ち（探索能力が低い） 性能に悪影響を与えていることが示唆される 結果２ Soft Pruningを使ったiEPにより，DRが抑制され ImageNetで同等パラメータ数で3.0%改善 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 20

勾配法による重み学習 最適化方法の違いはあるが，DNNは次 のような手続きで最適化される (1) 構造（モデル）を決める 例：3層のMLP,Transformer (2) 重みを初期化する． 例：正規分布からのサンプリング (3) 重みを更新する≒学習 例：SGD，Adam，AdaMax ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 22

過剰パラメータ (Overparameterization) と二重降下 (Double Decent) 従来の原則 モデルを複雑にすると，訓練誤差は 下がるがテスト誤差は上がる （モデル複雑度を高めると過学習） 近年の経験則 パラメータが極端に大きいとテスト 誤差が一度上昇しその後減少する， 二重降下現象が起こる ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 23

過剰パラメータにまつわる課題 (1) コストがかかる • 金銭的コスト，Latency，メモリサイズ（エッジデバイスでの活用） • 省エネで高性能なモデルは作れないのか？ (2) 原理が不明 • 二重降下やScaling Lawの存在は様々な条件で観察 • なぜこのような現象が起こるのか？深層NNである意味は？ (3) データの不足 • Web上の良質な言語データこのまま行くとは遅くとも2026年には不足． • よりデータ効率の良いアルゴリズムは作れないのか？ ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 24

Pruning at Initialization Sparse Trainingが宝くじ仮説，Sparse selectionが強い宝くじ仮説に対応 “Recent Advances on Neural Network Pruning at Initialization”, IJCAI2022 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 25

宝くじ仮説 (Lottery Ticket Hypothesis） 過剰パラメータのモデルがうまくいくのは，籤（スパースなサブネット）を たくさん引いているからでは無いか，と言う仮説． 次の図ような実験的観察 [Frankle+2020]に基づく ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 26

宝くじ仮説 (Lottery Ticket Hypothesis)のより形式的な記述 オリジナル論文での主張 ランダムネット𝑔を学習したものを𝑔𝑙𝑒𝑎𝑟𝑛 とする．𝑔に対しサブネット𝑔が存在し， ො 𝑔ො を学習したもの𝑔ො𝑙𝑒𝑎𝑟𝑛 は𝑔𝑙𝑒𝑎𝑟𝑛 と同等の性能を持つ． （弱い）宝くじ仮説 目標ネットを𝑓とする．十分に大きいランダムネット𝑔に対しサブネット𝑔が存在し， ො 𝑔ො を学習したもの𝑔ො𝑙𝑒𝑎𝑟𝑛 は𝑓と同等の性能を持つ． ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 27

Iterative Magnitude Pruning (IMP) Magnitude Pruningを再帰的に行なう 1. 2. NNをランダムに初期化（𝜽𝟎 ）． 𝒎𝟎 = 𝟏 For i in 0…L 1. 2. 3. 𝒎𝒊+𝟏 ⊙ 𝜃𝟎 を訓練 重みの大きさ下位α%を刈り取るマスク𝒎𝒊+𝟏を作成 最終的な𝒎𝑳 ⊙ 𝜽𝟎 を訓練する 𝒎𝑳 ⊙ 𝜽𝟎 はWining Ticketと呼ばれる． ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO ︙ 28

LeNetとConvにおける実験結果 [Frankle+2019] • • • 左：LeNet，右：Conv 実線：Iterative Magnitude Pruningにより得られたサブネット 点線：ランダムに選んだサブネット ランダムよりWining Ticketが大幅に良い（重みと構造のペアが重要） ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 29

Fine-Tuningとの比較 [Renda+2020] • • • 緑：Fine-Tune（重みを継続して学習） 黄色：Learning rate rewinding（学習率のみもとに戻す） 青色：Weight rewinding（重みと学習率をもとに戻す） Fine-TuneよりRewindingする方が良い（特に圧縮率が大きいと顕著） CIFAR-10 ImageNet ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 30

より大きなモデルで比較 • • • 左：CIFAR-10＋VGG，右：CIFAR-10＋ResNet18 点線：再初期化，実線：Winning Ticket 青：学習率デフォルト (0.1)，黄：学習率小，緑：ワームアップあり VGG ResNet18 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 31

（補足）Error Barrier, Local Mode Connectivity Q.なぜ初期値のサブネットで良い解にたどり着けるのか？ W0 W3 W1 W2 （左図）単純なタスクでは初期値から得られた２つの解の内挿にBarrierが発生する点が無い （右図）Barrierの図解 • W1とW2は間を補完しても性能が下がる点がない（同じ局所解周辺） • W1とW3は間を保管すると性能が下がる（異なる局所解周辺）  Barrierがない状況はSGDがノイズに対して頑健（同じ解周辺に到達）を意味 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 32

宝くじ仮説の後継論文の例：宝くじの発見に学習は必要か？ • • 通常の宝くじの発見では，学習後の重みの大きさを利用して刈り込み 宝くじ仮説自体は，「ネットワーク全体の中に学習可能な小さなサブネットワ ークが存在する」というだけ（発見方法は規定していない&IMPはコスト高い） 問：学習可能な良いサブネットワークを初期値から見つけられるないか？ （スパースなサブネットを学習するため，Sparse Trainingとも呼ばれる） => SNIP [Lee+2019], GraSP [Wang+2020], SynFlow [Tanaka+2020]など ※ これらの手法は単に層ごとの刈り込み率を決めているだけだという批判もある （”Pruning Neural Networks at Initialization: Why are We Missing the Mark?”, ICLR2021) 問：初期値ではなく，学習初期に見つけられるか？ => Early Bird Tickets [You+2020] ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 33

宝くじ仮説まとめ • 宝くじ仮説とは次のようなもの 「目標ネットを𝑓とする．十分に大きいランダムネット𝑔に対しサブネット𝑔が存在し， ො 𝑔ො を学習したもの𝑔ො𝑙𝑒𝑎𝑟𝑛 は𝑓と同等の性能を持つ．」 • これ自体は実験的に検証がなされている． • • 画像以外での検証，転移性能の検証なども 宝くじ仮説は「ランダムに初期化したネットワークのうち，実際には疎なサブネットのみを学 習すれば良い」≒「初期化時にPruning出来る可能性を示唆」 • 「宝くじ」というのは「重みと構造のペア」を籤と見立てたアナロジー • 過剰パラメータが良いのは大量の「重みと構造のペア」を引いているから ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 36

目次 • 背景：深層学習の進展と過剰パラメータモデル • 宝くじ仮説 • 強い宝くじ仮説 • 議論と今後の展望 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 37

（再掲）強い宝くじ仮説 目標ネットを𝑓とする．十分に大きいランダムネット𝑔に対しサブネット𝑔が ො 存在し， 𝑔は𝑓と同等の性能を持つ ො 実験 ランダムなWideResNet50の中に ResNet34相当のネットワーク [Ramanujan+2020] 理論 SubSetSumなどによる理論証明 [Pensia+2020] 意義（議論） 新しい学習パラダイムを示唆？ ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 38

宝くじ仮説との違い [弱い宝くじ仮説] 目標ネットを𝑓とする．十分に大きいランダムネット𝑔に対しサブネット𝑔が ො 存在し， 𝑔を学習したもの ො 𝑔ො𝑙𝑒𝑎𝑟𝑛 は𝑓と同等の性能を持つ． [強い宝くじ仮説] “What‘s Hidden in a Randomly Weighted Neural Network?”(CVPR2020) 目標ネットを𝑓とする．十分に大きいランダムネット𝑔に対しサブネット𝑔が ො 存在し， 𝑔は𝑓と同等の性能を持つ． ො 同じ点：どちらもランダムなネットワークの中に「性質の良い」ネットワークが含 まれるということを主張している． 違う点：強い宝くじでは重みの学習を全く必要としない． ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 39

Edge-Popup Algorithm [Ramanujan+2019]で提案された強い宝くじを見つけるための手続き 下記2と3を繰り返す． 1. ランダムネットワークの各パラメータにスコアを割り当て 2. 3. スコアがtop k%の重みを使用して順伝播 損失に基づき逆伝播してスコアを更新（重みは更新しない） ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 40

参考 | 通常の重み学習 vs. 強い宝くじ仮説による構造探索 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 41

Edge-popupに関する補足 • Backward時には使われなかった重みにも勾配を流す • Straight Through Estimatorによる粗い勾配を利用 • スコアの初期値は一様分布に従いサンプリング • 重みの初期値は正負のみを持つ定数{-c, c}のどちらかに初期化 • 通常の学習は正規分布からサンプリングすることが多い • 実験上定数＋正負でのサンプリングの方が性能が良い（後述） ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 42

分類タスクでの結果（[Ramanujan+2020]） Edge-Popupを分類タスクに適用した結果 様々なモデル，様々データで重み学習と同等の性能を達成（初期値は重要） CIFAR-10 • 横軸Prune Rate，縦軸性能 • 青とオレンジが普通の重み学習 • 赤と青がSLTH（異なる重み初期化） ImageNet ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 43

画像生成タスクでの実験結果 • DCGANにおける検証（Discriminatorは学習済み） “Can We Find Strong Lottery Tickets in Generative Models? “, AAAI2023 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 44

強い宝くじ仮説の数学的表現 定理 (強い当たりくじの存在) Optimal Lottery Tickets via SUBSETSUM: Logarithmic Over-Parameterization is Sufficient (2020) 目標ネット 幅 サブネット ランダムネット 刈り込み 幅 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 45

証明のポイント：SubSetSum（部分和近似） 補題 (部分和近似) ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 46

ニューラルネットで考える キーポイント 部分和近似 目標ネット サブネット ランダムネット 刈り込み ※ 重 み を 1に 制限 幅 ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 47

文献: 理論的側面（弱い宝くじ仮説も含む） いろいろな条件での宝くじ仮説の証明 • Optimal Lottery Tickets via SUBSETSUM: Logarithmic Over-Parameterization is Sufficient (NeurIPS2020) • • • • Most Activation Functions Can Win the Lottery Without Excessive Depth (2022) A General Framework For Proving The Equivariant Strong Lottery Ticket Hypothesis (2022) Proving the Strong Lottery Ticket Hypothesis for Convolutional Neural Networks (ICLR2022) On the Existence of Universal Lottery Tickets (2022) なぜ当たりくじを引くと良いのか？ • Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks(NeurIPS2020) なぜ当たりくじを引くと良いのか？ • Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks(NeurIPS2020) ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 48

• https://proceedings.neurips.cc/paper/2020/file/1b742ae215adf18b75449c6e272fd92d-Paper.pdf
• https://arxiv.org/pdf/2205.02321.pdf
• https://arxiv.org/pdf/2206.04270.pdf
• https://hal.archives-ouvertes.fr/hal-03548226/file/SLTHforCNNs.pdf
• https://arxiv.org/pdf/2111.11146.pdf
• https://proceedings.neurips.cc/paper/2021/file/15f99f2165aa8c86c9dface16fefd281-Paper.pdf

（補足）その他の宝くじ仮説 普遍宝くじ “On the Existence of Universal Lottery Tickets” (ICLR2022) ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 49

（再掲）強い宝くじ仮説 「ランダムに初期化したネットワークのなかに，すでに良い性能を達成する 疎なサブネットが含まれる」 実験 ランダムなWideResNet50の中に ResNet34相当のネットワーク [Ramanujan+2020] 理論 SubSetSumなどによる理論証明 [Pensia+2020] 意義（議論） 新しい学習パラダイムを示唆？ ©︎MATSUO LAB, THE UNIVERSITY OF TOKYO 50