혼동하기 쉬운 점과 요약

코드 길이: 예측기가 곧 압축기

토론 1. 짧은 번호를 더 주면 긴 번호는 몇 개나 남나

분식집 키오스크는 메뉴 번호를 누르는 순간 주문이 들어간다(확인 단추가 없다). 번호를 0~9로 적을 때, 메뉴 셋에 한 자리 번호를, 나머지 72가지에 두 자리 번호를 줄 수 있는가?

분식집 키오스크는 메뉴 번호를 누르는 순간 주문이 들어가요. 떡볶이, 김밥, 라면처럼 많이 팔리는 셋에는 한 자리 번호를, 나머지 72가지에는 두 자리 번호를 주고 싶어요. 될까요?

떡볶이 1, 김밥 2, 라면 3을 주고요. 두 자리는 10부터 99까지 90개나 있으니까 72개는 넉넉하죠.

손님이 「15」를 누르려고 1을 누르면 무슨 일이 생기죠?

1을 누르는 순간 떡볶이가 주문돼요. 아, 1, 2, 3으로 시작하는 두 자리는 못 쓰네요. 그럼 40부터 99에 00~09까지 더해서 70개요. 두 개 모자라요.

한 자리 번호를 다른 숫자로 바꿔 보면 어떨까요? 1, 2, 3 대신 0, 5, 9로 하면…

어느 숫자를 한 자리로 쓰든, 한 자리 번호 하나가 두 자리 열 개를 막아. 셋이면 늘 30개가 막히고 70개가 남아. 크래프트 부등식으로 쓰면 3/10 + 72/100 = 1.02라서 1을 넘고.

그럼 72가지를 다 담으려면 무엇을 바꿔야 할까요?

음… 한 자리를 둘로 줄이면 80개가 남으니까 72개가 들어가요. 한 자리 셋을 꼭 두겠다면, 두 자리 하나를 비워서 세 자리 열 개로 쓰면 69 + 10 = 79가지까지 돼요. 그 메뉴들은 세 번 눌러야 하지만요.

국가 번호도 그렇게 돼 있었지. 짧은 번호가 하나 늘면 그 번호로 시작하는 긴 번호가 다 막히고, 자리가 꽉 차면 누군가 한 자리 늘어나야 자리가 나.

그래요. 번호를 짜 맞춰 보기 전에 Σ 10^(−길이)부터 더해 보면 돼요. 1을 넘으면 어떤 배치로도 안 되고, 꽉 찼으면 기존 번호 하나를 길게 쪼개야 자리가 나요.

토론 2. 흔한 순서대로 1, 2, 3, 3비트를 주면 늘 허프만 코드인가

택배 기사가 남기는 문자는 「문 앞」 30%, 「경비실」 30%, 「택배함」 20%, 「직접 받음」 20%다. 흔한 순서대로 1, 2, 3, 3비트를 주면 가장 짧은 코드인가?

택배 기사가 남기는 문자가 「문 앞」 30%, 「경비실」 30%, 「택배함」 20%, 「직접 받음」 20%예요. 이 넷에 코드를 준다면요?

음, 흔한 순서대로 1, 2, 3, 3비트를 주면 되겠죠. 단톡방 답장도 그렇게 해서 허프만 코드가 나왔으니까요. 평균은 0.3 × 1 + 0.3 × 2 + 0.2 × 3 + 0.2 × 3 = 2.1비트예요.

넷에 2비트씩 주면요?

그냥 2비트요. 어, 2.1보다 짧은데.

흔한 말에 짧게 줬는데 더 길어졌다고?

가장 작은 둘부터 합쳐 보면 어떻게 되나요?

해 볼게요. 택배함 0.2와 직접 받음 0.2를 합치면 0.4. 남은 건 0.3, 0.3, 0.4니까 다음엔 0.3 둘을 합쳐 0.6. 마지막에 0.4와 0.6. 합쳐진 횟수가 넷 다 두 번이니까… 2, 2, 2, 2비트네요.

흔한 말을 짧게 주는 건 맞는데, 얼마나 짧게 줄지는 확률이 얼마나 치우쳤는지에 달려 있었어요. 단톡방 답장은 「응」이 40%로 많이 치우쳐서 1, 2, 3, 3이 맞았던 거고요.

「문 앞」에 1비트를 주면 [0, 1)의 절반을 혼자 쓰는 거잖아. 30%짜리 말한테 구간의 절반은 너무 크고, 나머지 셋이 70%인데 남은 절반을 나눠 써야 해.

