# DEEP COMPRESSION: COMPRESSING DEEP NEURAL NETWORKS WITH PRUNING, TRAINED QUANTIZATION AND HUFFMAN CODING [2015]

# 介紹

隨著深度神經網路在電腦視覺領域中取得突破性成果，其廣泛應用於影像分類、物件偵測等任務。然而，這些模型通常包含上千萬至上億個參數，導致：

* 儲存空間需求極高（例如 AlexNet 約 240MB、VGG-16 約 552MB）
* 記憶體頻寬消耗大，難以部署於行動裝置或嵌入式系統上

**行動裝置部署的挑戰**
1. 應用大小受限
* 許多行動應用需上架於 App Store / Google Play，這些平台對應用大小十分敏感。
* 以 Apple App Store 為例，超過 100MB 的應用需連接 Wi-Fi 才能下載。
* DNN 模型若增加應用體積過大，將導致部署門檻提高。

2. 能源消耗高
* 記憶體存取比運算本身更耗能：
* 32-bit 浮點加法：0.9pJ
* SRAM 存取：5pJ
* DRAM 存取：640pJ

* DNN 模型過大，導致頻繁的 DRAM 存取，對電池壽命極為不利。

例如：以 20 fps 運行含 10 億個連結的模型，光是 DRAM 存取即需耗費約 12.8W，遠超過行動設備可接受的功耗範圍。

# **研究目標：壓縮而不損失準確率**
為解決上述問題，作者提出 「Deep Compression」，一個三階段的神經網路壓縮流程，能 顯著減少模型體積與能源消耗，同時保持原始準確率：

🔧 三階段壓縮流程：
* Pruning（剪枝）：去除不重要的連線，保留關鍵結構
* Quantization（量化與權重共享）：將多個連線權重共享同一值，只需儲存少量 centroid 與對應索引
* Huffman Coding（霍夫曼編碼）：進一步對偏態分佈進行無損編碼

這三個步驟彼此互不干擾，能疊加壓縮效果，最終讓模型壓縮至原始大小的 2~3%（例如 AlexNet 壓縮 35×，VGG-16 壓縮 49×）。

# 網路裁減（Network Pruning）
早期的研究中，Network Pruning（網路剪枝） 就已被證實是一種有效的方式來降低網路的複雜度與過擬合
近年來，Han 等人（2015）展示了對先進 CNN 模型進行剪枝，可以不損失準確率。本研究基於該方法進一步發展。

如圖左側所示，流程如下：

1. 正常訓練神經網路，學習連接權重（weights）。
1. 剪除權重較小的連線：將所有低於某個閾值的連線權重視為不重要，並從網路中移除。
1. 重新訓練（retrain）：針對剩下的稀疏連線，重新學習它們的最終權重。

使用這種方法後，參數量分別減少了 9 倍（AlexNet）與 13 倍（VGG-16）。

為了儲存剪枝後的稀疏結構（sparse structure），使用以下兩種其中一種：

* CSR（Compressed Sparse Row）-> 壓縮按「列」來儲存
* CSC（Compressed Sparse Column）-> 壓縮按「欄」來儲存

不論是哪一種，目的都是：只儲存有用的非零值，節省空間。

這種儲存格式需要的數量為 2a + n + 1 個數字，其中：

* a 是非零元素的數量（non-zero elements）
* n 是 row 或 column 的數量

在 CSR 來說，我們會儲存三個陣列：

* values：長度 a，存的是非零的數值
* col_indices：長度 a，每個值對應的 column index
* row_ptr：長度 n+1，指出每一列開始的位置（pointer）

這樣就可以 reconstruct 原本的矩陣，但只儲存有效資訊。

為了進一步壓縮資料，採用以下技巧：

* 不儲存絕對位置，而是儲存index 差值（index difference）
* 差值使用 8-bit 編碼（conv layer）、5-bit 編碼（fc layer）

當 index 差值超過這個位元數能表示的最大值時，使用一種稱為 zero padding 的方法（如圖所示）：

(若使用 3-bit 表示 index difference，最大值為 7，若遇到差值為 10，就會插入一個 zero filler（填充 0） 來處理超出範圍的情況。)

# 舉例來說 :
假設你有以下的 column index：
[3, 4, 6, 10]
你可以儲存成
[3, 1, 2, 4] → 這樣最大值是 4
就可以用更少的bit來儲存了

