Deep Compression : Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding 모델 압축 논문

2016년 ICLR 논문

며칠 전에 나동빈님께서 유튜브에 좋은 리뷰를 해 주셔서 많은 도움을 받았습니다. 설명을 잘 해주셔서 내용은 참고를 했지만 만드신 자료 그 자체(이미지, 영상)은 인용하지 않았습니다. 좋은 자료 공유해 주셔서 감사합니다.

아래 내용은 논문을 번역한 내용을 기반으로 구글링, 위 유튜브의 설명, 제 생각이 더해져서 작성되었습니다.

1. INTRODUCTION

그림1 : 3단계 압축 파이프라인: 가지치기(pruning), 양자화(quantization), 허프만 코딩(Huffman coding). 가지치기는 가중치의 수를 10배 줄이는 반면, 양자화는 압축률을 27배에서 31배 사이로 더욱 향상 시킨다. 허프만 코딩은 35~49배 사이의 더 많은 압축을 제공한다. 압축률은 희소 표현을 위한 메타 데이터를 이미 포함하고 있다. 압축 방식은 정확성을 잃지 않는다.

2. NETWORK PRUNING

네트워크 가지치기(pruning)는 CNN 모델을 압축하기 위해 널리 연구되었다. 초기 연구에서 네트워크 가지치기는 네트워크 복잡성과 과적합성을 줄이는 유효한 방법임이 입증되었다(LeCun et al., 1989; Hanson & Pratt, 1989; Hassibi et al., 1993; Strom, 1997).

푸르닝 기초 지식
원본 행렬의 가중치 값을 특정 값으로 threshold를 걸어서 그 미만 값은 0으로 푸르닝 하면,
0이 아주 많이 포함 된 행렬이 나올 것, 0이 많은 matrix를 별도의 자료구조로 압축(?) 디코딩 함

Coordinate list (COO) : 행과 열 정보만 기록 하는 방식, 큰 matrix에 대부분이 0이므로 (4, 6)위치에 5가 있다. 는 식의 표현이 전체를 표현 하는 것보다 효율적임

Compressed sparse row (CSR) : column데이터는 별도 list로, row 데이터는 Row pointer로 표현 함
Row Pointer는 row 개수를 직접 기록하는 게 아니라 누적 합을 기록함 (이전 값과 비교해서)

그림 1의 왼쪽에 표시된 것처럼, 우리는 일반적인 네트워크 학습을 통해 연결을 학습하는 것으로 시작합니다. 다음으로, 우리는 작은 가중치 연결을 제거한다. 가중치가 임계값 보다 낮은 모든 연결은 네트워크에서 제거된다. 마지막으로, 나머지 희소 연결에 대한 최종 가중치를 학습하기 위해 네트워크를 재교육한다. 가지치기는 AlexNet과 VGG-16 모델의 매개 변수 수를 9배, 13배 줄였다.

압축 희소 행(CSR)을 사용하여 푸르닝에서 발생하는 희소 구조를 저장한다. 압축 희소 열(CSC) 형식: 2a + n + 1개의 숫자가 필요하다. 여기서 a는 0이 아닌 요소의 수이고 n은 행 또는 열의 수이다.

더 압축하기 위해, 논문에서는 절대 위치 대신 인덱스 차이를 저장하고, 이 차이를 Conv layer의 경우 8비트, FC layer의 경우 5비트로 인코딩한다. 한계보다 큰 인덱스 차이가 필요할 경우 그림 2에 표시된 패딩 제로 솔루션: 차이가 8을 초과할 경우 최대 3비트(예: 서명되지 않은 숫자) 필러 0을 추가한다.