그래요. 흔한 순서는 길이의 순서만 알려 줘요. 길이가 몇인지는 가장 작은 둘을 합치는 순서로 정해요.

토론 3. 압축한 비트열만 받으면 누구나 되살릴 수 있나

휴대폰 자동 완성으로 문장을 쓰면서, 낱말마다 「몇 번째 후보를 눌렀나」의 순번만 친구에게 보낸다. 친구가 무엇을 가지고 있어야 문장을 되살릴 수 있는가?

휴대폰 자판의 자동 완성은 다음 낱말 후보를 확률 순서로 세 개 띄우죠. 문장을 쓰면서 「몇 번째 후보를 눌렀나」만 적어 친구에게 보낸다고 해 봐요. 「1, 1, 3, 2」처럼요. 친구가 이걸로 문장을 되살릴 수 있을까요?

순번이 1, 2, 3 셋뿐이니까 프리픽스 코드로 적으면 끊어 읽기도 돼요. 받은 비트만 있으면 친구가 혼자서 1, 1, 3, 2를 읽어 낼 수 있으니까 되살릴 수 있죠.

친구가 읽어 낸 첫 「1」은 어떤 낱말인가요?

아… 제 휴대폰이 첫째로 띄운 후보요. 친구가 그 낱말을 알려면 제 자동 완성과 같은 것이 친구 휴대폰에도 있어야 하네요. 숫자를 끊어 읽는 것과 낱말을 되살리는 걸 같은 일로 봤어요.

그럼 같은 앱만 깔려 있으면 되겠네. 버전이 조금 달라서 확률이 소수점 아래에서 살짝 달라도 순서는 거의 같을 테니까 괜찮을 거고.

내 휴대폰에서 「밥」이 0.31, 「빵」이 0.30이었는데, 친구 휴대폰에서는 「밥」 0.30, 「빵」 0.31이라면요?

친구한테는 1번이 「빵」이 되네요. 「점심에 밥」이 「점심에 빵」으로 바뀌고… 그다음 후보는 「빵」 뒤에 올 낱말로 다시 뽑으니까 그 뒤 순번도 전부 엉뚱한 낱말을 가리켜요. 조금 달라도 괜찮다고 한 건 틀렸네요.

한 칸만 어긋나도 그 뒤가 다 무너지는구나. 산술 코딩은 칸 경계로 고르니까 경계가 조금만 옮겨져도 다른 칸이 골라질 수 있겠다.

그래서 두 사람의 예측기는 비트 하나까지 같은 확률을 내야 해요. 정수 빈도처럼 두 사람이 똑같은 값을 쓰는 것이 안전하죠. 그리고 받는 사람이 미리 가져야 하는 그 예측기의 크기도 압축의 비용으로 계산해야 해요.

문장은 숫자 넷으로 줄었지만, 숫자 넷을 읽으려면 자동 완성 모델 전체가 먼저 가 있어야 하는 거네요.

토론 4. 퍼플렉서티가 2면 두 번에 한 번 맞히나

친구의 가위바위보를 맞히는 두 예측기의 퍼플렉서티가 똑같이 2다. 가장 그럴듯하다고 본 손을 고를 때 맞히는 비율도 같은가?

친구의 가위바위보를 맞히는 예측기가 둘 있어요. 친구가 실제로 낸 손에 준 확률로 퍼플렉서티를 쟀더니 둘 다 2였어요. 가장 그럴듯하다고 본 손을 고르면 몇 번에 한 번 맞힐까요?

퍼플렉서티 2면 둘 가운데 하나를 고르는 셈이니까 두 번에 한 번이요. 둘 다 50%겠죠.

예측기 A는 친구가 낸 손에 늘 0.5를, 나머지 두 손에 0.25씩을 줬어요. 퍼플렉서티와 맞힌 비율을 내 볼까요?

매번 −log₂ 0.5 = 1비트니까 퍼플렉서티는 2¹ = 2요. 맞힌 비율은… 낸 손이 늘 0.5로 가장 크니까 매번 맞혀요. 100%예요?

예측기 B는 절반의 판에서는 낸 손에 1을 줬고, 나머지 절반에서는 낸 손에 0.25, 다른 한 손에 0.5를 줬어요.

