閑話模型壓縮之網絡剪枝（Network Pruning）篇

1. 背景

今天，深度學習已成為機器學習中最主流的分支之一。它的廣泛應用不計其數，無需多言。但衆所周知深度神經網絡（DNN）有個很大的缺點就是計算量太大。這很大程度上阻礙了基于深度學習方法的産品化，尤其是在一些邊緣裝置上。因為邊緣裝置大多不是為計算密集任務設計的，如果簡單部署上去則功耗、時延等都會成為問題。即使是在服務端，更多的計算也會直接導緻成本的增加。人們正在從各個角度試圖克服這個問題，如這幾年如火如荼的各處神經網絡晶片，其思路是對于給定的計算任務用專用硬體加速。而另一個思路是考慮模型中的計算是不是都是必要？如果不是的話，有沒有可能簡化模型來減少計算量和存儲占用。本文主要談的就是這一類方法，稱為模型壓縮（Model compression）。它是軟體方法，應用成本低，而且與硬體加速方法并不沖突，可以互相加成。細分來說，模型壓縮又可分很多方法，如剪枝（Pruning）、量化（Quantization）、低秩分解（Low-rank factorization）、知識蒸餾（Knowledge distillation）。每一子類方法展開都可以是很大的話題，是以我們一個個來，今天主要隻限于pruning方法。

它基于一個假設，或者說目前的共識。就是DNN的過參數化（Over-parameterization）。我們知道，深度神經網絡與其它很多機器學習模型一樣，可分為訓練和推理兩個階段。訓練階段是根據資料學習模型中的參數（對神經網絡來說主要是網絡中的權重）；推理階段中将新資料喂進模型，經過計算得出結果。而過參數化是指訓練階段我們需要大量的參數來捕捉資料中的微小資訊，而一旦訓練完成到了推理階段，我們并不需要這麼多的參數。這樣的假設就支援我們可以在部署前對模型進行簡化。模型壓縮中的pruning和quantization兩類方法正是基于這樣的前提。模型簡化後有很多好處，包括但不限于：1）最直接的好處就是計算量的減小，進而使計算時間更少，功耗更小。2）Memory footprint變小，可以放到更低端的裝置上跑。還有個額外的性能好處是本來需要既慢又耗電的DRAM參與，現在有可能放在SRAM就搞定。3）Size更小的包有利于應用釋出和更新。如一些手機市場會對應用的大小有限制，另外也有利于車OTA更新。

有了『理論』上的啟發後，下一個問題就是how。顯然不能拿了模型瞎剪，因為這樣精度可以會下降得很厲害以至無法接受。當然，也有情況會在pruning後精度提高的，這說明原模型過似合（overfit）了，pruning起到了regularization的作用。就一般情況下講，核心問題是成如何有效地裁剪模型且最小化精度的損失。其實這不是一個新的問題，對于神經網絡的pruning在上世紀80年代末，90年代初左右就有研究了。如論文《Comparing Biases for Minimal Network Construction with Back-Propagation》提出了magnitude-based的pruning方法，即對網絡中每個hidden unit施加與其絕對值相關的weight decay來最小化hidden unit數量。又如上世紀90年代初當時經典的論文《Optimal brain damage》與《Second order derivatives for network pruning: Optimal Brain Surgeon》分别提出OBD和OBS方法，它們基于損失函數相對于權重的二階導數（對權重向量來說即Hessian矩陣）來衡量網絡中權重的重要程度，然後對其進行裁剪。但因為當時的大環境下，神經網絡（那時沒有deep neural network，隻有neural network，或為區分稱為shadow neural network）并不是機器學習的一個特别主流的分支，是以之後的很長一段時間也沒有大量開枝散葉，但他們對問題的梳理定義和解決問題思路對二十多年後的很多工作産生了深遠的影響。到了2012年，我們都知道深度學習一戰成名，大放異彩。之後刷榜之風興起且愈演愈烈，大家的注意力就是提高精度。于是大趨勢就是不斷地加深加重網絡以提高精度，ImageNet準确率每年都創新高。2015-16年期間，Hang Song等人發表了一系列對深度神經網絡進行模型壓縮的工作。如《Learning both weights and connections for efficient neural networks》，《EIE: Efficient inference engine on compressed deep neural network》。其中《Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding》獲得了ICLR 2016的best paper。其中對當時經典網絡AlexNet和VGG進行了壓縮。結合pruning，quantization和huffman encoding等多種方法，将網絡size壓縮了幾十倍，性能獲得成倍的提升。其中對于pruning帶來的精度損失，使用了iterative pruning方法進行補償，可以讓精度幾乎沒有損失。這讓大家意識到DNN參數備援程度如此之大，可榨油水如此之多。之後這幾年，模型壓縮領域變得越豐富，越來越多的相關工作衍生出各種玩法。

