1강에서 압축은 자주 나오는 메시지에 짧은 이름을 붙이는 일이라고 했다. 이제 “자주"와 “짧게” 사이의 관계를 수로 나타낼 차례다. 맥케이는 확률이 작은 사건일수록 더 많은 정보를 준다는 직관에서 출발해 정보량을 정의하고, 그 평균인 엔트로피를 압축의 기준으로 세운다.
교재: 2장 Probability, Entropy, and Inference, 4장 The Source Coding Theorem.
정보는 놀라움이다
해가 동쪽에서 떴다는 소식은 거의 정보를 주지 않는다. 내일 해가 서쪽에서 뜬다는 소식은 사실이라면 엄청난 정보를 준다. 예상하기 어려운 사건일수록 관측했을 때 더 놀랍고, 가능한 세계를 더 크게 좁힌다.
확률 $P(x)$인 사건 $x$의 섀넌 정보량은 다음과 같다.
$$ h(x) = \log_2 \frac{1}{P(x)} = -\log_2 P(x) $$밑이 2인 로그를 쓰므로 단위는 비트다.
| 사건의 확률 | 정보량 |
|---|---|
| $1$ | $0$비트 |
| $1/2$ | $1$비트 |
| $1/4$ | $2$비트 |
| $1/8$ | $3$비트 |
반드시 일어날 사건은 새로 알려주는 것이 없으므로 0비트다. 똑같이 가능한 두 선택지 가운데 하나를 알아내면 1비트, 여덟 선택지 가운데 하나를 알아내면 3비트다.
왜 로그일까. 서로 독립인 두 사건 $x$와 $y$가 함께 일어날 확률은 곱이다.
$$ P(x,y)=P(x)P(y) $$하지만 두 사건에서 얻은 정보는 더해지기를 바란다. 로그가 곱을 합으로 바꿔 준다.
$$ h(x,y) = -\log_2 P(x)P(y) = h(x)+h(y) $$독립인 동전 던지기 한 번이 1비트라면 두 번의 결과는 2비트다. 우리가 세려는 양에 정확히 맞는 성질이다.
엔트로피는 평균 정보량이다
확률변수 $X$가 여러 값 $x$를 확률 $P(x)$로 낸다고 하자. 어떤 결과가 나올지는 아직 모르므로 결과 하나의 정보량 대신 평균을 계산한다.
$$ H(X) = \sum_x P(x)\log_2\frac{1}{P(x)} = -\sum_x P(x)\log_2 P(x) $$이것이 엔트로피다. 한 번 관측할 때 평균적으로 얼마나 놀랄지, 또는 결과를 알려면 평균적으로 몇 비트가 필요한지를 잰다.
앞면 확률이 $p$인 동전의 엔트로피는 이진 엔트로피 함수다.
$$ H_2(p) = -p\log_2 p -(1-p)\log_2(1-p) $$- $p=1/2$이면 $H_2(p)=1$비트다. 앞뒤가 똑같이 가능해 불확실성이 가장 크다.
- $p=0$이나 $p=1$이면 엔트로피는 0이다. 결과를 던지기 전부터 안다.
- $p=0.1$이면 약 $0.469$비트다. 결과 하나는 여전히 앞이나 뒤지만, 평균 불확실성은 1비트보다 작다.
여기서 “동전 한 번의 결과를 0.469비트에 어떻게 넣는가"라는 의문이 생긴다. 비트 수는 정수인데 엔트로피는 소수다. 답은 한 결과를 따로 부호화하지 않고 긴 묶음을 함께 부호화하는 데 있다.
부호는 가능성에 붙이는 이름이다
네 기호 $a,b,c,d$가 다음 확률로 나온다고 하자.
$$ P(a)=\frac12,\quad P(b)=\frac14,\quad P(c)=\frac18,\quad P(d)=\frac18 $$모두를 고정 길이로 표현하면 기호마다 2비트가 필요하다.
a = 00, b = 01, c = 10, d = 11
하지만 확률에 맞춰 가변 길이 부호를 줄 수 있다.
a = 0, b = 10, c = 110, d = 111
평균 길이는
$$ \bar L = \frac12(1)+\frac14(2)+\frac18(3)+\frac18(3)=1.75\text{비트} $$이고, 이 분포의 엔트로피도 정확히 1.75비트다. 각 부호 길이가 $-\log_2 P(x)$와 정확히 맞아떨어졌기 때문이다.
아무 짧은 부호나 쓸 수는 없다
가변 길이 부호는 이어 붙인 문자열을 다시 하나씩 풀어낼 수 있어야 한다. 위 부호에서 010111은 앞에서부터 0 | 10 | 111, 곧 $abd$로 유일하게 읽힌다. 어느 부호어도 다른 부호어의 시작 부분이 아니기 때문이다. 이런 부호를 접두 부호라고 한다.
반대로 $a=0$, $b=01$로 정하면 01이 $b$인지 $a$ 다음에 무엇이 더 오는 중인지 즉시 알 수 없다. 경계 표시를 따로 보내야 하고, 짧게 만든 이득이 사라진다.
이진 접두 부호의 길이 $l_i$들은 크라프트 부등식을 만족해야 한다.
$$ \sum_i 2^{-l_i} \le 1 $$이 식은 이진 나무의 공간을 생각하면 자연스럽다. 길이 1인 부호어는 전체 잎의 절반을 차지하고, 길이 2인 부호어는 4분의 1을 차지한다. 서로의 시작 부분이 되지 않게 배치하려면 차지한 몫의 합이 1을 넘을 수 없다.
이상적인 길이 $l_i=-\log_2 p_i$를 넣으면 각 항이 $p_i$가 되어 합이 1이다. 확률분포와 접두 부호의 나무가 같은 수학 구조를 공유한다는 뜻이다.
확률이 2의 거듭제곱이 아니면
$p=1/3$이라면 이상적인 길이는 $-\log_2(1/3)\simeq1.585$비트다. 한 기호에 1.585개의 비트를 붙일 수는 없다. 기호를 하나씩 부호화한다면 길이를 올림한 섀넌 부호를 쓸 수 있다.
$$ l_i = \left\lceil \log_2\frac{1}{p_i}\right\rceil $$이때 평균 길이는 엔트로피보다 작아질 수 없고, 엔트로피에 1비트를 더한 값보다는 작다.
$$ H(X) \le \bar L < H(X)+1 $$기호 하나마다 생기는 최대 1비트의 반올림 손실은 여러 기호를 묶으면 줄어든다. $N$개짜리 묶음의 엔트로피는 독립이라면 $NH(X)$이고, 묶음 전체에서 반올림 손실은 여전히 1비트 미만이다. 기호 하나당 손실은 $1/N$보다 작아져 $N$이 커질수록 0에 가까워진다.
압축기는 확률을 말하고 있다
부호 길이와 확률의 관계를 뒤집으면 부호가 암묵적으로 가정하는 확률분포를 읽을 수 있다.
$$ q(x)=2^{-l(x)} $$짧은 부호를 받은 기호는 높은 확률, 긴 부호를 받은 기호는 낮은 확률을 배정받는다. 따라서 자료를 잘 압축하려면 자료의 실제 규칙을 잘 예측해야 한다.
영어 문장에서 q 다음에는 u가 자주 온다. 문자를 서로 독립이라고 보는 모형은 이 규칙을 놓친다. 앞 문맥까지 이용하는 모형은 다음 문자의 확률을 더 날카롭게 예측하고 더 짧게 압축할 수 있다. 압축률은 그 모형이 자료의 구조를 얼마나 이해했는지 재는 점수가 된다.
엔트로피가 말하는 것과 말하지 않는 것
엔트로피는 분포의 평균 불확실성이다. 결과의 의미나 중요도를 재는 값은 아니다. 천재적인 문장과 무의미한 문자열이 같은 확률로 나온다면 정보량도 같다. 정보이론은 우선 메시지가 얼마나 드문지를 다루고, 그 메시지가 사람에게 어떤 뜻인지는 따로 묻지 않는다.
또 엔트로피는 분포를 알아야 계산할 수 있다. 실제 압축에서는 그 분포를 추정하거나 자료와 함께 모형을 보내야 한다. 분포를 잘못 잡으면 예상보다 부호가 길어지고, 그 추가 비용은 뒤에서 교차 엔트로피와 상대 엔트로피로 나타난다.
이번 강의의 결론은 간단하다.
확률 $p$인 사건의 이상적인 설명 길이는 $-\log_2 p$비트이고, 그 평균이 엔트로피다.
다음 강에서는 편향 동전을 여러 번 던지는 복권을 통해 긴 메시지 대부분이 어떤 작은 무리에 모이는지 본다. 그 전형 집합을 세면 엔트로피가 손실 없는 압축의 한계가 되는 까닭이 드러난다.