Entropy의 의미 (정보이론)

Entropy in information theory

정의

정보이론에서, 확률변수의 엔트로피는 변수의 불확실성의 기댓값이다.

$\mathcal{X}$에서 추출한 (이산)확률변수 $X$의 엔트로피를 $H(X)$라 하고 아래와 같다.

\[ H(X) = -\sum_{x \in \mathcal{X}}p(x)\log{p(x)} = E[-\log{p(X)}] \]

$H(X)$로 얻은 수가 정보의 양이라 할 수 있다.

이때 $\log$의 밑은 도메인에 따라 달라지는데, 밑이 $2$인 경우 비트, $e$인 경우 nat(natural unit), $10$인 경우에는 dit라고 부른다.

 

정보의 불확실성, 그 의미는?

확률적으로, 어떤 사건이 더 정보를 가질까?

'정보'라고 하니 유용성과 엮여 직관적이지 않게 느껴질 수도 있다.

항상 일어나는 사건은 정보로서 가치가 있는가를 생각해보면 좋다. 그렇지 않다.

오히려 드물게 일어나는 사건이 오히려 정보로써 가치가 있다.

즉 사건 $E$의 확률인 $ p(E)$가 $1$에 가까울수록 surprisal of the event는 낮아지고, $p(E)$가 $0$에 가까울 수록 높은 관계를 갖는다. 이를 함수로 표현하면 다음과 같다.

\[ \log{\left( \cfrac{1}{p(E)} \right)} \]

따라서 사건 $E$의 정보 $I(E)$를 다음과 같이 표기한다,

\[ I(E) = -\log_2{(p(E))} \]

 

예시 1. 동전 던지기

앞면과 뒷면이 나올 확률이 동일한 동전의 정보를 알아보자.

\begin{align*} H(X) &= -\sum_{i=1}^{2}p(x_i)\log_2{p(x_i)} \\ &= -\sum_{i=1}^{2}\cfrac{1}{2}\log_2\cfrac{1}{2} \\ &= -\sum_{i=1}^{2}(0.5) \cdot (-1) = 1 \end{align*}

따라서 동전 던지기에 대한 정보는 1비트만으로 표현할 수 있다.

 

예시2. 데이터 압축

어떤 사건의 확률을 이용하여 해당 정보를 표현하는 비트수를 계산할 수 있다는 것을 알았다.

이제 데이터를 압축할 때 필요한 최소 비트수를 알아보자.

문자열 "aaaabbbcccdefg"를 표현하는데 최소 비트수를 알아보자.

각 알파벳 별로 해당 데이터에서 확률을 구하면 $0.285,\ 0.214,\ 2.14,\ 0.071,\ 0.071,\ 0.071,\ 0.071$이다.

엔트로피를 구하면 $2.556$이므로 평균 한 글자당 2.556비트가 필요하므로 35.79비트가 필요하다.

이를 고정 길이 인코딩을 하면 (a=000, b=001, ..., g=110) 메시지 길이가 14이므로 14*3=42비트가 필요한 것에 비해 효과적이다.

 

응용 Information gain

엔트로피를 이용하여 정보획득(information gain)을 계산할 수 있다.

이는 decision tree에서 feature selection에 사용되는 개념으로 사용된다.

일반적으로 정보획득 $IG$는 다음과 같이 정의된다.

\[ IG(T, a) = H(T) - H(T|a) \]

$a$는 attribute(feature)이고, $T$는 target variable이다.

$H(T|a)$는 아래와 같이 정의된다.

\[ H(T|a) = \sum_{v \in Values(a)} \cfrac{|S_a(v)|}{|T|} \cdot H(S_a(v)) \]