Entropy, Cross Entropy, KL divergence

Entropy

엔트로피는 Random Variable의 평균 정보량을 의미합니다

 

$H(X) = -\sum_X p(x)I(x)$

 

I(x)는 information function입니다

$I(x) = -log(p(x))$로 정의되는데, 어떻게 이렇게 정의될 수 있는지 살펴보겠습니다

 

정보량이라는 것이 무슨의미를 가지는 것인지 생각해봅시다

 

어떠한 사건이 발생했을 때 그 사건이 일어날 확률이 높을수록 정보량은 적다고 할 수 있습니다

예를들어, 당첨되지 않는 로또번호를 아는 것은 주는 정보가 매우 적습니다.

왜냐하면 대부분의 로또번호는 당첨되지 않기 때문입니다

하지만 당첨되는 로또 번호를 아는 것은 적은 확률에 대한 정보를 알고있는 것이기 때문에 정보량이 많다고 할수있습니다

 

이러한 사실들로 다음과 같은 식을 만족하는 I를 information function이라고 정의할 수 있습니다

1. I(p)는 monotonically decreasing in p: 사건이 일어날 확률이 높을 수록 정보량이 적습니다
2. I(1) = 0: 항상 일어나는 사건은 정보량이 없습니다
3. I(p1·p2) = I(p1) + I(p2): 독립된 두 사건으로부턴 얻은 정보의 합은 두 사건이 동시에 일어났을 때 주는 정보량과 같습니다

위를 만족하는 I는 -log가 유일합니다

 

logarithm base를 정의하는 방법은 많은데 컴퓨터에서는 보통 2로 정의합니다

 

Arithmetic coding

Arithmetic coding은 데이터를 압축하는 방법입니다

Cross Entropy를 설명하는데 필요한 개념입니다

 

input이 a와b인 N의 길이를 가진 string을 압축한다고 가정합시다

N=2이라고 가정합니다

가능한 string은 다음과 같습니다

aa / ab / ba / bb

목표는 길이가 2인 string을 bit로 전달할 때 bit수를 최대한 줄이는 것입니다

a가 등장할 확률이 0.9, b가 등장할 확률이 0.1이라고 가정해봅시다

 

가능한 압축방법은 다음과 같습니다

aa => 0 (1bit)

ab => 1 (1bit)

ba =>10 (2bits)

bb =>11 (2bits)

 

길이가 2인 string을 표현하는데 드는 평균 비트수는

0.9*0.9*1(bit) + 0.9*0.1*1(bit) + 0.1*0.9*2(bit) + 0.1*0.1*2(bit)  = 1.10 (bit)

 

길이가 1인 string을 표현하는데 평균 1비트가 듭니다 (a=>0   /  b=>1)

길이가 2인 string을 표현하는데 2비트가 들것같지만, string마다 bit길이를 다르게 할당하면(Variable-length code) 압축을 할수있습니다

 

Arithmetic coding의 방법은 다음과 같습니다

 

방법은 다음과 같습니다

 

arithmetic coding

위 그림처럼 a,b 확률에 따라 [0,1)의 범위를 나눕니다

최종적으로 아래와 같은 범위가 나옵니다

aa = [0,0.81)

ab = [0.81,0.9)

ba = [0.9,0.99)

bb = [0.99,1)

 

위 범위를 만족하는 숫자중에 길이가 제일 짧은 것이 arithmetic encoding이 됩니다

aa => 0.0 => 1bit

ab  => 0.875 => 0.111(2진수) => 3bits

ba  => 0.9375 => 0.1111 => 4bits

bb  => 0.9921875 => 0.1111111 => 7bits

(arithmetic coding말고 그냥 처음에 설명했던 압축방법을 쓰는게 더 효율적일것같은데 왜이렇게 하는지는 잘 모르겠습니다)

 

Average Bits=(0.81×1)+(0.09×3)+(0.09×4)+(0.01×7)=1.51 bits

 

S = [l,h) 라고 segment가 지정되었을 때 coding을 구하는 방법과 이를 통해 필요한 비트 수를 알아봅시다

 

목표로 구하고 싶은 건 하나의 문자가 인코딩되는데 얼마만큼의 평균 bit가 필요한지 입니다

 

l와 h는 아래 그림처럼 소수점 어느 부분까지는 동일하다가 숫자가 달라지는 기점이 있을것입니다

$l = 0.b_1b_2b_3b_4b_50...$

$h = 0.b_1b_2b_3b_4b_51...$

그러면 이는 $0.b_1b_2b_3b_4b_51$로 인코딩 할 수있습니다 (h=$ 0.b_1b_2b_3b_4b_51$ 면 $ 0.b_1b_2b_3b_4b_5$) 

 