差值太大怎麼辦？-> Zero Padding 解法
假設你用 8-bit 編碼（最大可以表示 255），但某次 index 差值是 300，超過了。

這時候怎麼辦？

➡️ 解法是使用「Zero Padding（補 0）」
* 把一個很大的差值，分成幾個小的段落表示，中間加「填充 0」當作「換行」或「分隔」的記號。
* 例如：300 太大，我們可能把它拆成兩個 index 差值 150 + 150，中間加個 0 當作記號。

這樣做可以保證：

* 所有儲存的差值都不會超過最大 bit 可以表示的數字
* 解壓縮時只要根據 zero padding 的規則，就能把差值還原回去

# 網路量化與權重共享

網路量化與權重共享可以進一步壓縮剪枝後的神經網路，方式是減少儲存每個權重所需的 bit 數。

透過「多條連線共用相同的權重值」，來減少需要儲存的「有效權重」數量，並在這之後對這些共享權重進行微調（fine-tune）。
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/BkQM9WyTke.png" style="width:1000%;"><br>
<em>Figure 3. 透過純量量化進行的權重共享（上）與重心微調（下）</em>
</div>

假設有一層神經網路，有 4 個輸入與 4 個輸出節點，對應的權重矩陣為 4×4，總共 16 個權重。
* 左上圖是原始的 4×4 權重矩陣
* 左下圖是對應的 4×4 梯度矩陣

這些權重會被「量化」成 4 個 bin（4 個顏色），每個 bin 裡的權重共用同一個值。
因此，只需要：
* 儲存 一個小的索引（index） 指向共享權重表（shared weight table）
* 不再儲存原始的浮點權重

# 更新機制
在進行權重更新時：
1. 把每一個 bin（顏色）內的梯度加總
1. 用 learning rate 乘上這個總梯度
1. 再從上一輪的共享權重中減去這個值，更新共享權重（centroid）

# 壓縮實例：Pruned AlexNet
對於剪枝後的 AlexNet：
* CONV 層：可量化成 8-bit，也就是 256 個共享權重
* FC 層：可量化成 5-bit，也就是 32 個共享權重
* 而且這樣做 完全不會降低模型準確率

# 壓縮率（Compression Rate）計算方式
若使用 k 個 cluster（共享權重）：
* 每個 index 只需要 log₂(k) 個 bit 表示
假設：
* 網路有 n 條連線
* 每條原始連線是 b bit
那麼使用權重共享後：
* 只需儲存 k × b 個共享權重（每個還是 b bit）
* 再加上 n × log₂(k) 個 bit 的 index

範例（Figure 3）：
* 原本有 4×4 = 16 個權重，每個 32-bit → 共 512 bit
* 使用 4 個共享權重（藍、綠、紅、橘），每個 32-bit → 共 128 bit
* 再加上 16 個 2-bit index（因為 4 個 cluster 只要 log₂(4) = 2 bit）→ 共 32 bit

壓縮率：

$$
\text{Compression Rate} = \frac{16 \times 32}{4 \times 32 + 16 \times 2}
= \frac{512}{128 + 32}
= \frac{512}{160} = 3.2
$$

# 權重共享（WEIGHT SHARING）
* 我們對每一層的已訓練網路，使用 K-means clustering 來找出可以共享的權重（shared weights）。也就是說，落在同一個 cluster 的權重會共用同一個值。
* 注意：不同層的權重不會互相共享，每一層是獨立做 clustering 的。

### 具體做法
假設一層有 $n$ 個原始權重，記為：

$$
W = \{w_1, w_2, ..., w_n\}
$$

要將這些權重分成 $k$ 個 cluster：

$$
C = \{c_1, c_2, ..., c_k\}, \quad n \gg k
$$

我們的目標是讓群內的權重盡量接近各自的 cluster centroid，也就是最小化群內平方誤差（**Within-Cluster Sum of Squares, WCSS**）：

$$
\arg\min_{C} \sum_{i=1}^{k} \sum_{w \in C_i} \lvert w - c_i \rvert^2 \tag{2}
$$

每個 cluster 的中心（centroid）$c_i$ 就是共享權重的值。