從network pruning的粒度來說，可以分為結構化剪枝（Structured pruning）和非結構化剪枝（Unstructured pruning）兩類。早期的一些方法是基于非結構化的，它裁剪的粒度為單個神經元。如果對kernel進行非結構化剪枝，則得到的kernel是稀疏的，即中間有很多元素為0的矩陣。除非下層的硬體和計算庫對其有比較好的支援，pruning後版本很難獲得實質的性能提升。稀疏矩陣無法利用現有成熟的BLAS庫獲得額外性能收益。是以，這幾年的研究很多是集中在structured pruning上。Structured pruning又可進一步細分：如可以是channel-wise的，也可以是filter-wise的，還可以是在shape-wise的。

2. 方法介紹

Network pruning的基本思想就是剪裁最不重要的部分。形式化地，可以表達成：

min ⁡ w L ( D ; w ) + λ ∣ ∣ w ∣ ∣ 0 \min_w L(D; w) + \lambda ||w||_0 wmin​L(D;w)+λ∣∣w∣∣0​

或者将參數裁剪寫成限制優化形式：

min ⁡ w L ( D ; w ) s.t. ∣ ∣ w ∣ ∣ 0 ≤ κ \min_w L(D; w) \quad \text{s.t.} ||w||_0 \leq \kappa wmin​L(D;w)s.t.∣∣w∣∣0​≤κ

由于L0範數的存在，讓該問題成為一個組合優化問題。由于是NP-hard問題，顯然不能硬來。

2.1 分類

其中一個最簡單的思路就是貪心法，或稱為saliency-based方法。即按重要性排序，然後将不重要的部分去除。然而問題來了，就是重要性如何衡量。

