# 李宏毅_Network Compression
###### tags: `Hung-yi Lee` `NTU` `Network Compression`

## MNetwork Compression(1/6)
[課程連結](https://www.youtube.com/watch?v=dPp8rCAnU_A)

### Resource Limited Deviced

訓練好的模型我們可以希望可以佈到一些移動設備上，像是手機、手錶、空拍機之類的設備。但這類的設備本身並沒有足夠的計算資源，因此我們沒有辦法將整個網路完整的佈上，因此我們需要壓縮網路。

課程會提到幾種方式：
1. Network Pruning
2. Knowleadge Distillation
3. Parameter Quantization
4. Architecture Design
5. Dynamic Computation

當然還可以客製化硬體，不過課程中不會提，在臉書有一位石小川，他就提過他用光來做網路的推論，速度非常快。

### Network can be pruned

實作上，我們常會覺得有部份的參數是無效的，也就是over-parameterized，解一個問題並不需要那麼多的參數，甚至有些參數的輸出永遠都是0。如果我們可以把這類的神經元剪掉，自然就可以得到一個比較小的模型。

這並不是一個新穎的觀念，在90年代中，Yann Le Cun就提出相關的論文。
### Network Pruning

Network Pruning的觀察說明：
* 首先，要有一個訓練好的模型
* 評估每一個神經元(權重)的重要性
* 觀察其值，如果接近0代表不那麼重要，因此可以計算其L1、L2
* 除移不重要的神經元
* 得到較小的模型，但因為我們移除了部份的參數，因此還要確認效能是否下降太多
* 將得到的新的模型用原始的訓練集再做微調，通常可以復原

值得注意的是，我們在移除神經元的時候並不會一次移除太多，而是漸進式的，移除之後做微調，避免無法將損失的部份再利用原始訓練集還原回來。

## MNetwork Compression(2/6)
[課程連結](https://www.youtube.com/watch?v=7B8Cx7woQk4)

### Why Pruning?

為什麼我們要這麼麻煩，先訓練一個大的模型再來修剪成一個小的模型?為什麼我們不一開始就訓練一個比較小的模型?因為實務上小的模型比較不好訓練，而大型的模型比較好最佳化，只要模型過大，就比較不會有局部最佳或鞍點的問題出現，已經有愈來愈多的論文證明，只要模型夠大，就算只是單純的梯度下降也可以找到全域最佳。

可參考先前的[上課錄影](https://www.youtube.com/watch?v=_VuWvQUMQVk)

### Why Pruning?

[參考論文_The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://arxiv.org/abs/1803.03635)

稍早有提到，大的模型比較好訓練，我們知道，整個訓練流程就是先隨機初始化權重，接著訓練，最後執行Pruning。上面論文作者做了兩個有趣的實驗：
1. 拿Pruned後的模型來隨機初始化，然後重新訓練，最後無法成功訓練模型
2. 拿Pruned後的模型，然後拿原始模型中隨機初始化的權重來使用，重新訓練是可以成功的

作者就因此提出一個大樂透的理論，訓練模型就跟買樂透一樣，買愈多重獎機會愈高。每個大的模型裡面都是由很多小的模型所組成，只要小的模型夠多，那能成功訓練的小模型就愈有機會愈多，最後只要再拿掉訓練不起來的就可以。而可以成功訓練的小模型就意味著它的初始值是好的，因此拿著這個好的初始值來訓練自然就可以成功。
### Why Pruning?

[參考論文_Rethinking the Value of Network Pruning](https://arxiv.org/abs/1810.05270)

不過另一篇論文又告訴我們，不需要什麼大樂透假說，直接訓練就可以了，從Scratch-E、Scrathch-B可以看的到，跟Finu-tuned的結果相比是相差不遠的。
### Network Pruning - Practical Issue

實作Purning有一些問題，我們說，Prune做的就是將一些不重要的權重刪掉。但這麼做的一個問題就是會造成模型變成不規則狀，這實作上太難了，即使成功了，到GPU上去也不好計算。

因此實作上我們並不是真的將權重拿掉，而是單純的讓它的值變成0。

### Network Pruning - Practical Issue

[參考論文_Learning Structured Sparsity in Deep Neural Networks](https://arxiv.org/abs/1608.03665)

上面是實作的結果，拿掉非常大量的權重之後還是可以保有不錯的效果。將AlexNet拿掉95%的權重之後，其效能只掉2%，非常驚人。但是可以看的到，在GPU上的實作基本上是沒有加速的效果。因為你的網路已經是不規則型，無法矩陣計算。

### Network Pruning - Practical Issue

因此不拿掉權重，拿掉神經元或許是一個比較好的方式，拿掉神經元之後只是讓你的hidden layer直接少一個連接點，對整個網路而言是沒有影響的，實作上也比較容易。

## MNetwork Compression(3/6)
[課程連結](https://www.youtube.com/watch?v=mzZzn8fBvEs)

### Knowledge Distillation

[參考論文_Distilling the Knowledge in a Neural Network](https://arxiv.org/pdf/1503.02531.pdf)
[參考論文_Do Deep Nets Really Need to be Deep?](https://arxiv.org/pdf/1312.6184.pdf)

Knowledge Distillation的大致概念就是訓練一個大的網路(Teacher Net)，再訓練一個小的網路(Student Net)來學習大的網路的行為。

作法上就是讓Student Net來學習Teacher Net的output。這麼做的好處在於，Teachet Net提到了比label data更豐富的資料，上圖可以看的到，Teacher Net提供給Student Net不若label data僅告訴Student Net那是1，而是告訴Student Net那有0.7的機率是1、0.2的機率是7、0.1的機率是9。論文中提到，在Student Net沒見過label data的情況下還是可以有機會正確的分辨。

從影片中老師與學生的討論也可以知道，最小化的目標是兩個網路之間的KL-Divergence，因為我們希望兩個網路輸出的分佈是愈接近愈好。
### Knowledge Distillation

Knowledge Distillation的另一個優點在於，我們可以讓Student Net學到整個Ensemble的資訊。平常我們對於Ensemble可能只能用於競賽，因為實務上我們不大可能拿著多個網路來應用在一個目標上，可是透過Knowledge Distillation，我們可以讓整個Ensemble學到的東西通通灌輸給Student Net。

### Knowledge Distillation

訓練Knowledge Distillation有一個小技巧，平常我們在做最後的輸出是單純的經過softmax，但在Knowledge Distillation中，我們執行softmax之前可以先除上一個$T$，這個$T$稱為Temperature。

這麼做的好處在於，我們稍早說過，Knowledge Distillation的好處在於提供的資訊比label data更豐富，以上圖左為例，原本的softmax的輸出跟one-hot一樣，就像是label data提供的資訊，這樣子的資訊跟直接跟label data學習是一樣的，可是在設置Temperature之後，最大值的結果一樣，但提供的資訊更為豐富。

課程中提到，助教實作之後發現，Knowledge Distillation沒有特別有用!
## MNetwork Compression(4/6)
[課程連結](https://www.youtube.com/watch?v=fMsNf0ufYnY)

### Parameter Quantization

也有其它的方法可以使用：
1. 如果原本是採用float32，那就調整為float16，網路可以瘦身一半
2. 將權重分群，以16個權重為例，分為4群，那就只需要2個bit就可以記錄，然後另外用一個table來計算每一個分群的平均值，這對效能當然有影響，但明顯可以讓網路成功的瘦身
3. 也可以採用像是Huffman encoding來表示，讓比較常出現的token用比較少的bit來表示

### Binary Weights

[參考論文_BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://arxiv.org/abs/1511.00363)
[參考論文_Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1](https://arxiv.org/abs/1602.02830)
[參考論文_XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks](https://arxiv.org/abs/1603.05279)

Parameter的極限在於是否可以使用1、-1來表示權重就好，上面文獻也確實有人用binary wegith來訓練網路。

上圖為例來看，灰點就是binary wegith，藍點則是平常所用的real value weight，藍點的更新不再是依自己，而是依著最接近的灰點來更新，最終停下來的時候，最接近的那個灰點就是它的weight。

### Binary Connect

以結果來看，binary weight的效能是不錯的。直觀來看，binary weight有著正則化的效果，但比起dropout來看還是稍為遜色。

## MNetwork Compression(5/6)
[課程連結](https://www.youtube.com/watch?v=L0TOXlNpCJ8)

### Low rank approximation

實務上調整網路的架構設計或許是一個比較理想的方式。

以fully connected為例說明：
* 前一層有著N個neuron，下一層有著M個neuron，中間存在著權重W
* 將中間的權重W變更為V、K、U，其中K是一個hidden layer，沒有activation function，單純的linear

這麼做並不會讓權重數量更多，只要我們能夠控制K < M, N，這種情況下，U、V的參數和是比W還要少(W=MxN，轉換過後為Kx(N+M))。

因此，對於fully connected layer而言，我們可以利用中間調整為線性函數的方式來減少參數量。但也要注意到，以線性代數的角度來看，U、V相乘之後得到的RANK一定是小於等於K，這也某種角度的限制這個模型的效能。

### Review: Standard CNN

以CNN為例：
* input feature map為6x6x2，然後有4個3x3x2的filters，最終的輸出為4x4x4
* 總參數量為3x3x2x4=72

### Depthwise Separable Convolution

標準的conv來看，input的channel有多少，你的filter的channel也就是多少，但Depthwise Separable Convolution將conv拆成兩個步驟：
1. Depthwise Convolution：filter會是一個平面，維度為$k \space \text{x} \space k$，也就是你的input channel有多少，你的filter就有幾個，而且每一個filter只負責一個channel，各自處理各自負責的feature map之後得到output

### Depthwise Separable Convolution

接下來處理第二步：
2. Pointwise Convolution：步驟一我們一個各玩各的feature map output，然後我們再利用1x1 filter來讓它們有關聯，你有幾個1x1 filter就會得到幾個feature map output

剛剛標準的CNN我們用了72個參數，但Depthwise Separable Convolution：
* 第一步中我們用了2個3x3的filter，因此2x3x3=18
* 第二步中我們用了4個1x1的filter，因此1x1x2x4=8

總共26個，這數量遠低於72。

## MNetwork Compression(6/6)
[課程連結](https://www.youtube.com/watch?v=f0rOMyZSZi4)

### Depthwise Separable Convolution

上圖簡單說明著原始的Conv與Depthwise Separable Convolution的差異：
* 上圖上方說明著，原始的Conv的output是來自於input經過filter連同channel一起處理而得，也因此，左上的輸出是來自輸入的feature map的左上的計算，以3x3的filter為例，每一個point就是需要處理18個input point
* 上圖下方說明著，Depthwise Separable Convolution是在中間再加一個layer，這個layer的input一樣是feature map，但不同的是，feature map的計算是不考慮channel，而是每個channel各自處理，再經過一個1x1的filter將資訊匯整做為輸出

### Depthwise Separable Convolution

這邊比較兩種Convolution的參數量差異：
* 上圖左說明著原始Conv的參數量
* 上圖右說明著Depthwise Separable Convolution的參數量

兩者的參數量差異主要會來自於filter size，也就是kernel size，因為$O$通常很大，可以無視。

### To learn more ......

[參考論文_SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model size](https://arxiv.org/abs/1602.07360)
[參考論文_MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications](https://arxiv.org/abs/1704.04861)
[參考論文_ShuffleNet: An Extremely Efficient Convolutional Neural Network for Mobile Devices](https://arxiv.org/abs/1707.01083)
[參考論文_Xception: Deep Learning with Depthwise Separable Convolutions](https://arxiv.org/abs/1610.02357)

相關技術被廣泛的應用在比較小的網路架構上，可見上圖說明。

### Dynamic Computation

舉例來說，當手機電量不足的時候，網路會自己知道減少運算量，但效能不要太糟，而當手機電量充足的時候，就全力計算。

### Possible Solutions

[論文參考_MULTI-SCALE DENSE NETWORKS FOR RESOURCE EFFICIENT IMAGE CLASSIFICATION](https://arxiv.org/pdf/1703.09844.pdf)

幾種作法可以做到：
1. 訓練一把的模型，依狀況選擇不同的模型來使用，不過缺點就是你要弄一把的模型來佔儲存空間
2. 訓練一個模型，而這個模型的每一個中間層都可以直接得到結果，那就可以依網路需求的計算量來自己決定在那一個中間層直接output，但這麼做有幾個缺點：
* 以CNN來看，前面幾個filter所抽的特徵都只是特徵，因此效能不會很好，可見上圖左
* 這會影響到原始模型的效能，如上所述，CNN的前面幾個layer所取得的都是簡單的特徵，如果要讓模型在前面幾層就可以得到一個好的結果，這意味著強迫模型在前面幾層就必需有好的特徵才有辦法得到好的結果，這就影響到原始CNN的一個結構(由簡單的特徵到複雜)，可見上圖右。

不過這並不代表不能這麼做，可以參考MSDNET的作法，見上論文連結。