정보이론은 통신이론의 맥락에서 탄생하였다. 어떻게 하면 데이터를 생성하는 소스로부터 이를 받아들이는 싱크로 데이터를 잘 전달할 수 있는지에 대한 고민으로부터 출발한 것이다. 데이터를 전달하는 것에 관심이 있다 보니 그렇게 전달하고자 하는 메시지에 얼마나 많은 "정보"가 포함되어 있는지도 하나의 관심사이다.
본격적인 내용에 들어가기 전에 주의해야 할 점이 있다. 위에 썼다시피 정보이론은 통신의 맥락에서 탄생하였으며 그 맥락에서 이해하는 것이 가장 좋다. 항상 기술적 문서에서 사용하는 용어는 기술적인 맥락에서 이해해야 하는데 특히 정보라는 단어는 일상생활에서 다양한 의미로 사용하지만 여기에서는 지정된 의미가 있음을 인지해야 한다. 정보이론에서 다루는 정보의 의미, 엔트로피의 의미를 이해한 후에 일상어에서 사용하는 용어와의 관계를 고민하여도 늦지 않다.
어떤 사건 $i$가 $p_{i}$의 확률로 일어난다고 할 때, 이를 관측하는 것은 얼마만큼의 정보를 가져다주는지에 대해 고민해보자.
특정 사건의 정보량을 표현하는 함수 $I(p)$가 있다면 이 함수는 $p$가 커지면 작은 값을, 반대로 $p$가 작아지면 큰 값을 내는 것이 합당한 것으로 보인다. 즉, 자주 일어나는 일을 관측하는 것은 적은 양의 놀라움만 가져다주며 반대로 가끔 일어나는 일을 관측하는 것은 많은 양의 놀라움을 가져다준다. 같은 논리로 늘 일어나는 사건은 전혀 놀라움을 주지 않으므로 $I(1) = 0$이고 $I(0)$은 정의되지 않는다고 하자. 위의 내용으로부터 정보량은 음수가 아니라는 가정도 합당해 보인다. 마지막으로 독립인 두 사건의 놀라움은 각각의 놀라움을 더한다고 가정하자. 이는 통신의 관점에서 보면 $n$개의 선을 사용해서 데이터를 전송하면 한 개의 선을 사용하는 것보다 $n$ 배의 정보를 전달할 수 있어야 한다는 믿음에 부합한다.
위의 조건들을 만족하는 정보량을 표현하는 함수는 로그의 꼴을 띤다는 사실을 Shannon이 발견하였다.
$$I(p) = \log (\frac{1}{p})$$
보통 로그의 밑은 2를 사용한다.
단일 사건의 정보량에 대해 다뤘으니 이제 데이터를 생성하는 분포에 대해 논해보자. 데이터를 생성하는 어떤 소스가 있을 때, 그 소스가 발생시키는 데이터의 불확실성을 측정하는 척도를 만들고자 한다. 가장 먼저 떠오르는 것은 역시 정보량의 기대값을 사용하는 것이다.
$$H(X) = \sum_{i} p_i \log \frac{1}{p_i} = - \sum_{i} p_i \log p_i$$
이를 엔트로피라 하며 특정 사건이 일어날 때마다 우리가 얻는 평균적인 정보량, 놀라움을 나타낸다. 이는 열역학에서 사용하는 엔트로피와 식의 꼴이 같이 때문에 붙은 이름이며 처음 정보이론의 엔트로피를 접할 때는 둘의 관계를 떠올리지 않는 편이 이해에 더 도움이 된다.
참고로 $H(X)$가 다음의 조건을 만족해야 한다고 가정하면 위의 꼴은 유일하게 결정됨이 알려져 있다.
엔트로피 계산의 예를 살펴보자. 가장 단순한 경우는 두 가지 심볼이 소스로부터 독립적으로 생성되는 경우이다. $X = h$가 $p(h)$의 확률로 발생하고 $X = t$가 $p(t) = 1 - p(h)$의 확률로 발생하는 동전을 생각해보자.
공평한 동전이라면 아래와 같이 계산된다.
\begin{align} H(X) &= p(h) \log \frac{1}{p(h)} + p(t) \log \frac{1}{p(t)} \\ &= 0.5 \log 2 + 0.5 \log 2 \\ &= 1 \end{align}
즉, 이 경우 한 번의 관측을 할 때마다 우리는 평균적으로 1bit의 정보를 얻는다. 만약 우리가 동전을 여러 차례 던진 결과를 이진수로 표현한다면 앞면을 1, 뒷면을 0으로 표현하는 방식을 생각할 수 있다. 이 경우 엔트로피와 하나의 실험 결과를 표현하는 데 필요한 bit 수는 일치한다.
다른 예로 약간 불공평한 동전을 던지는 경우를 생각해보자. 앞면의 확률이 $\frac{1}{4}$이라면 엔트로피는 아래와 같다.
\begin{align} H(X) &= p(h) \log \frac{1}{p(h)} + p(t) \log \frac{1}{p(t)} \\ &= 0.25 \log 4 + 0.75 \log \frac{4}{3} \\ &= 0.5 + 0.75 \times (2 - \log 3) \\ &\approx 0.811 \end{align}
즉, 이 경우 우리는 한 번 동전을 던지면 약 0.811 bit의 정보를 얻는다. 동전의 뒷면이 더 잘 나온다는 사실을 알고 있으므로 평균적으로 실험을 통해 얻는 놀라움이 완전히 균등한 분포로부터 얻는 정보보다 적다. 바로 위의 공평한 동전의 예제에서 엔트로피와 bit 수의 관계를 생각해보았는데, 이 경우에는 왠지 한 개보다 적은 bit을 사용해서 데이터를 표현할 수 있을 것 같은 느낌이 든다.
동전을 1,000 번 던진 결과를 인코딩한다고 할 때, 처음의 경우에는 총 1,000 bit이 필요하지만 두 번째의 경우 약 811 bit만 필요하게 된다. 이는 가능한possible 모든 경우의 수는 $2^{1000}$ 개이지만 나올 확률이 충분한probable 경우는 약 $2^{811}$ 개이기 때문이다. 이를 엄밀하게 다루면 Shannon의 source coding theorem에 도달한다. Source coding theorem은 우리는 코드의 평균 길이를 엔트로피보다 작게 만들 수 없지만 우리가 원하는만큼 엔트로피에 가깝게 만들 수 있다는 내용을 담고 있다.
엔트로피가 특정 소스가 생성하는 데이터를 인코딩할 때 사용하는 코드 길이의 하한이 된다는 내용을 바탕으로 다시 엔트로피의 의미를 생각해보면, 엔트로피는 특정 분포에서 여러 차례 샘플링을 할 때 얻는 평균적인 정보량을 나타낸다. 이는 불확실성 혹은 놀라움의 정도로 해석할 수도 있으며, 만약 해당 정보를 인코딩한다고 하면 변환된 하나의 심볼이 평균적으로 차지하는 bit 수를 나타낸다.
데이터를 생성하는 소스가 정확히 어떤 확률로 데이터를 생성하는지 잘 모른다고 가정해보자. 그때 인코딩을 하면 어떤 일이 생길까?
엔트로피는 $p_i$들에 대한 함수이다. 이는 평균적인 정보량을 나타내는 함수이며 소스가 생성하는 데이터를 인코딩하기 위해 평균적으로 필요한 bit 수를 나타낸다. 만약 실제로 데이터가 분포 $p$로부터 생성되는데 우리가 $p$에 대해 잘 몰라서 대신 분포 $q$의 정보를 활용하면 어떻게 될까? 이를 수식으로 나타내면 다음과 같다.
$$H(p, q) = - \sum_{x} p(x) \log q(x)$$
위의 식은 분포 $q$를 사용해서 인코딩하였지만 실제로 데이터는 $p$의 분포로부터 샘플링되는 경우 사용하는 평균적인 bit 수를 나타낸다. 이를 cross entropy라 한다.
물론 이렇게 만들어진 코드는 엔트로피가 이야기하는 것보다 평균적으로 더 긴 코드 길이를 갖게 될 것이다. 즉, $H(p) \le H(p, q)$ 일 것이다.
기계 학습에서 multinomial logistic regression이나 뉴럴넷을 사용한 분류 등 여러 문제가 최종적으로 cross entropy를 최소화하는 문제를 푸는 것으로 치환되곤 하는데, 이는 결과적으로 데이터가 보여주는 분포와 모델이 학습한 분포의 각각의 확률이 같아지도록 하는 최적화는 하는 셈이다.
Entropy와 cross entropy를 활용하면 두 분포 사이의 거리에 대해 이야기할 수도 있다. Cross entropy는 entropy보다 항상 크고 $p = q$인 때에만 같으므로 cross entropy로부터 entropy를 뺀 값을 두 분포 사이의 거리처럼 사용할 수 있다. 이를 Kullback-Leibler divergence, KL divergence, 혹은 relative entropy라 한다.
\begin{align} D_{KL}(p || q) &= H(p, q) - H(p) \\ &= \sum_{x} p(x) \log \frac{1}{q(x)} - p(x) \log \frac{1}{p(x)} \\ &= \sum_{x} p(x) \log \frac{p(x)}{q(x)} \end{align}
잘 살펴보면 사실 KL divergence는 거리함수가 아니다. $D_{KL}(p || q) \neq D_{KL}(q || p)$이기 때문이다. 하지만 어찌 되었든 두 분포가 다르면 다를수록 큰 값을 가지며 둘이 일치할 때에만 0을 갖기 때문에 거리와 비슷한 용도로 사용할 수 있다. 위의 cross entropy minimization 문제를 생각해보면 이는 결국 KL divergence를 최소화하는 문제와 동치임도 쉽게 알 수 있다.
데이터 인코딩의 관점에서 보면 KL divergence는 데이터 소스의 분포인 $p$ 대신 다른 분포 $q$를 사용해서 인코딩하면 추가로 몇 bit의 낭비가 생기는지 나타낸다고 이해할 수 있다.
특정 사실을 알게 되었을 때 다른 변수의 확률을 나타낼 때 조건부확률을 사용하는데, 이를 적용해서 엔트로피를 계산해보면 어떻게 될까? $X$와 $Y$가 독립이 아니라면 $X = x$라는 사실을 알게 되면 $p(Y | X = x) \neq p(Y)$이고 이를 활용해서 데이터를 인코딩한 결과의 bit 수도 줄일 수 있을 것이다. 이를 수식으로 쓰면 다음과 같다.
$$H(Y|X=x) = - \sum_{y} p(y | x) \log p(y | x)$$
이를 모든 $X$에 평균을 내면 conditional entropy라 한다.
\begin{align} H(Y|X) &= \sum_{x} p(x) H(Y|X=x) \\ &= - \sum_{x} p(x) (\sum_{y} p(y|x) \log p(y|x)) \\ &= - \sum_{x} \sum_{y} (p(x)p(y|x) \log p(y | x)) \\ &= - \sum_{x, y} p(x, y) \log p(y | x) \\ &= - \sum_{x, y} p(x, y) \log \frac{p(x, y)}{p(x)} \\ &= - \sum_{x, y} p(x, y) (\log p(x, y) - \log p(x)) \\ &= - \sum_{x, y} p(x, y) \log p(x, y) + \sum_{x, y} p(x, y) \log p(x) \\ &= H(X, Y) + \sum_{x} \sum_{y} p(x, y) \log p(x) \\ &= H(X, Y) + \sum_{x} \log p(x) \sum_{y} p(x, y)\\ &= H(X, Y) + \sum_{x} p(x) \log p(x) \\ &= H(X, Y) - H(X) \end{align}
마지막으로 얻어낸 식을 살펴보면 conditional entropy는 joint entropy와 marginal entropy의 차임을 알 수 있다.
$$H(X, Y) = H(X) + H(Y|X)$$
이는 조건부확률의 product rule과 같은 맥락에서 생각할 수 있다. $X$라는 정보를 인코딩하는 데 필요한 최소 bit과 이 정보가 주어졌을 때 $Y$라는 정보를 인코딩하는 데 필요한 최소 bit의 합은 $X, Y$의 정보를 한 번에 인코딩하는 데 필요한 최소 bit과 같다.
위의 conditional entropy를 활용하면 두 변수의 독립성/연관성에 대한 고민을 더 해볼 수 있다. 가령 변수 $X$와 변수 $Y$는 서로 얼마나 관련이 있을까? $H(X|Y)$는 $Y$라는 추가 정보가 주어졌을 때 $X$를 표현하기 위한 최소 bit 수를 의미한다. 만약 $Y$가 $X$에 대한 충분한 정보를 제공한다면 $H(X|Y)$는 매우 작을 것이다. 그리고 애초에 $H(X)$는 추가적인 정보 없이 $X$를 표현하기 위한 최소 bit 수를 의미하는데 만약 이 값이 크다면 많은 정보를 담고 있음을 의미한다. 즉, $H(X) - H(X|Y)$는 $X$와 $Y$가 공유하고 있는 정보가 얼마나 큰지를 나타내는 것으로 생각할 수 있다. 만약 $X$와 $Y$가 독립이라면 $H(X|Y) = H(X)$일 것이고 위의 값은 0이 될 것이다. 반대로 둘이 공유하는 정보가 많으면 이 값은 커질 것이며 극단적으로 $Y = X$라면 이는 엔트로피와 같아질 것이다. 이를 mutual information이라 한다.
$$I(X; Y) = H(Y) - H(Y|X) = H(X) - H(X|Y)$$
위의 식을 조작해보면 어떤 의미를 갖는지 더 살펴볼 수 있다.
\begin{align} I(X; Y) &= H(Y) - H(Y|X) \\ &= - H(Y|X) + H(Y) \\ &= - \sum_{x} p(x) H(Y|X=x) - \sum_{y} p(y) \log p(y) \\ &= \sum_{x} p(x) (\sum_{y} p(y|x) \log p(y|x)) - \sum_{y} \log p(y) (\sum_{x} p(x, y)) \\ &= \sum_{x, y} p(x) p(y | x) \log p(y|x) - \sum_{x, y} p(x, y)\log p(y) \\ &= \sum_{x, y} p(x, y) \log \frac{p(x, y)}{p(x)} - \sum_{x, y} p(x, y) \log p(y) \\ &= \sum_{x, y} p(x, y) \log \frac{p(x, y)}{p(x)p(y)} \\ &= D_{KL}(p(x, y) || p(x)p(y)) \\ \end{align}
즉, mutual information은 joint probability $p(x, y)$와 두 marginal의 곱 $p(x)p(y)$ 사이의 KL divergence를 측정하는 것이기도 하다. 두 변수 $X$와 $Y$가 독립이라면 $p(x, y) = p(x)p(y)$이므로 두 분포 사이의 거리가 0이면 독립일 것이고 mutual information이 없다고 볼 수 있을 것이다. 반면 두 분포 사이의 거리가 멀다는 것은 결과적으로 두 변수 $X$와 $Y$ 사이에 공유하는 정보가 많아서 독립의 조건으로부터 멀다고 해석할 수 있겠다.
1948년 Claude Shannon은 정보이론의 기반을 다진 A mathematical theory of communication을 발표하였다. 그 부록 2에 엔트로피의 식이 유일함에 대한 증명이 실려있다.
위에서는 기계학습의 맥락에서 필요한 정보이론의 개념만 간단하게 소개하였으나 정보이론 자체도 매우 흥미로운 분야이다. 정보이론의 자세한 내용을 알고 싶다면 Cover와 Thomas의 Elements of information theory를 참고하기 바란다. 그보다 가볍고 친절한 설명을 찾는다면 John Pierce의 An introduction to information theory를 추천한다. 위의 예제는 많은 부분, 이 책에서 발췌한 것이다. 정보이론과 기계학습 사이의 관계를 살펴보며 다루는 책으로는 David Mackay의 Information theory, inference, and learning algorithms를 추천한다.
엔트로피가 평균 코드 길이의 하한이라는 증명은 mathematicalmonk의 Entropy as a lower bound on expected length를 참고하기 바란다.