[PRML] 1.6 Information Theory (작성중)

1.6 Information Theory

 

이 장에서는 정보 이론(Information Theory)에 대해서 간략히 소개한다.

 

먼저, 이산 랜덤 변수 $x$를 생각해 보자.

$x$의 구체적인 값을 관찰하는 경우 어느 정도의 정보(information)를 얻을 수 있는지를 정량화하고자 한다.

정보의 양이라는 것은 놀람의 정도(degree of suprise)로 볼 수 있다.

예컨대 아주 일어날 법 하지 않은 일이 일어났을 때 얻을 수 있는 정보의 양은 일어날 법한 일이 일어났을 때 얻을 수 있는 정보의 양보다 많다.

그리고 일어날 것이 확실한 사건이 일어났다는 소식은 우리에게 아무런 정보도 주지 않을 것이다.

 

따라서 $x$를 관찰하는 사건에서 얻을 수 있는 정보의 양은 확률분포 $p(x)$에 의존한다.

따라서 우리가 찾고자 하는, 정보의 양을 나타내는 함수 $h(x)$는 확률 분포 $p(x)$에 대한 단조 함수여야 할 것이다.

 

$h(x)$의 형태에 대해 조금 더 힌트를 얻어보자.

만약 서로 독립인 두 사건 $x$와 $y$가 관찰되었다면, 그 관찰에서 얻을 수 있는 정보의 양은 각각의 정보의 양을 합친 것과 같을 것이다.

즉, $h(x, y) = h(x) + h(y)$이다.

그런데 서로 독립인 두 사건 $x$, $y$가 동시에 관찰될 확률은 $p(x, y) = p(x)p(y)$이므로, 찾고자 하는 $h(x)$가 $p(x)$에 로그를 취한 값과 관계가 깊을 것이라 추론할 수 있다.

 

따라서 $h(x)$를 다음과 같이 정의할 수 있다.

 

$h(x) = -\log_2 p(x)$

 

확률이 0에서 1사이에서 정의되기 때문에, 맨 앞에 붙은 마이너스 표시는 정보량이 0보다 크거나 같도록 한다.

로그의 밑이 되는 숫자의 선택은 임의적이며, 이 장에서는 2를 사용한다.

 

이제, 송신자가 수신자에게 확률변수의 값을 전하고 싶어한다고 가정해 보자.

전해지는 메세지의 평균 정보량은 다음과 같이 정의될 수 있을 것이다.

 

$H[x] = - \sum_{x} p(x) \log_2 p(x)$

 

이를 엔트로피(entropy)라 한다.

 

---

 

예제를 통해 엔트로피를 이해해 보자.

확률 변수 $x$가 가질 수 있는 상태가 8개이며, 각 상태를 가질 확률은 동일하다고 하자.

$x$의 값을 수신자에게 정하기 위해서는 3bit 짜리 메세지를 전송해야 한다.

그런데 이 확률 변수 $x$의 엔트로피를 계산해 보면 다음과 같다.

 

$H[x] = -8 \times \frac{1}{8}\log_2\frac{1}{8} = 3$bits

 

만약 각각의 상태를 가질 확률이 균일하지 않고, $(\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{64}, \frac{1}{64}, \frac{1}{64}, \frac{1}{64})$라고 하면 어떻게 될까?

 

$H[x] = -\frac{1}{2}\log_2 \frac{1}{2} - \frac{1}{4}\log_2{1}{4} - \frac{1}{8} \log_2\frac{1}{8} - \frac{1}{16}\log_2\frac{1}{16} - \frac{4}{16}\log_2\frac{1}{64} = 2$bits

 

위의 결과로부터, 균일하지 않은 확률 분포를 가지는 확률 변수가 균일한 확률 분포를 가지는 확률 변수보다 더 적은 엔트로피를 가지는 것을 확인할 수 있다.

또한, 자주 나타나는 값들에 더 짧은 bit를 할당함으로써 효율적으로 전송할 수 있다.

 

8가지 상태를 가지는 확률 변수 $x$의 현재 상태를 전송하고 싶다고 할 때,  3bit의 숫자를 사용해서 전송할 수도 있지만 다음과 같은 방법을 사용할 수도 있다.

각각의 상태에 대해서 0, 10, 110, 1110, 111100, 111101, 111110, 111111을 할당하게 되면 최대 코드 길이는 더 길어지지만, 평균 코드 길이는 2bit로 더 짧아지게 된다. (이는 확률 변수의 엔트로피 값과도 같다.)

 

엔트로피와 최소 전송 비트 사이의 관계는 이 예제에만 국한되는 성질은 아니다.

Noiseless coding theorem은 엔트로피가 확률 변수의 상태를 전송하기 위해 쓰이는 비트 수의 lower bound가 된다는 내용을 담고 있다.

 

앞으로는 엔트로피를 정의할 때 밑이 2인 로그 대신 자연로그를 사용하기로 하겠다.

 

---

 

앞에서 엔트로피를 확률 변수의 상태를 나타내는 데 필요한 평균 정보량의 측면으로 소개했다.

그러나 실제로 엔트로피의 개념은 평균 열역학에서 처음 소개되고 통계 역학을 통해 무질도의 척도로서 더 깊이 해석되었다.

이러한 관점을 이해해보도록 하자.

 