• 一個最簡單的啟發就是按參數（或特征輸出）絕對值大小來評估重要性，然後用貪心法将那部分幹掉，這類稱為magnitude-based weight pruning。如2016年經典論文《Pruning Filters for Efficient ConvNets》中把權重的絕對值作為衡量其重要性的手段。但訓練出來的權重如果不稀疏不利于pruning怎麼辦，常用的辦法是在訓練時loss中加regularizer，尤其是L1 regularizer，進而使得權重稀疏化。對于structured pruning來說，我們想獲得結構化的稀疏權重，是以常用group LASSO來得到結構化的稀疏權重，如2015-16年的論文《Learning Structured Sparsity in Deep Neural Networks》和《Sparse Convolutional Neural Networks》等。2017年論文《Learning Efficient Convolutional Networks Through Network Slimming》通過一種巧妙的方法，基于BN（Batch Normalization）層的廣泛使用，在BN層加入channel-wise scaling factor 并對之加L1 regularizer使之稀疏，然後裁剪scaling factor值小的部分對應權重。另外，重要性評估也可以針對activation（激活值，即激活函數的輸出），當然就算是針對activation最後也會展現在權重的裁剪上。一般來說，像Relu這樣的激活函數會傾向産生稀疏的activation；而權重相對而言不太容易是稀疏的（目前，如前所說，我們可以通過regularizer這種外力使它變得稀疏）。從這種意義上說，activation更适合pruning。如2016年論文《Network Trimming: A Data-Driven Neuron Pruning Approach towards Efficient Deep Architectures》中提出采用Average Percentage of Zeros，即APoZ來衡量activation的重要性。它定義為activation中為0的比例。
• 上面方法有個假設就是參數絕對值越小，其對最終結果影響越小。我們稱之為’‘smaller-norm-less-important’'準則。然而這個假設未必成立（如2018年的論文《Rethinking the Smaller-Norm-Less-Informative Assumption in Channel Pruning of Convolution Layers》有對其的讨論）。第二種思路就是考慮參數裁剪對loss的影響。其實前面提到的始祖級的OBD和OBS就是屬于此類。但這兩種方法需要計算Hessian矩陣或其近似比較費時。近年來有一些基于該思路的方法被研究和提出。如2016年論文《Pruning Convolutional Neural Networks for Resource Efficient Transfer Learning》也是基于Taylor expansion，但采用的是目标函數相對于activation的展開式中一階項的絕對值作為pruning的criteria。這樣就避免了二階項（即Hessian矩陣）的計算。2018年論文《SNIP: Single-shot Network Pruning based on Connection Sensitivity》将歸一化的目标函數相對于參數的導數絕對值作為重要性的衡量名額。
• 第三個思路是考慮對特征輸出的可重建性的影響，即最小化裁剪後網絡對于特征輸出的重建誤差。它的intuition是如果對目前層進行裁剪，然後如果它對後面輸出還沒啥影響，那說明裁掉的是不太重要的資訊。典型的如2017年論文《ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression》和《Channel pruning for accelerating very deep neural networks》都是通過最小化特征重建誤差（Feature reconstruction error）來确定哪些channel需要裁剪。前者采用貪心法，後者用的LASSO regression。2017年論文《NISP: Pruning Networks using Neuron Importance Score Propagation》提出隻考慮後面一兩層啥的不夠，于是提出NISP（Neuron importance score propagation）算法通過最小化分類網絡倒數第二層的重建誤差，并将重要性資訊反向傳播到前面以決定哪些channel需要裁剪。2018年論文《Discrimination-aware Channel Pruning for Deep Neural Networks》提出一種比較有意思的變體。它提出DCP（Discrimination-aware channel pruning）方法一方面在中間層添加額外的discrimination-aware loss（用以強化中間層的判别能力），另一方面也考慮特征重建誤差的loss，綜合兩方面loss對于參數的梯度資訊，決定哪些為需要被裁剪的channel。
• 另外還有基于其它的準則對權重進行重要性排序。如2018年的論文《Filter Pruning via Geometric Median for Deep Convolutional Neural Networks Acceleration》讨論了magnitude-based方法的前提與局限（即需要其範數值方差大，且最小值接近于0）。它提出了 FPGM（Filter Pruning via Geometric Median）方法。其基本思想是基于geometric median來去除備援的參數。

我們知道貪心算法的缺點就是隻能找到局部最優解，因為它忽略了參數間的互相關系。那自然肯定會有一些方法會嘗試考慮參數間的互相關系，試圖找導全局更優解。

• 離散空間下的搜尋：如2015年的論文《Structured Pruning of Deep Convolutional Neural Networks》基于genetic algorithm與particle filter來進行網絡的pruning。2017年的論文《N2N Learning: Network to Network Compression via Policy Gradient Reinforcement Learning》嘗試将網絡的壓縮分成兩個階段-layer removal和layer shrinkage，并利用強化學習（Reinforcement learning）分别得到兩個階段的政策。
• 規劃問題：如比較新的2019年論文《Collaborative Channel Pruning for Deep Networks》提出CCP（Collaborative channel pruning）方法，它考慮了channel間的依賴關系 ，将channel選取問題形式化為限制下的二次規劃問題，再用SQP（Sequential quadratic programming）求解。
• Bayesian方法：如2017年論文《Variational Dropout Sparsifies Deep Neural Networks》提出了sparse variational droput。它對variational droput進行擴充使之可以對dropout rate進行調節，最終得到稀疏解進而起到裁剪模型的效果。
• 基于梯度的方法：回顧上面問題定義中的數學最優化問題，其最惡心的地方在于regularizer中那個L0-norm，使目标不可微，進而無法用基于梯度的方法來求解。如2017年的論文《Learning Sparse Neural Networks through L0 Regularization》的思路是用一個連續的分布結合 hard-sigmoid recification去近似它，進而使目标函數平滑，這樣便可以用基于梯度的方法求解。
• 基于聚類的方法：一般地，對于壓縮問題有一種方法就是采用聚類。如将圖檔中的顔色進行聚類，就可以減小其編碼長度。類似地，在模型壓縮中也可以用聚類的思想。如2018年的論文《SCSP: Spectral Clustering Filter Pruning with Soft Self-adaption Manners》和《Exploring Linear Relationship in Feature Map Subspace for ConvNets Compression》分别用譜聚類和子空間聚類發掘filter和feature map中的相關資訊，進而對參數進行簡化壓縮。

