TV에 신호가 잡히지 않을때 나오는 지저분한 노이즈와 한 편의 명작 영화는 같은 양의 정보를 지니고 있을까요? 같은 시간동안 재생된다고 해도 노이즈로부터는 특별한 정보를 뽑아내기가 힘들어 보입니다. 이번 포스트에서는 클로드 엘우드 섀넌(Claude Elwood Shannon)으로부터 시작된 정보이론(Information Theory)과 엔트로피(Entropy)의 개념에 대해 간단히 알아보도록 하겠습니다.
- 선수 지식: 고등학교 수준의 ‘확률’에 대한 지식만 있으면 충분히 이해할 수 있습니다.
알파벳 맞추기 게임
정보이론에 대해 공부하기 전에, 간단한 게임을 하나 생각해보도록 하자. 게임의 규칙은 다음과 같다.
- A는 알파벳 a,b,c,d가 각각 적혀 있는 카드 중 하나를 뽑아 본인만 확인한다.
- B는 A에게 YES 또는 NO의 대답이 나올 수 있는 질문만을 할 수 있다.
- B는 최소한의 질문을 통해 A가 뽑은 카드의 알파벳을 맞춰야 한다.
스무고개를 연상케 하는 매우 간단한 게임이다. 여러분이 B라면 어떤 전략을 써서 A의 카드를 맞출 것인가?
복잡하게 생각하기가 귀찮은 사람은 아마 다음과 같은 전략을 짤 것이다.
[전략 1]
- a인지 물어본다. YES면 a이다.
- a가 아니면 b인지 물어본다. YES면 b이다.
- b가 아니면 c인지 물어본다. YES면 c, NO면 d이다.
과연 효과적인 전략일까?
우리는 이제부터 어떤 전략이 효과적인 전략인지 알아보기 위해서 질문 횟수의 기댓값($E[X]$)을 구해볼 것이다. 위에서 제시한 전략을 쓰면 평균적으로 몇회의 질문을 거쳐야 하는지를 알아보자.
| A가 들고 있었던 카드($s_i$) | a | b | c | d |
|---|---|---|---|---|
| 그 카드를 뽑을 확률($p_i = P(s_i)$) | 1⁄4 | 1⁄4 | 1⁄4 | 1⁄4 |
| 이 경우 필요한 질문의 횟수($x_i$) | 1 | 2 | 3 | 3 |
이를 바탕으로 고등학교 때 배웠던 기억을 되살려 기댓값을 구해보도록 하자.
$$E[X] = \sum_{i=1}^{4} p_i x_i = \frac{1}{4} \times 1 + \frac{1}{4} \times 2 + \frac{1}{4} \times 3 + \frac{1}{4} \times 3 = 2.25$$
위 전략을 사용할 경우 우리는 평균적으로 2.25회의 질문을 해야만 답을 얻을 수 있다.
그렇다면 다른 전략을 써보도록 하자. 안정성을 추구하는 사람이라면 분명히 다음과 같은 전략을 생각해 낼 것이다.
[전략 2]
- {a,b} 중에 있는지 물어본다.
- {a,b} 중에 있다면 a인지 물어보고, 그렇지 않다면 c인지 물어본다.
이른바 ‘반씩 쪼개서 물어보기’ 전략 되시겠다. 이 전략의 경우, a,b,c,d중 어떤 카드가 뽑히더라도 2번의 질문으로 그 카드의 정체를 알 수 있다. 즉 질문 횟수의 기댓값은 굳이 계산하지 않아도 2임을 알 수 있다. 계산을 통해 확인해보자.
| A가 들고 있었던 카드($s_i$) | a | b | c | d |
|---|---|---|---|---|
| 그 카드를 뽑을 확률($p_i = P(s_i)$) | 1⁄4 | 1⁄4 | 1⁄4 | 1⁄4 |
| 이 경우 필요한 질문의 횟수($x_i$) | 2 | 2 | 2 | 2 |
$$E[X] = \sum_{i=1}^{4} p_i x_i = \frac{1}{4} \times 2 + \frac{1}{4} \times 2 + \frac{1}{4} \times 2 + \frac{1}{4} \times 2 = 2$$
즉, 이 전략은 첫 번째 전략에 비해 효과적이다. 무려 평균 0.25회의 질문을 아낄 수 있다. 역시 안전빵.
Shannon의 정보이론에 따르면, 모든 카드가 뽑힐 확률이 동일할 경우 위의 두번째 전략과 같이 반씩 쪼개 먹는 전략이 가장 효과적이다. 그래서 일반적으로 $N$개의 카드가 존재할 경우, 이 전략을 사용할 시 질문의 횟수($I$)는 결국 반씩 쪼갠 횟수와 같기 때문에 로그를 이용하여 다음과 같이 표현한다.
$$I = \log_2 N$$
즉 방금 든 예시의 경우 $N=4$이기 때문에 $\log_2 4 = 2$만큼의 질문이 필요한 것이다. 여기서, N은 결국 각 카드가 뽑힐 확률의 역수라고 볼 수 있으므로 다음과 같이 쓰도록 하자.
$$I(s_i) = \log_2 \frac{1}{P(s_i)} = -\log_2 P(s_i) = -\log_2 p_i$$
이 식은 ‘가장 안전한 전략’인 ‘반씩 쪼개기 전략’을 쓴 경우의 질문의 횟수를 계산하는 식이 된다. 갑자기 식에 $s_i$를 명시한 이유는 A가 뽑은 카드에 어떤 알파벳이 써 있었느냐에 따라 질문의 횟수가 달라질 수도 있기 때문이다. 지금은 모든 카드가 뽑힐 확률이 동일하여 그런 일이 발생하지 않으므로, $I$가 아니라 왜 $I(s_i)$인지 이해가 안 가시는 분은 일단 $s_i$는 무시하고 다음으로 넘어가도록 하자.
확률이 같지 않은 경우
다시 알파벳 맞추기 게임으로 돌아가보자. 이번에는 각 카드가 뽑힐 확률이 다음과 같다고 가정하자.
| A가 들고 있었던 카드($s_i$) | a | b | c | d |
|---|---|---|---|---|
| 그 카드를 뽑을 확률($p_i = P(s_i)$) | 1⁄2 | 1⁄6 | 1⁄6 | 1⁄6 |
방금 전에 했던 게임과는 다르게 각 알파벳이 뽑힐 확률이 같지 않다. a가 뽑힐 확률이 다른 알파벳에 비해 무려 3배나 높다. 이 경우에도 앞에서 했던 것 처럼 ‘반씩 쪼개기 전략’을 이용할 것인가? 왠지 그러면 안 될 것 같다. a가 뽑힐 확률이 더 높다는 이 귀한 정보를 어떻게든 활용해서 이득을 보고 싶다. a가 나올 확률이 높으니, 다음과 같이 a를 먼저 물어보고, 맞으면 좋고 틀리면 나머지 b,c,d 중에서 해결을 보는 전략을 택해보자.
[전략 3]
- a인지 물어본다. YES면 a이다.
- a가 아니면 {b,c}중에 있는지 물어본다.
- {b,c}중에 있다면 b인지 물어보고, 그렇지 않다면 정답은 d이다.
복잡해 보이지만, 쪼개는 방식을 달리 했을 뿐이다. a의 확률이 가장 높으니 {a}와 {b,c,d}로 쪼갠 다음에 {b,c,d}는 홀수개 이므로 2개와 1개로 쪼갠 것이다. 이 경우 질문 횟수의 기댓값을 계산해보도록 하자.
| A가 들고 있었던 카드($s_i$) | a | b | c | d |
|---|---|---|---|---|
| 그 카드를 뽑을 확률($p_i = P(s_i)$) | 1⁄2 | 1⁄6 | 1⁄6 | 1⁄6 |
| 이 경우 필요한 질문의 횟수($x_i$) | 1 | 3 | 3 | 2 |
$$E[X] = \sum_{i=1}^{4} p_i x_i = \frac{1}{2} \times 1 + \frac{1}{6} \times 3 + \frac{1}{6} \times 3 + \frac{1}{6} \times 2 = 1.8333…$$
네 카드가 뽑힐 확률이 전부 동일했던 상황과는 달리, 평균 2회보다 적은 질문으로 게임을 완료할 수 있게 되었다. 역시 귀한 정보를 통해 이득을 본 보람이 있는 것 같다.
네 카드가 뽑힐 확률이 같지 않을 경우의 가장 효율적인 이 전략을 정리하자면, ‘반씩 쪼개기’이긴 하지만 정확히 말하면 ‘확률을 반씩 쪼개기’ 전략이다. [전략 2]에서와 같이 a,b,c,d의 확률이 전부 동일한 경우에 {a,b}와 {c,d}로 쪼갰었던 이유는 {a,b} 중에 정답이 있을 확률과 {c,d} 중에 정답이 있을 확률이 같기 때문이다. 만약 이 상황에서 {a}, {b,c,d}로 쪼갰었다면 이 전략은 도박성이 증가한다. 만약 정답이 a일 경우엔 이득이지만 b,c,d중에 있었을 경우에는 손해를 보게 된다. 그리고 실험을 통해 확인해봤듯이, 안전한 전략을 택하는 쪽이 질문 횟수의 기댓값이 작다.
그렇다면 왜 [전략 3]과 같이 a,b,c,d의 확률이 다른 경우에는 반반 쪼개지 않고 {a}, {b,c,d}로 쪼갰을까? 이 경우도 역시 {a} 중에 정답이 있을 확률과 {b,c,d} 중에 정답이 있을 확률이 같기 때문이다. {a,b}, {c,d}로 쪼갠 경우에 비해 안전하다.
이제 위에서 봤던 식으로 되돌아가보자.
$$I(s_i) = \log_2 \frac{1}{P(s_i)} = -\log_2 P(s_i) = -\log_2 p_i$$
이제 알파벳에 따라 질문의 횟수가 다를 수 있음을 이해할 수 있다. 각 알파벳이 나올 확률이 같지 않은 경우에는 그렇다. 위에서 들었던 예시만 봐도 정답이 a였다면 1번의 질문으로 게임을 끝낼 수 있지만 b,c,d였다면 그렇지 않다. 이 식을 이용하면 정말 질문 횟수가 나오는지 확인해보도록 하자. 먼저 정답이 a였을 경우에는 다음과 같다.
$$I(a) = -\log_2 \frac{1}{2} = 1$$
실제로 위 전략에 따르면 정답이 a일 경우 1번의 질문만 하면 정답을 알아낼 수 있게 된다. 그렇다면 b,c,d인 경우는 어떻게 되는지 계산해보자.
$$I(b) = I( c ) = I(d) = -\log_2 \frac{1}{6} = 2.5850…$$
몇몇 분은 아마 이미 직감했겠지만 질문의 횟수와 일치하지 않는 값이 나왔다. 심지어 ‘횟수’라고 하기도 애매하게 자연수도 아닌 값이 나왔다. 그 이유는 바로 b,c,d를 정확히 반으로 쪼갤 수 있는 방법이 존재하지 않기 때문이다. 로그를 이용한 계산은 모든 경우에 대해서 확률이 정확히 반으로 쪼개지도록 할 수 있다는 가정 하에 진행된다. 그래서 사실 위에서 제시한 전략은 이론적으로는 ‘가장’ 효율적인 전략이라고는 볼 수 없다. 하지만 위와 같은 경우 이론적인 최적점에 도달하는 것은 불가능한 상황이기 때문에, 가능한 전략중에서는 그나마 최선이다.
그러면, 어차피 도달하는 것은 불가능하지만, 로그를 이용해 기댓값을 계산하면 이론적으로 가장 적은 질문 횟수의 기댓값을 구할 수 있지 않을까? 다음과 같이 구하면 될 것이다.
| A가 들고 있었던 카드($s_i$) | a | b | c | d |
|---|---|---|---|---|
| 그 카드를 뽑을 확률($p_i = P(s_i)$) | 1⁄2 | 1⁄6 | 1⁄6 | 1⁄6 |
| 이론적인 질문 횟수의 최솟값($x_i = I(s_i)$) | 1 | $\log_2 6$ | $\log_2 6$ | $\log_2 6$ |
$$E[X] = \sum_{i=1}^{4} p_i x_i = \frac{1}{2} \times 1 + \frac{1}{6} \times \log_2 6 + \frac{1}{6} \times \log_2 6 + \frac{1}{6} \times \log_2 6 = 1.7925…$$
계속 말하지만, 이 값은 카드의 개수에 따라서 도달할 수도, 도달하지 못할 수도 있는 값이다. 지금같은 경우는 도달하지 못하는 값이고, 맨 처음 봤던 a,b,c,d의 확률이 모두 동일한 경우는 도달 가능한 값이다. 하지만 이 값은 우리에게 의미가 있다. 무슨 수를 쓰건간에, 이렇게 구한 값보다 질문 횟수의 기댓값이 적은 전략은 존재하지 않는다. 이 값을 우리는 엔트로피(Entropy)라고 부르고, 식으로는 다음과 같이 계산한다.
$$H = \sum_i p_i I(s_i) = -\sum_i p_i \log_2 (p_i)$$
엔트로피와 불확실성
자, 우리는 각 카드의 확률 분포가 어떻게 되는지에 따라서 최소의 질문 횟수가 존재한다는 사실을 알게 되었으며, 구할 수도 있다. 그리고 엔트로피가 그 최소의 질문 횟수를 의미한다는 사실도 알았다. 하지만 한 가지 궁금증이 분명히 남아 있다.
“왜 a,b,c,d의 확률이 동일할 때보다 a의 확률이 더 높은 경우에 엔트로피가 더 작은 것인가?”
이 질문을 해결하기 위해서는 먼저, 엔트로피가 갖는 의미에 대해서 더 생각해볼 필요가 있다. 물리학에서는 엔트로피를 ‘무질서도’라고 한다. 정보이론에서 엔트로피가 갖는 의미를 한 마디로 표현하자면, ‘불확실성’이라고 볼 수 있다. 왜 엔트로피가 불확실성일까? 엔트로피가 크다는 것은 A가 들고 있는 카드에 적힌 알파벳을 맞추기 위해 더 많은 질문을 필요로 한다는 것이고, 결국 A가 들고 있는 카드의 알파벳을 알아내기가 더 힘들다는 뜻이다. 즉 불확실하다는 뜻이다.
자, 그러면 왜 a,b,c,d의 확률이 전부 동일한 경우가 특정 알파벳의 확률이 높은 경우보다 불확실성이 크다는 것일까? 극단적인 예를 들어보면 쉽다. a,b,c,d의 확률이 다음과 같다고 가정하자.
| A가 들고 있었던 카드($s_i$) | a | b | c | d |
|---|---|---|---|---|
| 그 카드를 뽑을 확률($p_i = P(s_i)$) | 0.97 | 0.01 | 0.01 | 0.01 |
A가 들고 있는 카드가 무엇인지 대충 감이 오지 않는가? 우리는 사실 질문을 하지 않고 그냥 a라고 찍기만 해도 100번 중 97번꼴로 정답을 맞출 수 있다. A가 들고 있는 카드가 a라는 사실은 ‘거의 확실’하다. 하지만 a,b,c,d의 확률이 전부 동일한 경우에는 우리는 그 카드에 어떤 알파벳이 적혀 있는지 조금의 확신도 할 수 없다. 그렇기 때문에 특정 알파벳의 확률이 커지는 순간, 우리는 그 정보를 활용하여 게임을 유리하게 이끌어나갈 수 있으며, 이는 게임의 불확실성, 즉 엔트로피를 감소시킨다. 그러면 얼마나 감소하였는지 알아보도록 하자.
$$H = -\sum_i p_i \log_2 (p_i) = 0.97 \log_2 0.97 + 3 \times 0.01 \log_2 0.01 = 0.2419 $$
예상했던 대로 엔트로피 값이 매우 작다.
정보량과 부호화(Coding)
엔트로피에 관한 논의는 여기서 마무리하고, 마지막으로 엔트로피를 구성하는 $I(s_i)$라는 녀석에게 조금 더 집중해보도록 하자. $I(s_i)$는 정답이 $s_i$인 경우 ‘반씩 쪼개기 전략’을 썼을 때 필요한 이상적인 최소 질문 횟수이다. 하지만 이 의미는 우리가 가정한 알파벳 맞추기 게임에서만 통용될 수 있고, 일반적인 정보 이론에서는 $I$를 정보량이라고 한다. 왜 정보량이라고 할까? $I$가 클수록 정보를 많이 담고 있는 것일까? 그렇다. 이를 이해하기 위해 알파벳 맞추기 게임으로 돌아가보자.
카드에 적혀 있는 알파벳은 사실 그냥 보기에는 다 똑같아 보이지만, 어떤 전략을 쓰느냐에 따라 다른 의미를 갖는다. 스무고개의 예를 들어보자. ‘한국’이 정답이고 다음 질문들을 통해 한국이 정답임을 알아냈다고 가정하자.
- {한국, 중국, 일본} 중의 하나인가? YES
- 인구가 5억명 미만인가? YES
- 섬으로 구성된 나라인가? NO
이렇게 YES, YES, NO의 패턴이 나오는 나라는 한국밖에 없으므로 우리는 답을 구할 수 있다. 우리는 한국이라는 단어를 다양한 말로 표현할 수 있다. ‘자본주의 국가이다’, ‘한국어를 사용하는 국가이다’, ‘UN 회원국이다’ 등등으로 표현할 수 있지만 이 스무고개 게임에서만큼은 한국은 ‘한국, 중국, 일본중에 하나이며 인구가 5억명 미만이고, 섬나라가 아닌 나라’, 더 짧게 쓰면, ‘위 세 질문에 대해 YES, YES, NO가 나오는 나라’로 정의할 수 있다. 즉, 각 질문에 대한 YES, NO의 패턴으로 한 대상을 정의할 수가 있게 되는 것이다.
이제 [전략 3]을 보도록 하자. 위의 스무고개에서 한국을 정의한 것 처럼 [전략 3]의 질문들에 대한 대답으로 a,b,c,d를 정의하면 다음과 같다.
- a: YES
- b: NO,YES,YES
- c: NO,YES,NO
- d: NO,NO
각 알파벳을 알아내기 위해 필요한 질문의 개수가 달랐기 때문에, 정의의 길이가 다른 것도 당연하다. 여기서 정의의 길이가 바로 정보량이 된다. b,c를 표현하기 위해서는 YES 또는 NO가 3개씩 필요하지만 a를 표현하기 위해서는 YES 또는 NO가 1개만 있으면 된다. 즉, 질문의 개수가 많으면 그 대상이 지니는 정보량은 많다.
확률적인 관점에서 보더라도 마찬가지이다. $I(s_i) = -\log_2 p_i$ 이 식을 보면 확률이 작을수록 정보량이 크다는 사실을 알 수 있다. 사실 직관적으로 생각해봐도 매번 나오는 값들 보다는 어쩌다 한 번 나오는 값이 더 가치 있으며, 우리에게 더 큰 정보를 줄 수 있다. 무심하던 친구가 평소답지 않게 격식을 차리고 나에게 잘해준다면 뭔가 바라는 바가 있다는 메세지를 담고 있는 것과 비슷(?)하다.
위에서 a,b,c,d를 YES와 NO의 집합으로 나타내는 모습을 보면서 뭔가 눈치 채신 분들이 계실 것이다. 사실 이 과정이 ‘부호화(Coding)’의 방식이다. 컴퓨터는 정보를 전송하기 위해서 숫자든 알파벳이든 그림이든 모든 신호를 0과 1의 조합으로 만들 필요가 있는데, a,b,c,d를 YES는 1로, NO는 0으로 바꿔서 부호화 하면 다음과 같이 된다.
- a: 1
- b: 011
- c: 010
- d: 00
위에서 살펴본 바에 의하면, 특정 알파벳의 등장 확률이 작을수록 질문 횟수가 많이 필요하고, 이로 인해 정보량이 많아져서 부호화 결과 비트 수가 많아진다. 이 방식을 이용하여 부호화를 했을 경우, 자연스럽게 많이 등장하는 신호에는 적은 비트가 할당되고, 적게 등장하는 비트에는 많은 비트가 할당되어 전체 부호의 길이가 줄어들게 된다. 그렇기 때문에 매우 효율적인 코딩이 가능하다. 이 원리를 이용한 부호화에는 허프만 부호화(huffman coding)가 있다. 참고로, [전략 3]에서 직면했던 ‘알파벳들의 집합이 완벽하게 똑같이 쪼개지지 않음으로 인해 발생한 문제’를 해결하기 위해 실수 도메인으로 부호화를 하는 방식이 있는데, 이 방식을 산술 부호화(arithmetic coding)라고 하며, 이 방식을 통해 이상적으로 구한 Entropy에 더 가깝게 부호화 하는 것이 가능하다.