### 與 HashNet 的差異
這種方法與 HashNet（Chen et al., 2015） 不同：

| 項目 | 本方法 | HashNet |
|--------------------------|---------------------------------------------|------------------------------------------------|
| 權重共享時間點 | 訓練完成後才做 clustering | 訓練前就用 hash 決定權重 mapping |
| 是否考慮原始權重分佈 | ✅（因為是在訓練後） | ❌（訓練前就固定） |
| 精度保留程度 | 較佳（因為更貼近原始模型） | 可能較差 |

總結來說，該方法會讓「共享後的權重分佈」更接近原始模型權重分佈，因此更容易保持原本的模型準確度。

**共用權重的初始化（Initialization of Shared Weights）**
初始化方式會影響 clustering 的品質，也就影響最終模型的預測準確率。
這裡比較了三種初始化方法：

| 方法 | 特性 | 分佈密度 | 備註 |
|------|------|----------|------|
| 🔹 **1 Forgy（隨機初始化）** | 隨機從資料中選出 $k$ 個點作為初始 **centroid** | 聚集在資料分佈的高密度區（例如雙峰） | 容易忽略極端（大）權重 |
| 🔹 **2 Density-based（依機率分佈初始化）** | 在 CDF 的 y 軸等距抽點，回推對應的 $x$ 值 | 也會聚集在分佈的高密度區，但比 Forgy 更分散 | 同樣可能低估大權重 |
| 🔹 **3 Linear（線性初始化）** | 在原始權重的 $min, max$ 範圍內等距劃分 | 完全不管原始分佈，分佈最平均 | 能涵蓋較大權重，表現較穩定 |

<p align="center">
<img src="https://hackmd.io/_uploads/H1VOBqfpkl.png" width="1000%"><br>
<strong>圖 4：</strong>左圖：三種不同的重心初始化方法。右圖：權重的分布（藍色）、微調前的碼本分布（綠色叉號）以及微調後的碼本分布（紅色圓點）。
</p>

- 藍線：累積分佈函數
- 紅線：機率密度函數
- 權重呈現雙峰分佈（bimodal distribution） → 是 pruning 後常見的情況。

* 底下顯示的是 13 個 cluster 的初始化方式：
* 黃色點：Forgy（集中在雙峰附近）
* 藍色點：Density-based（圍繞雙峰但較分散）
* 紅色點：Linear（在整個區間均勻分佈）

* 為什麼 Linear Initialization 效果最好？
* 雖然大的權重較少出現，但對模型表現影響大（Han et al., 2015）。

- Forgy 和 Density-based 方法，大多數 centroid 都集中在權重分佈的中心（也就是雙峰）。
- 對於那些**極值（large weights**來說，代表性不足。
- Linear initialization 能在整個區間平均分布，即使是少數的大權重，也有對應的 centroid。
- 更能保留大權重的代表性，因此 fine-tune 後的表現更好。

### 前向與反向傳播

在使用 一維 K-means clustering 後，每個 cluster 的中心（centroid）就代表一個 共享權重（shared weight）。

### 前向傳播（Feed-forward）
* 每條連線不再直接儲存一個浮點數權重 Wij
* 而是儲存一個 索引值 Iij，指向 shared weight table（共享權重表） 中的某個 centroid Ck
* 在進行前向傳播時，會先查表（indirection）取得對應的權重值再做運算

### 反向傳播（Back-propagation）
* 為了更新共享權重，我們要計算每個 centroid 的梯度
* 這裡用到了 indicator function（指示函數）1(Iij = k)：
如果 Wi,j 屬於第 k 個 centroid，則值為 1，否則為 0

### 數學公式
損失函數為 $L$，權重 $W_{ij}$ 位於第 $i$ 列、第 $j$ 行，該位置的 centroid 索引為 $I_{ij}$，第 $k$ 個 centroid 為 $C_k$。

則第 $k$ 個共享權重（$C_k$）的梯度如下：

$$
\frac{\partial L}{\partial C_k} = \sum_{i,j} \frac{\partial L}{\partial W_{ij}} \cdot \mathbf{1}(I_{ij} = k) \tag{3}
$$

這代表：

- 把所有指向第 $k$ 個 centroid 的權重的梯度加總起來
- 然後拿這個總和去更新 $C_k$（配合 learning rate）