2.2 Sparsity Ratio

上面的很多方法，研究的是給定裁剪量的前提下如何做pruning，如采用什麼樣的criteria去做參數選取。然而其實還有個核心問題是在哪裡裁剪多少，即sparsity ratio的确定。這裡的sparsity ratio定義為層中為0參數所占比例，有些文章中也稱為pruning rate等。從目标結構或者sparsity ratio的指定方式來說，按2018年論文《Rethinking the Value of Network Pruning》中的說法可分為預定義（predifined）和自動（automatic）兩種方式。Predefined方法由人工指定每一層的比例進行裁剪，是以目标結構是提前确定。而automatic方法會根據所有的layer資訊（即全局資訊）由pruning算法确定每層裁剪比例，是以目标結構一開始并不确定。

• 從某種意義上來說，著名的MobileNet《MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications》中提出的multiplier參數也是一種predefined的network pruning方法。隻是它比較簡單粗暴，将相同的裁剪比例用于所有層，且裁剪後權重不重用。2019年在《EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks》中提出的EfficientNet将這種參數調節更進一步，提出compound scaling method将width, depth, resolution按特定比例一起調節。但它們調節參數都是針對網絡中所有層的，粒度比較粗。顯然，網絡中不同層對于pruning的敏感（sensitivity）程度是不一樣的，隻有根據層的屬性為每層設定最适合的sparsity ratio才是最優的，這種為每層專設的稱為local sparsity，相對地前面那種就稱為global sparsity。2015和2016年經典論文《Learning both Weights and Connections for Efficient Neural Networks》和《Pruning Filters for Efficient ConvNets》中對網絡中各層的敏感度進行了分析，發現卷積層比全連接配接層對pruning更敏感（直覺上，由于卷積層中的參數共享，是以參數量會比全連接配接層少得多），另外不同的卷積層之間敏感度也不一樣，如第一層卷積對pruning就相對更敏感，ResNet中每個stage中第一個和最後一個residual block比中間block更敏感等。這裡就引申出一個重要問題，就是如何确定每一層的最優的sparsity ratio。在predefined這類方式中，一種就是通過前面的提到的sensitivity analysis進而确定每一層的sparsity ratio。
• 另觀automatic方法，如上所說，它需要pruning算法從全局資訊中自動得到每層裁剪多少。上面提到過的論文《Learning Efficient Convolutional Networks through Network Slimming》就屬于此類。另外，2019年論文《Play and Prune: Adaptive Filter Pruning for Deep Model Compression》将pruning問題模組化成min-max優化問題，然後通過兩個子產品交替疊代分别進行裁剪和通過調節pruning rate控制精度損失。2018年論文《ADC: Automated Deep Compression and Acceleration with Reinforcement Learning》提出ADC（Automated deep compression）方法，根據不同需求（如保證精度還是限制計算量），利用強化學習來學習每一層最優的sparsity ratio。2018年論文《“Learning-Compression” Algorithms for Neural Net Pruning》提出Learning和Compression兩步交替優化的pruning方法，在Compression操作中，通過将原參數向限制表示的可行集投影來自動找到每層的最優sparsity ratio。因為此類方法不需要計算量較大的sensitivity analysis，也減少了超參數的引入。是以，近年來，這類方法的研究越來越多。

2.3 精度恢複

當模型經過pruning，一般會帶來精度損失，是以我們在pruning的同時也需要考慮精度的恢複：

