데이비드 맥케이의 강의는 정보량 공식부터 꺼내지 않는다. 먼저 정보이론이 해결하려는 문제들을 한데 펼쳐 놓는다. 파일을 얼마나 작게 줄일 수 있는가, 잡음이 섞인 선로로 얼마나 빠르고 정확하게 말할 수 있는가, 불완전한 관측에서 숨은 원인을 어떻게 알아내는가. 겉으로는 서로 다른 문제지만 모두 가능성들에 확률을 붙이고, 관측이 그 가능성을 어떻게 좁히는지 묻는다.
교재: Information Theory, Inference, and Learning Algorithms. 이번 강의는 책 전체의 길잡이이며, 확률과 엔트로피의 기초는 2장을 함께 보면 좋다.
세 갈래가 만나는 자리
책 제목에는 정보이론, 추론, 학습 알고리즘이라는 세 주제가 나란히 놓인다.
- 정보이론은 데이터를 압축하고 잡음 속에서 전달할 수 있는 근본 한계를 묻는다.
- 추론은 관측한 데이터로부터 보이지 않는 원인이나 매개변수를 거꾸로 알아낸다.
- 학습은 많은 데이터에서 규칙을 찾아 앞으로의 데이터를 예측한다.
압축기는 자주 나오는 패턴에 짧은 표현을 주어야 한다. 수신기는 훼손된 신호를 보고 송신자가 보냈을 법한 메시지를 골라야 한다. 학습기는 데이터가 어떤 모형에서 나왔을 법한지 비교해야 한다. 셋 모두 “무엇이 얼마나 그럴듯한가"를 계산한다. 그 공통 언어가 확률이다.
정보이론의 놀라운 점은 좋은 방법 하나를 제시하는 데 그치지 않는다는 것이다. 어떤 방법을 쓰더라도 넘을 수 없는 선을 먼저 알려준다. 압축에서는 엔트로피가 그 선이고, 잡음 있는 통신에서는 채널 용량이 그 선이다. 뒤의 강의들은 그 경계가 어디서 나오며 실제 부호가 어떻게 가까이 다가가는지를 보여준다.
첫 번째 문제: 얼마나 압축할 수 있는가
길이가 $N$인 이진 문자열을 생각하자. 아무 규칙 없이 0과 1이 똑같은 확률로 나온다면 가능한 문자열은 $2^N$개다. 이 가운데 어느 하나도 다른 것보다 특별히 자주 나오지 않는다. 서로 다른 $2^N$개를 빠짐없이 구별하려면 결국 $N$비트가 필요하다.
하지만 1이 나올 확률이 $0.01$인 자료라면 사정이 다르다. 대부분이 0이고 가끔 1이 나온다. 모든 이진 문자열이 수학적으로 가능하더라도 실제로 자주 만나는 것은 1이 약 $0.01N$개 들어 있는 일부 문자열뿐이다. 그 작은 무리에 짧은 이름을 붙이면 원래의 $N$비트보다 훨씬 적은 비트로 저장할 수 있다.
아래에서 1의 확률을 바꿔 보자. 0과 1이 비슷하게 나오면 압축기는 얻을 것이 거의 없다. 반대로 0이 압도적으로 자주 나오면 흔한 문자열에 매우 짧은 이름을 붙일 수 있다. 다만 드문 문자열은 오히려 원본보다 길어질 수 있다. 절약되는 것은 모든 개별 문자열의 길이가 아니라 전체의 평균 길이다.
여기서 압축의 핵심이 드러난다.
압축은 반복되는 글자를 지우는 일이 아니라, 가능성이 고르지 않다는 사실을 이용해 자주 나오는 메시지에 짧은 이름을 붙이는 일이다.
자료의 확률분포를 모르면 무엇이 흔한지 알 수 없고, 무엇에 짧은 이름을 줄지도 알 수 없다. 그래서 압축과 확률 모형은 떼어 놓을 수 없다. 좋은 압축기는 곧 자료를 잘 예측하는 모형이다.
두 번째 문제: 잡음 속에서 얼마나 보낼 수 있는가
이제 비트를 저장하는 대신 채널로 보낸다고 하자. 채널이 가끔 0을 1로, 1을 0으로 뒤집는다. 가장 단순한 대응은 같은 비트를 여러 번 보내는 것이다.
예를 들어 0을 000, 1을 111로 보내고 다수결로 읽으면 한 비트가 뒤집혀도 원래 값을 되찾는다. 신뢰도는 높아졌지만 정보 한 비트를 보내는 데 채널을 세 번 썼다. 오류를 줄이려고 무작정 반복하면 전송률이 너무 낮아진다.
그렇다면 두 목표가 맞선다.
- 오류 확률은 아주 작아야 한다.
- 채널 한 번당 보내는 정보량은 커야 한다.
섀넌의 잡음 채널 부호화 정리는 둘을 동시에 달성할 수 있는 경계를 말한다. 채널 용량보다 낮은 전송률에서는 충분히 긴 부호를 써서 오류 확률을 원하는 만큼 작게 만들 수 있다. 반대로 용량보다 높은 전송률에서는 어떤 기발한 부호를 써도 믿을 만한 통신이 불가능하다.
이 결과가 직관에 거스르는 까닭은 잡음을 없애지 않기 때문이다. 채널은 계속 비트를 뒤집는다. 대신 긴 메시지 전체에 여분의 구조를 심어, 훼손된 결과가 어느 유효한 부호어에서 왔는지 알아낼 수 있게 한다. 개별 비트를 지키는 대신 메시지 공간의 모양을 설계하는 것이다.
부호화와 추론은 앞뒤가 뒤집힌 같은 문제다
송신자는 메시지 $x$를 부호어로 바꾸고, 채널은 관측 $y$를 만든다. 이 과정을 확률로 쓰면 $P(y\mid x)$다. 수신자가 해야 할 일은 반대 방향이다. 관측 $y$를 보고 어떤 $x$가 보내졌는지를 추론한다.
가장 그럴듯한 메시지는 베이즈 규칙으로 찾을 수 있다.
$$ P(x\mid y) = \frac{P(y\mid x)P(x)}{P(y)} $$여기서 $P(x)$는 메시지를 보기 전의 믿음, $P(y\mid x)$는 $x$를 보냈을 때 지금의 신호가 나올 가능성이다. $P(x\mid y)$는 신호를 본 뒤의 믿음이다. 복호화는 이 사후확률이 큰 메시지를 고르는 추론 문제다.
같은 그림은 머신러닝에도 나타난다. 모형의 매개변수를 $x$, 학습 데이터를 $y$라 두면 학습은 $P(x\mid y)$를 구하는 일이 된다. 통신에서는 채널이 데이터를 만들고, 학습에서는 생성 모형이 데이터를 만든다는 이름만 다르다.
확률은 무지를 다루는 계산법이다
확률을 단지 무작위 장치의 성질로만 보면 추론과의 연결이 낯설다. 맥케이는 확률을 불완전한 정보 아래에서 믿음의 정도를 일관되게 다루는 계산법으로 사용한다.
확률의 합 규칙과 곱 규칙이면 기본 뼈대가 생긴다.
$$ P(x) = \sum_y P(x,y) $$$$ P(x,y) = P(x\mid y)P(y) $$첫 식은 관심 없는 가능성 $y$를 모두 더해 없애는 주변화다. 둘째 식은 두 사건이 함께 일어날 확률을 조건부 확률로 나눈 것이다. 곱 규칙에서 $x$와 $y$의 순서를 바꾸면 베이즈 규칙이 바로 나온다.
$$ P(x\mid y) = \frac{P(y\mid x)P(x)}{P(y)} $$이 규칙은 새 정보를 얻었을 때 믿음을 어떻게 고쳐야 하는지 말한다. 사전확률 $P(x)$에 관측의 가능도 $P(y\mid x)$를 곱하고, 전체가 다시 확률분포가 되도록 $P(y)$로 나눈다.
모형은 압축에서도 중심에 있다
압축과 추론의 연결을 한 단계 더 밀어 보자. 어떤 모형이 자료 $x$에 높은 확률을 준다면 그 자료는 모형 아래에서 예상하기 쉽다. 예상하기 쉬운 자료에는 짧은 부호를 줄 수 있다. 반대로 모형이 거의 일어나지 않으리라 본 자료는 긴 부호가 필요하다.
뒤에서 정확히 배우겠지만, 이상적인 부호 길이는 대략 다음과 같다.
$$ L(x) \simeq -\log_2 P(x) $$확률이 $1/2$이면 1비트, $1/4$이면 2비트, $1/1024$이면 10비트다. 자료에 높은 확률을 주는 모형일수록 그 자료를 짧게 설명한다. 그래서 모형 비교를 “어느 모형이 자료를 가장 잘 압축하는가"로 바꾸어 생각할 수 있다. 이 관점은 뒤의 베이즈 추론과 최소 설명 길이로 이어진다.
정보이론이 답하려는 두 질문
첫 강을 마치며 두 질문을 분명히 세워 두자.
- 어떤 확률분포에서 나온 자료를 손실 없이 평균 몇 비트까지 압축할 수 있는가?
- 잡음 있는 채널을 통해 오류를 거의 내지 않으면서 한 번에 몇 비트를 보낼 수 있는가?
첫 질문의 답은 엔트로피, 둘째 질문의 답은 채널 용량이다. 둘 다 확률분포에서 계산되고, 둘 다 달성 가능한 영역과 불가능한 영역의 경계를 긋는다.
다음 강에서는 한 사건이 주는 정보량을 $-\log_2 p$로 재고, 그 평균인 엔트로피를 정의한다. 그리고 이 추상적인 숫자가 실제 압축 길이와 어떻게 이어지는지 살펴본다.