1을 준 판은 0비트, 0.25를 준 판은 2비트라 평균 1비트, 퍼플렉서티는 똑같이 2예요. 그런데 0.25를 준 판에서는 0.5를 받은 다른 손을 고르니까 틀려요. 맞힌 비율은 50%고요. 퍼플렉서티가 같은데 맞힌 비율은 100%와 50%로 갈리네요. 퍼플렉서티를 맞힌 비율로 읽은 게 틀렸어요.

퍼플렉서티는 낸 손에 확률을 얼마나 줬는지를 평균한 거고, 맞힌 비율은 1등만 보니까 재는 게 다르네. 그럼 퍼플렉서티 2는 무슨 뜻이에요?

친구가 늘 가위와 바위 가운데서만 낸다고 하고, 두 손에 0.5씩 주는 예측기를 생각해 봐요.

매번 1비트니까 퍼플렉서티 2예요. 두 손 가운데서 고르게 헷갈리는 예측기만큼 헷갈린다는 뜻이네요. 맞힌 비율을 세는 숫자는 따로 있고, 퍼플렉서티는 몇 면짜리 주사위만큼 헷갈리는지를 세는 거고요.

혼동하기 쉬운 점

혼동하기 쉬운 생각	나온 문제	바로잡는 법
짧은 번호를 더 주어도 긴 번호의 가짓수는 그대로라고 봄	토론 1	짧은 번호 하나가 그 번호로 시작하는 긴 번호를 모두 막는다. 어떤 번호도 다른 번호의 앞부분이 아니어야 끊어 읽힌다
코드표를 손으로 맞춰 보다 안 되면 더 찾음	2, 토론 1	크래프트 합 Σ 2^(−ℓ)를 먼저 더한다. 1을 넘으면 어떤 배치로도 안 된다
예산이 꽉 찬 코드표에 말을 그냥 더하려 함	2, 토론 1	기존 코드 하나를 한 자리 늘려 둘로 쪼개야 자리가 난다
합이 1이 아닌 점수로 −log₂를 손실로 씀	3	크래프트 부등식을 어긴 길이라 실제로 낼 수 없는 코드다. 합으로 나눠 확률로 만든다
흔한 순서대로 길이를 주면 허프만 코드라고 봄	토론 2	가장 작은 둘을 합치는 순서로 확인한다. 길이가 같아 보여도 순서가 근거다
말 하나에 코드 하나로 1비트 아래를 내려 함	6	정수 코드는 말 하나에 적어도 1비트. 묶거나 산술 코딩으로 글 전체에 코드 하나를 준다
글자가 많을수록 코드가 길다고 봄	8	코드 길이는 예측 확률의 곱(구간 폭)이 정한다. 흔한 글자 여섯과 드문 글자 둘이 같은 비트일 수 있다
압축된 비트열만 있으면 되살릴 수 있다고 봄	토론 3	받는 사람에게 같은 예측기가 있어야 한다. 그 크기도 비용이다
보내는 사람과 받는 사람의 예측 확률이 아주 조금 달라도 괜찮다고 봄	토론 3	칸의 경계가 옮겨지면 그 뒤가 모두 틀린다. 정수 빈도처럼 두 사람이 똑같은 값을 쓴다
퍼플렉서티를 맞힌 날 수나 정답률로 읽음	토론 4	「몇 가지 가운데 고르게 헷갈리는 셈인가」. 2^(평균 비트) 또는 e^(평균 nat)
nat을 비트로 바꿀 때 ln 2를 곱함	11	nat이 큰 단위다. 비트 = nat ÷ ln 2
토크나이저가 다른 모델을 토큰당 손실로 견줌	12	원래 글의 바이트 수로 나눈 바이트당 비트로 비교한다

요약

이 장에서 한 일을 정리해 보자. 0과 1로 끊어 읽을 표시 없이 말을 적으려면 어떤 코드도 다른 코드의 앞부분이 아니어야 하고, 그런 코드의 길이는 크래프트 부등식 Σ 2^(−ℓ) ≤ 1을 따른다. 길이 ℓ인 코드는 [0, 1)의 2^(−ℓ)을 차지하므로, 코드 길이를 정하는 일은 확률을 정하는 일과 같다. 확률 p로 나오는 말의 가장 좋은 길이는 −log₂ p이고, 평균 길이가 내려갈 수 있는 가장 낮은 값이 엔트로피다. 정수 길이 가운데서는 가장 작은 둘을 합쳐 가는 허프만 코드가 가장 짧지만, 말 하나에 적어도 1비트를 써서 흔한 말이 많을수록 비트를 버린다.

