---
tags: 技術研討
---
# Week 2：模型壓縮 - 剪枝 (pruning)
## PRUNING FILTERS FOR EFFICIENT CONVNETS

## 剪枝 - Filter & feature maps
### 數學符號與圖例說明
$n_{i}$ : 第 i 層 input channel 數
$F_{i,j}$ : 第 i 層的第 j 個 filter
$X_{i}$ : 第 i 層的 feature maps

### 模型運算量計算

:question: 如果剪掉其中一個 filter $F_{i,j}$，會減少多少運算量呢？
圖示如下：
其實一個 filter 掃一次 $X_{i}$ 的 feature maps，需要 $n_{i}k^2$ 的運算量，所以把整個 feature maps 掃完，就會變成 $X_{i+1}$ 的其中一片 feature map，其長寬為 $h_{i+1}w_{i+1}$。所以總的來說，<font color=red>裁減一個 filter ，可以減少 $n_{i}k^2h_{i+1}w_{i+1}$ 的運算量</font>。

:::warning
要注意的是，裁減 $F_{i,j}$ 也會對於下一層的 input channel 有影響，所以除了裁減當層的運算量之外，<font color=red>還會另外在減少下一層的運算量 $n_{i+2}k^2h_{i+2}w_{i+2}$</font>。

:::

:star: 全部的 filters $F_{i}$ 對 $X_i$ 做 convolution 轉換到 $X_{i+1}$ 的總運算量就是 $n_{i+1}n_{i}k^2h_{i+1}w_{i+1}$。

### 如何剪枝 filter？

#### <ins>3.1 如何決定裁減哪些 filters？</ins>
* 透過 $l_1$-nrom $||F_{i,j}||_{1}$，也就是每個 filter 絕對值得平均 $\sum|F_{i,j}|$ 來決定哪些 filters 是重要的
* 因為 input channel 數 $n_i$ 都一樣，所以 $\sum|F_{i,j}|$ 其實就等同於 kernel 的平均大小

:star: 從實驗結果來看，sum of absolute weights 權重越大的 filter 剪枝影響越大，權重越小的對於模型準確度影響越小，如下圖：

* 剪枝四步驟
1. 計算出每個 filter $F_{i,j}$ 的 kernel weights 絕對值得總合，$s_{j}=\sum^{n_{i}}_{l=1}\sum|K_{l}|$
2. 依照 $s_j$ 將 filters 排序
3. 從最小的加總權重開始，裁減 m 個 filters 以及其相對應的 feature maps。還有被裁減的 feature maps 在下一層對應到的 filter kernel 也應該被裁減
4. 最後產生新的 $i$ 跟 $i+1$ 層的 kernel matrix，剩下的 weights 會被複製到新的模型中

:pushpin: 用低的 absolute weights sum 來決定要裁減哪些 filters 跟 Magnitude-based 的差別？
$\to$ magnitude-based 的剪枝方式是決定一個權重的 threshold，如果 filters 中的權重都小於 threshold 的話，就將該 filter 裁減，但就會有兩個問題：<font color=red>1. 如何決定適當的門檻值 2. 比較難預測最終會有多少 filters 被裁減</font>

:pushpin: 作者有實驗用 $l_1-norm$ 或 $l_2-norm$ 進行權重的排序，但實驗結果發現兩種方法沒有顯著的差異

什麼是稀疏矩正 :question:
在矩陣中，若數值為0的元素數目遠遠多於非0元素的數目，並且非0元素分佈沒有規律時，則稱該矩陣為稀疏矩陣。

#### <ins>3.2 決定單一層對於剪枝的敏感度</ins>

* 透過計算每個 filters 的加總權重 $s_j$ 並依照大小排序，圖 2 (a) 顯示將權重標準化到 0~1 之間的權重分佈圖，不同的 Convolution layer 的權重分佈差異很大。
* <font color=red>斜率越大的線</font>，權重分佈的越不平均，也就表示主要的權重值來自於少數 rank 前面的 filters，大部分的 filters 可能權重都非常小，所以<font color=red>對於剪枝的敏感度較低</font>。
* <font color=red>斜率越小的線</font>，權重分佈的越平均，也就表示大部分的 filters 都有不小的權重值，都算有資訊的 filter，所以<font color=red>對於剪枝的敏感度較高</font>。
* 在比較深層的網絡架構中 (VGG-16 or ReNets)，作者發現同一個 stage 的卷積層，同樣大小的 feature maps，每個 filter 對於剪枝的敏感度是差不多的。