인코딩된 길이를 k라고 했을 때 다음 식을 만족하는 k를 생각해봅시다

$l \leq \frac{n}{2^k}\leq  \frac{n+1}{2^k} \leq h$

위 수식을 만족하는 최소 k가 최적으로 인코딩 되었을 때 비트 길이 입니다

(개인적인 생각으로는 $\frac{n'}{2^{k-1}} \leq l  \leq  \frac{n'+1}{2^{k-1}} \leq h$를 동시에 만족할 수도 있기 때문에 저 수식을 만족한다고 해서 최적으로 인코딩 되었는지는 잘 모르겠습니다, 어쨌든 필요한 최대 비트수를 계산할 수는 있습니다)

$\frac{1}{2^k}\leq h-l$

$k=\lceil -\log_2(h-l) \rceil$

 

문자 XXXXX의 segment가 [l,h)라면 XXXXX가 등장할 확률이 h-l입니다

 

이제 길이가 N인 string의 arithmetic coding의 평균길이를 구해봅시다

$\bar l_N = \sum_MP(M)l(M)$

M은 message의 약자입니다

$l(M) \leq \lceil \log_2(h_M-l_M) + 1 \rceil = \lceil \log_2(\frac{1}{P(M)}) + 1 \rceil \leq log_2(\frac{1}{P(M)}) + 2$

(중간 부등호에서 +1은 왜있는건진 모르겠음)

$N*H \leq \bar l_N \leq N*H +2$

H는 처음에 저희가 구했던 엔트로피 입니다.

왼쪽 부등식은 Shannon's theorem에 의해 성립된다고 합니다.

 

양변에 N을 나눠주고 N이 충분히 크다면

$\bar l\approx H$

즉, 하나의 symbol이 인코딩되는데 H(엔트로피)만큼 bit가 필요하다는 뜻입니다

Cross Entropy

p는 실제 분포이고 q는 추정 분포입니다. 추정된 분포로 비트수를 계산할 때 실제로 필요한 하나의 symbol당 평균 비트수를 cross entropy라고 합니다

$H(p,q)=-\sum _{X}p(x)\log _{2}q(x)$

 

마찬가지로 P(a)=0.9 / P(b) = 0.1로 가정하겠습니다

N=2 이면, arithmetic coding에 의해 다음과 같이 인코딩 됩니다

aa => 0.0 => 1bit

ab  => 0.875 => 0.111(2진수) => 3bits

ba  => 0.9375 => 0.1111 => 4bits

bb  => 0.9921875 => 0.1111111 => 7bits

 

하지만 a와 b의 추정치가 실제와 다를수도 있습니다

P(a)=0.9 / P(b) = 0.1 인줄 알았지만, 실제로 P(a)=0.8 / P(b) = 0.2이라고 합시다

 

그러면 이때 평균 비트수는

Average Bits=(0.64×1)+(0.16×3)+(0.16×4)+(0.04×7)= 2.04 bits

 

symbol당 평균 비트는 1.02 bits가 됩니다

이 값이 Cross Entropy 입니다

(예시를 들기위해서 N=2로 가정하고 계산했고 실제로는 공식에 따라 계산하면 됩니다)

 

KL-divergence

Cross Entropy와 Entropy의 차이가 KL-divergence입니다

확률분포 P가 Q로부터 얼마나 차이가 나는지 측정할때 쓰입니다

$D_{KL}(P||Q) = H(p,q) - H(p)=-\sum _{X}p(x) \frac{\log _{2}q(x)}{\log _{2}p(x)}$

 

Loss function

 

Cross Entropy는 one-hot label에서 classification을 할 때 씁니다.

$−∑_iy_i\log(p_i)$

y가 한개만 1이고 나머지는 0입니다. 따라서 true label에 얼마나 잘 따라가는지 측정하는 것이기 때문에 직관적으로 이해하기 쉽습니다

 

KL-divergence는 one-hot label에서는 쓸수없습니다. 왜냐하면, log(0)이 정의가 안되기 때문입니다.

두 확률분포를 비교해야할 때 loss function으로 쓸 수 있습니다. 예를 들어, knowledge distillation에서 student는 teacher의 확률분포를 배우는데 이 때 KL-divergence를 쓸 수 있습니다.

또한 두 확률 분포를 계산하는데 Cross Entropy를 loss로 썼다고 해봅시다. Cross Entropy는 두 확률분포가 동일하더라도 0이 아니기 때문에 부적합합니다.

 

 

 

https://en.wikipedia.org/wiki/Entropy_(information_theory)

Entropy (information theory) - Wikipedia

 

https://web.mat.upc.edu/sebastia.xambo/CDI15/CDI15-04-ArithmeticCoding.pdf