산술 코딩은 글자마다 예측 확률대로 [0, 1)을 쪼개 글 전체를 구간 하나로 만들고, 그 구간을 가리키는 비트를 낸다. 코드 길이는 예측기가 실제로 온 글자에 준 확률의 −log₂ 합보다 많아야 2비트 길다. 그래서 확률을 내는 것이면 무엇이든 압축기가 되고, 거꾸로 압축기가 매기는 비트는 확률로 읽힌다. 언어 모델의 크로스 엔트로피 손실은 토큰 하나를 적는 nat이고, ln 2로 나누면 비트, 토큰 수 ÷ 바이트 수를 곱하면 바이트당 비트, e의 거듭제곱으로 올리면 퍼플렉서티다. 직접 쓴 빵집 이야기에서 앞 글자를 보는 예측기는 시험 글을 글자당 6.18비트에서 3.95비트까지 줄였고, 친칠라는 글로 배우고도 그림과 소리를 PNG와 FLAC보다 작게 줄였다.

flowchart LR
  A["예측기<br/>다음 글자의 확률 q"] -- "산술 코딩<br/>구간을 q대로 쪼갠다" --> B["압축기<br/>비트 ≈ Σ −log₂ q"]
  B -- "크래프트 부등식<br/>q = 2^(−ℓ)" --> A
  B --> C["손실 = 비트 × ln 2<br/>바이트당 비트로 비교한다"]

정리 연습문제

물음. 말 넷에 길이 1, 2, 2, 2비트의 코드를 주되, 어떤 코드도 다른 코드의 앞부분이 아니게 하려 한다. 어떻게 되는가?

[ ] 길이 1인 코드는 길이 2인 코드를 하나만 막으니, 잘 배치하면 된다 〔틀림: 길이 1인 코드 0은 0으로 시작하는 길이 2 코드 00과 01을 둘 다 막는다.〕
[ ] 손으로 몇 가지 더 배치해 보면 찾을 수 있다 〔틀림: 손으로 맞춰 보기 전에 크래프트 합부터 더한다. 1을 넘으면 어떤 배치로도 안 된다.〕
[x] 어떤 배치로도 만들 수 없다 〔맞음: 길이 1인 코드가 전체의 절반을, 길이 2인 코드가 4분의 1씩을 차지해 합이 4분의 5로 1을 넘는다.〕

물음. 어떤 모델이 소프트맥스 대신 토큰마다 따로 점수를 내서, 세 토큰에 모두 0.5를 주었다. 이 점수를 확률로 믿고 −log₂를 취해 세 토큰에 1비트씩 코드를 주면 어떻게 되는가?

[ ] 된다. 어느 토큰이 와도 1비트이니 좋은 코드다 〔틀림: 길이가 짧아 보여도 받는 사람이 끊어 읽을 수 없어 실제로 낼 수 없는 코드다.〕
[x] 이런 코드는 만들 수 없다. 점수를 합으로 나눠 확률로 바꿔야 한다 〔맞음: 1비트 코드는 0과 1 둘뿐이라 세 토큰에 나눠 줄 수 없다. 합이 1이 아닌 점수로 매긴 길이는 크래프트 부등식을 어긴다.〕
[ ] 된다. 높은 점수에 짧은 코드를 주는 원칙을 지켰다 〔틀림: 그 원칙은 확률에 대한 것이다. 합이 1을 넘는 점수는 확률이 아니다.〕

물음. 언어 모델이 글의 토큰 대부분을 0.99쯤의 확률로 맞힌다. 토큰마다 정수 길이의 코드(허프만 코드처럼)를 주면 어떻게 되는가?

[ ] 허프만 코드가 가장 좋은 코드이니, 확률대로 적은 길이와 거의 같다 〔틀림: 허프만 코드는 정수 길이 가운데서 가장 짧을 뿐이다. 0.99짜리 토큰에 알맞은 길이는 0.0145비트인데 정수 코드는 1비트를 쓴다.〕
[x] 토큰마다 적어도 1비트를 써서, 쉬운 글일수록 비트를 많이 버린다 〔맞음: 말 하나에 코드 하나를 주면 1비트 아래로 못 내려간다. 여러 말을 묶거나 산술 코딩으로 글 전체에 코드 하나를 주면 이 손해가 거의 사라진다.〕
[ ] 쉬운 글일수록 확률대로 적은 길이와의 차이가 줄어든다 〔틀림: 확률대로 적은 길이는 0에 가까워지는데 정수 코드는 1비트에 머물러, 쉬울수록 차이가 커진다.〕

