The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks 【2 WINNING TICKETS IN FULLY-CONNECTED NETWORKS】【論文 ほぼ Google 翻訳 自分用】

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

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

前: [【1 INTRODUCTION】](https://qiita.com/tomato_/items/81f8b26b4c7ee1979a6f)
次: [【3 WINNING TICKETS IN CONVOLUTIONAL NETWORKS】](https://qiita.com/tomato_/items/15b964f9bdb67fa7abc7)

# 2 WINNING TICKETS IN FULLY-CONNECTED NETWORKS

### 訳文

このセクションでは, MNISTでトレーニングされた全結合ネットワークに適用される宝くじ仮説を評価します. 図 2 で説明する Lenet-300-100 アーキテクチャ (LeCun et al., 1998) を使用します. セクション 1 の概要に従います: ネットワークをランダムに初期化およびトレーニングした後, ネットワークを枝刈りし, 残りの接続を元の初期値にリセットします. レイヤーごとの単純な枝刈りヒューリスティックを使用します: 各レイヤー内で最小の大きさの重みの割合で削除します (as in Han et al. (2015)). 出力への接続は, ネットワークの残りの半分の割合で枝刈りされます. 学習率, 最適化戦略 (SGD, モメンタム), 初期化スキーム, ネットワークサイズなど, 他のハイパーパラメーターについては付録 G で説明します. 

![2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88255/72849bda-34d9-666f-c7a8-f13aa66d4b14.png)

> 図 3:トレーニングの進行に伴う Lenet (反復枝刈り) の精度のテスト. 各曲線は, 5 回の試行の平均です. ラベルは$P_m$—枝刈り後にネットワークに残っている重みの割合です. エラーバーは, 試行の最小値と最大値です.

**表記法.** $P_m=\frac{||m||\_0}{\theta}$ はマスク $m$ のスパース性です. たとえば, $P_m=25\%$ の場合, 重みの $75\%$ が枝刈りされます. 

**反復プルーニング.** 見つかった当選チケットは, 元のネットワークよりも早く学習します. 図 3 は, さまざまな範囲で反復的に枝刈りされた当選チケットをトレーニングするときの平均テスト精度をプロットしています. エラーバーは, 5 回の実行の最小値と最大値です. 最初の枝刈りラウンドでは, ネットワークは枝刈りされるほど学習が速くなり, より高いテスト精度に達します (図 3 の左のグラフ). 元のネットワークからの重みの $51.3\%$ (つまり, $P_m=51.3\%$) で構成される当選チケットは, 元のネットワークよりも高いテスト精度に達しますが, $P_m=21.1\%$ の場合よりも遅くなります. $P_m <21.1\%$ の場合, 学習が遅くなります (中央のグラフ). $P_m=3.6\%$ の場合, 当選チケットは元のネットワークのパフォーマンスに回帰します. この論文全体を通して, 同様のパターンが繰り返されます.

図 4a は, 反復ごとに $20\%$ ずつ枝刈りする場合のすべての枝刈りレベルのこの動作をまとめたものです (青). 左側には, 枝刈り後に残っている重みの割合に関連して, 各ネットワークが最小検証損失に達するイテレーション (つまり, アーリーストッピングの基準でトレーニングを停止するとき) です. 中央はそのイテレーションでのテスト精度です. アーリーストッピングの基準が満たされるイテレーションを, ネットワークがどれだけ速く学習するかのプロキシとして使用します.

$P_m$ が $100\%$ から  $21\%$ に減少すると, 当選チケットはより早く学習します. この時点で, アーリーストッピングは元のネットワークよりも $38\%$ 早く発生します. さらに枝刈りすると, 学習が遅くなり,$P_m=3.6\%$ のときに元のネットワークの アーリーストッピングのパフォーマンスに戻ります. テストの精度は枝刈りで向上し,$P_m=13.5\%$ のときに $0.3$ パーセントポイント以上向上します; この時点以降, 精度は低下し, $P_m = 3.6\%$ のときに元のネットワークのレベルに戻ります.

アーリーストッピング時に, トレーニング精度 (図 4a, 右) は, テスト精度と同様のパターンで枝刈りを行うことで増加します. アーリーストッピング時に, トレーニング精度 (図 4a, 右) は, 枝刈りを行うことでテスト精度と同様のパターンで増加します. 当選チケットはより効果的に最適化されますが, より一般化されないことを暗示しているようです. ただし, イテレーション $50,000$ (図 4b) で, ほぼすべてのネットワークでトレーニングの精度が $100\%$ に達しているにもかかわらず, 繰り返し枝刈りされた当選チケットでは, 最大 $0.35$ パーセントポイントのテスト精度の改善が見られます (付録 D, 図 12). これは, 入場チケットのトレーニング精度とテスト精度の差が小さくなり, 一般化が改善されることを意味します.

**ランダム再初期化.** 当選チケットの初期値の重要性を測定するために, 当選チケットの構造 (つまりマスク $m$) を保持しますが, 新しい初期値 $\theta_0' \sim \mathcal{D}_\theta$ をランダムにサンプリングします. 各当選チケットを $3$ 回ランダムに再初期化し, 図 4 でポイントごとに合計 $15$ 回します. 当選チケットの有効性には初期値が重要であることがわかりました. 図3の右のグラフは, 反復枝刈りのこの実験を示しています. 元のネットワークに加えて, $P\_m=51\%$ と $21\%$ のチケットがランダムに再初期化されます. 当選チケットは, 枝刈りされるにつれて速く学習しますが, ランダムに再初期化されると徐々に学習が遅くなります.

この実験のより広範な結果は, 図 4a のオレンジ色の線です. 当選チケットとは異なり, 再初期化されたネットワークは, 元のネットワークよりも学習が遅くなり, 少しの枝刈りの後テストの精度が低下します. $P_m=21.1\%$ の場合, 再初期化された繰り返しの当選チケットの平均のテスト精度は, $2.9\%$ の当選チケットと比較して, 元の精度から低下します. $P_m=21\%$ の場合, 当選チケットは再初期化された場合よりも $2.51$ 倍速く最小検証損失に達し, 0.5パーセントポイント正確になります. すべてのネットワークは, $P_m \geq 5\%$ で $100\%$ のトレーニング精度に達します; したがって, 図 4b は, ランダムに再初期化された場合よりも, 当選チケットが大幅に一般化されることを示しています. この実験は, 初期値に関する宝くじ仮説をサポートしています: 元の初期値は枝刈りに耐え, メリットがありますが, ランダム再初期化のパフォーマンスはすぐに影響を受け, 着実に低下します.

![3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88255/1303f39a-d420-9653-88df-c6e400bac530.png)

>図 4: ワンショットおよび反復枝刈りでの Lenet のアーリーストッピングの反復および精度. 5 回の試行の平均;  最小値と最大値の誤差範囲. イテレーション$50,000$ で, 繰り返し当選チケット $P_m \geq 2\%$ でのトレーニング精度 $\approx 100\%$ (付録 D, 図 12 を参照).

**ワンショット枝刈り.** 反復枝刈りは, より小さな当選チケットを抽出しますが, 繰り返しトレーニングを行うと, 見つけるのにコストがかかります. ワンショット枝刈りにより, この繰り返しのトレーニングなしで当選チケットを識別することができます. 図 4c は, ワンショット枝刈り (緑) とランダム再初期化 (赤) の結果を示しています; ワンショット枝刈りは, 実際に当選チケットを見つけます. $67.5\% \geq P_m \geq 17.6\%$ の場合, 平均的に当選チケットは, 元のネットワークよりも早く最小検証精度に達します. $95.0\% \geq P_m \geq 5.17\%$ の場合, テスト精度は元のネットワークよりも高くなります. ただし, 繰り返し枝刈りされたチケットは, より小さなネットワークサイズでより速く学習し, より高いテスト精度に達します. 図 4c の緑と赤の線は, 図 4a の対数軸上に再現されており, このパフォーマンスのギャップが明確になっています. 私たちの目標は, 可能な限り最小のチケットを特定することであるため, 残りの論文全体で繰り返しの枝刈りに焦点を当てています.


### 原文

In this Section, we assess the lottery ticket hypothesis as applied to fully-connected networks trained on MNIST. We use the Lenet-300-100 architecture (LeCun et al., 1998) as described in Figure 2. We follow the outline from Section 1: after randomly initializing and training a network, we prune the network and reset the remaining connections to their original initializations. We use a simple layer-wise pruning heuristic: remove a percentage of the weights with the lowest magnitudes within each layer (as in Han et al. (2015)). Connections to outputs are pruned at half of the rate of the rest of the network. We explore other hyperparameters in Appendix G, including learning rates, optimization strategies (SGD, momentum), initialization schemes, and network sizes.

![2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88255/72849bda-34d9-666f-c7a8-f13aa66d4b14.png)

>Figure 3: Test accuracy on Lenet (iterative pruning) as training proceeds. Each curve is the average of five trials. Labels are $P_m$—the fraction of weights remaining in the network after pruning. Error bars are the minimum and maximum of any trial.

**Notation.** $P_m=\frac{||m||\_0}{\theta}$ is the sparsity of mask $m$, e.g., $P_m=25\%$ when $75\%$ of weights are pruned.

**Iterative pruning.** The winning tickets we find learn faster than the original network. Figure 3 plots the average test accuracy when training winning tickets iteratively pruned to various extents. Error bars are the minimum and maximum of five runs. For the first pruning rounds, networks learn faster and reach higher test accuracy the more they are pruned (left graph in Figure 3). A winning ticket comprising $51.3\%$ of the weights from the original network (i.e., $P_m=51.3\%$) reaches reaches higher test accuracy faster than the original network but slower than when $P_m=21.1\%$. When $P_m <21.1\%$, learning slows (middle graph). When $P_m=3.6\%$, a winning ticket regresses to the performance of the original network. A similar pattern repeats throughout this paper.

Figure 4a summarizes this behavior for all pruning levels when iteratively pruning by $20\%$ per iteration (blue). On the left is the iteration at which each network reaches minimum validation loss (i.e., when the early-stopping criterion would halt training) in relation to the percent of weights remaining after pruning; in the middle is test accuracy at that iteration. We use the iteration at which the early-stopping criterion is met as a proxy for how quickly the network learns.

The winning tickets learn faster as $P_m$ decreases from $100\%$ to $21\%$, at which point early-stopping occurs $38\%$ earlier than for the original network. Further pruning causes learning to slow, returning to the early-stopping performance of the original network when $P_m=3.6\%$. Test accuracy increases with pruning, improving by more than $0.3$ percentage points when $P_m=13.5\%$; after this point, accuracy decreases, returning to the level of the original network when $P_m = 3.6\%$

At early stopping, training accuracy (Figure 4a, right) increases with pruning in a similar pattern to test accuracy, seemingly implying that winning tickets optimize more effectively but do not generalize better. However, at iteration $50,000$  (Figure 4b), iteratively-pruned winning tickets still see a test accuracy improvement of up to $0.35$  percentage points in spite of the fact that training accuracy reaches $100\%$ % for nearly all networks (Appendix D, Figure 12). This means that the gap between training accuracy and test accuracy is smaller for winning tickets, pointing to improved generalization.

**Random reinitialization.** To measure the importance of a winning ticket’s initialization, we retain the structure of a winning ticket (i.e., the mask $m$) but randomly sample a new initialization $\theta_0' \sim \mathcal{D}_\theta$. We randomly reinitialize each winning ticket three times, making $15$ total per point in Figure 4. We find that initialization is crucial for the efficacy of a winning ticket. The right graph in Figure 3 shows this experiment for iterative pruning. In addition to the original network and winning tickets at $P\_m=51\%$ and $21\%$ are the random reinitialization experiments. Where the winning tickets learn faster as they are pruned, they learn progressively slower when randomly reinitialized.

The broader results of this experiment are orange line in Figure 4a. Unlike winning tickets, the reinitialized networks learn increasingly slower than the original network and lose test accuracy after little pruning. The average reinitialized iterative winning ticket’s test accuracy drops off from the original accuracy when $P_m=21.1\%$, compared to $2.9\%$  for the winning ticket. When $P_m=21\%$ , the winning ticket reaches minimum validation loss $2.51$x x faster than when reinitialized and is half a percentage point more accurate. All networks reach $100\%$ training accuracy for $P_m \geq 5\%$; Figure 4b therefore shows that the winning tickets generalize substantially better than when randomly reinitialized. This experiment supports the lottery ticket hypothesis’ emphasis on initialization: the original initialization withstands and benefits from pruning, while the random reinitialization’s performance immediately suffers and diminishes steadily.

![3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88255/1303f39a-d420-9653-88df-c6e400bac530.png)

>Figure 4: Early-stopping iteration and accuracy of Lenet under one-shot and iterative pruning. Average of five trials; error bars for the minimum and maximum values. At iteration $50,000$ training accuracy $\approx 100\%$ for $P_m \geq 2\%$ for iterative winning tickets (see Appendix D, Figure 12).

**One-shot pruning.** Although iterative pruning extracts smaller winning tickets, repeated training means they are costly to find. One-shot pruning makes it possible to identify winning tickets without this repeated training. Figure 4c shows the results of one-shot pruning (green) and randomly reinitializing (red); one-shot pruning does indeed find winning tickets. When $67.5\% \geq P_m \geq 17.6\%$ the average winning tickets reach minimum validation accuracy earlier than the original network. When $95.0\% \geq P_m \geq 5.17\%$, test accuracy is higher than the original network. However, iterativelypruned winning tickets learn faster and reach higher test accuracy at smaller network sizes. The green and red lines in Figure 4c are reproduced on the logarithmic axes of Figure 4a, making this performance gap clear. Since our goal is to identify the smallest possible winning tickets, we focus on iterative pruning throughout the rest of the paper.