압축하는 것이 이해하는 것이다

튀코 브라헤가 20년 동안 적은 행성의 위치를 케플러는 법칙 세 줄로 줄였습니다. 짧게 적는 일과 이해하는 일은 정말 같은 일일까요? 오컴의 면도날⁠(Occam's razor)⁠을 비트로 재는 법과, 그 말이 정리인 곳과 철학인 곳.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 색이 칠해진 같은 말은 눌러서 바꿀 수 있습니다. 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 그림 속 점은 끌 수 있고, 칸과 막대에 마우스를 올리면 정확한 값이 나옵니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

1600년 2월 4일, 프라하에서 북동쪽으로 40킬로미터쯤 떨어진 베나트키 성에서 스물여덟 살의 요하네스 케플러가 쉰세 살의 튀코 브라헤를 처음 만났습니다. 튀코는 망원경이 나오기 전 가장 정밀한 관측자였습니다. 덴마크 왕에게서 외레순 해협의 벤섬(지금은 스웨덴 땅)을 받아 천문대를 짓고, 1576년부터 20년 넘게 별과 행성의 위치를 쟀습니다. 정밀도⁠(precision)⁠는 맨눈 관측의 한계에 가까운 각도 1~2분(1분은 1도의 60분의 1)이었습니다. 1597년 왕의 후원을 잃은 그는 신성 로마 제국 황제 루돌프 2세의 궁정 천문학자가 되어 프라하로 왔고, 계산을 도울 젊은 수학자로 케플러를 불렀습니다.

튀코는 자료를 쉽게 내주지 않았습니다. 케플러에게 맡긴 것은 화성이었습니다. 화성은 궤도⁠(orbit)⁠가 원에서 꽤 많이 벗어나서 어떤 이론으로도 잘 맞지 않았기 때문입니다(수성은 더 많이 벗어나지만, 늘 해 가까이 있어 관측할 기회가 드뭅니다). 이듬해인 1601년 10월 24일 튀코가 프라하에서 세상을 떠나자 케플러가 황실 수학자 자리를 이었고, 튀코의 상속인들과 실랑이를 겪으면서도 관측 기록을 계속 쓸 수 있었습니다. 그렇다면 케플러가 그 기록으로 한 일은 정확히 무엇이었을까요? 그가 남긴 것은 세 문장입니다. 행성은 해를 한 초점에 둔 타원⁠(ellipse)⁠을 돈다. 해와 행성을 잇는 선은 같은 시간에 같은 넓이⁠(area)⁠를 쓸고 지나간다. 공전 주기⁠(period)⁠의 제곱은 궤도 크기의 세제곱에 비례한다.

세 문장은 튀코의 표를 버린 것이 아닙니다. 세 문장과 행성마다 여섯 개의 수(궤도의 크기, 찌그러진 정도, 기울기⁠(slope)⁠와 방향, 어느 날 어디에 있었는지)만 있으면 표의 수천 줄을 관측 오차에 가까운 정밀도로 다시 만들어 낼 수 있습니다. 행성끼리 끌어당기는 효과가 큰 목성과 토성에서는 조금 더 어긋납니다. 셋째 법칙 자체가 정확하지 않은 까닭 하나는 1절 끝에서 봅니다. 긴 표를 짧은 설명과 조금의 나머지로 바꾼 것, 곧 압축입니다. 이 글은 이 말을 비유가 아니라 셈으로 따라갑니다. 법칙 하나가 표를 몇 비트나 줄이는지 직접 셉니다. 그리고 14세기의 오컴의 면도날이 어떻게 확률⁠(probability)⁠과 비트의 언어로 정확한 말이 되었는지, 그 말이 오늘날 과적합⁠(overfitting)⁠을 막는 방법과 언어 모델⁠(language model)⁠을 평가하는 방법에까지 어떻게 이어지는지 봅니다.

미리 밝혀 둘 것이 있습니다. '압축하는 것이 이해하는 것이다'라는 제목에는 증명된 정리인 부분과, 그럴듯하지만 증명할 수는 없는 철학적 주장이 섞여 있습니다. 부호의 길이와 확률이 서로 바꿔 쓸 수 있는 말이라는 것, 가장 짧은 설명을 고르는 일이 특정한 사전확률⁠(prior probability)⁠을 둔 베이즈 추론에서 사후확률⁠(posterior probability)⁠이 가장 큰 가설을 고르는 일과 같다는 것은 정리입니다. 사전확률은 자료를 보기 전에 가설에 주는 믿음의 크기이고, 사후확률은 자료를 본 뒤에 고친 믿음의 크기입니다(3절에서 다시 풉니다). 자연이 단순하다는 것, 짧은 설명일수록 참일 가능성이 높다는 것은 정리가 아닙니다. 글 내내 둘을 구별하겠습니다.

1 · 여덟 분튀코의 표와 케플러의 세 줄

이 절의 물음은 이것입니다. 법칙 하나는 관측표를 정확히 몇 비트 줄일까? 그리고 틀린 법칙은 왜 거의 줄이지 못할까? 먼저 케플러가 법칙에 이른 길을 보고, 그다음 셋째 법칙으로 비트를 직접 셉니다.

케플러는 원에서 출발했습니다. 2,000년 동안의 천문학자들처럼 화성이 원을 돈다고 보고, 원의 중심과, 화성이 고르게 도는 것처럼 보이는 점(등각속도점⁠, equant⁠)의 위치를 이리저리 옮겼습니다. 기준으로 삼은 것은 화성이 해의 정반대편에 오는 '충' 때의 관측 10여 개였습니다. 그 가운데 넷으로 원의 위치를 정하는 데 몇 해의 계산이 들었고, 이렇게 얻은 모형은 충의 관측을 모두 각도 2분 안쪽으로 맞혔습니다. 그런데 다른 때의 관측에 대 보니 8분까지 어긋났습니다. 프톨레마이오스의 시대라면 무시해도 될 크기였지만, 케플러는 튀코의 관측이 그만큼 틀릴 리 없다고 믿었습니다.

이 8분을 무시해도 된다고 믿었다면 가설을 적당히 기워 맞췄을 것이다. 그러나 무시할 수 없었으니, 이 8분이 천문학 전체를 개혁하는 길을 가리켰다.— 케플러, 『새로운 천문학』(1609) 19장의 요지

압축의 말로 옮기면 이렇습니다. 표를 모형으로 적는다는 것은 모형이 예측한 위치를 먼저 받아들이고, 실제 관측이 예측에서 벗어난 만큼(나머지, 또는 잔차⁠(residual)⁠)만 따로 적는다는 뜻입니다. 원 모형으로 표를 적으면 8분짜리 나머지가 남습니다. 나머지가 크면 그것을 적는 데 비트가 많이 듭니다. 관측이 정밀할수록 그 나머지는 '잡음'이라고 둘러댈 수 없게 되고, 설명을 기다리는 규칙이 됩니다. 케플러는 결국 원을 버리고 타원에 이르렀고, 8분짜리 나머지는 관측 오차 수준으로 줄었습니다. 1609년 하이델베르크에서 찍은 『새로운 천문학』에 첫째와 둘째 법칙이 실렸습니다.

셋째 법칙은 『새로운 천문학』이 나오고 9년 뒤에 왔습니다. 케플러의 회고에 따르면 그는 1618년 3월 8일에 이 법칙을 떠올렸다가 계산 착오로 버렸고, 5월 15일에 다시 돌아와 맞는 것을 확인했습니다. 이듬해 린츠에서 펴낸 『세계의 조화』에 실린 이 법칙은 행성의 공전 주기 T와 해에서의 평균⁠(mean)⁠ 거리 a(타원의 긴반지름) 사이의 관계입니다. 지구의 주기를 1년, 거리를 1로 잡으면 $T^2 = a^3$, 곧 $T = a^{3/2}$입니다. 목성으로 확인해 봅시다. 케플러의 값으로 목성의 거리는 5.2, 주기는 11.86년이니 $T^2 \approx 140.7$, $a^3 \approx 140.6$으로 거의 같습니다.

이 법칙은 로그를 쓰면 직선이 됩니다. 여기서 $\log$는 밑이 10인 로그, 곧 '10을 몇 번 곱해야 그 수가 되는가'입니다($\log_{10} 100 = 2$). 로그는 거듭제곱을 곱셈으로 바꾸므로($\log a^{3/2} = \tfrac32 \log a$), 양변에 로그를 씌우면 $\log T = \tfrac32 \log a$입니다. 그러니 두 축을 로그 눈금으로 그리면 행성들이 기울기 1.5인 직선 위에 놓입니다.

이 법칙이 표를 몇 비트 줄이는지 세어 봅시다. 거리 a는 보내는 쪽과 받는 쪽이 이미 안다고 하고 주기 T만 보냅니다. 주기는 의 정밀도로 적습니다. $\log_{10} T$를 그 정밀도에 맞는 눈금 간격 δ(델타)로 나누어 반올림한 정수⁠(integer)⁠를 보내는 것입니다. 정밀도 0.1%라면 δ는 주기가 0.1% 늘 때 $\log_{10} T$가 느는 양, 곧 $\log_{10} 1.001 \approx 0.000434$입니다. 화성의 주기는 케플러의 값으로 686.95일, 곧 약 1.8808년이고 $\log_{10} T \approx 0.274335$이니, 0.274335 ÷ 0.000434를 반올림한 정수 632를 보냅니다. 받는 쪽은 632 × δ로 주기를 0.1% 안쪽까지 되살립니다.

정수를 비트로 적는 방법도 정해야 합니다. 받는 쪽이 한 수가 어디서 끝나는지 알아야 하니 엘리아스 감마 부호⁠(Elias gamma code)⁠를 씁니다. 양의 정수 m을 적을 때, 먼저 m의 이진수 자릿수보다 하나 적은 개수의 0을 쓰고 그다음 m의 이진수를 씁니다(5는 이진수 101이니 00101). 받는 쪽은 앞의 0을 세어 뒤에 몇 자리가 올지 압니다. 0과 음수까지 적으려면 0, −1, +1, −2, +2, …를 차례로 1, 2, 3, 4, 5, …로 바꿔서 적습니다. 그러면 0은 1비트이고, 크기가 m 안팎인 정수는 약 $2\log_2 m$비트가 듭니다. 화성의 632는 1,265번째 수로 바뀌고, 1,265는 이진수로 11자리이니 0 열 개와 11자리를 합쳐 21비트입니다. 작은 수일수록 싸다는 것이 요점입니다.

'표를 그대로' 보내면 행성마다 $\log_{10} T$의 정수를 통째로 보냅니다. '법칙으로' 보내면 먼저 지수 k를 소수 둘째 자리까지 보내고(1.5라면 정수 150), 그다음 행성마다 법칙의 예측에서 벗어난 나머지, 곧 잔차 $\log_{10} T - k \log_{10} a$만 같은 눈금으로 보냅니다. 받는 쪽은 k와 잔차로 표를 한 칸도 틀리지 않고 되살립니다. 어림이 아니라 무손실 압축입니다. 화성으로 해 봅시다. k = 1.5이면 법칙의 예측은 $1.5 \times \log_{10} 1.524 \approx 0.274477$이고, 실제 값 0.274335와의 차이는 약 0.000142로 눈금 한 칸(0.000434)의 3분의 1도 안 되니 반올림하면 0입니다. 0은 1비트이니, 표를 그대로 보낼 때 21비트이던 화성이 1비트가 됩니다. 대신 지수 150을 한 번 보내는 데 17비트가 듭니다. 자료: , 지수 $k =$ k = 1.5로

그림에서 할 일은 지수 k를 1에서 2까지 끌어 보며, 오른쪽 그래프의 노란 선(법칙으로 보낼 때의 전체 비트)이 어디서 가장 낮아지는지, 그리고 분홍 점선(표를 그대로 보낼 때)보다 얼마나 아래로 내려가는지 보는 것입니다.

지금 표를 그대로 보내면 비트, 법칙으로 보내면 지수 비트와 잔차 비트를 합쳐 비트입니다. 비트 수가 가장 적은 지수는 이고, 그때 비트입니다.

그래프에서 세 가지를 읽을 수 있습니다. 첫째, 비트 수가 가장 적은 곳이 정확히 1.5이고, 골짜기가 아주 좁습니다. 케플러의 값을 정밀도 0.1%로 적을 때, k = 1.5에서 39비트이던 길이가 k를 1.4나 1.6으로만 옮겨도 90비트를 넘습니다. 이 셈은 케플러의 법칙을 미리 알려 주지 않아도 자료에서 지수를 찾아냅니다. 가장 짧게 적게 해 주는 지수가 가장 잘 맞는 지수입니다.

둘째, 틀린 법칙은 거의 아무것도 줄이지 못합니다. 케플러의 값에서 k = 1(주기가 거리에 비례)로 두면 잔차 비트가 커져서 표를 그대로 보내는 것과 거의 같아지고, 더 멀리 가면 오히려 길어집니다. 잔차가 원래 값과 비슷한 크기로 남으면 잔차를 적는 비트도 원래 값을 적는 비트와 비슷하게 들고, 거기에 법칙을 적는 비트까지 더해지기 때문입니다.

셋째, 두 선 사이의 띠, 곧 법칙을 적는 비트는 k가 달라져도 거의 그대로입니다. 법칙 자체는 13~17비트로 싸고, 차이를 만드는 것은 법칙이 얼마나 많은 잔차를 없애 주느냐입니다. 그만큼 잔차를 줄여 주지 못하는 법칙은 적는 값만큼 손해입니다.

잔차 속에는 다음 이론이 숨어 있기도 합니다. 1687년 뉴턴의 『프린키피아』는 세 법칙을 운동 법칙과 만유인력 하나에서 끌어냈습니다. 행성과 달과 밀물과 떨어지는 사과를 한 식이 설명하게 되었으니, 압축으로 보면 여러 표를 한꺼번에 줄이는 더 짧은 설명입니다. 그리고 뉴턴의 이론은 셋째 법칙이 정확하지 않다고 말합니다. 행성도 해를 끌어당기므로 정확한 관계는 $T^2 \propto a^3/(M+m)$입니다(∝는 '비례한다'로 읽고, M은 해의 질량, m은 행성의 질량입니다). 행성이 무거울수록 분모가 커지니 주기는 조금 짧아집니다. 목성의 질량은 해의 약 1,000분의 1이어서, 목성의 주기는 케플러의 법칙이 주는 값보다 약 0.05% 짧습니다. 케플러의 자료에서는 이 차이가 관측 오차에 묻혀 있었지만, 법칙으로 적고 남은 잔차 속에 행성의 질량이 들어 있었던 셈입니다. 좋은 법칙은 잔차를 줄이고, 더 좋은 법칙은 남은 잔차에서 다시 규칙을 찾아냅니다. 정리하면, 법칙으로 적은 길이는 '법칙을 적는 비트 + 잔차를 적는 비트'이고, 참인 법칙은 법칙 값의 몇 배를 잔차에서 아껴 줍니다.

짧아진 설명은 곧 쓸모의 시험을 받았습니다. 케플러는 튀코의 관측과 자기 법칙으로 행성의 위치를 미리 계산해 두는 표를 만들어, 후원자인 황제의 이름을 따 『루돌프 표』라 부르고 1627년 울름에서 1,000부를 찍었습니다. 이 표는 13세기부터 쓰이던 알폰소 표나 코페르니쿠스의 체계로 계산한 프로이센 표보다 훨씬 정확했습니다. 케플러는 1630년에 펴낸 천체력에서 수성과 금성이 해의 앞을 지나가는 일을 예고했고, 그가 세상을 떠난 이듬해인 1631년 11월 7일 파리의 피에르 가상디가 처음으로 수성의 태양면 통과를 보았습니다. 1635년 무렵에는 명나라에서 역법을 고치던 예수회 선교사 아담 샬도 이 표를 썼습니다. 압축의 말로 하면, 법칙은 이미 적힌 표만이 아니라 아직 아무도 적지 않은 표까지 줄여 준 것입니다.

짧다고 다 맞는 것은 아니라는 교훈도 케플러 자신에게서 나옵니다. 튀코를 만나기 네 해 전인 1596년, 그라츠의 수학 교사였던 케플러는 첫 책 『우주의 신비』에서 행성이 왜 여섯 개인지를 설명했습니다. 모든 면이 같은 정다각형⁠(regular polygon)⁠인 입체, 곧 정다면체(정사면체, 정육면체 등)는 다섯 가지뿐이니, 여섯 행성의 궤도를 담은 구들 사이에 다섯 정다면체⁠(regular polyhedron)⁠를 차례로 끼워 넣으면 행성의 수와 간격이 한꺼번에 설명된다는 것입니다. 행성의 수와 간격을 도형 다섯 개로 줄인, 아주 짧고 아름다운 설명이었습니다. 그러나 그 간격은 관측과 딱 맞지 않았고, 케플러가 튀코의 정밀한 자료를 그토록 원한 것도 이 모형을 확인하고 싶어서였습니다. 튀코의 자료는 모형을 확인해 주는 대신 그를 타원으로 이끌었고, 1781년 일곱째 행성 천왕성이 발견되면서 '여섯 행성'이라는 전제도 무너졌습니다. 행성의 거리를 수열 하나로 줄인 티티우스–보데 규칙도 천왕성과 세레스를 맞힌 뒤 1846년 해왕성에서 크게 어긋났습니다. 그 규칙이 세레스를 찾아 나서게 한 이야기는 「잃어버린 소행성」 7절에 있습니다. 위에서 센 비트로 말하면, 설명이 짧아도 나머지(잔차)가 크면 둘을 합친 전체는 짧아지지 않습니다.

2 · 면도날오컴, 라이프니츠, 그리고 '단순함'이라는 문제

1절에서는 '짧다'를 비트로 셌습니다. 그런데 무엇을 짧다고 할지는 누가 정할까요? 이 절의 물음은 이것입니다. 오래된 원칙인 '단순한 설명을 택하라'에서 '단순하다'는 정확히 무슨 뜻이고, 그것을 재는 자는 하나뿐일까?

짧은 설명을 좋아하는 생각은 오래되었습니다. 14세기 잉글랜드의 프란치스코회 수사 오컴의 윌리엄(1287년 무렵–1347년)은 페트루스 롬바르두스의 『명제집』에 붙인 주석 등에서 "필요 없이 여럿을 가정해서는 안 된다(Numquam ponenda est pluralitas sine necessitate)"는 원칙을 되풀이해 썼습니다. 흔히 오컴의 말로 인용되는 "존재는 필요 이상으로 늘려서는 안 된다"는 문장은 오컴의 글에는 없고, 1639년 아일랜드의 신학자 존 펀치가 둔스 스코투스의 저작에 붙인 주석에 나옵니다.

'오컴의 면도날'이라는 이름이 쓰인 이른 예로는 1649년 루뱅의 신학자 리베르 프루아몽의 책이 꼽힙니다. 오컴 자신은 이 원칙을 주로 신학과 형이상학의 논쟁에 썼고, 과학의 원칙으로 널리 쓰인 것은 그 뒤의 일입니다. 그가 이 원칙으로 겨눈 것은 이를테면 '보편자'였습니다. 사람들 하나하나 말고 '사람임'이라는 것이 따로 존재한다고 가정할 필요가 없다는 것입니다. 이름만 있을 뿐이라는 이 입장을 유명론⁠(nominalism)⁠이라 부릅니다. 면도날이라는 이름도 필요 없는 가정을 깎아 낸다는 뜻입니다. 사실 단순함을 좋아하는 말은 오컴보다 훨씬 오래되었습니다. 2세기 알렉산드리아의 프톨레마이오스는 『알마게스트』 3권 첫머리에 "현상을 되도록 가장 단순한 가설로 설명하는 것이 좋은 원칙이라고 우리는 생각한다"고 적었습니다. 뒷날 복잡함의 대명사처럼 불리게 되는 천문 체계를 만든 사람의 말입니다.

뉴턴도 『프린키피아』 3권 첫머리에 자연을 탐구하는 규칙들을 적으며 첫째로 이렇게 썼습니다. "자연 현상의 원인으로는, 참이면서 그 현상을 설명하기에 충분한 것보다 더 많은 것을 받아들이지 말아야 한다." 그런데 무엇이 '단순한' 설명일까요? 흔히 드는 예가 코페르니쿠스입니다. 프톨레마이오스를 따르던 천문학자들이 관측에 맞추려고 원 위에 원(주전원⁠, epicycle⁠)을 수십 개씩 덧붙였고, 코페르니쿠스가 해를 가운데 두어 그 복잡함을 한 번에 걷어 냈다는 이야기입니다. 과학사가 오언 깅거리치 등의 연구에 따르면 이 이야기는 대부분 전설입니다. 중세의 천문표는 행성마다 주전원 하나를 쓰는 프톨레마이오스의 방식 그대로 계산되었습니다. 1543년 코페르니쿠스의 체계도 여전히 주전원을 써서 원의 개수가 크게 줄지 않았고, 예측의 정확도도 비슷했습니다.

코페르니쿠스 체계의 장점은 원의 개수가 아닌 다른 곳에 있었습니다. 행성이 가끔 뒤로 가는 것처럼 보이는 역행을 행성마다 따로 설명하지 않고 지구가 움직인다는 사실 하나로 설명했고, 행성들의 상대적인 거리를 정해 주었습니다. 프톨레마이오스의 체계에서 따로따로 맞추던 수들이 서로 묶인 것입니다. 원을 몇 개 쓰느냐로 세면 둘은 비슷하고, 자유롭게 고르는 수가 몇 개냐로 세면 코페르니쿠스가 앞섭니다. 단순함을 무엇으로 셀지부터가 문제입니다.

이슬람 세계의 천문학자들은 또 다른 잣대를 썼습니다. 프톨레마이오스는 관측에 맞추려고 '등각속도점'을 두었습니다. 행성이 원의 중심이 아닌 다른 한 점에서 볼 때만 고르게 도는 것처럼 꾸민 장치입니다. 천체는 원을 고르게 돈다는 원칙과 어긋나는 이 장치를 13세기 마라게 천문대를 이끈 나시르 알딘 알투시와 그 뒤의 천문학자들이 문제 삼았습니다. 알투시는 고르게 도는 원 두 개를 짝지어 직선 위의 왕복 운동을 만드는 장치(투시 쌍)를 고안했고, 14세기 다마스쿠스의 이븐 알샤티르는 이런 장치로 등각속도점 없이 관측에 맞는 모형을 만들었습니다. 그의 달과 수성의 모형은 코페르니쿠스의 것과 똑같습니다. 코페르니쿠스도 등각속도점을 없애는 것을 중요하게 여겼습니다. 그 생각이 어떤 길로 코페르니쿠스에게 닿았는지, 아니면 따로 이른 것인지는 아직 논쟁 중입니다. 이들이 따진 것은 원의 개수가 아니라 원칙에 어긋나는 장치가 있느냐였습니다(마라게 천문대가 세워진 사정은 「평행선의 반란」에서 알투시의 평행선 연구와 함께 볼 수 있습니다).

이 문제를 가장 날카롭게 짚은 사람은 라이프니츠였습니다. 1686년에 쓴 『형이상학 논고』 6절에서 그는 이런 생각 실험을 합니다. 종이 위에 아무렇게나 점을 찍어 보자. 그래도 그 모든 점을 차례로 지나가면서 어떤 규칙으로 정해지는 선은 언제나 있다. 그러니 '규칙이 있다'는 것만으로는 아무것도 말해 주지 않는다. 규칙이 아주 복잡하면, 그 규칙을 따르는 것은 불규칙하다고 여겨진다. x좌표가 서로 다른 점 n개가 있으면 그 점을 모두 지나는 (n−1)차 이하의 다항식⁠(polynomial)⁠이 늘 있다는 것을 떠올리면 라이프니츠의 말이 정확히 이해됩니다. 점이 두 개면 둘을 지나는 직선(1차식)이, 세 개면 셋을 모두 지나는 포물선(2차식)이 늘 있습니다. 점 열 개를 아무렇게나 찍어도 그 열 개를 모두 지나는 9차식이 있는데, 그 식을 적으려면 계수 열 개가 필요하니 점 열 개를 그대로 적는 것과 다를 바 없습니다. 어떤 자료든 자료를 통째로 적은 '설명'은 늘 있으니, 설명이 자료보다 짧을 때에만 설명의 값어치가 있습니다. 이 문단은 300년 가까이 지나 콜모고로프 복잡도⁠(Kolmogorov complexity)⁠를 연구한 그레고리 차이틴이 자기 생각의 뿌리로 즐겨 인용했습니다. 『형이상학 논고』는 라이프니츠가 살아 있을 때는 출판되지 않았고 19세기에야 세상에 나왔습니다.

19세기 말 프라하 대학의 물리학자 에른스트 마흐는 1883년의 책 『역학의 발달』에서 과학을 '사고의 경제⁠(economy of thought)⁠'라고 불렀습니다. 법칙은 수많은 개별 경험을 하나하나 기억하는 수고를 덜어 주는 요약이라는 것입니다. 마흐가 그 무렵 가르치던 프라하는 케플러가 튀코의 자료와 씨름한 바로 그 도시입니다.

남은 문제는 '짧다'가 어떤 언어로 짧으냐는 것입니다. 1955년 미국의 철학자 넬슨 굿맨은 이것을 '그루(grue)'라는 말로 보였습니다. 정해진 어느 날(예를 들어 2100년 1월 1일) 전에 관찰되었고 초록색이거나, 그렇지 않고 파란색인 것을 '그루'라고 부르자. 지금까지 본 에메랄드는 모두 초록색이면서 모두 그루입니다. '에메랄드는 초록색이다'와 '에메랄드는 그루다'는 지금까지의 자료에 똑같이 맞지만, 그날 뒤에 처음 관찰할 에메랄드에 대해서는 서로 다르게 예측합니다. 앞의 가설은 초록을, 뒤의 가설은 파랑을 예측합니다. 우리말에서는 '초록'이 짧고 '그루'가 길지만, 그루와 '블린'(그날 전에 관찰되었고 파란색이거나, 그렇지 않고 초록색인 것)을 기본 낱말로 쓰는 언어에서는 '초록'이 도리어 긴 말이 됩니다. 단순함은 언어에 달려 있습니다. 이 문제는 글의 끝까지 따라옵니다. 수학이 해 줄 수 있는 일은, 언어를 하나 정해 두면 그다음부터 모든 것을 정확히 셀 수 있게 해 주는 것입니다.

사고의 경제는 면도날이 너무 날카로울 때의 위험도 보여 줍니다. 마흐는 눈으로도 기구로도 직접 볼 수 없는 원자를, 경험을 정리하는 데 필요 없는 가정으로 여겨 오랫동안 받아들이지 않았습니다. 그래서 원자의 운동으로 열과 기체를 설명하던 빈의 루트비히 볼츠만과 맞섰습니다. 마흐에게 원자는 더 짧은 설명이 아니라 군더더기로 보였던 것입니다. 1905년 아인슈타인은 물에 뜬 아주 작은 알갱이가 쉬지 않고 떨리는 브라운 운동⁠(Brownian motion)⁠을 분자의 충돌로 설명하고, 그 떨림의 크기로 분자의 크기를 잴 수 있다고 계산했습니다. 1908년 무렵 파리의 장 페랭이 그 떨림을 정밀하게 재어 예측을 확인하자, 원자를 의심하던 물리학자들 대부분이 돌아섰습니다. 원자라는 가정은 기체의 성질, 화학 반응의 정수 비, 브라운 운동처럼 따로 떨어져 있던 현상들을 하나로 묶어 주었으니, 그 표들을 함께 적으면 오히려 더 짧은 설명이었습니다. 면도날로 무엇을 잘라 낼지는 어떤 자료들을 함께 설명하려 하느냐에 달려 있습니다. 브라운 운동과 확산의 수학은 「라플라시안, 가장 많이 재사용된 식」에 있습니다.

오컴의 이름이 옥스퍼드에서 아비뇽과 뮌헨으로 옮겨 간 데에는 교회의 정치가 있었습니다. 1324년 그는 이단을 가르친다는 고발을 받아, 그 무렵 교황청이 있던 남프랑스의 아비뇽으로 불려 갔습니다. 심사를 기다리는 동안 프란치스코회는 교황 요한 22세와 '청빈 논쟁'에 휘말렸습니다. 예수와 사도들이 아무것도 소유하지 않았다는 수도회의 가르침을 교황이 받아들이지 않자, 오컴은 교황의 문서들을 검토한 끝에 교황 자신이 이단이라고 결론지었습니다. 1328년 5월 26일 밤 그는 수도회 총장 체세나의 미카엘 등과 함께 아비뇽을 빠져나가, 교황과 맞서던 신성 로마 제국 황제 바이에른의 루트비히에게 몸을 의탁했고 곧 파문되었습니다. 1347년 뮌헨에서 죽을 때까지 그가 쓴 글은 주로 정치에 관한 것이었습니다. 면도날이 나오는 『명제집』 주석 같은 철학과 신학의 글은 그 전에 쓴 것입니다.

면도날에서 법칙까지. 오컴이 옥스퍼드에서 아비뇽을 거쳐 뮌헨으로 간 길, 튀코가 벤섬을 떠나 프라하로 간 길, 그라츠의 케플러가 베나트키로 온 길을 보세요. 동쪽 끝의 다마스쿠스에는 등각속도점을 없앤 이븐 알샤티르가 있습니다. 철학 줄(보라)에는 펀치와 프루아몽, 라이프니츠가 이어집니다.

3 · 짧은 이름은 흔한 것에부호의 길이는 확률이다

이 절의 물음은 이것입니다. 설명의 '길이'와 설명이 옳을 '확률'은 어떤 관계일까? 둘이 같은 것이라면, 가장 짧은 설명을 고르는 일은 확률의 말로 무엇일까?

언어를 하나 정했다고 합시다. 그 언어로 쓴 설명들이 받는 쪽에서 한 가지로만 읽히려면, 어떤 설명도 다른 설명의 앞부분이 되어서는 안 됩니다(접두 부호⁠, prefix code⁠). 부호 0, 10, 110, 111이 그런 예입니다. 「짧게 보내기」 4절에서 본 크래프트 부등식⁠(Kraft inequality)⁠에 따르면 그런 부호의 길이 $\ell(x)$('x의 부호 길이')들은 언제나 $\sum_x 2^{-\ell(x)} \le 1$을 만족합니다. 부호마다 $2^{-(\text{길이})}$를 구해 모두 더하면 1 이하라는 뜻입니다. 네 부호의 길이 1, 2, 3, 3이라면 $\tfrac12 + \tfrac14 + \tfrac18 + \tfrac18 = 1$입니다.

그러니 길이를 정하는 일은 1이라는 몫을 나눠 주는 일이고, $q(x) = 2^{-\ell(x)}$는 합이 1 이하인 확률처럼 쓸 수 있습니다. 위의 네 부호는 차례로 확률 $\tfrac12, \tfrac14, \tfrac18, \tfrac18$을 준 셈입니다. 거꾸로 확률분포⁠(probability distribution)⁠ q가 있으면 길이 $\lceil -\log_2 q(x) \rceil$로 접두 부호를 만들 수 있습니다(⌈ ⌉는 올림입니다. 확률 0.3이면 $-\log_2 0.3 \approx 1.74$를 올려 2비트). 산술 부호화⁠(arithmetic coding)⁠를 쓰면 반올림 손해도 거의 없어서, 메시지 전체를 $-\log_2 q(\text{메시지})$보다 2비트 미만만 긴 길이로 적을 수 있습니다.

결론은 한 줄입니다. 부호의 길이와 확률은 같은 것의 두 이름입니다. 짧은 이름을 받은 것은 흔하다고 가정된 것이고, 흔하다고 가정한 것에는 짧은 이름을 줄 수 있습니다. 반올림에서 생기는 비트 한두 개를 빼면 '짧다'와 '확률이 높다'는 정확히 서로 바꿔 쓸 수 있는 말입니다. 섀넌의 원천 부호화 정리⁠(source coding theorem)⁠는 여기에, 그 확률이 실제 분포와 같을 때 평균 길이가 가장 짧아진다는 것을 덧붙입니다. 실제 분포가 p인데 q에 맞춘 부호를 쓰면, 반올림을 무시할 때 기호마다 평균 KL 발산⁠(KL divergence)⁠ $D(p\,\|\,q)$만큼 더 듭니다. 예를 들어 공정한 동전(앞 1/2, 뒤 1/2)을 앞이 3/4이라고 믿는 부호로 적으면 던질 때마다 평균 약 0.21비트를 더 씁니다.

이제 가설을 적어 봅시다. 자료 D를 설명하는 가설 H가 있을 때, 먼저 가설을 적고($L(H)$비트) 그다음 그 가설이 주는 확률로 자료를 적습니다. $P(D \mid H)$는 'H가 참일 때 자료 D가 나올 확률'이고, 위의 결론대로 그 확률로 자료를 적으면 $L(D \mid H) = -\log_2 P(D \mid H)$비트가 듭니다. 이것을 두 부분 부호⁠(two-part code)⁠라고 합니다. 1절의 '지수 17비트 + 잔차'가 바로 그것이었습니다.

가설을 적는 부호도 부호이니 $P(H) = 2^{-L(H)}$는 가설들 위의 확률, 곧 자료를 보기 전의 믿음인 사전확률로 읽을 수 있습니다. 17비트짜리 가설이라면 사전확률 $2^{-17}$입니다. 한편 베이즈 정리⁠(Bayes' theorem)⁠는 자료를 본 뒤의 믿음, 곧 사후확률 $P(H \mid D)$('D를 보았을 때 H가 참일 확률')를 이렇게 줍니다. $P(H \mid D) = P(H)\,P(D \mid H)/P(D)$. 말로 하면 '사후 = 사전 × 그 가설이 자료를 설명하는 정도 ÷ 자료 자체의 확률'입니다. 양변에 $-\log_2$를 씌우면 곱은 합으로, 나눗셈은 빼기로 바뀝니다($-\log_2 (xy) = -\log_2 x - \log_2 y$). 그 결과가 다음 식입니다.

왼쪽은 사후확률이 클수록 작아지는 값입니다. 오른쪽의 마지막 항 $\log_2 P(D)$에는 가설이 들어 있지 않으니 어느 가설에나 같습니다. 그러니 두 부분 부호의 길이가 가장 짧은 가설은 사후확률이 가장 큰 가설과 정확히 같습니다. 계산 한 줄이면 되는 정리입니다. 이 정리가 말하지 않는 것도 분명히 해 둡시다. 사전확률로 $2^{-L(H)}$를 쓰라는 것, 곧 짧게 적히는 가설을 더 믿으라는 것은 정리가 아니라 선택입니다. 오컴의 면도날은 이 선택의 이름입니다.

작은 예로 확인해 봅시다. 동전을 20번 던져 앞면이 14번 나왔습니다. 가설 '공정한 동전'으로 적으면 던질 때마다 1비트, 모두 20비트입니다. 가설 '치우친 동전'으로 적으려면 두 부분이 필요합니다. 먼저 가설 쪽으로, 앞면이 몇 번 나왔는지를 적습니다. 0부터 20까지 21가지 가운데 하나이니 $\log_2 21 \approx 4.39$비트입니다(2를 4.39번쯤 곱하면 21이 됩니다). 그다음 자료 쪽으로, 앞면 14개가 20자리 가운데 어느 자리에 있는지를 적습니다. 20자리에서 14자리를 고르는 방법은 이항계수⁠(binomial coefficient)⁠ $\binom{20}{14} = 38{,}760$가지이니, 그 가운데 몇 번째인지를 적는 데 $\log_2 38{,}760 \approx 15.24$비트가 듭니다. 합은 19.63비트로 공정한 동전보다 0.37비트 짧을 뿐입니다. 치우쳤다는 증거가 아주 약하다는 뜻입니다. 앞면이 16번이면 자리를 고르는 방법이 $\binom{20}{16} = 4{,}845$가지로 줄어 약 12.24비트가 되고, 합은 16.63비트로 3비트 넘게 짧아집니다. 이 계산은 최소 기술 길이⁠(minimum description length)⁠ 페이지의 그림에서 직접 해 볼 수 있습니다.

가설을 적는 값을 빼고 $L(D \mid H)$만 가장 작게 하면 최대가능도 추정이 됩니다. 최대가능도 추정은 자료가 나올 확률 $P(D \mid H)$를 가장 크게 하는 가설을 고르는 방법입니다. 앞면이 14번이면 최대가능도는 앞면의 확률이 0.7이라고 답하고, 그 가설로 적은 자료는 $-\log_2(0.7^{14} \times 0.3^{6}) = 14 \times 0.515 + 6 \times 1.737 \approx 17.63$비트로 공정한 동전의 20비트보다 짧습니다. 앞면이 정확히 10번이 아닌 한 늘 이렇습니다. 최대가능도만 보면 동전은 언제나 치우쳐 있는 셈입니다. 가설의 값을 치르지 않으면 가장 복잡한 가설이 늘 이깁니다. 이것이 5절과 6절에서 볼 과적합의 뿌리입니다.

정리하면, 짧은 부호는 높은 확률과 같은 말이고, '가설 + 가설로 적은 자료'의 길이를 가장 짧게 하는 것은 사전확률 $2^{-L(H)}$를 둔 베이즈 추론과 같습니다. 가설의 길이를 빼먹으면 늘 가장 복잡한 가설이 이깁니다.

이 선택을 확률의 말로 처음 분명히 적은 사람들은 1920년대 영국에 있었습니다. 1921년 수학자 도러시 린치와 지구물리학자 해럴드 제프리스는 「과학 탐구의 몇 가지 근본 원리에 관하여」에서, 단순한 법칙일수록 사전확률을 크게 주어야 한다는 '단순성 공준⁠(simplicity postulate)⁠'을 내세웠습니다. 논거는 셈이었습니다. 관측에 맞는 법칙은 늘 끝없이 많은데, 그 모두에게 똑같이 0보다 큰 사전확률을 주면 합이 1을 넘어 버립니다. 그러니 사전확률은 법칙들을 어떤 순서로 늘어놓고 뒤로 갈수록 줄어들어야 하고, 그 순서로 가장 그럴듯한 것이 단순함입니다. 크래프트 부등식이 부호의 길이에 대해 말하는 것과 같은 구조입니다. 다만 단순함을 재는 방법은 법칙에 든 매개변수⁠(parameter)⁠의 개수와 차수 같은 어림에 머물렀고, 부호의 길이라는 정확한 자는 섀넌 뒤에야 생겼습니다.

4 · 모든 프로그램에 거는 내기솔로모노프, 콜모고로프, 차이틴

사전확률을 정할 언어로 가장 넓은 것을 고르면 어떻게 될까요? 레이 솔로모노프는 시카고 대학에서 철학자 루돌프 카르나프에게 확률로 귀납을 설명하려는 시도를 배웠습니다. 1956년에는 '인공지능⁠(artificial intelligence)⁠'이라는 이름을 내건 첫 모임인 다트머스 워크숍에 여름 내내 머문 몇 안 되는 참가자 가운데 한 사람이었습니다. 그는 1960년의 보고서와 1964년 학술지 『인포메이션 앤드 컨트롤』에 두 부분으로 실은 논문 「귀납 추론⁠(inductive inference)⁠의 형식 이론」에서 이렇게 제안했습니다. 모든 계산을 흉내 낼 수 있는 보편 튜링 기계(어떤 프로그램이든 받아 실행하는 기계, 오늘날의 컴퓨터를 추상화한 것) 하나를 정하고, 그 기계의 프로그램을 모두 가설로 삼자. 길이가 ℓ비트인 프로그램에는 사전확률 $2^{-\ell}$를 주자. 출력이 지금까지의 자료로 시작하는 프로그램들만 남기고, 다음 기호는 남은 프로그램들의 가중 투표로 예측하자. 곧 남은 프로그램마다 사전확률만큼의 표를 주고, 다음 기호로 0을 내놓는 쪽과 1을 내놓는 쪽의 표를 비교합니다. 짧은 프로그램일수록 표가 많으니, 이것이 오컴의 면도날을 모든 프로그램에 적용한 것입니다.

작은 판으로 흉내 내 봅시다. 여기서 프로그램은 두 종류뿐입니다. 하나는 '길이 L인 무늬 p를 끝없이 되풀이하라'입니다. 이 프로그램은 되풀이 표시 1비트, L을 적는 L비트(0을 L−1개 쓰고 1), 무늬 L비트를 합쳐 $2L+1$비트이고, 사전확률은 $2^{-(2L+1)}$입니다. 예를 들어 '01 되풀이'는 L = 2이니 5비트이고 사전확률은 1/32입니다. 무늬는 8비트까지만 허락합니다. 다른 하나는 '동전 던지기', 곧 표시 1비트 뒤에 자료를 그대로 적는 프로그램으로, 사전확률 1/2에 비트마다 1/2이 곱해집니다. 모든 사전확률을 더하면 $1 - 2^{-9}$이니 크래프트 부등식이 지켜집니다(길이 L인 무늬 $2^L$가지의 사전확률을 더하면 $2^{-(L+1)}$이고, L = 1부터 8까지 더하면 $\tfrac12 - 2^{-9}$, 여기에 동전의 1/2을 더합니다). 비트를 하나씩 덧붙이며 혼합이 무엇을 믿는지 보세요. 볼 것은 가운데의 가설 목록에서 어느 가설이 맨 위로 올라오는지, 그리고 위 칸의 붉은 빛이 언제 사라지는지(비트를 적는 값이 싸지는지)입니다. 시작: 0 덧붙이기 1 덧붙이기 하나 지우기 비우기

지금 비트 개를 혼합으로 적으면 비트이고, 다음 비트가 1일 확률은 입니다.

'0101…'에서는 처음 몇 비트 동안 동전과 짧은 무늬들이 겨룹니다. '01 되풀이'는 5비트짜리 프로그램이고, 동전은 1비트에 자료 길이를 더한 길이입니다. 그래서 비트가 네 개일 때 둘이 비기고, 다섯 번째 비트부터 '01 되풀이'가 앞섭니다. 그 뒤로 혼합은 다음 비트를 거의 확신하고, 비트 하나에 드는 값은 0에 가까워집니다. 무늬를 알아낸 순간부터 자료가 거의 공짜가 되는 것입니다. 여기에 무늬를 깨는 비트를 하나 넣어 보세요. 그 비트 하나에 여러 비트를 치르고, 믿음은 동전이나 더 긴 무늬로 옮겨 갑니다. '0101'도 가설 목록에 함께 남아 있다는 것도 보세요. 같은 자료를 내는 더 긴 프로그램이니 사전확률이 16분의 1로 작을 뿐, 솔로모노프의 혼합은 이런 것들까지 모두 더합니다.

'π의 이진 전개⁠(binary expansion)⁠'는 이 작은 언어의 한계를 보여 줍니다. π를 이진수로 적으면 11.001001000011…이고, 소수점 아래를 자료로 씁니다. 처음 여덟 비트 00100100은 '001 되풀이'처럼 보이지만 아홉 번째 비트에서 깨지고, 그 뒤로는 어떤 짧은 무늬도 맞지 않아 동전이 이깁니다. 이 언어에서 π는 무작위입니다. 그러나 π의 자릿수를 계산하는 짧은 프로그램은 실제로 있습니다. 그래서 보편 튜링 기계⁠(universal Turing machine)⁠의 언어에서는 π의 앞 n비트를, n이 아무리 커도 n을 적는 약 $\log_2 n$비트에 일정한 상수를 더한 길이로 적을 수 있습니다. 무엇이 규칙으로 보이는지는 가설의 언어가 얼마나 넓은지에 달려 있습니다. 솔로모노프가 모든 프로그램을 가설로 삼은 까닭입니다.

진짜 솔로모노프 혼합에 대해서는 두 가지가 알려져 있습니다. 첫째는 좋은 소식입니다. 1978년 솔로모노프는 자료가 어떤 계산 가능한 확률 규칙 μ(뮤)를 따라 나올 때 이 혼합이 얼마나 빨리 배우는지를 증명했습니다. 계산 가능한 확률 규칙이란 '지금까지의 자료가 이러하면 다음 비트가 1일 확률은 얼마'를 어떤 프로그램으로 계산할 수 있는 규칙입니다. 걸음마다 혼합의 예측이 μ의 참 확률에서 벗어난 정도(차이의 제곱)를 재어 끝없이 더해도, 그 합의 기댓값(같은 일을 수없이 되풀이할 때 나오는 평균)은 유한합니다. 끝없이 더한 합이 유한하려면 더하는 값이 결국 0에 가까워져야 하니, 혼합은 언젠가부터 참 확률과 거의 같은 예측을 내놓는다는 뜻입니다. 이진 자료라면 그 값은 μ를 적는 가장 짧은 프로그램의 길이 K(μ)에 $\tfrac12\ln 2$를 곱한 값을 넘지 않습니다. 규칙이 짧을수록 빨리 배웁니다.

둘째는 나쁜 소식입니다. 이 혼합은 계산할 수 없습니다. 어떤 프로그램이 끝내 멈출지 미리 알 수 없다는 정지 문제⁠(halting problem)⁠ 때문에, 프로그램들을 모두 돌려 보고 투표를 셀 수가 없습니다. 프로그램을 더 오래 돌릴수록 참값에 아래에서 다가가는 어림은 만들 수 있지만, 언제 충분히 가까워졌는지 알 길이 없습니다. 위의 작은 판은 출력의 각 비트를 반드시 곧바로 내놓는 프로그램만 골랐기 때문에 계산할 수 있었습니다.

같은 무렵 두 사람이 따로 같은 곳에 닿았습니다. 1965년 모스크바의 안드레이 콜모고로프는 「정보의 양을 정의하는 세 가지 방법」에서 대상을 출력하는 가장 짧은 프로그램의 길이로 그 대상의 정보를 쟀고, 뉴욕의 10대 학생 그레고리 차이틴도 비슷한 생각을 담은 논문을 1966년에 발표했습니다. 이것이 콜모고로프 복잡도 $K(x)$입니다. 콜모고로프 복잡도는 대상 하나를 가장 짧게 적는 설명의 길이이고, 솔로모노프의 혼합은 그런 설명들 모두에 표를 나눠 준 것이니, 둘은 같은 생각의 두 얼굴입니다.

곧 한 가지 고침이 뒤따랐습니다. 처음의 정의에서는 한 프로그램이 다른 프로그램의 앞부분일 수 있어서, 프로그램마다 $2^{-\ell}$을 주면 그 합이 1을 넘을 수 있었습니다. 예를 들어 길이 1인 프로그램 0과 1이 둘 다 있고 길이 2인 00도 따로 있다면, 벌써 $\tfrac12 + \tfrac12 + \tfrac14$으로 1을 넘습니다. 솔로모노프의 혼합이 확률이 되려면 3절의 크래프트 부등식이 지켜져야 합니다. 1974년 콜모고로프의 제자 레오니드 레빈과 1975년 차이틴은 따로, 어떤 프로그램도 다른 프로그램의 앞부분이 되지 않는 기계로 복잡도를 다시 정의했습니다. 오늘날 $K(x)$라고 쓰면 대개 이 '접두 복잡도⁠(prefix complexity)⁠'를 뜻하고, 위의 작은 판이 프로그램의 길이를 적는 데 0과 1의 약속을 둔 것도 이 때문입니다.

기계를 바꾸면 값이 달라지지만, 그 차이는 x와 상관없는 상수(한 기계로 다른 기계를 흉내 내는 프로그램의 길이)를 넘지 않습니다. 이 불변성 덕분에 긴 자료에서는 언어의 선택이 거의 문제 되지 않습니다. 거꾸로 말하면 짧은 자료에서는 언어의 선택이 결과를 좌우할 수 있고, 2절의 '그루' 문제는 이 상수 안에 그대로 남아 있습니다. 비둘기집 원리⁠(pigeonhole principle)⁠에 따라 대부분의 문자열은 거의 줄일 수 없다는 것과 K 자체를 계산할 수 없다는 것은 「짧게 보내기」 8절에 있습니다.

정리하면, 모든 프로그램을 가설로 삼고 짧은 프로그램에 큰 사전확률을 주는 솔로모노프의 혼합은 계산 가능한 규칙이면 무엇이든 결국 배우지만, 그 자체는 계산할 수 없습니다. 그리고 언어(기계)를 고르는 문제는 상수만큼 남습니다.

5 · 두 부분 부호월리스의 메시지와 리사넨의 기술 길이

이 절의 물음은 이것입니다. 곡선 맞추기처럼 실제로 계산할 수 있는 문제에서, 모형을 적는 값을 몇 비트로 매겨야 할까? 그렇게 매기면 알맞은 복잡도가 저절로 골라질까?

솔로모노프의 혼합은 계산할 수 없지만, 그 생각은 계산할 수 있는 모양으로 통계학⁠(statistics)⁠에 들어왔습니다. 1968년 오스트레일리아 모내시 대학의 크리스 월리스와 데이비드 볼턴은 자료를 무리로 나누는 문제에서, 무리들을 적은 설명과 그 설명으로 적은 자료를 합친 '메시지'가 가장 짧은 분류를 고르자고 제안했습니다(최소 메시지 길이⁠, minimum message length⁠). 1978년 IBM 샌호세 연구소의 요르마 리사넨은 따로 같은 원리를 「가장 짧은 자료 기술로 모형 세우기」라는 논문에 내놓았고, 이것이 최소 기술 길이 원리입니다. 리사넨은 그보다 두 해 앞서 산술 부호화의 기초⁠(basics)⁠를 놓은 사람이기도 했습니다. 확률을 비트로 바꾸는 장치를 손에 쥔 사람이 모형도 비트로 재자고 한 것입니다.

모형을 적는 데는 몇 비트가 들까요? 다항식이라면 계수를 적어야 하는데, 계수를 소수점 아래 끝까지 적으려면 끝이 없습니다. 요점은 계수를 자료가 뒷받침하는 만큼만 정밀하게 적으면 된다는 것입니다. 점 n개로 추정한 계수에는 어차피 대략 $1/\sqrt n$에 비례하는 불확실성(표준오차⁠(standard error)⁠, 표본⁠(sample)⁠을 새로 뽑을 때마다 추정값이 흔들리는 정도)이 있으니, 그보다 정밀하게 적는 것은 낭비이고, 훨씬 거칠게 적으면 잔차가 커집니다. 둘을 저울질하면 계수 하나에 약 $\tfrac12 \log_2 n$비트가 알맞다는 것이 리사넨의 계산입니다. 뜻은 이렇습니다. 계수를 $1/\sqrt n$ 간격의 눈금으로 적으면, 일정한 범위 안에 눈금이 $\sqrt n$개쯤 있으니 그 가운데 하나를 고르는 데 $\log_2 \sqrt n = \tfrac12 \log_2 n$비트가 듭니다. 점이 30개면 약 2.5비트입니다.

잔차는 크기가 σ̂('시그마 햇', 잔차가 퍼진 정도를 자료에서 어림한 값)인 정규분포⁠(normal distribution)⁠의 잡음으로 보고 그 확률로 적습니다. 정규분포는 0 근처가 가장 흔하고 멀어질수록 드물어지는 종 모양의 분포이니, 작은 잔차는 싸고 큰 잔차는 비쌉니다. 모두 합하면 계수가 k개인 모형(차수가 d인 다항식이면 k = d + 1)의 기술 길이는 대략 다음과 같습니다.

앞 항은 계수 k개에 $\tfrac12 \log_2 n$비트씩입니다. 뒤 항은 점 n개의 잔차를 적는 값으로, 잔차가 퍼진 정도 σ̂가 클수록 커집니다. 2πe(약 17.08)는 정규분포에서 나오는 상수이고, δ는 자료를 적는 정밀도(여기서는 0.01)입니다. 잔차 항을 풀어 보면 어느 차수에나 똑같이 $n\log_2(1/\delta)$가 들어 있습니다. 그래서 δ를 바꾸면 모든 차수의 길이가 같은 양만큼 함께 움직이고, 어느 차수가 이기는지는 바뀌지 않습니다.

비슷한 벌점이 전혀 다른 길에서도 나왔습니다. 1978년 통계학자 기데온 슈바르츠의 베이즈 정보 기준(BIC)은 두 부분 부호와 같은 $\tfrac k2 \log n$의 벌점을 베이즈 추론의 어림에서 얻었습니다. 1973년 일본의 통계학자 아카이케 히로쓰구의 정보 기준(AIC)은 새 자료에서의 예측을 기준으로 계수 하나에 1나트(자연로그⁠(natural logarithm)⁠로 잰 정보의 단위, 약 1.44비트)의 벌점을 매겼습니다. 이런 공식들은 n이 클 때 맞는 어림이라는 것도 기억해 둡시다.

파란 점 30개는 매끄러운 곡선(회색 점선)에 크기 σ = 인 잡음을 더한 자료입니다. 이 점들에 차수가 인 다항식을 최소제곱⁠(least squares)⁠으로(잔차의 제곱을 모두 더한 값이 가장 작게) 맞추고, 차수마다 두 부분 부호의 길이를 셉니다. 점은 끌어서 옮길 수 있습니다. 새 표본 가장 짧은 차수로 차수를 0부터 9까지 바꿔 가며, 왼쪽의 노란 곡선이 점들을 얼마나 따라가는지와 오른쪽의 노란 선(전체 비트)이 어디서 가장 낮은지를 함께 보세요.

지금 차수에서는 모형 비트, 잔차 비트, 합해서 비트입니다. 기술 길이가 가장 짧은 차수는 차이고, 학습에 쓰지 않은 새 자료 400개에서 오차가 가장 작은 차수는 차입니다.

차수를 올리면 잔차 비트는 줄어듭니다. 곡선이 점들에 가까워지니까요. 그러나 줄어드는 폭은 점점 작아지는데 모형 비트는 계수 하나마다 약 2.5비트씩 꼬박꼬박 늘어납니다. 그래서 전체 길이는 3차에서 크게 떨어진 뒤(이 곡선을 따라가려면 3차 항이 필요합니다) 대체로 서서히 다시 올라갑니다. 1차와 2차가 거의 같다는 것도 보세요. 2차 항을 더해도 잔차가 2비트 남짓밖에 줄지 않으니, 그 계수를 적는 2.5비트와 엇비슷합니다. 새로 더한 계수는 그 값 이상으로 잔차를 줄여 줄 때에만 남습니다.

아카이케가 이 기준을 처음 영어로 발표한 곳은 1971년 9월 소련 아르메니아의 차흐카조르에서 열린 제2회 국제 정보 이론 심포지엄이었고, 논문집은 1973년 부다페스트에서 나왔습니다. 냉전 한가운데서 동서의 정보 이론가들이 모인 자리에서, 통계학의 모형 고르기가 정보의 말로 다시 적힌 것입니다.

6 · 외운 모형은 줄이지 못한다과적합, 규제, 교차 검증⁠(cross-validation)⁠

이 절의 물음은 이것입니다. 자료를 통째로 외운 모형은 왜 새 자료 앞에서 틀리고, 흔히 쓰는 처방들(규제, 교차 검증)은 압축의 말로 무엇을 하는 것일까?

이제 과적합을 압축의 말로 다시 읽을 수 있습니다. 「배우는 기계」 7절에서 점 10개를 모두 지나는 9차 다항식은 학습 오차가 0이었습니다. 두 부분 부호로 보면 이 모형은 잔차를 적는 비트가 거의 들지 않는 대신 계수 10개를 적어야 합니다. 점 10개를 적는 대신 계수 10개를 적는 것이니 거의 아무것도 줄지 않았습니다. 표를 그대로 보내면서 이름만 '모형'이라고 붙인 것입니다. 라이프니츠가 말한 '아무렇게나 찍은 점을 모두 지나는 선'이 바로 이것입니다. 과적합은 압축에 실패한 모형이고, 그래서 새 자료 앞에서 할 말이 없습니다.

과적합을 막는 흔한 방법인 규제(정규화라고도 합니다)도 같은 말로 읽힙니다. 규제는 맞추기 오차에 '계수가 크면 내는 벌점'을 더해, 둘의 합을 가장 작게 하는 계수를 고르는 방법입니다. 릿지 회귀⁠(ridge regression)⁠는 제곱 오차에 계수 제곱합의 벌점 $\lambda \sum_j c_j^2$를 더한 것을 최소화합니다. $c_j$는 j번째 계수이고, λ(람다)는 벌점의 세기입니다. 예를 들어 λ = 1이고 계수가 3과 −1이면 벌점은 9 + 1 = 10입니다.

왜 이것이 두 부분 부호일까요? 잡음이 분산(퍼진 정도의 제곱) σ²인 정규분포라면 $L(D \mid H)$는 제곱 오차를 $2\sigma^2 \ln 2$로 나눈 것에 상수를 더한 값이고, 벌점은 계수마다 평균 0, 분산⁠(variance)⁠ $\sigma^2/\lambda$인 정규분포의 사전확률을 준 것의 $-\log$와 같은 꼴입니다. 말로 풀면, 제곱 오차는 '가설로 적은 자료'의 비트이고, 계수 제곱합의 벌점은 '가설'의 비트입니다. 0에 가까운 계수를 흔하다고 믿는 사전확률을 두면, 큰 계수는 드문 것이라 적는 데 비트가 많이 듭니다. 그러니 릿지 회귀의 답은 그 사전확률을 둔 사후확률 최대의 답이고, 3절의 정리에 따라 '작은 계수에 짧은 이름을 주는' 부호로 쟀을 때 가장 짧은 설명입니다. 절댓값⁠(absolute value)⁠ 합의 벌점을 쓰는 라소⁠(lasso)⁠는 라플라스 분포(0에서 뾰족하게 솟고 양쪽으로 지수적으로 줄어드는 분포)의 사전확률에 해당합니다.

벌점의 세기 λ는 '계수가 얼마나 작을 것이라고 미리 믿는가'를 정하는 수입니다. 편향–분산 분해⁠(bias–variance decomposition)⁠로 말하면, 사전확률은 편향(평균적으로 한쪽으로 치우치는 오차)을 조금 받아들이는 대가로 분산(표본마다 답이 흔들리는 정도)을 줄입니다.

모형을 보내지 않고 압축하는 길도 있습니다. 보내는 쪽과 받는 쪽이 같은 학습 절차를 약속해 둡니다. 그리고 자료를 하나씩 보내면서, 그때까지 보낸 자료만으로 모형을 맞춰 다음 자료를 예측하고, 그 예측 확률로 부호화합니다. 받는 쪽도 같은 자료로 같은 모형을 맞출 수 있으니 모형을 따로 보낼 필요가 없습니다. 1984년 영국의 통계학자 필립 다위드가 '순차 예측(prequential)'이라고 이름 붙인 이 방식에서는, 복잡한 모형은 자료가 적은 초반에 엉뚱한 예측을 해서 값을 치릅니다. 모형의 값이 사라진 것이 아니라 '배우는 동안 틀린 예측'으로 모양을 바꾼 것입니다. 이것은 교차 검증과 같은 생각입니다. 교차 검증은 모형을 맞추는 데 쓰지 않은 자료로 성적을 매기고, 순차 예측은 늘 '아직 보지 않은 다음 자료'로 성적을 매깁니다. 그래서 기술 길이와 교차 검증은 가까운 친척입니다. 다만 늘 같은 답을 내지는 않습니다. 자료가 많을 때 하나씩 빼는 교차 검증은 AIC와 비슷하게, 기술 길이는 BIC와 비슷하게 행동합니다.

여기까지가 정리로 뒷받침되는 부분입니다. 이 방법들이 실제로 잘 되는 까닭은 정리가 아닙니다. '공짜 점심은 없다' 정리에 따르면, 모든 가능한 세계를 똑같이 중요하게 칠 때 어떤 학습 방법도 보지 못한 자료에서 다른 방법보다 낫지 않습니다. 그러니 짧은 설명을 고르는 방법이 실제로 잘 된다면, 그것은 우리가 사는 세계가 대체로 짧게 적히는 규칙을 따르기 때문일 것입니다. 이는 지금까지의 관찰이지 증명이 아닙니다.

이 벌점들에도 내력이 있습니다. 제곱합의 벌점은 거의 같은 무렵 두 곳에서 나왔습니다. 모스크바의 안드레이 티호노프는 1943년 흐린 자료에서 원인을 되찾는 역문제⁠(inverse problem)⁠가 왜 불안정한지를 짚었고, 1963년 이 벌점으로 그런 문제를 푸는 정규화 방법을 내놓았습니다. 화학 회사 듀폰의 공정 자료를 다루던 통계학자 아서 호얼은 1960년대 초 같은 벌점을 회귀 분석에 가져왔고, 1970년 로버트 케너드와 함께 '릿지 회귀'로 정리했습니다(「거꾸로 푸는 문제는 왜 어려운가」 5–6절). 라소는 1996년 토론토 대학의 로버트 팁시라니가 내놓았습니다.

7 · 예측한 만큼 줄어든다산술 부호화와 문맥 모형

이 절의 물음은 이것입니다. 예측을 잘하는 것과 짧게 적는 것이 정말 같은 일이라면, 예측기의 복잡도를 늘릴 때 무엇을 얻고 무엇을 치를까?

순차 예측이 곧 압축이라는 말을 직접 돌려 봅시다. 산술 부호화는 글자마다 예측 확률 q를 받아, 글 전체를 $\sum -\log_2 q$비트(글자마다의 놀람 $-\log_2 q$를 모두 더한 값)에 2비트 미만을 더한 길이로 적습니다. 다음 글자를 확률 1/2로 맞혔다면 그 글자에 1비트, 1/8로 맞혔다면 3비트가 드는 셈입니다. 이렇게 되면 압축의 성능은 오로지 예측의 성능입니다. 1951년 섀넌이 사람에게 다음 글자를 맞히게 해서 영어의 엔트로피⁠(entropy)⁠를 어림한 것도 같은 생각이었습니다(「말을 세는 기계」).

가장 단순한 예측기는 '앞의 k글자 다음에 무엇이 왔는가'를 세는 것입니다(n-그램⁠(n-gram)⁠, 마르코프 연쇄⁠(Markov chain)⁠). k를 차수라고 부릅시다. 0차는 문맥 없이 글자의 빈도만 보고, 2차는 앞 두 글자가 같았던 자리들의 빈도를 봅니다. 여기서는 글을 읽으면서 세기 때문에 처음에는 아무것도 모릅니다. 어떤 문맥에서 지금까지 n번 가운데 글자 c가 $n_c$번 나왔다면 c에 확률 $(n_c + \tfrac12)/(n + A/2)$를 줍니다(A는 글에 쓰인 글자의 가짓수). 처음 보는 문맥에서는 모든 글자에 확률을 고르게 나누고, 셀수록 예측이 날카로워집니다. 예를 들어 글자가 50가지인 글에서 어떤 문맥을 10번 보았고 그 가운데 e가 7번 왔다면, 다음 e의 확률은 (7 + 0.5) ÷ (10 + 25) ≈ 0.21입니다. 아직 10번밖에 못 보았으니, 70%라고 단정하지 않고 보지 못한 글자들에게도 몫을 남겨 둔 것입니다. 글: , 차수: , 방식: , 보는 곳:

이 글은 글자를 가지 쓰니, 모든 글자에 같은 길이를 주면 글자당 비트입니다. 지금 차수는 글자당 비트이고, 가장 짧은 차수는 차(비트), 일곱 차수를 모두 섞으면 비트입니다.

'차수마다 따로 배우기'로 다윈의 글을 읽으면 1차가 가장 좋고, 2차부터는 오히려 나빠집니다. 영어에서 앞의 두세 글자가 다음 글자를 훨씬 잘 알려 준다는 것은 분명한데 왜 그럴까요? 위의 칸에서 '처음 480글자'를 고르고 차수를 4쯤으로 올려 보세요. 거의 모든 칸이 분홍빛입니다. 4차 모형은 문맥의 가짓수가 너무 많아서, 약 6,000글자로는 대부분의 문맥을 한두 번밖에 보지 못합니다. 처음 보는 문맥마다 50가지 글자에 확률을 고르게 나누니 매번 크게 놀랍니다. 복잡한 모형은 배우는 데 자료가 많이 들고, 순차 예측에서는 그 값이 초반의 놀람으로 청구됩니다. 5절의 계수 비용이 다른 모양으로 나타난 것입니다. 아래 그래프에서 0차는 일찍 자리를 잡지만 더 내려가지 못하고, 높은 차수는 높은 곳에서 출발해 천천히 내려옵니다. 글이 훨씬 길다면 높은 차수가 결국 앞지를 것입니다.

방식을 '짧은 문맥에 기대기'로 바꾸면 사정이 달라집니다. 이 방식은 문맥을 처음 보거나 조금밖에 보지 못했을 때, 확률을 고르게 나누는 대신 한 차수 낮은 모형의 예측을 빌려 옵니다(확률을 $(n_c + 2q)/(n + 2)$로 줍니다. q는 한 차수 낮은 모형이 준 확률). 문맥을 한 번도 보지 못했으면(n = 0) 확률은 그대로 q이고, 많이 볼수록 직접 센 비율 $n_c/n$에 가까워집니다. '긴 문맥에서도 짧은 문맥에서와 비슷한 일이 일어날 것'이라는 사전확률을 둔 셈이니, 6절의 규제와 같은 구실을 합니다. 이제 3차가 가장 좋아지고, 더 높은 차수도 크게 나빠지지 않습니다. 1984년 존 클리어리와 이언 위튼이 발표한 PPM(부분 일치에 의한 예측⁠, prediction by partial matching⁠)은 이런 기대기를 체계적으로 한 압축 방법으로, 오랫동안 글 압축에서 가장 좋은 성적을 냈습니다.

'같은 글자를 뒤섞은 것'을 골라 보세요. 글자의 빈도는 그대로이고 순서만 무작위입니다. 0차 모형은 순서를 전혀 보지 않으니 원래 글에서와 비트 수가 정확히 같습니다(지금 방식으로 글자당 비트). 그러나 문맥을 보는 모형은 모두 나빠집니다. 찾을 문맥이 없으니 문맥을 셀수록 헛수고입니다. 원래 글에서 1차나 3차가 0차보다 아낀 비트만큼은 다윈의 글에 '순서의 규칙'이 들어 있다는 뜻입니다. 더 좋은 모형은 그보다 많이 찾아낼 테니, 이것은 규칙의 양의 아래쪽 어림입니다. '마지막 문단을 두 번'을 고르고 '짧은 문맥에 기대기'로 두면, 이번에는 가장 높은 차수가 가장 좋아집니다. 두 번째 사본에서는 긴 문맥이 다음 글자를 거의 확실히 알려 주어 칸들이 어두워집니다. 「짧게 보내기」 5절의 렘펠–지브 압축⁠(Lempel–Ziv compression)⁠이 되풀이를 참조로 바꾸던 것과 같은 효과입니다.

흰검은 점선은 차수를 고르지 않고 일곱 차수를 모두 쓰는 방법입니다. 차수마다 사전확률 1/7을 주고, 글자마다 지금까지 잘 맞혀 온 차수의 말을 더 믿는 베이즈 혼합입니다. 이 혼합의 길이는 어떤 글에서든 가장 좋은 차수보다 $\log_2 7 \approx 2.81$비트 넘게 길어지지 않습니다. 까닭은 한 줄입니다. 혼합이 글 전체에 주는 확률은 $\tfrac17\sum_k 2^{-L_k}$이고, 이것은 가장 큰 항 $\tfrac17\, 2^{-L_{\min}}$보다 크거나 같으니 길이는 $L_{\min} + \log_2 7$보다 길 수 없습니다. 지금 글에서는 가장 좋은 차수보다 글 전체에서 비트 깁니다. 상한⁠(upper bound)⁠에 거의 붙어 있는 것은 가장 좋은 차수가 다른 차수들을 수백 비트 넘게 앞서서, 나머지 항이 합에 거의 보태지 못하기 때문입니다. 그래도 글자당으로 치면 없는 것과 같습니다. 어느 차수가 좋을지 미리 몰라도 된다는 뜻이고, 4절의 솔로모노프 혼합은 이 생각을 모든 프로그램으로 넓힌 것입니다.

정리하면, 산술 부호화를 거치면 글자마다 준 예측 확률이 곧 비트 수이고, 복잡한 예측기는 배우는 동안의 놀람으로 제 값을 치릅니다. 그 값보다 많이 아껴 줄 때에만 복잡함이 이득입니다.

산술 부호화는 1976년 리사넨과 스탠퍼드의 리처드 파스코가 따로 기초를 놓았고, 1987년 이언 위튼, 래드퍼드 닐, 존 클리어리가 누구나 쓸 수 있는 프로그램으로 정리했습니다.

8 · 기계에게 시킨 압축후터 상과 언어 모델

이 절의 물음은 이것입니다. 두 부분 부호의 셈을 실제 기계들에 그대로 적용하면, 흔한 압축 프로그램과 큰 언어 모델 가운데 어느 쪽이 더 짧은 설명일까?

2006년 8월 컴퓨터 과학자 마르쿠스 후터는 영어 위키백과의 앞부분 1억 바이트(enwik8)를 가장 작게 압축하는 사람에게 모두 5만 유로의 상금을 걸었습니다. 2020년 2월에는 자료를 10억 바이트(enwik9)로, 상금 총액을 50만 유로로 늘렸고, 이전 기록보다 1% 줄일 때마다 5,000유로를 줍니다. 후터는 잘 압축하려면 글에 담긴 지식을 이해해야 하고 그래서 압축이 지능을 재는 한 방법이 된다고 보았습니다. 이것은 그의 논제이지 정리가 아닙니다.

규칙에서 눈여겨볼 것은 심사하는 크기가 압축한 파일과 풀기 프로그램을 합친 크기라는 점입니다. 두 부분 부호를 규칙으로 못 박은 것입니다. 모형을 풀기 프로그램 속에 숨기면 그 크기가 그대로 셈에 들어갑니다. 풀기에 쓰는 시간과 메모리에도 제한이 있습니다.

같은 자료를 두고 흔한 압축 프로그램, 대회 기록, 그리고 큰 언어 모델을 한 줄에 놓아 봅시다. 막대는 잰 크기입니다.

렘펠–지브 참조를 쓰는 gzip은 원래의 32%, xz는 20%, 수많은 예측기를 섞는 cmix는 11%쯤입니다. 후터 상의 공식 기록은 2024년 9월에 세워진 카이도 오라브와 바이런 놀의 fx2-cmix로, 풀기 프로그램까지 합쳐 110,793,128바이트(원래의 약 11.1%)입니다.

2023년 9월 구글 딥마인드의 그레구아르 델레탕 등은 「언어 모델링은 압축이다」라는 논문에서, 글로 훈련한 언어 모델 친칠라(매개변수, 곧 훈련으로 맞춘 수가 700억 개)의 예측을 산술 부호화에 넣어 enwik9를 압축했습니다. 결과는 원래 크기의 8.3%로 막대들 가운데 가장 짧습니다. 그런데 모형까지 넣어 재면 이야기가 뒤집힙니다. 매개변수 700억 개를 2바이트씩 적은 140GB가 모형이니, 합치면 원래 파일의 14,008%, 곧 140배가 됩니다. 저자들도 이 '보정한 압축률'을 표에 함께 싣고, 이런 모형은 테라바이트 규모의 자료를 압축할 때에야 모형의 크기를 넘어서는 이득이 난다고 지적했습니다. 1GB의 자료를 설명하려고 140GB의 설명을 들고 온 것이니, 두 부분 부호로 재면 표를 그대로 보내는 것보다도 140배 긴 설명입니다. 게다가 친칠라의 훈련 자료에는 위키백과가 들어 있었다고 저자들이 밝혔으니, 8.3% 가운데 얼마가 규칙을 안 덕이고 얼마가 본 것을 기억한 덕인지 이 숫자만으로는 가릴 수 없습니다. 이 모델은 자료를 2,048바이트씩 끊어서, 앞 조각의 문맥 없이 압축했다는 점도 덧붙여 둡니다.

모형을 보내지 않는 길도 있습니다. 파브리스 벨라르의 nncp는 오늘날 언어 모델이 쓰는 신경망⁠(neural network)⁠ 구조인 트랜스포머⁠(transformer)⁠를 미리 훈련하지 않고 파일을 읽으면서 처음부터 훈련합니다. 푸는 쪽도 같은 순서로 같은 훈련을 되풀이하니 가중치⁠(weight)⁠를 보낼 필요가 없습니다. 대신 계산 결과가 똑같이 나오도록 같은 하드웨어와 소프트웨어를 써야 합니다. 프로그램은 1MB도 되지 않습니다. 6절의 순차 예측을 그대로 기계로 옮긴 것이고, 이 방식으로 enwik9를 10.7%까지 줄였습니다. 모형의 크기를 정직하게 셈에 넣으면 '큰 모형'이 저절로 이기지 않습니다. 델레탕 등은 작은 트랜스포머들로 실험해, 자료의 양마다 보정한 압축률이 가장 좋은 모형 크기가 따로 있다는 것도 보였습니다. 모형의 크기와 자료의 양 사이의 균형은 규모의 법칙⁠(scaling laws)⁠이 다루는 문제이기도 합니다.

그렇다고 '언어 모델은 압축기다'라는 말이 틀린 것은 아닙니다. 언어 모델은 다음 토큰⁠(token)⁠의 확률을 내놓도록 훈련되고, 훈련 목표는 교차 엔트로피입니다. 교차 엔트로피⁠(cross-entropy)⁠는 모델이 실제로 나온 다음 토큰에 준 확률 q로 $-\log q$를 구해 평균한 값이고, 보통 자연로그의 단위인 나트로 잽니다. 여기에 토큰 수를 곱하고 비트로 바꾸면, 모델의 예측으로 훈련 글을 산술 부호화했을 때의 길이와 2비트 미만으로만 다릅니다(「다음 단어를 맞히는 기계」). 훈련은 곧 훈련 글을 짧게 적는 법을 찾는 일입니다. 다만 짧게 적은 것을 '이해'라고 부를 수 있는지는 모형을 적는 값을 어떻게 셈하느냐에 달려 있고, 그 셈을 빼먹으면 외운 것과 배운 것을 구별할 수 없습니다.

후터는 2000년 스위스 루가노의 인공지능 연구소 IDSIA에서, 4절의 솔로모노프 혼합으로 세상을 예측하고 그 예측 아래 앞으로 받을 보상이 가장 큰 행동을 고르는 이론상의 행위자 AIXI를 내놓은 사람이기도 합니다. 솔로모노프 혼합처럼 AIXI도 계산할 수 없습니다.

기술 길이의 시대. 케임브리지(매사추세츠), 모스크바, 뉴욕에서 따로 태어난 알고리즘⁠(algorithm)⁠ 정보 이론이 멜버른과 샌호세의 통계학으로, 그리고 압축 대회와 언어 모델로 이어지는 것을 보세요.

9 · 압축은 이해인가정리와 철학 사이

이제 제목의 물음으로 돌아갑니다. 압축하는 것은 정말 이해하는 것일까? 답하려면 이 글에서 증명된 것과 증명되지 않은 것을 나눠 놓아야 합니다. 증명된 것부터 모아 봅시다.

부호의 길이와 확률은 비트 한두 개의 반올림을 빼면 서로 바꿔 쓸 수 있습니다(크래프트 부등식과 산술 부호화). 두 부분 부호의 길이를 가장 짧게 하는 가설은 사전확률 $2^{-L(H)}$를 둔 사후확률 최대의 가설입니다. 여러 모형의 베이즈 혼합은 가장 좋은 모형보다 그 모형에 준 사전확률의 $-\log_2$를 넘게 길어지지 않습니다. 대부분의 문자열은 거의 줄일 수 없고, 가장 짧은 설명의 길이는 계산할 수 없습니다. 자료가 계산 가능한 확률 규칙에서 나온다면, 솔로모노프의 혼합이 내는 총오차의 기댓값⁠(expected value)⁠은 그 규칙의 길이에 비례하는 유한한 값을 넘지 않고, 혼합은 참 확률을 따라잡습니다.

증명되지 않은 것도 있습니다. 세계가 짧게 적히는 규칙을 따른다는 것, 그래서 오늘 가장 짧은 설명이 내일도 맞으리라는 것은 관찰이자 믿음입니다. 1748년 흄이 던진 귀납의 문제가 여기 그대로 남아 있습니다. 면도날이 지금까지 잘 통했다는 것을 근거로 앞으로도 통하리라고 말하면, 귀납으로 귀납을 정당화하는 셈이기 때문입니다(「배우는 기계」 7절). 무엇이 짧은지는 언어에 따라 달라지고, 콜모고로프 복잡도의 불변성 정리⁠(invariance theorem)⁠는 그 차이를 상수로 묶어 줄 뿐 없애 주지 않습니다. 그리고 '이해'라는 말은 압축보다 넓습니다. 잘 압축하는 모형이 그 규칙을 사람이 읽을 수 있는 말로 내놓는다는 보장은 없습니다. 케플러의 세 줄은 짧기도 했지만 사람이 읽을 수 있었고, 그래서 뉴턴이 다음 질문을 던질 수 있었습니다. 가중치 수천억 개로 된 압축기는 짧을 수는 있어도 그대로 읽을 수는 없습니다.

그래도 두 부분 부호는 '이해'에 대해 쓸모 있는 말을 하나 남깁니다. 설명은 두 부분으로 나뉩니다. 모형에 들어간 것은 자료의 규칙이고, 잔차에 남은 것은 (지금으로서는) 우연입니다. 콜모고로프는 1970년대의 강연에서 이 나눔을 수로 다루는 '구조 함수⁠(structure function)⁠'를 제안했습니다. 이 관점에서 동전을 던져 얻은 비트열은 줄일 수 없으니 정보는 가장 많지만 그 정보는 거의 모두 잔차입니다. 반면 케플러의 표는 줄이고 나면 정보는 적지만, 그 상당 부분이 모형에 들어갑니다. 1절의 그래프에서 노란 띠가 케플러가 이해한 것이고, 파란 선 아래에 남은 것이 아직 이해하지 못한 것입니다. 뉴턴의 이론은 그 파란 부분의 일부가 우연이 아니라 행성의 질량이라고 알려 주었습니다. 이해가 깊어진다는 것은 잔차에서 모형으로 비트를 옮기는 일입니다.

10 · 이어지는 길짧은 설명이 닿는 곳

• 정보 이론으로: 부호 길이와 확률을 잇는 크래프트 부등식, 엔트로피가 정하는 압축의 한계, 허프만 부호⁠(Huffman coding)⁠와 렘펠–지브 압축은 「짧게 보내기」에 있습니다. 이 글은 그 한계를 '모형이 얼마나 좋은가'를 재는 자로 바꿔 쓴 것입니다.
• 최소제곱으로: 잡음이 정규분포라면 잔차를 적는 비트는 잔차의 제곱합으로 정해지니, 제곱합을 최소화하는 것은 곧 잔차를 가장 짧게 적는 것입니다. 가우스가 세레스의 궤도를 되찾으며 쓴 최소제곱과 오차의 법칙은 「잃어버린 소행성」에 있고, 그 이야기도 케플러의 타원에서 시작합니다. 행성의 거리를 수열 하나로 줄인 티티우스–보데 규칙이 어떻게 천문학자들을 세레스 사냥에 나서게 했는지도 그 글 7절에 있습니다.
• 역문제로: 6절의 릿지 벌점은 티호노프가 불안정한 역문제를 붙잡으려고 쓴 벌점과 같은 식이고, 거기서도 벌점은 곧 사전확률입니다. 흐린 사진과 CT, 블랙홀 사진까지 이어지는 그 이야기는 「거꾸로 푸는 문제는 왜 어려운가」에 있습니다.
• 물리로: 마흐가 군더더기로 여긴 원자가 브라운 운동의 떨림으로 드러난 과정, 곧 아인슈타인과 페랭의 확산 이야기는 「라플라시안, 가장 많이 재사용된 식」에 있습니다.
• 학습으로: 과적합, 교차 검증, 규제, 흄의 귀납 문제는 「배우는 기계」 7절에 있습니다. 이 글의 두 부분 부호는 그 세 가지를 '모형의 값'이라는 한 가지 셈으로 묶습니다.
• 언어 모델로: 다음 토큰의 확률, 교차 엔트로피와 퍼플렉시티⁠(perplexity)⁠, BPE가 압축에서 온 내력, 그리고 규모의 법칙이 무엇을 측정했는지는 「다음 단어를 맞히는 기계」에 있습니다. 모델의 크기를 셈에 넣느냐에 따라 같은 모델이 최고의 압축기도, 최악의 압축기도 된다는 것이 이 글이 보탠 관점입니다.
• 계산으로: 콜모고로프 복잡도를 계산할 수 없는 까닭인 정지 문제, 그리고 같은 논증으로 얻는 차이틴의 불완전성 정리⁠(incompleteness theorem)⁠는 「기계가 풀 수 없는 문제」로 이어집니다. 과학 이론을 '자료의 가장 짧은 설명'으로 본다면, 가장 좋은 압축기를 기계적으로 찾을 수 없다는 것은 가장 좋은 이론을 기계적으로 찾을 수 없다는 말이기도 합니다.
• 말로: 앞의 몇 글자로 다음 글자를 세는 n-그램과 마르코프 연쇄, 낱말의 빈도가 순위에 반비례한다는 지프의 법칙(지프는 흔한 낱말일수록 짧다는 것도 관찰했습니다)은 「말을 세는 기계」에 있습니다. 그 글은 언어 자체가 오랜 세월 쓰이며 다듬어진 압축이라는 관점으로도 읽을 수 있습니다.
• 확률로: 사전확률과 사후확률을 잇는 베이즈 정리와 베이즈, 라플라스의 확률 이야기는 「도박판에서 온 편지」에서 시작합니다. 사전확률을 '부호를 미리 약속하는 일'로 읽으면, 주관적 믿음이라는 오래된 비판에 다른 답을 할 수 있습니다. 약속은 누구나 확인할 수 있으니까요.
• 큰 생각⁠(big ideas)⁠으로: 줄일 수 없는 것을 무작위라 부르는 무작위성, 같은 대상을 더 짧게 적는 좌표를 찾는 표현 바꾸기, 잔차와 모형 사이의 저울질인 최적화⁠(optimization)⁠가 모두 이 글과 만납니다.