2강에서는 확률 $p$인 사건의 이상적인 부호 길이가 $-\log_2 p$이고, 그 평균이 엔트로피라고 했다. 하지만 한 기호의 부호 길이는 정수여야 한다. 엔트로피가 $0.469$비트인 편향 동전을 정말 던질 때마다 0.469비트로 저장할 수 있을까. 3강은 많은 결과를 한꺼번에 보면서 이 간극을 메운다.

교재: 4장 The Source Coding Theorem. 강의의 중심 예제는 편향 동전 복권이다.

편향 동전으로 만든 복권

앞면 확률이 $p$, 뒷면 확률이 $1-p$인 동전을 $N$번 던진다. 나온 이진 문자열 하나를 복권 번호라고 하자. 공정한 동전이라면 $2^N$개 문자열이 모두 같은 확률 $2^{-N}$을 가진다. 당첨 문자열을 알아내는 데 $N$비트가 필요하고 압축할 틈이 없다.

동전이 편향되어 $p=0.1$이라면 다르다. 길이 $N$인 모든 문자열은 여전히 가능하지만, 확률은 고르지 않다. 앞면이 $r$번 나온 특정 문자열의 확률은

$$ P(x)=p^r(1-p)^{N-r} $$

이다. 중요한 것은 앞면의 위치가 아니라 개수 $r$이다. 앞면이 같은 수만큼 들어간 문자열들은 모두 같은 확률을 가진다.

그렇다면 가장 확률이 큰 문자열은 앞면이 하나도 없는 문자열이다. 그런데 가장 확률이 큰 문자열 하나가 전체 결과를 대표하지는 않는다. $N$이 커지면 앞면이 대략 $pN$개 나오는 문자열이 엄청나게 많고, 이 무리의 확률을 모두 합치면 거의 1이 된다.

가장 흔한 하나와 전형적인 무리는 다르다

$p=0.1$, $N=100$이라 하자. 전부 뒷면인 문자열의 확률은

$$ 0.9^{100}\simeq 0.0000266 $$

이다. 개별 문자열 가운데서는 가장 그럴듯하지만 실제 추첨에서 볼 가능성은 매우 작다.

반면 앞면이 정확히 10개인 문자열은

$$ {100\choose10} $$

개나 된다. 각각의 확률은 $0.1^{10}0.9^{90}$으로 작지만, 모두 더한 확률은 상당히 크다. 앞면이 100번 중 10번 안팎으로 나오는 넓은 띠를 합치면 전체 확률 대부분을 차지한다.

이 구별은 추론에서도 중요하다. 가장 확률이 큰 결과 하나와 대부분의 확률 질량이 모인 영역은 같지 않을 수 있다. 높은 차원에서는 특히 그렇다. 맥케이의 복권은 이 사실을 압축 문제에서 눈에 보이게 만든다.

아래에서 동전의 편향과 던지는 횟수를 바꿔 보자. 파란 막대 하나는 앞면이 정확히 그만큼 나올 확률이고, 주황 띠는 확률 대부분이 모인 영역이다.

큰 수의 법칙이 만드는 전형성

동전을 오래 던지면 앞면의 비율 $r/N$은 $p$ 가까이에 모인다. 따라서 대부분의 문자열에서

$$ r\simeq pN,\qquad N-r\simeq(1-p)N $$

이다. 이런 문자열 하나의 로그 확률을 계산하면

$$ \begin{aligned} -\log_2 P(x) &= -r\log_2 p -(N-r)\log_2(1-p)\\ &\simeq N\left[-p\log_2p-(1-p)\log_2(1-p)\right]\\ &= NH_2(p). \end{aligned} $$

즉 대부분의 문자열은 대략

$$ P(x)\simeq 2^{-NH_2(p)} $$

라는 비슷한 확률을 가진다. 이들을 전형적인 문자열이라 하고, 그 집합을 전형 집합이라 부른다.

전형 집합 전체의 확률은 거의 1이고, 각 원소의 확률은 약 $2^{-NH_2(p)}$다. 따라서 원소 수는 대략

$$ |A_N|\simeq 2^{NH_2(p)} $$

이어야 한다. 전체 가능한 문자열은 $2^N$개지만 실제 확률 대부분은 약 $2^{NH_2(p)}$개의 전형적인 문자열에 모인다.

$p=0.1$이면 $H_2(p)\simeq0.469$다. 길이 1000인 문자열의 가능한 경우는 $2^{1000}$개지만, 실제로 신경 써야 할 전형적인 경우는 대략 $2^{469}$개다. 이들에 469비트 안팎의 번호를 매기면 대부분의 자료를 표현할 수 있다.

전형 집합 부호화

이제 실제 부호를 구성해 보자.

  1. 길이 $N$인 전형적인 문자열들을 모은다.
  2. 각 문자열에 $1$부터 약 $2^{NH(X)}$까지 번호를 붙인다.
  3. 입력이 전형 집합에 있으면 표시 비트 하나와 그 번호를 보낸다.
  4. 드물게 전형 집합 밖의 문자열이 나오면 다른 표시와 원문을 그대로 보낸다.