# HUFFMAN CODING（霍夫曼編碼）
Huffman 編碼是一種常見的**無損壓縮（lossless compression）**方法，屬於 prefix code（前綴碼） 類型中的最佳演算法（Van Leeuwen, 1976）。

### 原理：
* 使用可變長度（variable-length)的 bit 編碼方式。
* 編碼表根據各個符號的出現機率建立：
* 出現機率高的符號 → 編碼短（佔用位元少）
* 出現機率低的符號 → 編碼長（佔用位元多）

# 實際應用在壓縮 CNN 模型
Figure 5 顯示了兩個在 AlexNet 最後一層 FC layer 中的機率分佈：

1. Quantized Weights（量化後的權重）
* 分佈呈雙峰（bimodal）→ 多數權重集中在兩個特定區域

1. Sparse Matrix Index Difference（稀疏矩陣的索引差值）
* 大部分差值都小於 20 → 出現分布極度不均勻

這兩者都非常適合用 Huffman 編碼壓縮，因為它們的機率分布高度偏斜（biased / non-uniform）。

# 實驗結果
將這些值（quantized weights + sparse index differences）進行 Huffman 編碼後：
可進一步節省 20% 到 30% 的儲存空間
這代表即便前面已經做過：
* 剪枝（pruning）
* 量化與權重共享（quantization + weight sharing）
* 稀疏矩陣儲存（CSR / CSC）

仍然可以透過 Huffman 編碼，榨出額外的壓縮空間。

# 實驗的四個階段

| 階段 | 技術 | 效果 |
|------|------------------------------|---------------------------|
| 🔹 **1 剪枝（Pruning）** | 移除小權重 → 稀疏矩陣 | 大幅減少參數量 |
| 🔹 **2 量化與權重共享** | K-means 找共享權重 → 減少不同值數量 | 減少 bit 數與記憶體 |
| 🔹 **3 稀疏格式儲存（CSR / CSC）** | 只存非零元素與索引差值 | 減少空間浪費 |
| 🔹 **4 Huffman 編碼** | 對偏斜的值再壓縮 | 額外省 20–30% |

# 實驗（EXPERIMENTS）
### 實驗模型與資料集
我們對 四個模型應用「剪枝 + 量化 + Huffman 編碼」的壓縮流程：
| 資料集 | 模型 | 類型 |
|------------|----------------|------------------|
| MNIST | LeNet-300-100 | 全連接（FC）網路 |
| MNIST | LeNet-5 | 卷積神經網路 |
| ImageNet | AlexNet | 經典 CNN |
| ImageNet | VGG-16 | 大型深層 CNN |

### 實作細節