#### <ins>3.3 多層 filters 剪枝</ins>
* 兩種剪枝策略
1. Independent pruning：在進行剪枝的判斷時，獨立的計算 filters 的權重
2. Greedy pruning：在進行剪枝的判斷時，會將上層已經被剪枝的 filters 的權重跳過不算，如下圖黃色的方格就不會被計算到

* 較複雜的模型的剪枝

不同於較簡單的 CNNs 架構如 VGGNet or AlexNet 我們可以輕易的裁減在任何一層的 filters，較複雜的 Residual networks 在剪枝時就需要考量較多限制。

在進一步解說前，先稍微認識一下 Residual Networks
* 我們可以看到，在 residual block 最後的 output，在維度上需要與 input $X$ 相等，才能直接相加 (注意：不是 concatenate 而是相加喔！)


* 如上圖所示，因 Residual networks 是由 identity maps + residual maps 建構出來的，所以 <font color=red>residual block 的 output feature maps 必須要跟透過 projection shortcut 轉換出來的 identity map 維度相等</font>，不能隨意的剪枝 filters。
* 因為 identity maps 的重要性比 residual maps 還重要 (可以想像成原始資料的資訊量應該是比較多的)，所以在進行剪枝時，<font color=red>主要應該要以 identity maps 的 filter 進行排序剪枝而不是 residual maps 的 filters</font>。
* redidual block 的 output 前的 filters 可以隨意的進行剪枝，只要確保最後一層的 output 維度與 identity maps 相等即可。

#### <ins>3.4 重新訓練模型以回復剪枝後網絡的準確度</ins>

* 兩種策略
1. 一次性剪枝並重新訓練模型 (strategy 1)：Prune filters of multiple layers at once and retrain them until the original accuracy is restored.
2. 重複剪枝並訓練模型 (strategy 2)：Prune filters layer by layer or filter by filter and then retrain iteratively. The model is retrained before pruning the next layer for the weights to adapt to the changes from the pruning process.

* 針對對於剪枝較不敏感的卷積層，strategy 1 可以將很大比例的網絡裁減，並且可以透過少於原模型訓練的時間重新回復準確度；但是針對較敏感的卷積層進行剪枝，則有可能無法透過 retrain 回復原模型的準確度。
* strategy 2 可能可以產生更好的剪枝效果，但是遞迴的剪枝與訓練模型所需耗費的成本較高。

---
# 4. 實驗

|實驗中用到的Network|Dataset| 章節|
| :--: |:--: |:--: |
| VGG16| CIFAR10| 4.1 / 4.4 / 4.5|
|ResNet56|CIFAR10| 4.2|
|ResNet110|CIFAR10| 4.2|
|ResNet34|ImageNet|4.3|

## VGG16的實驗

### ==<ins>[VGG16的實驗] 在conv layer為512個feature maps下不影響準確度</ins>==

- 沒有retrain，可以至少剪枝60%
- retrain 20 epochs，可以至少剪枝90%

**為什麼可以剪這麼多:**
- 這些fliters比較小（4x4 / 2x2），沒有太多有用的資訊在裡面


### ==<ins>[VGG16的實驗] 觀察到與前人不同的結果</ins>==
- 剪枝完第一層layer後還是很robust（前人認為第一層不太能剪），在簡單的sample dataset中是有可能發生的唷～～～

下圖是第一層用l1-norm排序後的filters，看得出來有很多沒用的資訊可以剪掉

- 為什麼會和前人的研究結果不太一樣呢？
舉例來說：
>第一層有channel是64，假設剪掉80%剩12，<font color=red>12還是比原來的input channel的3還要多！</font>
`64 * (1 - 80%) = 12`
`(H, W, C=3) → (H, W, C=12)`

>但是如果將第二層的channel剪掉80%剩12，12就比++第一層的64++還要少很多，就會影響準確度

因此在VGG16的實驗中，維持一樣的準確度下，**剪枝layer 1, 2, 8~13，共減少34%的FLOP**

