Rigging the Lottery: Making All Tickets Winners 【2 Related Work】【論文 DeepL 翻訳】

この記事は自分用のメモみたいなものです.
ほぼ [DeepL](https://www.deepl.com/home) 翻訳でお送りします.
間違いがあれば指摘していだだけると嬉しいです.

翻訳元
[Rigging the Lottery: Making All Tickets Winners](https://arxiv.org/abs/1911.11134)

前: [【1 Introduction】](https://qiita.com/tomato_/items/eb46d3c59fa0a91fe46b)
次: [【3 Rigging The Lottery】]()


# 2 Related Work

### 訳文

スパースなニューラルネットワークの発見に関する研究は, 少なくとも大きさに基づく重みのプルーニングが単純で強力な手法であると結論づけた Thimm & Fiesler (1995) までは数十年前にさかのぼる. Strom(1997) は後に, 精度を高めるために以前にプルーニングされたネットワークを再訓練するという考えを導入した. Han et al. (2016b) はさらに進んで, 大きさのプルーニングと再訓練の複数ラウンドを導入した. しかし, これは比較的非効率的であり, 最終的なスパース度 90% に到達するために接続の 20% を除去する場合には, 10 ラウンドの再トレーニングが必要である. この問題を克服するために, Narang et al. (2017) は, 1 ラウンドの訓練の過程でゆっくりと接続を除去する漸進的プルーニングを導入した. Zhu & Gupta (2018) は, 必要とされるハイパーパラメータの選択量を最小限に抑えるために, この手法を改良した.

大きさによるプルーニングに基づかない多様なアプローチも提案されている. LeCun et al. (1990) と Hassibi & Stork (1993) は初期の例であるが, Hessian からの情報を利用して訓練されたネットワークをルーニングするため, 現代のニューラルネットワークには非現実的である. より最近の研究には, L0正則化 (Christos Louizos, 2018), 変分ドロップアウト  (Molchanov et al., 2017), 動的ネットワーク手術 (Guo et al., 2016), および感度駆動正則化 (Tartaglione et al., 2018) がある. Gale et al. (2019) は, 大きさによるプルーニング, L0正則化, および変動的ドロップアウトを検討し, これらはすべて ResNet50 および Transformer アーキテクチャ上でほぼ同じ精度対 sparsity のトレードオフを達成すると結論づけた.

トレーニングプロセス全体を通してスパース性を可能にするトレーニング技術は, 私たちの知る限り, Deep Rewiring  (DeepR) で初めて導入された (Bellec et al., 2018). DeepR では, 標準的な確率勾配降下 (SGD) オプティマイザが, パラメータ空間のランダムウォークで増強される. さらに, 接続にはあらかじめ定義された符号がランダムに割り当てられる. オプティマイザが通常符号を反転させる場合, 重みは代わりに 0 に設定され, 新しい重みがランダムにアクティブになる.

Sparse Evolutionary Training (SET) (Mocanu et al., 2018) は, 重みがプルーニングで使用される標準的な大きさの基準に従ってプルーニングされ, ランダムに加算されて戻ってくる, より単純なスキームを提案している. この手法は単純であり, 実際には合理的な性能を達成している. Dynamic Sparse Reparameterization (DSR) (Mostafa & Wang, 2019) は, モデルの異なる層間でパラメータバジェットをシフトさせ, 不均一なスパースを可能にするというアイデアを導入した. これにより, モデルが最も効果的な場所にパラメータを分散させることができる. 残念ながら, 検討中のモデルはほとんどが畳み込みネットワークであるため, このパラメータ再割り当ての結果 (初期の層のスパース度を下げ, 後期の層のスパース度を上げる)は, 空間サイズが初期で最大になるため, FLOP カウントを増加させるという全体的な効果がる. Sparse Networks from Scratch (SNFS) (Dettmers & Zettlemoyer, 2019) は, 各パラメータの運動量を重みを成長させるために使用する基準として使用するという考え方を導入し, それがテスト精度の向上につながることを実証している. DSR と同様に, 彼らは各層のスパース度を変化させ, FLOP ではなく一定のパラメータに焦点を当てることを可能にする. 重要なことに, この手法では, モデル内のすべてのパラメータ (ゼロであるパラメータであっても) の運動量を反復するたびに, グラデーションを計算して更新する必要がある. これは, 全体の計算量を大幅に増加させることになる. さらに, モデルと訓練設定によっては, 完全な運動量テンソルのために必要なストレージが法外な量になることがある. Single-Shot Network Pruning (SNIP) (Lee et al., 2019) は, ワンショットプルーニングで初期マスクを見つけようと試み, どのパラメータを保持するかを決定するためにパラメータのSaliency スコアを使用する. プルーニング後, この静的スパースネットワークを用いて訓練が進む. 異なるスパース訓練技法の特性を表 1 にまとめる.

![G1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88255/a7058288-af0f-5c14-f41c-8e856a09f6cd.png)

> 表1: 異なるスパーストレーニング技術の比較. Drop と Grow の列はマスク更新中に使用された戦略に対応している. 選択可能な FLOPs は, 訓練および/または推論のコストが訓練の開始時に固定されている場合に可能である.

宝くじ仮説を調査する一連の作業もあった (Frankle & Carbin, 2019). Frankle et al. (2019) は, ResNet-50 のような大規模ネットワークに適用するためには, 定式化を弱めなければならないことを示した (He et al., 2015). 大規模ネットワークでは, 元の初期化の代わりに, 数千の最適化ステップの後の値を初期化に使用しなければならない. Zhou et al. (2019) は, 宝くじは訓練が開始される前でも非ランダムな精度を得ることを示した. 宝くじを用いて固定スパースマスクを持つスパースニューラルネットワークを訓練する可能性は興味をそそられるが, そのような初期化を-マスクとパラメータの両方について-デノボで生成することが可能かどうかは不明のままである.


### 原文

Research on finding sparse neural networks dates back decades, at least to Thimm & Fiesler (1995) who concluded that pruning weights based on magnitude was a simple and powerful technique. Strom¨ (1997) later introduced the idea of retraining the previously pruned network to increase accuracy. Han et al. (2016b) went further and introduced multiple rounds of magnitude pruning and retraining. This is, however, relatively inefficient, requiring ten rounds of retraining when removing 20% of the connections to reach a final sparsity of 90%. To overcome this problem, Narang et al. (2017) introduced gradual pruning, where connections are slowly removed over the course of a single round of training. Zhu & Gupta (2018) refined the technique to minimize the amount of hyper-parameter selection required.

A diversity of approaches not based on magnitude based pruning have also been proposed. LeCun et al. (1990) and Hassibi & Stork (1993) are some early examples, but impractical for modern neural networks as they use information from the Hessian to prune a trained network. More recent work includes L0 Regularization (Christos Louizos, 2018), Variational Dropout (Molchanov et al., 2017), Dynamic Network Surgery (Guo et al., 2016) and Sensitivity Driven Regularization (Tartaglione et al., 2018). Gale et al. (2019) examined magnitude pruning, L0 Regularization and Variational Dropout and concluded that they all achieve about the same accuracy versus sparsity trade-off on ResNet50 and Transformer architectures.

Training techniques that allow for sparsity throughout the entire training process were, to our knowledge, first introduced in Deep Rewiring (DeepR) (Bellec et al., 2018). In DeepR, the standard Stochastic Gradient Descent (SGD) optimizer is augmented with a random walk in parameter space. Additionally, connections have a pre-defined sign assigned at random; when the optimizer would normally flip the sign, the weight is set to 0 instead and new weights are activated at random.

Sparse Evolutionary Training (SET) (Mocanu et al., 2018) proposed a simpler scheme where weights are pruned according to the standard magnitude criterion used in pruning and are added back at random. The method is simple and achieves reasonable performance in practice. Dynamic Sparse Reparameterization (DSR) (Mostafa & Wang, 2019) introduced the idea of allowing the parameter budget to shift between different layers of the model, allowing for non-uniform sparsity. This allows the model to distribute parameters where they are most effective. Unfortunately, the models under consideration are mostly convolutional networks, so the result of this parameter reallocation (which is to decrease the sparsity of early layers and increase the sparsity of later layers) has the overall effect of increasing the FLOP count because the spatial size is largest at the beginning. Sparse Networks from Scratch (SNFS) (Dettmers & Zettlemoyer, 2019) introduces the idea of using the momentum of each parameter as the criterion to be used for growing weights and demonstrates it leads to an improvement in test accuracy. Like DSR, they allow the sparsity of each layer to change and focus on a constant parameter, not FLOP, budget. Importantly, the method requires computing gradients and updating the momentum for every parameter in the model, even those that are zero, at every iteration. This can result in a significant amount of overall computation. Additionally, depending on the model and training setup, the required storage for the full momentum tensor could be prohibitive. Single-Shot Network Pruning (SNIP) (Lee et al., 2019) attempts to find an initial mask with one-shot pruning and uses the saliency score of parameters to decide which parameters to keep. After pruning training proceeds with this static sparse network. Properties of the different sparse training techniques are summarized in Table 1.

![G1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88255/a7058288-af0f-5c14-f41c-8e856a09f6cd.png)

> Table 1: Comparison of different sparse training techniques. Drop and Grow columns correspond to the strategies used during the mask update. Selectable FLOPs is possible if the cost of training and/or inference is fixed at the beginning of training.

There has also been a line of work investigating the Lottery Ticket Hypothesis (Frankle & Carbin, 2019). Frankle et al. (2019) showed that the formulation must be weakened to apply to larger networks such as ResNet-50 (He et al., 2015). In large networks, instead of the original initialization, the values after thousands of optimization steps must be used for initialization. Zhou et al. (2019) showed that lottery tickets obtain non-random accuracies even before the training has started. Though the possibility of training sparse neural networks with a fixed sparsity mask using lottery tickets is intriguing, it remains unclear whether it is possible to generate such initializations – for both masks and parameters – de novo.