| 技術 | 實作方式 |
|----------------------|-----------------------------------------------------------------------------------------------|
| 訓練框架 | 使用 [Caffe](https://caffe.berkeleyvision.org/) |
| 剪枝（Pruning） | 在 blob 上套用 **mask**，避免更新被剪掉的權重 |
| 量化與權重共享 | 使用 **codebook** 結構儲存共享權重，並在反向傳播後 **group by index** 累計梯度來更新 |
| Huffman 編碼 | 為離線處理，不需訓練，在 **fine-tune 完成後** 執行 |

### MNIST：LeNet-300-100 & LeNet-5

* LeNet-300-100：
* 結構：兩層隱藏層（300 & 100 neurons）
* 原始錯誤率：1.6%
* LeNet-5：
* 結構：兩層 CONV + 兩層 FC
* 原始錯誤率：0.8%

壓縮效果：

| 壓縮階段 | 壓縮倍率 |
|--------------------|--------------|
| 剪枝 + 量化 | 約 32× |
| Huffman 編碼後 | 約 40× |

### ImageNet：AlexNet

* 資料集：ImageNet ILSVRC-2012（訓練 120 萬張，驗證 5 萬張）
* 模型資訊：
* 參數量：61M
* Top-1 準確率：57.2%
* Top-5 準確率：80.3%

| 項目 | 結果 |
|------------------|------------------------------------------|
| 最終大小 | 從 240MB → 6.9MB |
| 整體壓縮率 | 35× |
| CONV 層 | 256 個共享權重，8-bit 表示 |
| FC 層 | 32 個共享權重，5-bit 表示 |
| Sparse index | 使用 4-bit 編碼 |
| Huffman 壓縮 | 額外省下 22% 空間 |
| 記憶體效益 | 模型可進入 SRAM，省電且高速 |

### ImageNet：VGG-16

* VGG-16 是更大、更深的網路（比 AlexNet 多很多卷積層）
* 只有最後 3 層是 FC 層

| 項目 | 結果 |
|------------------|----------------------------------------------------|
| 整體壓縮率 | 49× |
| CONV 層 | 使用 8-bit 表示共享權重 |
| FC 層 | 使用 5-bit 表示 |
| 最大的 2 層 FC | 可壓到原本大小的 1.6% 以下 |
| Huffman 壓縮 | 實際效果未單獨列出（包含在 49× 內） |
| 實用性 | FC 層佔用空間變小 → 可進 SRAM，對即時應用重要 |

### 對 real-time inference 非常重要（如 object detection）
因為這些 FC 層通常是「單張圖跑一次」，→ 壓縮可有效減少頻寬與延遲。

# 討論（DISCUSSIONS）
**剪枝與量化的協同作用**
下圖(6)比較了三種壓縮方式對模型準確率的影響：

<p align="center">
<img src="https://hackmd.io/_uploads/B1QBq9Makl.png" width="100%"><br>
<strong>圖 6：</strong>不同壓縮方法下的準確率與壓縮率比較。當剪枝與量化結合時，效果最佳。
</p>

### 結果

| 壓縮比例 | 結果 |
|------------|----------------------------------------------------|
| < 8% | 單獨使用剪枝或量化會明顯掉準確率 |
| 到 3% | 結合使用仍可維持零準確率損失 |

同時也與 SVD（奇異值分解）壓縮法比較，SVD 雖然實作簡單，但壓縮率遠不如 Deep Compression。

下圖(7)顯示量化 bit 數對不同層的影響（CONV / FC / ALL）：
* CONV 層需要 ≥4 bits 才能維持準確率
* FC 層容忍度較高，到 2 bits 才會顯著掉準確率
* 實驗顯示：剪枝 + 量化 ≈ 單量化，表示兩者可穩定配合

<p align="center">
<img src="https://hackmd.io/_uploads/Hyteo9Mp1g.png" width="100%"><br>
<strong>圖 7：剪枝不會影響量化效果。虛線：對未剪枝的網路進行量化；實線：對剪枝後的網路進行量化。無論網路是否經過剪枝，準確率都是在相同的量化位元數開始下降。雖然剪枝會減少參數數量，但量化仍然表現良好，甚至在某些情況下（如左圖中的 3 位元）表現比未剪枝網路更好。
</p>

**Centroid 初始化策略比較**
下圖(8)比較了三種初始化方式下，Top-1 / Top-5 準確率在不同 bit 數下的表現：

<p align="center">
<img src="https://hackmd.io/_uploads/SJrwo9MTke.png" width="100%"><br>
<strong>圖 8：不同初始化方法的準確率比較。左圖：Top-1 準確率；右圖：Top-5 準確率。線性初始化帶來最佳結果。
</p>

原因解析：
* 線性初始化將 centroids 平均分佈在 min,max 範圍，能保留少量但重要的大權重
* 隨機與密度初始化常把大權重壓縮進小值群 → 精度損失

**效能與能源效率（Speedup & Energy)**
目標場景：
* 低延遲即時推論應用（如自駕車中的行人辨識）
* 模型須可放入 SRAM（減少 DRAM 存取）

實驗重點：
* 使用 batch size = 1
* 評估層：AlexNet & VGG16 的 FC6 / FC7 / FC8

🧪 **Benchmark 硬體：**

| 類別 | 硬體 | 工具與庫 |
|--------------|---------------------|---------------------------------|
| Desktop GPU | NVIDIA Titan X | cuBLAS / cuSPARSE |
| CPU | Intel i7-5930K | MKL CBLAS / SPBLAS |
| Mobile GPU | NVIDIA Tegra K1 | Jetson TK1 + Power meter |

**測量方式：**
* 計算：矩陣向量乘法（MV）
* 功耗：AP + DRAM 合計（含轉換效率）
* CPU：用 pcm-power
* GPU：用 nvidia-smi

### 結果：