전형적인 경우에는 약 $NH(X)$비트, 비전형적인 경우에는 $N$비트가 든다. 그러나 $N$이 커질수록 비전형적인 경우의 확률은 0에 가까워진다. 따라서 기호당 평균 길이는 $H(X)$에 원하는 만큼 가까워진다.

$$ \frac{\bar L_N}{N}\longrightarrow H(X) $$

한 동전 결과를 0.469비트에 넣는 것이 아니다. 긴 결과 묶음 하나에 정수 길이의 부호를 주고, 전체 길이를 기호 수로 나눈 평균이 0.469에 가까워지는 것이다.

섀넌의 정보원 부호화 정리

독립이고 같은 분포를 따르는 정보원 $X$에 대해 정리는 두 방향을 함께 말한다.

달성 가능성

어떤 작은 $epsilon>0$을 택해도 충분히 큰 블록 길이 $N$에서는 기호당 평균 길이가

$$ H(X)+\epsilon $$

보다 작은 손실 없는 부호를 만들 수 있다. 전형 집합에 번호를 붙이는 위 방법이 존재 증명이다.

불가능성

반대로 기호당 $H(X)$보다 작은 비율로 모든 전형적인 메시지를 서로 다르게 표현할 수는 없다. $NR$비트로 만들 수 있는 부호어는 $2^{NR}$개뿐이다. 전형적인 문자열은 약 $2^{NH(X)}$개다. $R $$ 2^{NR}<2^{NH(X)} $$

이므로 이름표가 모자란다. 비둘기집 원리에 따라 둘 이상의 메시지가 같은 부호를 받아야 하고, 손실 없이 되살릴 수 없다.

따라서 엔트로피는 단순한 불확실성 점수가 아니다. 긴 독립 표본을 손실 없이 압축할 때 필요한 기호당 비트 수의 근본 한계다.

전형 집합을 조금 더 정확히 쓰면

길이 $N$인 표본 $x=(x_1,\ldots,x_N)$의 표본당 놀람값을 보자.

$$ -\frac{1}{N}\log_2 P(x) = \frac{1}{N}\sum_{n=1}^N -\log_2 P(x_n) $$

오른쪽은 독립이고 같은 분포에서 뽑은 정보량들의 표본평균이다. 큰 수의 법칙에 따라 그 평균은 기댓값 $H(X)$로 가까워진다.

$$ -\frac{1}{N}\log_2 P(x)\longrightarrow H(X) $$

이를 점근적 등분배 성질이라고 한다. “등분배"라는 말은 모든 문자열의 확률이 같다는 뜻이 아니다. 확률 대부분을 차지하는 전형 집합 안에서 문자열들이 지수 규모로 보아 거의 같은 확률을 가진다는 뜻이다.

무엇을 가정했는가

이번 정리의 가장 단순한 형태는 각 기호가 독립이고 같은 분포에서 나온다고 가정한다. 실제 문장, 음악, 영상은 그렇지 않다. 다음 글자는 앞의 글자와 강하게 얽혀 있고, 영상의 이웃 화소도 비슷하다.

그렇다고 정보원 부호화 정리가 쓸모없어지는 것은 아니다. 의존성이 있는 정보원에는 긴 문맥의 조건부 확률을 사용한다. 좋은 모형은 반복과 문맥을 이용해 다음 기호의 불확실성을 낮춘다. 압축기는 그 낮아진 불확실성만큼 더 짧은 부호를 만든다.

또 전형 집합 부호화는 한계가 존재함을 보여주는 사고실험에 가깝다. 실제로 전형적인 문자열을 전부 표로 저장하는 것은 불가능하다. 현실에서는 허프만 부호, 산술 부호 같은 효율적인 방법으로 확률에 가까운 길이를 구현한다. 이어지는 강의에서 이런 심볼 부호와 실제 압축 방법을 더 자세히 다룬다.

복권이 보여준 것

편향 동전 복권에서 배울 점을 묶으면 다음과 같다.

  • 가능한 문자열 수와 실제로 자주 나오는 문자열 수는 크게 다를 수 있다.
  • 가장 확률이 큰 문자열 하나가 아니라 확률 질량이 모인 전형 집합을 봐야 한다.
  • 전형 집합의 크기는 약 $2^{NH(X)}$다.
  • 그 원소를 구별하려면 약 $NH(X)$비트가 필요하고, 그보다 적게는 손실 없이 구별할 수 없다.

2강에서 엔트로피는 평균 놀라움으로 등장했다. 이제 같은 값이 전형적인 메시지의 수를 세고, 압축에 필요한 비트 수를 정한다. 확률, 조합, 부호 길이가 한 숫자에서 만난다.

다음 강에서는 이 한계를 실제 부호에 더 가까이 가져간다. 기호별 부호를 어떻게 설계하고, 평균 길이와 엔트로피 사이의 간격을 어떻게 줄이는지 살펴본다.