위에서 설명 한대로 Compressed sparse row (CSR)을 사용하는데, 이것은 차이 값을 기록하는 것.
노란 블록 index 1, 4, 15를 보면 0이 아닌 유효값 임. 이것의 diff값을 보면, index 4는 이전 유효값 1과 3만큼 차이나기 때문에 3으로 기록 한 것. 근데 이 diff값을 표현 하는데 3bit를 할당했고, 8까지 표현 할 수 있는 것, 근데 index 4와 15는 8이상 떨어져 있기 때문에 중간에 0이라서 그냥 넘겼을 index 12에 굳이 Filler zero를 넣고 diff값에 8을, index 15에 diff 3을 넣은 것

3. TRAINED QUANTIZATION AND WEIGHT SHARING

네트워크 양자화와 Weight 공유는 각 Weight를 나타내기 위해 필요한 비트 수를 줄임으로써 네트워크를 더욱 압축한다. 우리는 여러 연결부가 동일한 가중치를 공유하도록 하여 저장해야 하는 유효 가중치의 수를 제한한 다음 이러한 공유 가중치를 미세 조정한다.

Weight 공유는 그림 3에 나와 있다. 4개의 입력 뉴런과 4개의 출력 뉴런이 있는 층이 있다고 가정하자, Weight는 4 x 4 행렬이다. 왼쪽 위에는 4 × 4 Weight 매트릭스가, 왼쪽 아래에는 4 × 4 그레이디언트 매트릭스가 있다.

Weight는 4개 양자화된 값으로, 그림에서 4가지 색상으로 표현돼있다. 동일한 색으로 돼 있는 모든 Weight는 동일한 값을 공유하므로, 각 Weight에 대해 우리는 공유 Weight의 테이블에 작은 인덱스만 저장할 필요가 있다. 업데이트 중에 모든 그레이디언트는 컬러에 의해 그룹화 되고 합쳐서 lr 에 곱하고 마지막 반복에서 공유 중심에서 감산 된다. AlexNet의 경우, 우리는 정확성 손실 없이 각 CONV 계층에 대해 8비트(256 공유 가중치), 각 FC 계층에 대해 5비트(32 공유 가중치)로 정량화할 수 있다.

압축률 계산
원래 Weight = n = 16
클러스터 = k = 4
각 연결당 비트수 = b = 32 인 경우에...
r = nb / nlog2(k) + kb = 압축전 / 압축후 =
= 16 * 32 / 16 log2(4) + 4 * 32 = 512 / 16 * 2 + 128 = 512 / 160 = 3.2

3.1 WEIGHT SHARING

위 그림3의 상단 Weight를 보면 가까운 값들 끼리 클러스터링 돼 있음 이 값은 weight의 k-means에 의해 대표값이 설정 됨 레이어마다 이 값을 정함

3.2 INITIALIZATION OF SHARED WEIGHTS

중심 초기화는 클러스터링 품질에 영향을 미치므로 네트워크의 예측 정확도에 영향을 미친다. 랜덤, 밀도 기반, 선형 초기화 세 가지 초기화 방법을 알아봤다. 그림 4에서 알렉스넷(CDF는 파란색, PDF는 빨간색)의 conv3 레이어의 원래 가중치 분포를 그렸다. Weight는 네트워크 푸르닝 후 두 가지 분포를 형성합니다. 그래프 아래쪽에는 파란색, 빨간색, 노란색 세 가지 초기화 방법이 있는 유효 가중치(중심점)가 표시됩니다. 이 예에서는 13개의 클러스터가 있습니다.

Forgy(랜덤) 초기화(노란색 점)는 데이터 집합에서 k개의 관측치를 랜덤하게 선택하고 이를 초기 중심점으로 사용합니다. 초기화된 중심은 노란색으로 표시됩니다. 이항 분포에는 두 개의 피크가 있으므로 포기 방법은 두 피크를 중심으로 집중하는 경향이 있습니다.

밀도 기반 초기화(파란색 점)는 y축에서 가중치의 CDF(누적 분포 함수)를 선형으로 띄운 다음, CDF와 수평 교차점을 찾고, 마지막으로 파란색 점처럼 중심이 되는 x축에서 수직 교차점을 찾는다. 이 방법은 두 봉우리를 중심으로 중심점을 더 조밀하게 만들지만 Forgy보다 더 산란하게 만듭니다. (= Y축으로 동일한 간격으로 초기화)