$N$개의 동일한 개체를 여러 개의 통에 넣는 문제를 생각해 보자.

$i$번째 통에 들어가게 될 개체의 수를 $n_i$라고 하자.

이 때, 개체들을 통에 넣는 서로 다른 경우의 수를 생각해 보자.

 

이는 $N$개의 개체를 배열한 후($N!$), 각 통에 있는 개체끼리 순서를 바꾼 경우를 고려해서 나누어 주는 경우와 같다.

즉, 다음과 같이 주어진다.

 

$W = \frac{N!}{\prod_{i} n_i!}$

 

이를 multiplicity 라고 한다.

여기에 로그를 취하고 상수를 곱해 다음과 같은 식을 얻는다.

 

$H = \frac{1}{N} \ln W = \frac{1}{N} \ln N! - \frac{1}{N} \sum_{i} \ln n_i !$

 

여기에 Stirling's approximation($\ln N! \approx N\ln N - N$)을 적용하고 $N$을 무한대로 보내면 위 식을 다음과 같이 쓸 수 있다.

 

$H = - \lim_{N \rightarrow \infty} \sum_i (\frac{n_i}{N}) \ln (\frac{n_i}{N}) = - \sum_i p_i \ln p_i$

 

여기에서 $p_i = \lim_{N \rightarrow \infty} (\frac{n_i}{N})$으로, 개체가  $i$번째 통에 속할 확률이 된다.

 

---

 

각 통을 이산 확률 변수 $X$의 상태 $x_i$로 생각한다면 $X$에 대한 엔트로피를 다음과 같이 얻을 수 있다.

 

$H[p] = - \sum_{i} p(x_i) \ln p(x_i)$

($p(X = x_i) = p_i$)

 

Figure 1.30

 

그림 1.30을 통해 분포가 밀집되어 있을수록 엔트로피가 낮아지는 것을 확인할 수 있다.

이는 이전에 보았던 예제들과도 상통하는 결과이다.

 

최대 엔트로피는 라그랑주 승수를 이용해서 계산할 수 있다.

 

$\tilde{H} = -sum_{i} p(x_i) \ln p(x_i) + \lambda (\sum_i p(x_i) - 1)$

 

따라서, $p(x_i) = \frac{1}{M}$으로 항상 균일할 때 엔트로피는 최대인 $\ln M$이 된다.

 

---

이제, 연속적인 분포 $p(x)$를 갖는 확률 변수 $x$의 엔트로피를 생각해 보자.

앞서와 같이 $x$를 너비가 $\Delta$인 통들에 나누어 넣는다고 하자.

$p(x)$가 연속이면 중간값 정리에 따라 다음과 같은 식을 만족하는 $x_i$가 존재한다.

 

$\int _{i \Delta}^{(i+1) \Delta} p(x) dx = p(x_i) \Delta$

 

이제, 변수 $x$가  $i$번째 통에 들어간다면, 그 값을 항상 $x_i$로 할당해도 무방하다.

그러면 $x_i$를 관찰하게 될 확률은 $p(x_i) \Delta$와 같다.

이러한 전 작업으로 이제 연속 확률 변수 $x$에 대한 엔트로피를 이산 확률 변수의 엔트로피와 같이 나타낼 수 있다.

 

$H_{\Delta} = -\sum_{i} p(x_i) \Delta \ln (p(x_i) \Delta) = -sum_i p(x_i) \Delta \ln p(x_i) -\ln \Delta $

 

위 식에서 마지막 항인 $-\ln \Delta$는 상수이므로 생략하고, $\Delta$가 0에 무한히 가까워진다고 가정하면 다음 식을 얻는다.

 

$\lim_{\Delta \rightarrow 0} \left \{ \sum_{i} p(x_i) \Delta \ln p(x_i) \right\}$ = - \int p(x) \ln p(x) dx

 

위와 같은 식을 미분 엔트로피(differential entropy)라고 한다.

위 식을 다차원으로 확장하여 다음과 같은 식을 최종으로 얻을 수 있다.

 

$H[\mathbb{x}] = - \int p(\mathbb{x}) \ln p(\mathbb{x}) d\mathbb{x}$

 

 

(추후 추가)

 

1.6.1 Relative entropy and mutual information

이 장에서는 위에서 배웠던 엔트로피의 개념을 패턴 인식과 연결짓는다.

알려지지 않은 확률 분포 $p(\mathbb{x})$에 대해서 이 확률 분포를 최대한 근사한 $q(\mathbb{x})$를 가지고 있다고 하자.

확률 변수 $\mathbb{x}$를 수신자에게 보내기 위해서 $q(\mathbb{x})$를 사용했다고 하자.

 

그러면 $q(\mathbb{x})$를 $p(\mathbb{x})$대신 사용함으로써 추가적으로 필요해진 정보량의 기대값이 다음과 같이 주어진다.

 

$\begin{align} \textit{KL}(p||q) &= - \int p(\mathbb{x}) \ln q(\mathbb{x}) d \mathbb{x} - (- \int p(\mathbb{x}) \ln p(\mathbb{x})  d \mathbb{x} ) \\ &= \int p(\mathbb{x}) \ln \frac{q(\mathbb{x})}{p(\mathbb{x})} d \mathbb{x}\end{align}$

 

이를 relative entropy 혹은 KL(Kullback-Leibler) divergence라고 한다.