최소 기술 길이(Minimum description length)

동전을 20번 던져 앞면이 14번 나왔습니다. 이 기록을 친구에게 비트로 보낸다고 합시다. '공정한 동전'이라고 보면 던질 때마다 1비트, 모두 20비트입니다. '치우친 동전'이라고 보면 먼저 앞면이 몇 번인지(0부터 20까지 21가지, $\log_2 21 \approx 4.39$비트)를 보내고, 그다음 앞면 14개가 어느 자리에 있었는지를 $\binom{20}{14} = 38{,}760$가지 가운데 하나로 보냅니다($\log_2 38{,}760 \approx 15.24$비트). 합은 19.63비트, 공정한 동전보다 0.37비트 짧습니다. 두 설명의 차이가 이렇게 작다면 '치우쳤다'는 주장의 근거도 그만큼 약합니다.

최소 기술 길이(MDL) 원리는 이 셈을 원칙으로 삼습니다. 자료 D를 설명하는 가설 H마다 먼저 가설을 적는 길이 $L(H)$를 세고, 그 가설이 주는 확률로 자료를 적는 길이 $L(D \mid H) = -\log_2 P(D \mid H)$를 더합니다. 이 '두 부분 부호⁠(two-part code)⁠'의 길이가 가장 짧은 가설을 고릅니다. 둘째 항만 보면 무슨 일이 생기는지가 이 원리의 요점입니다. 자료의 확률을 가장 크게 만드는 가설을 고르는 최대가능도 추정이 바로 그렇게 합니다. 앞면 비율을 그대로 앞면 확률로 쓰는 '치우친 동전'은 자료에 공정한 동전보다 늘 크거나 같은 확률을 주므로, 최대가능도는 앞면이 정확히 절반이 아닌 한 늘 치우친 동전을 고릅니다. 가설의 값을 치르지 않으면 조절할 손잡이가 많은 가설이 늘 이깁니다.

이 원리는 1978년 IBM 샌호세 연구소의 요르마 리사넨이 내놓았습니다. 그보다 앞선 1968년, 오스트레일리아의 크리스 월리스와 데이비드 볼턴이 분류 문제에서 아주 가까운 생각을 발표했고, 이것은 뒤에 '최소 메시지 길이(MML)'라는 이름으로 불리게 됩니다. 두 흐름의 뿌리는 1960년대의 콜모고로프 복잡도⁠(Kolmogorov complexity)⁠와 레이 솔로모노프의 귀납 이론에 있습니다.

던진 횟수 $n =$ , 앞면의 수 로 바꾸어 가며 두 설명의 길이를 비교해 보세요. 그림의 노란 점을 좌우로 끌어도 앞면의 수가 바뀝니다. 앞면 수가 절반에서 멀어질수록 노란 곡선이 분홍 선 아래로 내려갑니다. 20번 던졌다면 앞면이 6번 이하이거나 14번 이상일 때만 '치우쳤다'는 설명이 더 짧습니다.

공정한 동전은 비트, 치우친 동전은 비트, 가설의 값을 뺀 최대가능도는 비트입니다.

이 원리가 왜 그럴듯한지는 세 가지 사실로 설명됩니다. 첫째는 길이와 확률이 서로 바뀐다는 사실입니다. 받는 쪽이 한 가지로만 끊어 읽을 수 있는 부호라면, 낱말 길이들은 크래프트 부등식⁠(Kraft inequality)⁠ $\sum 2^{-\ell} \le 1$을 만족합니다. 그래서 길이 $\ell$은 합이 1을 넘지 않는 확률 $2^{-\ell}$로 읽을 수 있습니다. 거꾸로 확률 q를 주면 길이가 $-\log_2 q$보다 1비트 이내로 긴 부호를 만들 수 있습니다(원천 부호화 정리⁠(source coding theorem)⁠, 산술 부호화⁠(arithmetic coding)⁠).

