[논문 정리] Deep Compression : Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding

졸업프로젝트를 시작하면서 하드웨어 최적화와 관련된 다양한 논문을 읽고 있어 정리해보고자 한다

이 논문은 2016년에 나왔고 글을 쓰는 현재 3900회가 넘게 인용되었다고 나오고 있다

교수님께서 예시로 들어주신 pruning의 개념이 포함된 논문이라 읽기 시작했는데 추가로 다양한 개념들을 알 수 있었다

Abstract

임베디드 시스템에서는 연산량과 메모리 사용량이 중요 

연산량을 고려하지 않으면 임베디드 시스템에서 사용 X

3 stage pipelines : pruning → trained quantization → Huffman coding

처음 두 단계 후, 남은 연결과 정량화된 중심들을 미세하게 조정하기 위해 네트워크를 재교육

필요한 용량이 줄어들어 off-chip DRAM 대신 on-chip SRAM에서 모델 사용 가능

Introduction

AlexNet Caffe model(200MB), VGG-16 model(500MB)와 같은 모델들은 너무 커서 mobile system에서 사용하기에 적절하지 X

모바일 앱에서 deep neural network를 사용하면 프라이버시, network 대역폭, 실시간 처리 등의 장점이 존재하지만 저장공간 때문에 사용이 어렵다

큰 뉴럴 네트워크 모델을 사용하면 에너지 사용량이 커지므로 배터리를 사용하는 모바일 기기에 적합하지 X

에너지 사용량은 메모리 접근 횟수에 정비례 ( 연산과 SRAM 접근에 비해 DRAM에 접근할 때 훨씬 에너지 소모가 크다 )

three stage pipeline을 이용하여 deep compression을 구현하여 적은 공간 사용량과 적은 에너지 사용량이 목표

중복 연결을 제거하고 가장 유용한 연결만 유지함으로써 네트워킹을 제거 →가중치를 정량화하여 여러 연결부가 동일한 가중치를 공유하도록 하여 코드북(유효한 가중치)과 지수만 저장→유효체중의 편중분포를 이용하기 위해 허프만 코딩을 적용

Network Pruning

네트워크 프루닝은 CNN model의 크기를 줄이고 과적합을 막기 위해 사용

 

평범한 network training으로 학습  후 weight이 작은 connection의 가지치기( threshold보다 작은 weight은 삭제 )

retrain 후 final weight 구하기

그 결과 9~13배로 용량 감소

 

프루닝 후의 결과인 sparse structure를 compressed sparse row (CSR), compressed sparse column (CSC) 에 저장

2a + n + 1 개 필요

a : the number of non-zero elements

n : the number of rows and cols

 

CSR이란?

행렬 M( m*n ) 을 세개의 일차원 배열로 나타내는 것

• non-zero values (V)
• extents of rows (COL_INDEX)
• column indices (ROW_INDEX)

빠른 열 접근과 행렬-벡터 곱에 도움

NNZ : 행렬 M안에 있는 0이 아닌 값들의 개수

V와 COL_INDEX의 길이는 NNZ

ROW_INDEX 배열에는 각 열별로 하나의 원소를 갖고, 그 원소는 V 배열에서 각 열이 어디서 시작하는지 해석하는 데 쓰인다

예제

V = [ 5 8 3 6 ]

COL_INDEX = [ 0 1 2 1 ]

ROW_INDEX = [ 0 0 2 3 4 ]

열의 값을 구하기 위해서는

row_start = ROW_INDEX[row]

row_end = ROW_INDEX[row+1]

두번째 열을 구하기 위해서는 row_start = ROW_INDEX[1] = 0, row_end = ROW_INDEX[2] = 2

V[0:2] = [ 5 8 ]

COL_INDEX[0:2] = [ 0 1 ]

두번째 열 = [ 5 8 0 0 ]

CSR은 $NNZ < (m*(n-1)-1)/2$ 일 때만 메모리 절약

→ 2a + n + 1에서 2a는 V+COL_INDEX, n은 COL_INDEX, 1은 COL_INDEX 시작에 필요

 

index difference가 지정 범위를 넘어서면 zero padding solution을 사용

 

