Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding

arxiv.org
2016

一言で言うと

Deep compressionを使って，精度劣化なしに35倍から49倍NNの必要ストレージを削減する．
Deep compressionは以下の3つのパイプラインステージから成る

枝刈り（学習フェーズで必要な（重要な）接続だけを学習）
量子化（あと重み共有）
ハフマン符号（バイアスの偏りを有効に利用するため）

これらを一緒に使う．
はじめの2ステップをやったら，残りのパラメータを微調整するために再学習する．枝刈りは9倍から13倍のパラ数を削減，量子化は32倍から5倍のビット表現を削減する．

結果

精度劣化無しで，AlexNetを35倍圧縮（240MB-->6.9MB）, VGG-16を49倍圧縮（552MB-->11.3MB）に成功．
これによりオフチップのDRAMメモリではなく，オンチップなSRAMキャッシュにモデルを搭載させることができる．

f:id:taku-buntu:20190116113043p:plain

枝刈り+量子化を同時に使うと最も圧縮率が高い。枝刈りを使うと、同程度の量子化でも高い精度を保つことができる。また、線形な重心初期化が最も良かった。

手法

f:id:taku-buntu:20190115114429p:plain — Deep compressionの3つのパイプラインステージ

枝刈り

完全な学習済みネットワークを作る．
値の小さい重みを枝刈りする．しきい値よりも小さな結合重み全てをネットワークから削除．
最終的なスパース重みを再学習

これにより9倍から13倍のパラ数を削減行圧縮（CSR）か列圧縮（CSC）を使った枝刈りの結果をスパース構造で結果を保存．絶対位置ではなくインデックス差を下図の形式で保存する．このインデックス差をconv層では8bit，fc層では5ビットにエンコード．それらの境界よりも差が大きければ0パディング．

f:id:taku-buntu:20190115114733p:plain — 相対インデックスを持つスパース行列表現．オーバーフローを防ぐためにゼロパディング．

量子化と重み共有

以下の図の様に重み共有をする．重みパラの値が近い者同士をビン（上段の色）に入れる．それに対応する勾配のところをグループ化して積み重ねる（下段）．下段の同じビンの中身を全部足して，学習率と掛けて，最後にcentroidsとを減算する．

f:id:taku-buntu:20190115121720p:plain — 図1 重み共有．（上）重みパラ（下）勾配．centroidsは入力．

k=クラスタ数としたとき，インデックスをエンコードするのに必要なビット数は $log _ { 2 } (k)$ bits．一般的に，それぞれb bitsのn個の結合を持つネットワークでは
圧縮率は，
$r = \frac { n b } { n \log _ { 2 } ( k ) + k b }$

上の図1では，元々4x4=16の重みがあるが，4つのグループとして重み共有するとそれぞれ32bitで構成される4個の重みになり，それと3.2（=1632/(432+2*16)）の圧縮率を与える2ビットで構成される16のインデックスになる．（うまい翻訳わからない）

重み共有

重みを共有するパラメータを決定するのには学習済みネットワークの各層に対して，k-meansクラスタリングを利用する．層を超えての共有はない．nのパラをkクラスタにするのにはWCSS（within-cluster sum of squares）を最小化する．

$\underset { C } { \arg \min } \sum _ { i = 1 } ^ { k } \sum _ { w \in c _ { i } } \left| w - c _ { i } \right| ^ { 2 }$
$W = \left{ w _ { 1 } , w _ { 2 } , \ldots , w _ { n } \right}, C = \left{ c _ { 1 } , c _ { 2 } , \ldots , c _ { k } \right}$

HashNet(Chen et al. 2015)と違うのは，ネットワークが訓練データを見る前に重み共有はハッシュ関数によって決定されていること．今回は，完全にネットワークを学習させて，そのあとにオリジナルネットワークに近似していく．

共有重みの初期化

Forgy:ランダムにk個の観測値を取ってきて，それを重心（centroid）とする．観測点は黄色o．
Density-based: 重みのCDF空間のy軸に線形に棒線（赤い点線）を引いて，CDFとの交点のx軸ポイントを重心として取り出す．（青o）
Linear:オリジナル重みの[min, max]の範囲から線形に重心を取り出す．で初期化，元の分布とそれぞれで初期化した重みの分布を示す．

f:id:taku-buntu:20190115172320p:plain — （左）重心初期化の分布．（右）重み分布（青）とコード分布（緑x）とファインチューニングあとの分布（赤）

CDF：累積分布関数
PDF：確率密度関数

Forgy, Density-basedだと重みに広がりがでない（値の大きな値がない）からよくない．

逆伝搬は以下の式で行う．
$\frac { \partial \mathcal { L } } { \partial C _ { k } } = \sum _ { i , j } \frac { \partial \mathcal { L } } { \partial W _ { i j } } \frac { \partial W _ { i j } } { \partial C _ { k } } = \sum _ { i , j } \frac { \partial \mathcal { L } } { \partial W _ { i j } } \mathbb { 1 } \left( I _ { i j } = k \right)$