둘째, 그렇게 읽으면 두 부분 부호는 베이즈 추론이 됩니다. $L(H) = -\log_2 P(H)$로 두고 베이즈 정리⁠(Bayes' theorem)⁠에 로그를 씌우면 $-\log_2 P(H \mid D) = L(H) + L(D \mid H) + \log_2 P(D)$입니다. 마지막 항은 가설과 상관없으니, 두 부분 부호가 가장 짧은 가설은 사전확률 $2^{-L(H)}$를 둘 때 사후확률이 가장 큰 가설과 같습니다.

셋째, 위의 '개수를 적고 배치를 적는' 부호는 아무렇게나 고른 것이 아닙니다. 앞면의 확률 p를 0과 1 사이에서 고르게 퍼진 것으로 보고, 자료의 확률을 모든 p에 대해 평균⁠(mean)⁠하면(이것을 베이즈 주변 확률이라 합니다) $\int_0^1 p^h (1-p)^{n-h}\,dp = 1/\bigl((n+1)\binom{n}{h}\bigr)$입니다. 여기에 $-\log_2$를 씌운 값이 바로 $\log_2(n+1) + \log_2\binom{n}{h}$, 곧 이 부호의 길이입니다. 스털링 공식⁠(Stirling's formula)⁠으로 펼치면 이 길이는 최대가능도의 길이에 약 $\tfrac12 \log_2 n$비트를 더한 것입니다. 앞면 비율이 0이나 1에 붙어 있지 않으면, 나머지 차이는 n이 커져도 자라지 않습니다. 매개변수⁠(parameter)⁠ 하나의 값이 $\tfrac12 \log_2 n$비트라는 리사넨의 어림, 그리고 같은 해 기데온 슈바르츠가 낸 베이즈 정보 기준(BIC)의 벌점이 이것입니다.

흔한 오해가 셋 있습니다. 하나, 부호는 자료를 보기 전에 정해야 합니다. 자료를 본 뒤 그 자료에 짧은 이름을 붙이는 부호를 만들면 무엇이든 1비트로 '설명'할 수 있습니다. 그 부호 자체를 받는 쪽에 보내야 한다는 것을 잊은 것이고, 이것이 과적합의 가장 노골적인 모양입니다. 둘, MDL은 참 모형이 있다고 가정하지 않습니다. 사인⁠(sine)⁠ 곡선에 잡음이 섞인 자료에 다항식⁠(polynomial)⁠을 맞출 때처럼 어느 후보도 참이 아니어도, 주어진 자료를 가장 짧게 적는 후보를 고를 뿐입니다. 리사넨이 줄곧 강조한 점입니다. 셋, '가장 짧은 설명이 참일 가능성이 높다'는 것은 정리가 아닙니다. 정리는 '짧음'을 '사전확률'로 바꿔 읽을 수 있다고 말할 뿐입니다. 짧게 적히는 가설을 더 믿어야 한다는 것은 과적합을 피하려는 선택이자, 우리 세계가 지금까지 대체로 그래 왔다는 관찰입니다. 무엇이 짧은지는 어떤 부호(언어)를 쓰느냐에 따라서도 달라집니다.

위의 두 부분 부호는 거친 판입니다. 1990년대 이후의 MDL은 모형의 값을 더 정확히 세는 부호를 씁니다. 모든 가능한 자료에서 최대가능도가 받는 확률을 모아 정규화한 '정규화된 최대가능도⁠(normalized maximum likelihood)⁠' 부호, 그리고 모형을 보내지 않고 자료를 하나씩 앞의 자료로 예측하며 적는 순차 예측⁠(prequential prediction)⁠ 부호가 대표적입니다. 뒤의 것에서는 복잡한 모형이 자료가 적은 초반에 엉뚱한 예측으로 값을 치릅니다. 모형을 아직 보지 못한 자료로 평가한다는 점에서 교차 검증⁠(cross-validation)⁠과 닮은 생각입니다.

이어지는 곳. 다항식의 차수를 고를 때 계수 비트와 잔차⁠(residual)⁠ 비트가 저울질되는 모습, 케플러의 셋째 법칙이 행성 표를 몇 비트 줄이는지, 문맥 모형과 언어 모델⁠(language model)⁠을 압축기로 재는 이야기는 긴 글 「압축하는 것이 이해하는 것이다」에 있습니다. 가설을 적는 길이를 사전확률로 읽으면 규제의 벌점은 사전확률에 음의 로그를 씌운 것이 됩니다. 릿지는 계수에 정규분포⁠(normal distribution)⁠를, 라소⁠(lasso)⁠는 라플라스 분포⁠(Laplace distribution)⁠를 사전확률로 둔 셈이니, 둘이 왜 과적합을 억누르는지가 이 원리로 설명됩니다. 모형의 값과 잔차의 값을 맞바꾸는 저울질은 편향–분산 분해⁠(bias–variance decomposition)⁠가 오차의 말로 하는 이야기와 닮았습니다. 부호 길이의 바탕인 엔트로피⁠(entropy)⁠와 KL 발산⁠(KL divergence)⁠은 잘못된 모형을 쓸 때 몇 비트를 더 치르는지 알려 주고, 가능한 모든 프로그램으로 가설의 범위를 넓히면 콜모고로프 복잡도와 솔로모노프의 보편 예측이 되는데, 그 대가는 정지 문제⁠(halting problem)⁠ 때문에 계산할 수 없게 된다는 것입니다. 개수를 적고 배치를 적는 부호의 뼈대는 이항계수⁠(binomial coefficient)⁠입니다. n이 크면 $\log_2\binom{n}{h}$는 n에 앞면 비율의 엔트로피를 곱한 값에 가까워집니다. 그리고 큰 수의 법칙⁠(law of large numbers)⁠이 앞면 비율을 참 확률 가까이로 모으니, 이 길이는 원천 부호화 정리가 말하는 한계에 다가갑니다.