물음. 믿음 (가 1/2, 나 1/4, 다 1/8, 라 1/8)로 글자마다 구간을 쪼개는 산술 코딩을 한다. 「라라」와 「가가가가가가」 가운데 어느 글의 코드가 더 긴가?

[ ] 「가가가가가가」. 글자가 여섯이라 더 길다 〔틀림: 코드 길이는 예측 확률의 곱, 끝 구간의 폭이 정한다. 글자 수는 상관없다.〕
[ ] 「라라」. 드문 글자가 들어간 글은 늘 더 길다 〔틀림: 드문 글자 둘의 확률을 곱한 폭과 흔한 글자 여섯의 확률을 곱한 폭이 같을 수 있다.〕
[x] 같다 〔맞음: 「라라」의 끝 구간 폭은 8분의 1을 두 번, 「가가가가가가」는 2분의 1을 여섯 번 곱한 것이라 둘 다 64분의 1이고, 6비트다.〕

물음. 산술 코딩으로 줄인 비트열을 친구에게 보냈다. 친구가 글을 되살리려면 무엇이 있어야 하는가?

[ ] 비트열만 있으면 된다 〔틀림: 비트열은 예측 확률대로 쪼갠 구간을 가리킬 뿐이다. 같은 예측기가 없으면 구간을 어디서 쪼갰는지 모른다.〕
[ ] 비슷한 예측기. 확률이 아주 조금 달라도 대부분 되살아난다 〔틀림: 칸의 경계가 조금만 옮겨져도 그 뒤가 모두 틀린다. 그래서 정수 빈도처럼 두 사람이 똑같은 값을 쓴다.〕
[x] 내가 쓴 것과 똑같은 예측기 〔맞음: 친구도 글자마다 같은 확률로 구간을 쪼개야 같은 글자를 읽어 낸다. 받는 사람에게 있어야 할 예측기의 크기도 비용이다.〕

물음. 언어 모델의 평균 손실을 비트로 바꾸니 토큰당 1비트, 퍼플렉서티는 2였다. 맞는 말은?

[x] 둘 가운데서 고르게 헷갈리는 예측기만큼 헷갈린다 〔맞음: 매번 두 후보에 0.5씩 주고 그 가운데 하나가 오는 예측기가 토큰당 1비트, 퍼플렉서티 2다.〕
[ ] 두 번에 한 번은 다음 토큰을 맞힌다 〔틀림: 퍼플렉서티는 실제로 온 토큰에 준 확률로 재고, 맞힌 비율은 1등만 본다. 퍼플렉서티가 같아도 맞힌 비율은 100%일 수도 50%일 수도 있다.〕
[ ] 토크나이저가 다른 모델의 퍼플렉서티 3과 비교하면 이 모델이 낫다 〔틀림: 토큰이 다르면 토큰당 값을 비교할 수 없다. 원래 글의 바이트 수로 나눈 바이트당 비트로 비교한다.〕

막힌 곳

예측을 잘하면 짧게 적을 수 있다는 것은 이제 비트 단위로 말할 수 있지만, 이 장의 코드에는 아직 물음 두 가지가 남았다. 하나는 엔트로피와의 거리다. 맑은 날 90%인 도시의 날씨는 하루씩 보내면 1비트였고, 나흘씩 묶으니 하루 0.493비트로 엔트로피 0.469비트에 다가갔지만, 그 셈은 허프만 코드가 정수로 맞추느라 버리는 비트가 묶음마다 1비트 아래라는 데서 나왔다. 그러면 거꾸로 엔트로피보다 짧게 적는 방법은 정말 없을까? 아주 길게 묶은 날씨 가운데 거의 나오지 않는 것은 되살리기를 포기하고 나머지에만 번호를 붙이면, 하루에 드는 비트는 어디까지 내려갈까? 다른 하나는 노이즈다. 이 장의 코드는 보낸 비트가 그대로 도착한다고 쳤다. 산술 코딩으로 줄인 글에서 비트 하나가 뒤집혀 도착하면 받는 사람은 무엇을 되살리게 되고, 비트가 가끔 뒤집히는 선으로 보내려면 줄인 비트에 무엇을 얼마나 덧붙여야 할까?