선형 초기화(빨간색 점)는 원래 가중치의 [min, max] 사이에 중심을 선형으로 띄운다. 이 초기화 방법은 가중치의 분포에 불변하며 이전 두 방법과 비교하여 가장 산란적이다.

큰 가중치는 작은 가중치보다 더 중요한 역할을 하지만(Han et al., 2015) 이러한 큰 가중치는 더 적다. 따라서 Forgy 초기화 및 밀도 기반 초기화의 경우, 매우 적은 수의 중심체가 큰 절대값을 가지므로 이러한 몇 개의 큰 가중치를 제대로 표현하지 못한다. 선형 초기화는 이 문제를 겪지 않습니다. 실험 섹션에서는 클러스터링 및 미세 조정 후 다른 초기화 방법의 정확도를 비교하여 선형 초기화가 가장 잘 작동함을 보여준다.

등장 빈도가 높은 값이 잘 선택되는게 중요한게 아니라 딥러닝 특성상 절대값이 큰 값이 잘 선택돼야 함. 그래서 선형 초기화 방식이 더 좋음.. 너무 크거나 작은 값에도 잘 작용 함

3.3 FEED-FORWARD AND BACK-PROPAGATION

1차원 k-means의 중심은 공유 가중치이다. Feed-forward 단계 및 역전파(Back-propagation) 단계 중 weight 테이블을 조회하는 한 가지 간접 정보가 있음. 각 연결에 대해 공유 weight 테이블의 인덱스가 저장됩니다. 역전파 중에 각 공유 weight에 대한 그라데이션이 계산되고 공유 가중치를 업데이트하는 데 사용됩니다. 이 절차는 그림 3에 나와 있습니다.

4. HUFFMAN CODING

허프먼 코드(Huffman code)는 무손실 데이터 압축에 일반적으로 사용되는 최적의 코드이다. 가변 길이 코드 워드를 사용하여 소스 기호를 인코딩한다. 표는 각 기호에 대한 발생 확률에서 파생됩니다. 더 일반적인 기호는 더 적은 비트로 표시됩니다.

그림 5는 AlexNet에서 마지막으로 완전히 연결된 계층의 양자화된 가중치와 희소 행렬 지수의 확률 분포를 보여준다. 두 분포 모두 편향되어 있다. 양자화된 가중치는 대부분 두 피크를 중심으로 분포되어 있다. 희소 행렬 지수 차이는 거의 20을 넘지 않는다. 실험에 따르면 Huffman이 이러한 불균일하게 분포된 값을 코딩하면 네트워크의 20% - 30%가 절약된다.

5. EXPERIMENTS

논문에서 프루닝, 양자화 및 허프먼이 네 개의 네트워크, 즉 MNIST에 두 개, ImageNet 데이터 세트에 두 개 인코딩했다. 프루닝 전후의 네트워크 파라미터와 정확도-1은 표1에 나타나 있다. 압축 파이프라인을 사용하면 정확성 손실 없이 서로 다른 네트워크에서 네트워크 스토리지를 35~49배 절약할 수 있습니다. AlexNet의 총 크기는 240MB에서 6.9MB로 감소했다. 온칩 SRAM에 넣을 수 있을 정도로 작은 MB로, 에너지 소비량이 많은 DRAM 메모리에 모델을 저장할 필요가 없습니다.

뒤에 있는 FC레이어가 압축률이 좋음. FC는 연결이 많고.. 특히 FC6은 앞에 Conv의 정보를 아주 많이 포함하고 있어(혼자만 103MB임) 압축할게 많음.. 1%만 씀.. 이마저도 허프만 코딩으로 더 적은 비트로 압축 함

네트워크 용량을 30~50배정도 압축 하면서 인식률 저하가 없다. 짱이다.. 미쳤따...