# Week 12: The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
###### tags: `技術研討`
[paper] [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://arxiv.org/pdf/1803.03635.pdf)
[code] [github](https://github.com/Eric-mingjie/rethinking-network-pruning/tree/master/cifar/lottery-ticket)
## Lottery Ticket Hypothesis 介紹
<font color=#F6D55C>**2019 ICLR 最佳論⽂!!**</font>
**摘要**
> 神經網路的剪枝術⽬前可以減少將近 90% 的 parameters 仍能維持很好的準確度。然而，⽬前經驗是<font color=#20639B>剪枝後產生的稀疏架構很難從頭開始訓練，也很難提高訓練效能</font>
作者在本篇發現原始的網路架構剪枝後會<font color=#20639B>自然揭示出網路路中的⼦架構</font>！基於此假設，作者提出了彩票假設 lottery ticket hypothesis，任何密集、隨機初始化的網路路架構，在相同的 iteration 下可以達到與原本網路相同的測試精準度。<font color=#20639B>初始化的 intialize weights 對於訓練的結果影響很大!</font>
簡介
> 過往有許多的剪枝方法可以將神經網路中過多冗余的參數移除掉，不僅可減少模型大⼩，也可提升運算的速度。
然而過去的經驗告訴我們，<font color=#20639B>retrain 剪枝的架構很難訓練的比原本的效果來得更好</font>，樂透彩票假則是提出另外一個觀點來說明這個現象
:pushpin: The lottery ticket hypothesis
> A randomly-initialized, dense neural network contains a subnet- work 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.
* 簡單的來說就是，一個隨機初始化的 DNN 會<font color=#ED553B>有一組 subnetwork & 相對應的初始值</font>，可以在獨立訓練 (不會拿 network training 後的 weights) 的情況下，並<font color=#ED553B>在 <= 原 DNN 的 training iteration 次數下達到相同的 test accuracy</font>
* 初始化權重的重要性在後續的實驗中會一再被證明，使用 initialize weights 的成效比重新 random initiallize weights 好
:Question: 為什麼會有 lottery ticket？
以下是作者尚未證明的推測：
> <font color=#20639B>Dense, randomly-initialized networks</font> are easier to train than the <font color=#20639B>sparse networks that result from pruning</font> because there are <font color=#20639B>more possible subnetworks from which training might recover a winning ticket</font>.
:pushpin: Identifying wining tickets
1. Randomly initialize a neural network $f(x;θ_0)$ (where $θ_0∼D_θ$).
2. Train the network for $j$ iterations, arriving at parameters $θ_j$.
3. Prune p% of the parameters in $θ_j$ , creating a mask $m$.
4. Reset the remaining parameters to their values in $θ_0$, creating the winning ticket $f(x;m⊙θ_0)$.
<font color=#ED553B>$θ_0$:</font> 初始化權重
<font color=#ED553B>$f(x;θ_0)$:</font> 模型 + 初始化權重
<font color=#ED553B>$f(x;m⊙θ_0)$:</font> 裁減過後(masked)的模型 + 原初始化權重
* interative pruning：相對於 one shot pruning，在最終剪枝比例相同 (p%) 的情況下，透過迭代的方式剪枝，可以做到<font color=#ED553B>以更小的模型達到原模型相同 accuracy 的成果</font>
* 實驗小結
1. Winning tickets 在 testing accuracy 不變的情況下，<font color=#ED553B>可以壓縮到原模型 10~20% 的大小</font>
2. 在<font color=#ED553B>原模型訓練時間內</font>，winning tickets 就有辦法訓練出<font color=#ED553B>相同甚至準確度更高的壓縮模型</font>
3. 壓縮後的模型架構本身不能完全解釋 winning ticket 的成效，還<font color=#ED553B>需要搭配剪枝前的初始化權重</font>才行
:pushpin: Contributions
* Improve performance: 訓練的速度與準確度更高
* Design better networks: 剪枝後的網路在相同的 iteration 下可與原本的網路架構⼀致 Improve training
* Improve our theoretical understanding of neural networks: 提出⼀種新觀點重新看待 neural network
## 實驗結果
### 實驗總共可以分成三個區塊
* 全連接的網路架構 - LenNet 300-100
* 卷積的神經網路架構 - Conv-2, Conv-4, Conv-6
* 更深的卷積神經網路 - ResNet-18, VGG19
### 1. 全連接的網路架構
這章節證明的是在全連接的網路架構下 Lenet 300-100 的表現效果
==<ins>剪枝方法採用刪除每層最低重要性的權重 (weight-level purning)</ins>==，且每層剪枝的比例是固定相同的
* 左圖為原始網路 100%、保留一半 51.3% 與保留 21.1% 的比較結果，可以看出保留 21% 訓練結果比保留 51% 快且好
* 中圖為原始網路 100% 與其他保留低於 21% 的比較結果，可以看出從保留越少結果也越來越差，但僅有 1.9% 的比原始來得差，其他仍比原始網路好！
* 右圖為 51.3% 與 21.1% <font color=#ED553B>random reinitialization 的效果最差</font>
### 2. 卷積的神經網路架構
這章節證明的是在==卷積的神經網路架構 VGG 系列下==的結果表現
包含三種架構 Conv-2, Conv-4, Conv-6 (n 個 convolutional layers + 兩層 fully-connected layers)
* 實線表示使用 initialize weights，虛線表示使用 random initialize weights
* 左下為 train data 的結果，在越減越多參數的情況下，<font color=#ED553B>winning tickets 的優勢更加明顯</font>
* 右上為 test data 的結果，可以發現在 test 中不僅表現穩定且還有 imporve 的效果在，顯示此結構更適合使用 winning tickets 的方法
Dropout 在每個 iteration 下隨機抽取 subnetwork 借此提升訓練的準確度防止 overfit，但彩券理論假設子網路具有 winning ticket，==<ins>因此很自然的疑問是 dropout 與 winning ticket 是否有相互影響？</ins>==
* 左圖為 early-stop, 右圖為 accuracy (test)
* 從圖中可以看出有 dropout 的架構訓練速度較慢 (要較久才能收斂)，但相對的精準度也較高！
:exclamation: 加 dropout 雖然會讓<font color=#ED553B>收斂速度變慢</font>，但實際上對 test 的<font color=#ED553B>準確率較好</font> (可以找到 winning tickets)
### 3. 更深的卷積神經網路
這章節證明的是在更深的卷積神經網路 ==(VGG19, ResNet-18)== 的結果表現，同時這些網路也更加複雜 (+ batch-norm, weight decay, decreasing learning rate, data augmentation)
此外剪枝的方式也改變，不再以每層剪枝相同的比例去剪，而是==設定 global threshlod 的方式當門檻==，列出所有參數權重後依比例找出前某%，在依此當門檻做剪枝，因深層網路每一層的參數量差距過大，若都剪相同比例會出問題....
下圖為 VGG19 分別使用 initialize weights / random initialize weights 以及 learning rate = 0.1 / 0.01 的實驗比較結果
* 左中右圖分別為 iteration = 30k, 60k, 112k 的結果，可以看出較大的 lr (藍色) 並無法找到 winning ticket 表現與原本比也較差，而較小的 lr (橘色) 雖然精準度較高，但也沒找到 winning ticket 因其並無達到原本的準確度
* 因此作者<font color=#ED553B>使用 warmup 的方法在訓練過程中改變 lr 大小</font>，也就是 warmup 方法可以使深層網路找到 winning ticket！
:::info
:exclamation: warmup 為一開始使用較小的 lr 訓練，之後再改回大的
較大的梯度使得模型權重每次改變都較大，這樣就容易讓學習一開始就往該筆資料的分佈方向修正，可能導致此筆資料的overfitting。如果有個機制，模型可以針對每個資料都看過幾遍後在開始訓練，這樣每筆資料對於模型已經有了一些正確的先驗知識，但又不完全偏向某些資料，之後在進行模型訓練效果應該會更好。所以warm-up的機制一開始用小一點的learning rate，這樣模型可以看過所有資料，雖然一開始loss很大，但因為較低的learning rate這樣模型又不會更新太多。
[參考資料](https://chih-sheng-huang821.medium.com/深度學習warm-up策略在幹什麼-95d2b56a557f)
:::
ResNet-18 與 VGG19 的實驗結果相同~~
## 結論
1. The importance of winning ticket initialization
2. The importance of winning ticket structure
3. The improved generalization of winning tickets
4. Implications for neural network optimization
實驗證明 random initialize 比 winning tickets 訓練來得慢且效果差，==因此證明 initialize weights 對於模型的重要性！==
其中<font color=#ED553B>可能的解釋是 initial weights 更接近於最終的訓練結果</font>
此篇理論認為較大的網路結構，越有可能可以找到 lottery ticket (可能包含較簡單的表示方式存在)
## Pytorch Code解說
This directory contains a pytorch implementation of <u>Lottery Ticket Hypothesis</u> for <u>l1-norm based filter pruning</u> introduced in this paper [Pruning filters for efficient convnets](https://arxiv.org/abs/1608.08710) (ICLR 2017).
Pruning filters for efficient convnets vgg16架構圖：
vgg16 model架構:
```python=
16:
[64, 64, 'M', 128, 128, 'M', 256, 256, 256, 'M', 512, 512, 512, 'M', 512, 512, 512]
pruning:
[32, 64, 'M', 128, 128, 'M', 256, 256, 256, 'M', 256, 256, 256, 'M', 256, 256, 256]
```
```python
vgg(
(feature): Sequential(
(0): Conv2d(3, 64, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(1): BatchNorm2d(64, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(2): ReLU(inplace=True)
(3): Conv2d(64, 64, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(4): BatchNorm2d(64, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(5): ReLU(inplace=True)
(6): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
(7): Conv2d(64, 128, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(8): BatchNorm2d(128, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(9): ReLU(inplace=True)
(10): Conv2d(128, 128, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(11): BatchNorm2d(128, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(12): ReLU(inplace=True)
(13): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
(14): Conv2d(128, 256, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(15): BatchNorm2d(256, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(16): ReLU(inplace=True)
(17): Conv2d(256, 256, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(18): BatchNorm2d(256, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(19): ReLU(inplace=True)
(20): Conv2d(256, 256, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(21): BatchNorm2d(256, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(22): ReLU(inplace=True)
(23): Conv2d(256, 256, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(24): BatchNorm2d(256, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(25): ReLU(inplace=True)
(26): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
(27): Conv2d(256, 512, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(28): BatchNorm2d(512, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(29): ReLU(inplace=True)
(30): Conv2d(512, 512, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(31): BatchNorm2d(512, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(32): ReLU(inplace=True)
(33): Conv2d(512, 512, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(34): BatchNorm2d(512, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(35): ReLU(inplace=True)
(36): Conv2d(512, 512, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(37): BatchNorm2d(512, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(38): ReLU(inplace=True)
(39): MaxPool2d(kernel_size=2, stride=2, padding=0, dilation=1, ceil_mode=False)
(40): Conv2d(512, 512, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(41): BatchNorm2d(512, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(42): ReLU(inplace=True)
(43): Conv2d(512, 512, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(44): BatchNorm2d(512, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(45): ReLU(inplace=True)
(46): Conv2d(512, 512, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(47): BatchNorm2d(512, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(48): ReLU(inplace=True)
(49): Conv2d(512, 512, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), bias=False)
(50): BatchNorm2d(512, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
(51): ReLU(inplace=True)
)
(classifier): Linear(in_features=512, out_features=10, bias=True)
)
```
```
1. （main.py）訓練一個baseline的neural network
2. （lottery_vggprune.py）baseline neural network -> Interative Pruning -> subnetwork
3. 得到lottery ticket初始的參數
4. （main_lottery.py）用lottery ticket + subnetwork去訓練
```
```python=
"lottery_vggprune.py"
#original:[64, 64, 'M', 128, 128, 'M', 256, 256, 256, 'M', 512, 512, 512, 'M', 512, 512, 512]
cfg = [32, 64, 'M', 128, 128, 'M', 256, 256, 256, 'M', 256, 256, 256, 'M', 256, 256, 256]
layer_id = 0
for m in model.modules():
if isinstance(m, nn.Conv2d):
out_channels = m.weight.data.shape[0] #64
if out_channels != cfg[layer_id]: # 如果output_channels跟pruning後的channels不一樣，表示要剪枝
weight_copy = m.weight.data.abs().clone()
weight_copy = weight_copy.cpu().numpy()
L1_norm = np.sum(weight_copy, axis=(1, 2, 3)) # 用l1全部加總weight，計算重要與不重要的filter
arg_max = np.argsort(L1_norm) # 由小到大排序，取其相對應index
# x中的元素從小到大排列，提取其對應的index(索引)，然後輸出到y
# x=np.array([1,4,3,-1,6,9])
# -> 用index代表: 0,1,2,3,4,5
# -> 排序3,0,2,1,4,5 （-1,1,3,4,6,9）
# y=array([3,0,2,1,4,5])
if args.prune == 'small':
arg_max_rev = arg_max[:cfg[layer_id]] # 取前32小
elif args.prune == 'random': # 隨機取32個
arg_max_rev = np.random.choice(arg_max, cfg[layer_id], replace=False)
assert arg_max_rev.size == cfg[layer_id], "size of arg_max_rev not correct"
m.weight.data[arg_max_rev,:,:,:] = 0 # 要剪掉的weight都給0
# *注意：完全沒有對model架構做調整
# 以前是剪完以後64->32存到新的model裡，新的model就是32channels
# 但這次是讓64裡面的32變成0
# 因為這樣才知道original network的哪些init weight要留下來
layer_id += 1
elif isinstance(m, nn.MaxPool2d):
layer_id += 1
```
```python=
"main_lottery.py"
# model:original model
# model_ref: pruning model
#拿原來的model(原來的init weight)，把被剪掉的參數給0
for m, m_ref in zip(model.modules(), model_ref.modules()):
if isinstance(m, nn.Conv2d):
weight_copy = m_ref.weight.data.abs().clone()
mask = weight_copy.gt(0).float().cuda() # 和0比大小，return 0,1的結果
m.weight.data.mul_(mask) # 和0,1相乘，就可以得到subnetwork＋init weight
def train(epoch):
...
#grad也變0
for k, m in enumerate(model.modules()):
if isinstance(m, nn.Conv2d):
weight_copy = m.weight.data.abs().clone()
mask = weight_copy.gt(0).float().cuda()
m.weight.grad.data.mul_(mask)
...
```
為什麼不像以前一樣把subnetwork存在新的model裡，這次卻是把weight變成0？
猜測是可能是作者懶惰吧...比較好實作（雖然不是weight-level pruning）
---
小補充：
weight-level pruning為什麼是讓weight變0？為什麼不是把init weight放進pruning後的subnetwork架構內？
因為：
1.不規則的模型架構會導致實作困難
2.硬把不規則的模型架構實作出來，GPU也無法加速（GPU加速是把network運算看成矩陣乘法，剪枝過後不容易使用GPU加速）
一般weight pruning實際上實作大部分會將weight轉換成0
缺點：就是實際上沒有把network變小
如果是對filter/channel做修剪，network架構保持規則(每個神經元都是4input 3output，也就是pytorch實作只要修改input/output維度)
1.好實作
2.好加速
**unstructured pruning：weight-level pruning
structured pruning：channel/filter/layer-level pruning**
Reference: [宏毅大大](https://www.youtube.com/watch?v=utk3EnAUh-g)
---
提問區：
問老師真正應用專案該怎麼規劃～～
Sign in with Wallet
Connect another wallet