• 前面提到的論文《Channel Pruning for Accelerating Very Deep Neural Networks》中在進行channel pruning後，直接通過least square來得到最小化特征重建精度下的新參數，是以不需要fine-tuning來恢複精度，是一種inference-time pruning方法。它的好處是pruning過程不需要訓練環境。
• One-shot pruning指一趟頭的裁剪，但這種往往對精度影響很大。人們發現裁完後進行fine-tuning可以彌補pruning帶來的精度損失，是以很多方法會在pruning後做fine-tuning。比較經典的是training，pruning，fine-tuning三段式。後面兩個階段交替進行，每次pruning後損失的精度可以由後面的fine-tuning來彌補，該過程也稱為iterative pruning。簡單說就是砍一刀回點血，再砍一刀再回點血這樣，不一步到位是因為有些實驗表明一下子砍太狠就難回血了。當然現實中可以衍生出很多玩法。而在時間次元上，每步砍多少也是有藝術的。如2017年論文《To Prune, or Not to Prune: Exploring the Efficacy of Pruning for Model Compression》提出一種automated gradual pruning算法，它基于開始階段備援多可以裁得快，越到後面越裁得快的指導思想，給出在n步的pruning中，如何從初始sparsity ratio漸變到目标sparsity ratio的方法。

2.4 重新審視假設

比較有意思的是，最近不少工作開始反思一些之前固有的假設。比如一開始提到的over-parameterization對訓練是否真的那麼有益，還有原網絡的權重是否在pruning中很重要。在ICLR2019的best paper《The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks》提出The Lottery Ticket Hypothesis，即一個随機初始化，密集的網絡包含一個子網絡，這個子網絡如果沿用原網絡的權重初始化，在至多同樣疊代次數訓練後就可以比肩原網絡的測試精度。同時它還給出了找這種子網絡結構的方法。文章認為這個子結構和它的初始值對訓練的有效性至關重要，它們被稱為『winning logttery tickets』。另一篇論文2018年的《Rethinking the Value of Network Pruning》提出不僅over-parameterization對于訓練不是重要的，而且從原網絡中重用其權重也未必是很好的選擇，它可能會使裁剪後的模型陷入局部最小。如果原網絡的權重或其初始值不重要的話，那剩下最重要的就是pruning後的網絡結構了。換句話說，某種意義上來說，pruning即是neural architecture search（NAS），隻是由于 它隻涉及層的次元，搜尋空間相比小一些。但這也是它的優點，搜尋空間小了自然搜尋就高效了。

2.5 保留模型Capacity

Pruning按最初的字面意思了解就是給模型做減法。之前的主流pruning方法中，被裁剪的部分一般也就直接丢棄不會再拿回來了，即模型的capacity在iterative pruning的過程中不斷減少。這樣的話，一旦有參數被不适當地裁剪掉，便無法被恢複。而這兩年，學界正在嘗試在模型壓縮過程中保留被裁剪部分能力或者擴充能力的方法。2018年論文《Soft Filter Pruning for Accelerating Deep Convolutional Neural Networks》提出SFP（Soft filter pruning）讓被裁剪的filter在訓練中仍能被更新，這樣它仍有機會被恢複回來。2016年論文《Dynamic Network Surgery for Efficient DNNs》在pruning的基礎上加了splicing操作，避免不合适的pruning帶來的影響。2017年的論文《Morphnet: Fast & Simple Resource-Constrained Structure Learning of Deep Networks》也是基于這種思路，它會疊代地進行shrink和expand的操作。

Pruning的副作用就是可能會損害模型的capacity。盡管前面的各種方法讓該影響盡可能小，但我們往往隻能在有限的資料集上做。是以，很可能對于大部分簡單的樣本pruning對其沒有影響，但對于小部分難的資料會有較大影響。那有沒有可能在保留網絡capacity的同時又能精簡計算呢？一些學者嘗試結合dynamic NN來達到該目的，即網絡執行哪些子產品由輸出決定。如2017年論文《Dynamic Deep Neural Networks: Optimizing Accuracy-Efficiency Trade-offs by Selective Execution》引入Dynamic Deep Neural Networks，對于給定輸入，哪部分神經元被執行由網絡本身中的controller module來确定。這個module通過強化學習進行訓練。另一篇2017年論文《Runtime Neural Pruning》将pruning模組化為馬爾可夫決策過程（Markov decision process）并通過強化學習來學習pruning政策。當然，這類方法也有些局限，如由于保留了網絡原始capacity，是以size不會減少。另外由于執行哪部分是動态的，是以對于硬體加速會有影響（如算子間的fusion）。

3. 小結