예시를 보면 diff라는 곳에 가중치의 실제 위치 대신 그 전의 0이 아닌 가중치와의 difference를 저장해놓은 것을 확인 가능

만약 diff에 저장할 수 있는 bit 수를 넘어간 곳에 다음 0이 아닌 위치의 가중치가 있다면 filler zero를 삽입하여 overflow를 방지한다

Trained Quantization and Weight Sharing

각 가중치를 나타내는 데 필요한 비트 수를 줄여 pruned network를 더욱 압축

가중치의 개수에 제한을 두기 위해 같은 가중치를 공유하는 multiple connection 사용하고 그 공유된 가중치들을 fine-tune

가중치 공유 예시

4개의 input 뉴런, 4개의 output 뉴런, 4x4 행렬의 가중치

행렬은 색깔별로 4개의 bin으로 양자화되며 같은 bin에 있는 가중치는 같은 값을 갖게 된다

gradient는 bin별로 모여 더해진 후 learning rate를 곱해 가중치의 centroids에서 그 값을 빼주어 fine-tuned centroids를 만든다

k개의 cluster를 사용하면 index를 encoding하기 위해 $log_2(k)$ 비트가 필요

n connection이 있는 네트워크에서 각 connection이 b 비트로 이루어져있고 k개의 공유 가중치만 사용하기로 한다면 compression rate는 $r ={nb \over nlog_2(k)+kb}$

예시의 가중치는 4*4 = 16이었지만 공유를 통해 4로 줄어들었다

16개의 32bit → 4개의 32bit

n = 16

b = 32bit

k = 4

→ r = 3.2

Weight Sharing

공유할 가중치를 정하기 위하여 k-means 클러스터링 사용

같은 클러스터에 있는 가중치들은 같은 가중치가 된다

가중치는 layer간에는 공유되지 않는다

n개의 가중치를 k개의 클러스터로 WCSS를 최소화 시키면서 묶는다

공유된 가중치가 기존의 네트워크에 근접하도록 가중치 공유를 모델 학습이 완전히 끝난 후에 결정한다

→ hashNet과 다름(학습 전에 해시함수에 의해 가중치가 결정됨)

Initialization of Shared Weights

k-means 클러스터링에서 centroid의 초기값은 클러스터링에 큰 영향 → 네트워크의 예측 정확도에 영향

세가지 초기화 기법

1. Forgy 랜덤으로 k개를 골라 초기 centroid로 사용 그림에서의 노란색 → 두개의 지점에 가중치가 몰려있으므로 초기값도 그 지점에 대부분 형성된다

2. Density-based 누적분포함수(CDF)에 따라 일정 비율로 초기 centroid로 사용

   y축을 n등분 → 그 y값을 가지는 CDF의 x값 가중치들이 몰려 있는 부분에 맞추어 초기값이 지정되지만 forgy 방법에 비해 덜 몰리게 된다

3. Linear 가중치들의 최소값, 최대값에 균일하게 분포된다 1,2번에 비해 흩어져서 초기 centroid 값 분포

가중치가 큰 경우 작은 경우보다 그 가중치의 역할은 중요하지만 큰 가중치는 수가 적다 → 1,2번은 값이 큰 가중치를 잘 나타내지 못한다 → linear가 가장 정확 ( experiments에서 확인 )

Feed-forward and Back-propagation

1차원 k-means 클러스터링의 centroid 값들은 공유 가중치

각 공유 가중치의 그래디언트를 계산한 뒤, 이를 이용하여 공유 가중치를 갱신

Huffman Coding

허프만 코딩은 무손실 압축 알고리즘으로 prefix code이다

자주 쓰이는 symbol 일 수록 적은 비트를 할당한다

20~30퍼센트 만큼 공간을 적게 사용할 수 있다

Experiments

MNIST와 ImageNet 데이터셋을 사용하여 모델 생성

Caffe framework 사용

pruning은 mask를 추가하는 방법으로 구현

quantizaion과 공유 가중치는 공유 가중치를 저장하는 구조는 유지하며 각 layer의 그래디언트를 계산하며 update → 추가 공부하기

huffman coding은 학습과 관련이 없으므로 fine-tuning이 끝난 후 구현

 

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