:::warning
:mag_right: [什麼是FLOP？](https://zhuanlan.zhihu.com/p/137719986)
FLOPs：floating point operations的縮寫（s是小寫表示複數），指浮點運算數，也就是<font color=brown>運算量</font>，用来衡量模型的複雜度。

FLOPS：floating point operations per second的縮寫（S是大寫），意指<font color=brown>每秒浮點運算次數</font>，也就是運算速度。

公式：
<font color=brown>$(2C{i}K^2-1) H_{i+1}W_{i+1}C_{0}$</font>
:::

### ==<ins>[VGG16的實驗] 比較 剪枝l1-norm小的filters/剪枝l1-norm大的filters/隨機剪枝</ins>==

- 剪枝90%的filters，Accuracy overall比較：
**剪枝l1-norm小的filters > 隨機剪枝 > 剪枝l1-norm大的filters**
-> 剪枝l1-norm大的filters準確度下降得非常快

### ==<ins>[VGG16的實驗] 比較Activation-Based</ins>==

mean-mean公式解釋：
其他公式以此類推...
所以是以所有data來看，一樣看哪片filter平均小就刪掉誰

- 只有mean-std和用l1-norm看起來是差不多的，且在<font color=red>60%的accuracy mean-std還有好過l1-norm</font>
- 可是mean-std是要將<font color=red>所有data考量進去計算</font>，但l1-norm不用，因此作者認為不用因為data而有限制的l1-norm還是勝！

---

## ResNet56/110實驗


- 3 stage，每個stage的residual block數量一樣
- (32x32）(16x16) (8x8)

### ==<ins>[ResNet56的實驗]</ins>==

:::info
ResNet56-pruned-A:
skipped layer: 16, 20, 38, 54
p1=10%, p2=10%, p3=10%
:::

發現：剪枝越深的layer比前面的layer越sensitive
因調高stage1和stage2 pruning rate

:::info
ResNet56-pruned-B:
skipped layer: 16, 18, 20, 34, 38, 54
p1=60%, p2=30%, p3=10%
:::
由圖可看出調整為B的方式可以剪枝更多且保持在很高的準確度

由以上結果去看ResNet56的架構來看，<font color=red>sensitive layer大部分都是在stage相接的地方</font>

---

### ==<ins>[ResNet110的實驗]</ins>==

:::info
ResNet110-pruned-B:
skipped layer: 36(stage1的黑虛線), 38(stage2的紅實線), 74(stage3的紅實線)
p1=50%, p2=40%, p3=30%
:::

發現：
同一個stage有兩個以上的residual blocks，中間的residual blocks大部分是多餘的，可以直接把他們剪掉！

[ResNet50架構參考](https://medium.com/軟體之心/deep-learning-residual-leaning-認識resnet與他的冠名後繼者resnext-resnest-6bedf9389ce)

---

## ResNet34的實驗
- 4 stage
- (56x56)(28x28)(14x14)(7x7)

### ==<ins>[ResNet34的實驗] 剪residual block 的<font color=red>第一層</font></ins>==
- 在<font color=red>每個stage</font>的<font color=red>第一和最後的residual block</font>都比<font color=red>中間的residual block</font>更sensitive

:::info
(A & B) skipped layer: 2, 8, 14, 16, 26, 28, 30 ,32
:::
:::info
ResNet34-pruned-A:
p1=30%, p2=30%, p3=30%

ResNet34-pruned-B:
p1=50%, p2=60%, p3=40%
:::

和ResNet56/110有比較深層的架構相比，ResNet34相對較難剪枝

>想一想滿合理的，因為在ResNet56/100的實驗中發現：
同一個stage有兩個以上的residual blocks，中間的residual blocks大部分是多餘的，但ResNet34的架構較淺，一定相對較難剪！

### ==<ins>[ResNet34的實驗] 剪identity shortcuts & residual block 的<font color=red>第2層</font></ins>==

:::info
ResNet34-pruned-C:
p3=30%
:::

<font color=red>Identity shortcuts & Residual block 的第2層</font></br>比<font color=red>residual block 的第一層</font>更sensitivy，</br>accuracy下降的很快，</br>因此++剪第一層++是更有效率的!


[ResNet34架構參考](https://towardsdatascience.com/understanding-and-visualizing-resnets-442284831be8)

---

## 提問區

|姓名|問題|解答|
| - | - |-|
|昱睿|1. 是不是不同的 CNN 架構就會有不一樣的剪枝方式？<br/>2. 是不是只要是類似 CNN 架構的網路，都可以用 paper 的手法去計算可能剪枝的 filter 是哪裡？|
|沛筠|Independent pruning 和 Greedy pruning 的剪枝順序是否因為計算內容不同而有所差別? |
|昊中|兩種Retrain Strategies會不會也會受影像內容與架構有所差別?實驗中有討論到透過Training from scratch的訓練結果，不了解主要呈現的用意為何?|
|立晟|1. sparse library 的實際功能是什麼?<br/>2. magnitude-based weight pruning 如果刪掉全部的 filters 會發生什麼事?|