| 指標 | 效果 | 備註平台（可選） |
|----------------|----------------------|--------------------------|
| Speedup | 3×–4× 加速 | Desktop GPU |
| Energy Saving | 3×–7× 省電 | Mobile GPU (Tegra K1) |

若允許 batch 處理（變成 matrix-matrix），剪枝優勢會下降，因為此時能透過 blocking 技術改善 locality。

**權重 / 索引 / Codebook 的儲存比例**

* 剪枝 → 增加「索引空間」以儲存非零位置
* 量化 → 增加「codebook」空間儲存共享權重

<p align="center">
<img src="https://hackmd.io/_uploads/rkpmAqza1e.png" width="100%"><br>
<strong>圖 11：權重、索引與碼本的儲存比例。
</p>

整體壓縮率仍非常高，且 overhead 是可接受的。

# 相關研究（RELATED WORK）

**參數壓縮相關研究：**

深度神經網路普遍具有過度參數化（over-parametrized）的問題，導致計算與記憶體使用嚴重浪費（Denil et al., 2013）。

| 方法 | 核心概念 | 備註 |
|------|----------|------|
| Fixed-point 實作 (Vanhoucke et al., 2011) | 用 8-bit 整數取代 32-bit 浮點 | 可節省記憶體與功耗 |
| Ternary Weights + 3-bit Activation (Hwang & Sung, 2014) | 超低精度運算 | 適用於低資源設備 |
| 最小化 L2 誤差的量化 (Anwar et al., 2015) | 對 quantization 過程做優化 | 提升量化精度 |
| 低秩分解（SVD）(Denton et al., 2014) | 找出權重矩陣的低秩近似 | 精度下降小於 1% |
| 理論研究：隨機稀疏網路 (Arora et al., 2014) | ±1/0/-1 權重也具可訓練性與可逆性 | 有多項式時間訓練與演算法 |

**權重分桶（Weight Binning）與參數共享：**

| 方法 | 差異與侷限 |
|-----------------------------------------------|---------------------------------------------------------------------------|
| HashedNets (Chen et al., 2015) | 權重 binning 透過 hash function 決定，不依賴訓練結果，無法捕捉影像資料特性 |
| Vector Quantization** (Gong et al., 2014) | 精度下降約 1%，且只針對 FC 層壓縮，忽略 CONV 層 |

架構層面簡化：
* Global Average Pooling（Lin et al., 2013；GoogLeNet, 2014）：以平均池化取代 FC 層，減少參數
* 缺點：不利於 transfer learning，因此 GoogLeNet 最後仍保留線性層以支援微調

Network Pruning（剪枝）

| 方法 | 說明 |
|--------------------------------------|----------------------------------------------------------------------|
| 早期方法：Optimal Brain Damage / Surgeon | 使用 loss 函數的 Hessian 來決定剪枝的重要性，比 magnitude-based 更精確 |
| 近期方法：Han et al., 2015 | 成功剪枝多個大型模型，將參數數量降一個數量級 |

# 未來工作（FUTURE WORK）
目前剪枝後的模型已能在各種硬體上運行，但：

* 量化+共享權重的模型無法直接用現有的 BLAS 庫執行（例如 cuSPARSE / MKL）
* 原因是這些庫不支援 間接索引與相對索引（index lookup）

# 解法建議
| 類別 | 解決方案 |
|----------|--------------------------------------------------------------------------|
| 軟體層 | 撰寫客製化 GPU kernels，支援 quantized / sparse 資料存取 |
| 硬體層 | 設計專用 ASIC（可設定量化 bit width，支援稀疏結構邏輯層） |

# 結論（CONCLUSION）

提出的 Deep Compression 方法：
透過「剪枝 + 量化 + Huffman 編碼」在不犧牲準確率的情況下大幅壓縮神經網路。

| 模型 | 資料集 | 壓縮倍率 | 準確率損失 |
|----------|------------|----------|------------|
| AlexNet | ImageNet | 35× | 無 |
| VGG-16 | ImageNet | 49× | 無 |
| LeNet | MNIST | 39× | 無 |

* 壓縮後模型可放入 SRAM cache，從而減少能源與加速運算
* 提升 DNN 模型在 行動裝置與嵌入式系統上的部署潛力
* 更有利於 模型下載 / OTA 更新 / 即時推論