和DNN訓練不同，DNN的部署有個很大的挑戰是平台的多樣性。雲和端上的硬體平台差異很大，端裝置與端裝置之間在硬體種類和能力上差異也很大。對于加速硬體的多樣性問題，業界已有諸多研究和嘗試，如像基于編譯器的TVM，和runtime+廠商backend的Android NN runtime。但計算能力的差異仍然是個大問題。如同樣是手機，計算能力可能有巨大的差異。這本質上是一個考慮性能與精度等名額的多目标優化問題，我們需要針對不同平台在其pareto解集上找合适的trade-off 。如果要将同一DNN适用于多種平台，需要按不同算力進行裁剪并且訓練，這個成本很大（幾乎與平台種類線性相關），可伸縮性差。而模型壓縮成為了解決多類型平台統一部署方案的希望之一。像2018年論文《Slimmable Neural Networks》考慮不同移動端平台訓練同一網絡，對于不同計算能力的平台進行不同程度的裁剪。2019年論文《Once for All: Train One Network and Specialize it for Efficient Deployment》也是為了類似的目标，将一個大網絡通過progressive shrinking approach訓練不同超參下的子網絡，在部署時根據不同的精度要求和資源限制搜尋合适的子網絡。即一次訓練，可以适應多種平台部署，是以稱為Once for All（OFA）方案。它既可以說是一種模型壓縮方法，也可以說是一種神經網絡結構搜尋（Neural archtecture search）。NAS相關介紹可參見之前寫的雜文神經網絡架構搜尋（Neural Architecture Search）雜談。類似的，2018年論文《ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware》中其實是用pruning的方法來做NAS。

可以看到，這幾年network pruning作為模型壓縮中的主力之一，正在受到越來越多的關注。當然，各種更好的pruning參數選取方法一定還會層出不窮。另外，從趨勢來看，以下幾個方向值得關注：

• 如前面提到，network pruning方法與NAS的界限已經模糊了。事實上，NAS分支上也有一類搜尋加速方法，如One-Shot Architecture Search是先有一個大網絡，然後做減法。NAS與模型壓縮兩個一開始看似關系不是那麼大的分支最後似乎走到一塊去了。這兩個分支今天有了更多的交集，也必将擦出更多的火花。
• 挑戰已有的固有的假設。如前面對于over-parameterization與重用已有參數是否有有益的反思非常有意思。這樣的工作會給我們非常大的啟發，進而根本改變解決問題的思路。
• 随着AutoML的大潮，越來越多的東西開始自動化。模型壓縮能拉下嗎？當然不能。經過前面的介紹我們知道，像ADC，RNP，N2N Learning這些工作都是試圖将pruning中部分工作自動化。而且對于其它的模型壓縮方法，如quantization，也有一些空間可以自動化，如2018年論文《HAQ: Hardware-Aware Automated Quantization》考慮網絡中不同層資訊的備援程度不一樣，是以可以用不同位數進行量化。
• 這幾年機器學習最火熱的分支之一GAN，正在不斷滲透到已有領域，在pruning中也開始有它的身影。如2019年論文《Towards Optimal Structured CNN Pruning via Generative Adversarial Learning》采用了GAN的思想，讓generator生成裁剪後網絡，discrimintor來判别是否屬于原網絡還是裁剪後網絡，進而進行更有效的網絡結構化裁剪。
• 與硬體結合，如稀疏計算的支援。現在雖然有像cuSPARSE這樣的計算庫，但底層硬體GPU本身設計并不是專門為稀疏資料處理打造的。如果能将稀疏計算和處理能力做進晶片那必将極大提高計算效率，如早些年有像EIE這樣的嘗試。在現在神經網絡晶片的大潮下，相信這樣的案例會越來越多。
• 如文章一開始提到的，模型壓縮方法中pruning隻是其中一種，它與其它方法并不沖突，是以與其它方法，如knowledge distillation，quantization等的深度結合，是值得研究的方向。
• 和其它機器學習分支一樣，很多人提出很多算法，各家都說自家的好。一個分支發展到一定時候，就需要benchmark來進行客觀的橫向比較。Google在2019年論文《The State of Sparsity in Deep Neural Networks》正是這方面的嘗試。相信以後也會有越來越多的benchmark，和針對性的競賽。