컴퓨터 과학에서 말하는 compression의 개념

1. 손실압축과 비손실압축

 

비손실압축은 압축된 자료를 원래 자료로 복원하면 그대로 원래 자료가 나오는 압축 방식

 

손실압축은 압축된 자료를 원래 자료로 복원해도 원래 자료 그대로 나올수가 없는 압축 방식

 

mp3같은 소리 압축 방식은 original 소리에 사람이 들어도 이해할 수 없는? 너무 저주파나 너무 고주파를 Fourier transform으로 잘라 남은 것을 합쳐 가청주파수로 만드는 방식

 

그러니까 복원해도 원래 original 소리로 완벽하게 나오지 않는 대표적인 손실 압축이다

 

 

손실 압축과 비손실 압축의 차이

 

2. Huffman coding

 

message에 대한 encoding 약속이 original message의 길이에 depend하는 방식

 

original message에 등장을 자주하는 단어는 적은 bit로 압축하고 등장을 자주하지 않는 단어는 많은 bit로 압축하는 방식

 

무조건 동일한 bit로 압축하는 것보다 효율적으로 압축이 가능하다.

 

 

 

original message에 자주 등장하는 C,A,D는 적은 2bit로 상대적으로 덜 등장하는 B는 3bit로 F,E는 4bit로 표현함

 

compression rate는 압축 전 16 byte / 압축 후 4.625 byte =3.4595가 맞는 것 같은데 오류로 추측

 

 

3. compression

 

original message를 code rule에 의해 새로운 message로 바꾸는 과정을 encoding이라 한다.

 

code rule의 반대인 inverse mapping을 적용하여 새로운 message를 original message로 바꾸는 과정을 decoding이라 한다.

 

특히 original message를 표현하기 위한 bit 수가 새로운 message를 표현하기 위한 bit수보다 많을 때, 즉 encoding을 하여 필요한 bit수가 줄어들면 compression이라고 부른다

 

 

 

compression은 encoding의 subset개념이라고 할 수 있다

 

길이가 아니라 bit수가 줄어야 compression

 

huffman coding만 봐도 coding한게 길이가 길잖아

 

------------------------------------------------------------------------------------------------------------------------------------------------

 

예시)

 

1 bit는 2^1으로 2가지 경우의 수인 0과 1을 표현할 수 있다.

 

2 bit는 2^2으로 4가지 경우의 수인 0,1,2,3을 표현할 수 있다.

 

비슷하게 32bit는 2^32으로 0부터 ( (2^32) - 1)까지 표현(음수를 고려하지 않은 정수만 생각할 경우)할 수 있다.

 

1byte는 8bit이다.

 

 

 

 

문자 1문자당 1byte로 가정

 

코드북에서 압축하면 0,1,2,3 4가지로 표현하므로 1글자당 2bit표현

 

1byte=8bit니까 2bit= (1/4) byte여서 4로 나눠서 byte를 구함

 

 

 

문자 1문자당 1byte라고 가정해서 문자 길이만큼 byte로 표현

 

코드북에서 0,1만 사용했으므로 압축시 문자 하나당 1비트 표현

 

1byte=8bit니까 1bit는 (1/8)byte이므로 8로 나눠서 byte를 구했음(len(encoded)/8)

 

압축률은 뜬금없이 4로 나눈걸 사용(len(encoded)/4)하였는데 오타라고 추측하고 있음

 

------------------------------------------------------------------------------------------------------------------------------------------------

 

4. compression rate

 

original model의 parameter 수가 a이고 compressed model의 parameter 수가 a*이다.

 

original model의 실행 시간이 s이고 compressed model의 실행시간이 s*이다.

 

compression rate는 a/a*이고 speedup rate는 s/s*이고 공간절약률 space save rate는 (a-a*)/a*

 

기본적인 compression rate 관련 metric을 구하는 방법

 

 

5. deep compression

 

서로 independent한 pruning, quantization, huffman coding의 적절한 조합으로 compression을 하는 방법을 제안한 논문

 

deep compression에서 사용한 방법 도식화

 

P,Q,H 순서대로 해서 P만 할 수도 P+Q만 할 수도 P+Q+H를 할 수도

 

방법을 추가함에 따른 compression rate가 어느정도인지 알려주고 있음

 

network 단위로도 압축해봤고 layer 단위로도 압축해보아서 accuracy는 약간 더 좋아졌지만 그에 비해 parameter 수를 획기적으로 줄였다면서 성능이 좋다는 것을 표로 제시했음

 

 

 

평균적으로 거의 40배 정도 줄였음

 

acuuracy는 약간 더 좋아졌는데?(에러가 약간 감소)

 

compress rate가 위에서 말한 #original parameter/#compressed parameter

 

 

 

pruning과 quantization이, 필요없는 weight를 제거하는 기법인데

 

VGG16은 앞단 layer에 필요없는 weight가 많이 몰려있다는 것을 짐작할 수 있음

 

압축을 많이해도 성능 차이가 거의 없으니까

 

network 특성일수도 있고 dataset때문일 수도 있고

 

pruning과 quantization을 조합한 기법이 model size 약 98%까지 압축해도 accuracy loss가 0%, 정확도 손해가 거의 없다는 것도 보였음

 

 

 

각종 기법들의 model size 압축률 대비 정확도 손해(accuracy loss) 정도를 그래프로 나타냄

 

x축에 11%부분은 89%를 압축했다는 뜻