The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks 【1 INTRODUCTION】【論文 ほぼ Google 翻訳 自分用】

この記事は自分用のメモみたいなものです.
ほぼ Google 翻訳でお送りします.
間違いがあれば指摘していだだけると嬉しいです.

翻訳元
[The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://arxiv.org/abs/1803.03635)

前: [【ABSTRACT】](https://qiita.com/tomato_/items/81f8b26b4c7ee1979a6f)
次: [【2 WINNING TICKETS IN FULLY-CONNECTED NETWORKS】](https://qiita.com/tomato_/items/7ae8d891564ef159c9a6)

# 1 INTRODUCTION

### 訳文

ニューラルネットワークから不要な重みを削除する (プルーニング)  (LeCun et al., 1990; Hassibi & Stork, 1993; Han et al., 2015; Li et al., 2016) 手法により, 精度を損なうことなくパラメーター数を $90\%$ 以上削減できます. そうすることで, トレーニングされたネットワークのサイズ (Han et al., 2015; Hinton et al., 2015) またはエネルギー消費 (Yang et al., 2017; Molchanov et al., 2016; Luo et al., 2017) が減少し, 推論がより効率的になります. しかし, ネットワークのサイズを縮小できるなら, トレーニングをより効率的にするために, なぜこの小さなアーキテクチャをトレーニングしないのですか? 現在の経験では, プルーニングによって明らかにされたアーキテクチャは最初から訓練するのが難しく, 元のネットワークよりも精度が低くなります.[^j1]

例を考えてみましょう. 図 1 では, MNIST の全結合ネットワークと CIFAR10 のたたみ込みネットワークからサブネットワークをランダムにサンプリングしてトレーニングします. ランダムサンプリングは, LeCun et al. (1990) と Han et al. (2015) が使用する非構造化プルーニングの効果をモデル化します. さまざまなレベルのスパース性にわたって, 破線は最小検証損失[^j2]のイテレーションとそのイテレーションでのテスト精度をトレースします. ネットワークがよりスパースになると, 学習が遅くなり, 最終的なテストの精度が低下します.

![0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88255/6838930e-2ed2-749c-4324-fddaa658cb6c.png)

> 図 1: MNIST の Lenet アーキテクチャと CIFAR10 の Conv-2, Conv-4, および Conv-6 アーキテクチャのアーリーストッピングが発生するイテレーション (左) とそのイテレーション でのテスト精度 (右) (図 2 を参照). さまざまなサイズでトレーニングを開始したとき. 
> 破線はランダムにサンプリングされたスパースなネットワーク(10回の試行の平均). 実線は当選チケット (5回の試行の平均).

この論文では, 最初からトレーニングを行い, 同等のテスト精度に達しつつ, 少なくとも大規模なサブネットワークと同じ速度で学習する小さなサブネットワークが一貫して存在することを示します. 図 1 の実線は, 検出されたネットワークを示しています. これらの結果に基づいて, 宝くじ仮説を述べます

**宝くじ仮説.** ランダムに初期化された全結合ニューラルネットワークには, ある初期値のサブネットワークが含まれています. このサブネットワークは単独でトレーニングされると, 最大で同じイテレーション数のトレーニング後に元のネットワークのテスト精度と一致します.

より正式には, 初期パラメーター $\theta = \theta_0 \sim \mathcal{D}\_\theta$ を持つ全結合フィードフォワードニューラルネットワーク $f(x;\theta)$ を考えます. トレーニングセットで確率的勾配降下法 (SGD) を使用して最適化する場合 $f$ は, テスト精度 $a$, イテレーション $j$ で最小検証損失 $l$ に達します. さらに, 初期値が $m\odot\theta_0$ になるように, パラメーターにマスク $m\in\\{0,1\\}^{|\theta|}$ を使用して $f(x;m\odot\theta)$ をトレーニングすることを検討します. 同じトレーニングセット ($m$ を固定) で SGD を使用して最適化する場合, $f$ はテスト精度 $a'$, イテレーション $j'$ で最小検証損失 $l'$ に達します. 宝くじ仮説では,  $j'\leq j$ (相応のトレーニング時間), $a' \geq a$  (相応の精度), および $||m||_0 \ll |\theta|$ (より少ないパラメーター) を予測します.

標準のプルーニング手法により, このようなトレーニング可能なサブネットワークが全結合畳み込みフィードフォワードネットワークから自動的に発見されることがわかります. これらのトレーニング可能なサブネットワーク $f(x;m\odot\theta_0)$ を当選チケットとして指定します. これは, 重みと学習が可能な接続の組み合わせで初期値宝くじに当たったものが見つかったためです. パラメータがランダムに再初期化 $(f(x;m\odot\theta_0')$ where $\theta_0'\sim \mathcal{D}\_\theta)$ されると, 当選チケットは元のネットワークのパフォーマンスと一致しなくなり, 適切に初期化されない限りこれらの小規模ネットワークは効果的にトレーニングされないという証拠を提供します.

**winning tickets の特定.** ネットワークをトレーニングし, その最小の重みをプルーニングすることにより, 当選チケットを識別します. 残りの枝刈りされていない接続は, 当選チケットのアーキテクチャを構成します. 作業に固有の, プルーニングされていない各接続の値は, トレーニング前に元のネットワークからの初期値にリセットされます. これが私たちの中心的な実験を形成します:
1. ニューラルネットワーク $f(x;\theta_0)(where \theta_0 \sim \mathcal{D}\_{\theta})$ をランダムに初期化する.
2. パラメータ $\theta_j$ に到達するまで, $j$ 回のイテレーションについてネットワークをトレーニングする.
3. $\theta_j$ のパラメーターの $p\%$ をプルーニング, マスク $m$ を作成する.
4. 残りのパラメーターを $\theta_0$ の値にリセットし, 当選チケット $f(x;m\odot\theta_0)$ を作成する.

説明したように, このプルーニングアプローチはワンショットです: ネットワークは 1 回トレーニングされ, 重みの $p\%$ がプルーニングされ, 生き残った重みがリセットされます. ただし, この論文では, ネットワークのトレーニング, プルーニング, およびリセットを $n$ ラウンドにわたって繰り返し行う反復プルーニングに焦点を当てています; 各ラウンドは, 前のラウンドで生き残った重みの $p^{\frac{1}{n}}\%$ をプルーニングします. 結果は, 反復プルーニングが, ワンショットプルーニングよりも小さいサイズで元のネットワークの精度に一致する当選チケットを見つけることを示しています.

**結果.** ドロップアウト, 重み減衰, バッチ正規化, 残差ネットワークなどの手法を使用して, MNIST の全結合アーキテクチャと, CIFAR10 の畳み込みアーキテクチャで, 複数の最適化戦略 (SGD, モーメンタム, およびAdam) で当選チケットを識別します. 非構造化プルーニング手法を使用しているため, これらの当選チケットはスパースです. より深いネットワークでは, 当選チケットを見つけるためのプルーニングベースの戦略は学習率に敏感です: より高い学習率で当選チケットを見つけるには Warmup が必要です. 見つかった当選チケットは, 元のネットワークのサイズ (より小さいサイズ) の 10-20$\%$ (またはそれ以下) です. そのサイズまでは, 最大で同じイテレーション数 (相応のトレーニング時間) で, 元のネットワークのテストの精度 (相応の精度) を満たします. ランダムに再初期化されると, 当選チケットのパフォーマンスははるかに悪くなります. つまり, 構造だけでは当選チケットの成功を説明できません.

![1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88255/f203f20b-7160-40c2-1339-7c3dfb205f3d.png)

> 図 2: この論文でテストしたアーキテクチャ. Convolutions are 3x3. Lenet is from LeCun et al. (1998). Conv-2/4/6 are variants of VGG (Simonyan & Zisserman, 2014). Resnet-18 is from He et al. (2016). VGG-19 for CIFAR10 is adapted from Liu et al. (2019). Initializations are Gaussian Glorot (Glorot & Bengio, 2010). 括弧は, レイヤーの周りの残差接続を示します.

**宝くじ予想.**　動機付けの質問に戻ると, 仮説を, SGD が適切に初期化された重みのサブセットを探して訓練する未検証の予想に拡張します.高密度でランダムに初期化されたネットワークは, プルーニングから生じるスパースなネットワークよりもトレーニングが容易です. これは,トレーニングが当選チケットを回復する可能性のあるサブネットワークが多いためです.

**貢献.**

- プルーニングにより, 同等のイテレーション数で派生した元のネットワークに匹敵するテスト精度に達する, トレーニング可能なサブネットワークが明らかになることを実証します.
- プルーニングは, 元のネットワークよりも速く学習し, より高いテスト精度とより一般化された当選チケットを見つけることを示します.
- これらの発見を説明するために, ニューラルネットワークの構成に関する新しい視点として宝くじ仮説を提案します.

**理論的含意.** この論文では, 宝くじ仮説を経験的に研究します. 当選チケットの存在を実証したので, この知識を活用して次のことを行います:
トレーニングパフォーマンスの向上. 当選チケットは最初から分離してトレーニングできるため, 当選チケットを検索してできるだけ早くプルーニングするトレーニングスキームを設計できることが望まれます.

より良いネットワークを設計します. 当選チケットは, 特に学習が得意なスパースアーキテクチャと初期値の組み合わせを明らかにします. 当選チケットからインスピレーションを得て, 学習に役立つ同じプロパティを持つ新しいアーキテクチャと初期値スキームを設計できます. 1つのタスクで発見された当選チケットを他の多くのチケットに転移することもできます.

ニューラルネットワークの理論的理解を向上させます. ランダムに初期化されたフィードフォワードネットワークが当選チケットを含むように見える理由と, 最適化 (Du et al., 2019) と一般化(Zhou et al., 2018; Arora et al., 2018) の理論的研究への潜在的な影響を調べることができます.


### 原文

Techniques for eliminating unnecessary weights from neural networks (pruning) (LeCun et al., 1990; Hassibi & Stork, 1993; Han et al., 2015; Li et al., 2016) can reduce parameter-counts by more than 90$\%$ without harming accuracy. Doing so decreases the size (Han et al., 2015; Hinton et al., 2015) or energy consumption (Yang et al., 2017; Molchanov et al., 2016; Luo et al., 2017) of the trained networks, making inference more efficient. However, if a network can be reduced in size, why do we not train this smaller architecture instead in the interest of making training more efficient as well? Contemporary experience is that the architectures uncovered by pruning are harder to train from the start, reaching lower accuracy than the original networks.[^e1]

Consider an example. In Figure 1, we randomly sample and train subnetworks from a fully-connected network for MNIST and convolutional networks for CIFAR10. Random sampling models the effect of the unstructured pruning used by LeCun et al. (1990) and Han et al. (2015). Across various levels of sparsity, dashed lines trace the iteration of minimum validation loss[^e2] and the test accuracy at that iteration. The sparser the network, the slower the learning and the lower the eventual test accuracy.

![0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88255/6838930e-2ed2-749c-4324-fddaa658cb6c.png)

>Figure 1: The iteration at which early-stopping would occur (left) and the test accuracy at that iteration (right) of the Lenet architecture for MNIST and the Conv-2, Conv-4, and Conv-6 architectures for CIFAR10 (see Figure 2) when trained starting at various sizes. Dashed lines are randomly sampled sparse networks (average of ten trials). Solid lines are winning tickets (average of five trials).

In this paper, we show that there consistently exist smaller subnetworks that train from the start and learn at least as fast as their larger counterparts while reaching similar test accuracy. Solid lines in Figure 1 show networks that we find. Based on these results, we state the lottery ticket hypothesis.

**The Lottery Ticket Hypothesis.** A randomly-initialized, dense neural network contains a subnetwork that is initialized such that—when trained in isolation—it can match the test accuracy of the original network after training for at most the same number of iterations.

More formally, consider a dense feed-forward neural network $f(x;\theta)$ with initial parameters $\theta = \theta_0 \sim \mathcal{D}\_\theta$. When optimizing with stochastic gradient descent (SGD) on a training set, $f$ reaches minimum validation loss $l$ at iteration $j$ with test accuracy $a$. In addition, consider training $f(x;m\odot\theta)$ with a mask $m\in\\{0,1\\}^{|\theta|}$ on its parameters such that its initialization is $m\odot\theta_0$. When optimizing with SGD on the same training set (with $m$ fixed), $f$ reaches minimum validation loss $l'$ at iteration $j'$ with test accuracy $a'$. The lottery ticket hypothesis predicts that $\exists\;m$ for which $j \leq j'$(commensurate training time), $a' \geq a$(commensurate accuracy), and $||m||_0 \ll |\theta|$(fewer parameters).

We find that a standard pruning technique automatically uncovers such trainable subnetworks from
fully-connected and convolutional feed-forward networks. We designate these trainable subnetworks, $f(x;m\odot\theta_0)$, winning tickets, since those that we find have won the initialization lottery with a combination of weights and connections capable of learning. When their parameters are randomly reinitialized $(f(x;m\odot\theta_0')$ where $\theta_0'\sim \mathcal{D}\_\theta)$, our winning tickets no longer match the performance of the original network, offering evidence that these smaller networks do not train effectively unless they are appropriately initialized.

**Identifying winning tickets.** We identify a winning ticket by training a network and pruning its smallest-magnitude weights. The remaining, unpruned connections constitute the architecture of the winning ticket. Unique to our work, each unpruned connection’s value is then reset to its initialization from original network before it was trained. This forms our central experiment:

1. Randomly initialize a neural network $f(x;\theta_0)(where \theta_0 \sim \mathcal{D}\_{\theta})$.
2. Train the network for $j$ iterations, arriving at parameters $\theta_j$.
3. Prune $p\%$ of the parameters in $\theta_j$ , creating a mask $m$.
4. Reset the remaining parameters to their values in $\theta_0$, creating the winning ticket $f(x;m\odot\theta_0)$.

As described, this pruning approach is one-shot: the network is trained once, $p\%$ of weights are pruned, and the surviving weights are reset. However, in this paper, we focus on iterative pruning, which repeatedly trains, prunes, and resets the network over $n$ rounds; each round prunes $p^{\frac{1}{n}}\%$ of the weights that survive the previous round. Our results show that iterative pruning finds winning tickets that match the accuracy of the original network at smaller sizes than does one-shot pruning.

**Results.** We identify winning tickets in a fully-connected architecture for MNIST and convolutional architectures for CIFAR10 across several optimization strategies (SGD, momentum, and Adam) with techniques like dropout, weight decay, batchnorm, and residual connections. We use an unstructured pruning technique, so these winning tickets are sparse. In deeper networks, our pruning-based strategy for finding winning tickets is sensitive to the learning rate: it requires warmup to find winning tickets at higher learning rates. The winning tickets we find are 10-20$\%$ (or less) of the size of the original network (smaller size). Down to that size, they meet or exceed the original network’s test accuracy (commensurate accuracy) in at most the same number of iterations (commensurate training time). When randomly reinitialized, winning tickets perform far worse, meaning structure alone cannot explain a winning ticket’s success.

![1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88255/f203f20b-7160-40c2-1339-7c3dfb205f3d.png)

Figure 2: Architectures tested in this paper. Convolutions are 3x3. Lenet is from LeCun et al. (1998).
Conv-2/4/6 are variants of VGG (Simonyan & Zisserman, 2014). Resnet-18 is from He et al. (2016). VGG-19 for CIFAR10 is adapted from Liu et al. (2019). Initializations are Gaussian Glorot (Glorot & Bengio, 2010). Brackets denote residual connections around layers.

**The Lottery Ticket Conjecture.** Returning to our motivating question, we extend our hypothesis into an untested conjecture that SGD seeks out and trains a subset of well-initialized weights. Dense, randomly-initialized networks are easier to train than the sparse networks that result from pruning because there are more possible subnetworks from which training might recover a winning ticket.

**Contributions.**

- We demonstrate that pruning uncovers trainable subnetworks that reach test accuracy comparable to the original networks from which they derived in a comparable number of iterations.
- We show that pruning finds winning tickets that learn faster than the original network while
reaching higher test accuracy and generalizing better.
- We propose the lottery ticket hypothesis as a new perspective on the composition of neural
networks to explain these findings.

**Implications.** In this paper, we empirically study the lottery ticket hypothesis. Now that we have demonstrated the existence of winning tickets, we hope to exploit this knowledge to:

Improve training performance. Since winning tickets can be trained from the start in isolation, a hope is that we can design training schemes that search for winning tickets and prune as early as possible.

Design better networks. Winning tickets reveal combinations of sparse architectures and initializations that are particularly adept at learning. We can take inspiration from winning tickets to design new architectures and initialization schemes with the same properties that are conducive to learning. We may even be able to transfer winning tickets discovered for one task to many others.

Improve our theoretical understanding of neural networks. We can study why randomly-initialized
feed-forward networks seem to contain winning tickets and potential implications for theoretical
study of optimization (Du et al., 2019) and generalization (Zhou et al., 2018; Arora et al., 2018).

[^j1]: “プルーニングされたモデルを最初からトレーニングすることは, プルーニングされたモデルを再トレーニングすることよりもパフォーマンスが劣ります. これは, 小容量のネットワークをトレーニングすることの難しさを示している場合があります.” “再トレーニング中, プルーニングされたレイヤーを再初期化するよりも, プルーニングを生き残った接続の初期トレーニングフェーズからの重みを保持する方が良い ... 勾配降下法は, ネットワークが最初にトレーニングされたときに適切なソリューションを見つけることができますが, 一部のレイヤーを再初期化して再トレーニングした後ではありません.”

[^j2]: ネットワークが学習する速度のプロキシとして, アーリーストッピングの基準はトレーニングを終了するイテレーションを使用します. この論文全体で使用する特定のアーリーストッピングの基準は, トレーニング中の最小検証損失のイテレーションです. この選択の詳細については, 付録 C を参照してください.



[^e1]: “Training a pruned model from scratch performs worse than retraining a pruned model, which may indicate the difficulty of training a network with a small capacity.” “During retraining, it is better to retain the weights from the initial training phase for the connections that survived pruning than it is to re-initialize the pruned layers...gradient descent is able to find a good solution when the network is initially trained, but not after re-initializing some layers and retraining them.” 
[^e2]: As a proxy for the speed at which a network learns, we use the iteration at which an early-stopping criterion would end training. The particular early-stopping criterion we employ throughout this paper is the iteration of minimum validation loss during training. See Appendix C for more details on this choice.