혼동하기 쉬운 점과 요약

최소 기술 길이와 오컴: 모델까지 적어야 공평하다

토론 1. 몇 안 되는 점을 꼭 맞힌 곡선을 믿어도 되나

다이어트를 시작하고 사흘 동안 아침 체중이 70.0, 69.6, 69.4kg이었다. 세 점을 꼭 지나는 곡선으로 30일째 체중을 내다봐도 되는가?

다이어트를 시작하고 사흘 동안 아침 체중이 70.0, 69.6, 69.4kg이었어요. 30일째 체중을 내다보고 싶어요. 어떤 곡선을 쓸까요?

점이 셋이면 2차 곡선이 세 점을 꼭 지나요. 오차가 0이니까 이게 가장 잘 맞는 곡선이죠.

np.polyfit으로 맞추면 n일째가 70.0 − 0.4(n − 1) + 0.1(n − 1)(n − 2)야. 30일째를 넣으면 70.0 − 11.6 + 81.2 = 139.6kg. 다이어트를 하는데 두 배가 됐어.

사흘 동안 줄던 체중이 한 달 뒤에 두 배라니요. 세 점을 다 지난다고 믿을 만한 곡선은 아니었네요.

체중계는 같은 날 두 번 재도 0.3kg쯤 오르내려요. 셋째 날 값이 0.3kg 달랐다면 2차 계수 0.1은 어떻게 될까요?

넣어 볼게요. 69.7kg이면 2차 차분이 0.5라 계수가 0.25, 69.1kg이면 −0.1이라 −0.05예요. 체중계가 한 번 오르내린 것만으로 계수가 이만큼 오가네요. 계수 셋을 점 셋으로 정했으니 거의 정해지지 않은 거고요.

넷째 날 쟀더니 69.5kg이었어요. 2차 곡선과 직선 가운데 어느 쪽이 더 잘 맞혔나요?

2차 곡선은 69.4kg, 사흘로 맞춘 직선은 69.07kg을 내다봐요. 2차가 0.1kg 차이로 더 가까우니까 2차를 쓰면 되겠네요.

그 2차 곡선으로 30일째를 다시 보면요?

139.6kg 그대로예요. 넷째 날 하나로 고르니까, 체중계가 0.3kg쯤 오르내리는 것만으로도 순위가 뒤집히겠네요. 점 하나 맞힌 걸로 고른 건 운이었어요.

점이 적을 때는 계수가 덜 정해진 만큼 내다보는 폭을 넓혀야 하고, 고를 때도 2차 계수를 적는 비트까지 세야겠네요. 0.3kg 안에 묻히는 계수는 적어 봐야 값을 못 하니까 직선이 남을 거고요.

그래요. 몇 안 되는 점을 꼭 맞혔다고 그 곡선이 확실해지지는 않아요. 덜 정해진 계수의 퍼짐은 예측의 폭에 넣고, 검증 점 몇 개의 작은 차이보다 모델 비트까지 넣은 길이로 골라요.

토론 2. 내가 찾은 규칙과 다른 답은 틀린 답인가

할머니가 주신 세뱃돈이 해마다 1만, 2만, 4만 원이었다. 이듬해 7만 원을 주셨다면, 이 세뱃돈에는 규칙이 없는 것인가?

할머니가 주신 세뱃돈이 해마다 1만, 2만, 4만 원이었어요. 내년에는 얼마일까요?

해마다 두 배니까 8만 원이요. 다른 답은 틀린 거고요.

그런데 이듬해 할머니가 7만 원을 주셨어요.

몇 배씩 늘었나 보면 2배, 2배, 1.75배라 어떤 배수로도 안 맞아요. 규칙 없이 그해 형편대로 주신 거네요.

늘어난 액수로 보면요?

1만, 2만, 3만… 늘어난 액수가 만 원씩 커져요. 그럼 7만 원도 규칙대로예요. 그다음은 11만 원이고요.

그럼 1, 2, 4만 봤을 때 7을 틀렸다고 한 것도 성급했네요. 「두 배씩」도 「늘어나는 액수가 만 원씩 커진다」도 1, 2, 4에 다 맞았으니까요.

저는 「몇 배씩」 규칙만 후보로 놓고 봤어요. 후보에 없는 규칙이라서 규칙이 없다고 해 버린 거예요.

그럼 처음에 8만 원에 건 건 잘못이었을까요?

음… 셋만 봤을 때는 두 규칙이 다 맞았고, 적는 길이도 「1에서 시작해 두 배씩」과 「1에서 시작해 늘어나는 액수가 1씩 커진다」로 비슷해요. 무게가 비슷하니 8과 7을 둘 다 남겨 뒀어야 했던 거죠.

그래요. 본 자료와 맞는 규칙은 늘 여럿이라, 짧은 규칙에 무게를 더 줄 뿐 다른 규칙을 버리지는 않아요. 그리고 후보에 넣지 않은 규칙은 자료가 아무리 쌓여도 배울 수 없어요. 무엇을 후보에 넣느냐가 귀납 편향이에요.

토론 3. 노래방 기계는 가사를 천분의 일로 줄인 압축기인가

노래방 기계에서는 다섯 자리 노래 번호만 누르면 가사 2,000바이트가 화면에 나온다. 기계 안에는 노래 5만 곡의 가사가 들어 있다. 노래 번호는 가사를 얼마나 줄인 것인가?

노래방 기계에서는 다섯 자리 노래 번호만 누르면 그 노래 가사가 화면에 다 나오죠. 가사가 2,000바이트라면, 노래 번호는 가사를 얼마나 줄인 걸까요?

일단 다섯 자리면 10만 가지라 log₂ 100,000 = 16.6비트예요. 가사는 2,000 × 8 = 16,000비트니까 0.1%로 줄인 거네요. 친칠라의 8.3%보다 훨씬 좋은 압축기예요.

친구에게 노래 번호만 문자로 보내면, 친구는 가사를 알 수 있나요?

어… 친구 집에도 같은 노래방 기계가 있어야 해요. 아, 기계 안의 가사까지 세야 하네요. 5만 곡 × 2,000바이트면 100MB예요. 가사 한 곡을 보내려고 100MB를 먼저 보내면 0.1%는커녕 5만 배예요.

그럼 노래를 많이 보내면 본전을 찾지 않을까? 친칠라도 글이 583GB를 넘으면 gzip을 이겼잖아.

계산해 볼게. 한 곡을 가사로 보내면 2,000바이트, 번호로 보내면 2.08바이트니까 한 곡마다 1,998바이트를 아껴. 100MB를 되찾으려면 5만 곡이 조금 넘게 필요해. 그런데 기계 안의 노래가 5만 곡뿐이야.

기계 안의 노래를 전부 보내도 본전이 안 나는구나. 노래방 기계는 가사를 그대로 담아 둔 것뿐이라 모델이 곧 자료인 거네. 받는 사람이 모델을 가져야 하면 모델의 비트도 세야 하고, 모델이 크면 그 모델로 적을 자료가 많아야 본전을 찾아. 친칠라는 글의 규칙을 배워서 처음 보는 글까지 짧게 적으니까 140GB를 보내고도 본전을 찾을 수 있는 거고.

토론 4. 배우는 동안 낸 손실은 코드 길이로 칠 수 없나

어느 카페는 매장 음악 8곡을 늘 같은 순서로 되풀이해 튼다. 친구는 8곡의 목록과 「같은 순서로 되풀이한다」는 것만 알고 순서는 모른다. 그날 들은 24곡의 순서를 보내는 길이는, 들으며 순서를 배운 예측기의 비트와 순서를 다 안 뒤의 예측기의 비트 가운데 어느 쪽으로 재야 하는가?

서연 학생이 자주 가는 카페는 매장 음악 8곡을 늘 같은 순서로 되풀이해 튼대요. 그날 들은 24곡의 순서를 친구에게 0과 1로 보낸다고 해 봐요. 친구는 8곡의 목록과 「같은 순서로 되풀이한다」는 것만 알고, 순서는 몰라요. 몇 비트가 들까요?

모델 성능은 학습이 끝난 뒤의 손실로 재잖아요. 순서를 다 배운 예측기라면 24곡이 다 확률 1이라 −log₂ 1 = 0비트예요. 처음 몇 곡에서 헤매며 낸 손실은 연습 기록이고요.

0비트라면, 친구는 아무것도 받지 않고 24곡의 순서를 알게 되나요?

아… 친구는 순서를 몰라요. 순서를 다 아는 예측기는 제 쪽에만 있으니까, 그 순서부터 보내야 하네요. 8곡을 늘어놓는 가짓수는 8! = 40,320가지라 log₂ 40,320 = 15.30비트요. 0비트에 더하면 15.30비트예요.

나는 친구가 들으면서 배운다고 치고 세어 볼게. 첫 곡은 8곡 가운데 하나라 3비트, 둘째 곡은 아직 안 나온 7곡 가운데 하나라 log₂ 7 = 2.81비트, 셋째 곡은 log₂ 6비트… 한 바퀴를 돌면 log₂ 8 + log₂ 7 + … + log₂ 1 = log₂ 40,320 = 15.30비트야. 둘째 바퀴부터는 순서를 아니까 0비트고.

똑같이 15.30비트네. 순서를 따로 보내는 비트가 서연이 쪽에서는 첫 바퀴에 헤매며 낸 손실로 들어가 있었던 거구나. 헤맨 손실은 연습 기록이 아니라 모델을 보내는 값이었어.

그럼 친구가 같은 24곡 기록을 처음부터 한 번 더 훑으며 배운다고 해 봐요. 한 번 더 훑을 때 낸 손실은 무엇을 보내는 데 쓰인 비트일까요?

이 카페에서는 한 번 더 훑어도 곡마다 0비트라 더해도 합이 15.30비트에서 바뀌지 않아요. 그런데 신경망은 같은 자료를 다시 훑어도 손실이 0이 되지는 않으니까…

그 0이 아닌 손실을 더한다면요?

한 번 더 훑은 곡들은 처음 훑을 때 이미 다 보냈으니, 그 손실은 무엇을 보내는 길이도 아니에요. 자료를 한 번만 훑으며 배울 때만, 배우는 동안 낸 손실의 합이 순차 코드의 길이네요.

그래요. 다 배운 모델의 손실만 보면 모델을 보내는 비트가 빠지고, 같은 자료를 여러 번 훑은 손실을 다 더하면 같은 자료를 여러 번 센 거예요.

혼동하기 쉬운 점

혼동하기 쉬운 생각	나온 문제	바로잡는 법
규칙만 보내고 예외를 빼먹음	1	받는 사람이 자료를 그대로 되살려야 한다. 규칙(모델 비트)과 예외(자료 비트)를 함께 센다
계수는 정밀할수록 좋다고 봄	2	자료가 알려 주는 것보다 정밀하게 적으면 모델 비트만 는다. 알맞은 정밀도는 자료 수가 정한다(파라미터당 대략 ½ log₂ n비트)
압축률에서 모델의 크기를 뺌	토론 3	받는 사람이 모델을 가져야 하면 모델의 비트도 센다. 모델이 크면 적을 자료가 많아야 본전을 찾는다
짧게 적힌 규칙이 어디서나 맞는다고 봄	4	처음 보는 자료가 학습 자료와 같은 원천일 때만 기대할 수 있다. 학습 자료가 덮지 않은 곳에는 보증이 없다
검증 점 몇 개의 작은 차이로 모델을 고름	6, 토론 1	검증 점이 적으면 고르는 일이 흔들리고, 떼어 낸 만큼 학습 점이 준다. 자료가 귀하면 모델 비트까지 넣은 길이로 학습 자료 전체에서 고른다
「~로 말할 수 없는 가장 작은 수」를 그냥 큰 수로 봄	7	자기를 가리키는 설명은 모순을 낳는다. 그래서 콜모고로프 복잡도는 계산할 수 없다
어떤 자료든 조금은 압축된다고 봄	8	짧은 설명의 수가 모자라 거의 모든 줄은 압축되지 않는다
압축기가 못 줄인 자료는 규칙이 없다고 봄	9	압축 결과는 복잡도의 위쪽 경계일 뿐이다. 압축기가 못 본 짧은 규칙이 있을 수 있다
본 자료와 맞는 다른 규칙을 틀렸다고 함	토론 2	맞는 규칙은 늘 여럿이다. 짧은 규칙에 큰 무게를 줄 뿐 다른 규칙을 버리지는 않는다
무늬 길이를 빼고 무게를 2^(−m)으로 줌	11	끊어 읽을 수 있게 길이까지 적어야 무게의 합이 1을 넘지 않는다(크래프트 부등식)
섞기가 못 배운 줄은 규칙이 없다고 봄	12, 토론 2	후보에 없는 규칙은 배울 수 없다. 후보를 고르는 일이 곧 귀납 편향이다
비율을 보내는 두 부분 코드가 늘 더 짧다고 봄	13	배우면서 적는 순차 코드는 모델을 보내지 않고, 처음의 서툰 예측으로 비용을 치른다
적은 점으로 맞춘 곡선을 확실하게 믿음	14, 토론 1	덜 정해진 계수의 퍼짐을 예측 분포의 폭에 넣는다
학습 기록의 손실과 코드 길이는 상관없다고 봄	15, 토론 4	한 번만 훑는 학습이면 스텝마다의 손실 합이 순차 코드의 길이다

요약

이 장에서 한 일을 정리해 보자. 예측기를 압축기로 쓸 때 예측기 자신을 적는 비트도 세야 공평하다. 모델을 먼저 적고 그 모델로 자료를 적는 두 부분 코드에서, 학습 점 20개에 0~9차 다항식을 맞추면 합이 2차에서 144.8비트로 가장 짧았다. 차수를 올리면 자료 비트는 줄지만 커진 계수를 적는 모델 비트가 더 빨리 늘었고, 계수의 정밀도도 같은 저울로 정해졌다. 이 합이 가장 짧은 모델을 고르는 원칙이 리사넨의 최소 기술 길이다.

학습 점을 짧게 적은 2차 다항식은 같은 원천의 시험 점 200개도 점당 5.43비트로 가장 짧게 적었다. 학습 자료를 모델 비트까지 넣어 짧게 적는 모델이 처음 보는 자료도 짧게 적는다는 것이 이 책의 일반화의 첫째 정의이고, 그 기대는 자료가 같은 원천에서 왔다는 조건 위에 선다. 학습 구간 밖에서는 학습에서 3~4비트 차이였던 곡선들이 크게 갈라졌다.

내가 고른 모델 형태에 기대지 않는 가장 짧은 길이가 콜모고로프 복잡도, 줄을 찍는 가장 짧은 프로그램의 길이다. 원주율 10,000자리는 압축기로는 4,369바이트에 멈추지만 194바이트 프로그램이 찍는다. 콜모고로프 복잡도는 잘 정의되지만 계산할 수 없고 압축기는 위쪽 경계만 주는데, 솔로모노프는 같은 양에 예측에서 닿았다. 본 자료와 맞는 모든 프로그램에 2^(−길이)의 무게를 주어 다음 기호를 투표하게 하면, 적은 비트가 맞는 가장 짧은 프로그램의 길이를 넘지 않는다. 마지막으로, 앞의 자료로 배운 예측기로 다음 자료를 적는 순차 코드는 모델을 따로 보내지 않고도 모델의 비용을 계산에 넣는다. 다항식에서도 2차가 133.7비트로 가장 짧았고, 블리어와 올리비에는 깊은 신경망이 이 방법으로 자료를 잘 압축함을 보였다.

flowchart LR
  A["예측기의 비트<br/>Σ −log₂ q"] -- "모델도 적는다" --> B["두 부분 코드<br/>L(모델) + L(자료|모델)"]
  B -- "모델 형태를 고르지 않으면" --> C["콜모고로프 복잡도 K(x)<br/>계산할 수 없다"]
  C -- "예측으로 바꾸면" --> D["솔로모노프 귀납<br/>무게 2^(−길이)"]
  B -- "배우면서 적으면" --> E["순차 코드<br/>모델을 보내지 않는다"]
  B -- "같은 원천이면" --> F["처음 보는 자료도 짧게<br/>일반화 (1)"]

정리 연습문제

물음. 학습 점 20개에 0차부터 9차까지 다항식을 맞췄다. 9차 다항식이 학습 점에 가장 가깝게 지나간다. 최소 기술 길이로 고르면 몇 차인가?

[ ] 9차. 점을 가장 잘 맞히니 자료를 적는 비트가 가장 작다 〔틀림: 자료 비트는 가장 작지만, 커진 계수를 적는 모델 비트가 더 빨리 늘어난다.〕
[x] 모델 비트와 자료 비트의 합이 가장 짧은 차수, 이 장의 자료에서는 2차 〔맞음: 모델을 먼저 적고 그 모델로 자료를 적는 두 부분 코드의 합이 2차에서 144.8비트로 가장 짧았다.〕
[ ] 0차. 계수가 하나뿐이라 모델을 적는 비트가 가장 작다 〔틀림: 모델 비트는 작지만 점을 맞히지 못해 자료 비트가 크다.〕

물음. 노래방 기계에서 다섯 자리 노래 번호를 누르면 가사 2,000바이트가 나온다. 친구에게 노래 번호만 보내면 가사를 0.1%로 줄여 보낸 것인가?

[ ] 그렇다. 친칠라의 8.3%보다 훨씬 좋은 압축기다 〔틀림: 친구에게도 같은 기계가 있어야 하니, 기계 안의 가사를 적는 비트도 센다.〕
[ ] 한 곡으로는 손해지만, 노래를 많이 보내면 언제나 본전을 찾는다 〔틀림: 기계 안 노래는 5만 곡뿐이라 전부 보내도 기계 안 가사 100MB를 되찾지 못한다.〕
[x] 아니다. 기계 안의 가사까지 세면 줄인 것이 없다 〔맞음: 받는 사람이 모델을 가져야 하면 모델의 비트도 센다. 가사를 하나하나 담아 둔 기계는 처음 보는 노래를 짧게 적지 못해 본전을 찾을 자료가 없다.〕

물음. 학습 점을 가장 짧게 적은 2차 다항식은 같은 원천에서 뽑은 시험 점 200개도 가장 짧게 적었다. 이 2차 다항식에 기대해도 되는 것은?

[x] 같은 원천에서 온 처음 보는 점도 짧게 적으리라는 것 〔맞음: 학습 자료를 모델 비트까지 넣어 짧게 적는 모델이 처음 보는 자료도 짧게 적는다는 기대는, 자료가 같은 원천에서 왔다는 조건 위에 선다.〕
[ ] 학습 구간 밖의 점도 짧게 적으리라는 것 〔틀림: 학습 자료가 덮지 않은 곳에는 보증이 없다. 학습에서 3~4비트 차이였던 곡선들이 구간 밖에서는 크게 갈라졌다.〕
[ ] 검증 점 다섯 개를 떼어 다시 골라 봐야 믿을 수 있다는 것 〔틀림: 검증 점이 적으면 고르는 일이 흔들리고, 떼어 낸 만큼 학습 점이 준다. 자료가 귀하면 학습 자료 전체에서 모델 비트까지 넣은 길이로 고른다.〕

물음. 원주율 10,000자리를 압축기로 줄였더니 4,369바이트에서 멈췄다. 그런데 이 자리들을 찍는 194바이트짜리 프로그램이 있다. 맞는 말은?

[ ] 압축기가 더 못 줄였으니 원주율의 자리에는 규칙이 없다 〔틀림: 압축 결과는 가장 짧은 길이의 위쪽 경계일 뿐이다. 압축기가 못 본 짧은 규칙이 있을 수 있다.〕
[x] 원주율 10,000자리를 찍는 가장 짧은 프로그램은 194바이트보다 길 수 없다 〔맞음: 콜모고로프 복잡도는 줄을 찍는 가장 짧은 프로그램의 길이다. 194바이트 프로그램이 이미 있으니 그보다 길지 않다.〕
[ ] 압축기를 더 잘 만들면 가장 짧은 프로그램의 길이도 언젠가 계산해 낼 수 있다 〔틀림: 콜모고로프 복잡도는 잘 정의되지만 계산할 수 없다. 압축기는 위쪽 경계만 준다.〕

물음. 2, 4, 6, 8을 본 뒤 다음 수를 맞히려 한다. 「2씩 더한다」 말고도 본 네 수와 맞는 규칙이 여럿 있다. 솔로모노프 귀납은 이 규칙들을 어떻게 다루는가?

[ ] 가장 짧은 규칙 하나만 남기고, 다른 답을 내는 규칙은 틀렸으니 버린다 〔틀림: 본 자료와 맞는 규칙은 늘 여럿이다. 짧은 규칙에 큰 무게를 줄 뿐 다른 규칙을 버리지는 않는다.〕
[ ] 본 수와 맞는 규칙마다 같은 무게를 주어 공평하게 투표하게 한다 〔틀림: 같은 무게로는 짧은 규칙과 억지로 맞춘 긴 규칙이 같은 표를 가진다.〕
[x] 본 수와 맞는 규칙마다 짧을수록 큰 무게를 주어 다음 수를 투표하게 한다 〔맞음: 프로그램이 1비트 짧을 때마다 무게가 두 배다. 가장 짧은 규칙이 투표를 이끌고, 다른 규칙도 작은 무게로 남는다.〕

물음. 자료를 한 번만 훑으며 신경망을 학습시켰고, 스텝마다 다음 자료에 낸 손실을 비트로 기록했다. 이 자료를 순차 코드로 적는 길이는 무엇인가?

[x] 스텝마다 낸 손실의 합 〔맞음: 받는 사람도 같은 방법으로 배우며 읽으니 모델을 따로 보내지 않는다. 한 번만 훑으면 배우는 동안 낸 손실의 합이 순차 코드의 길이다.〕
[ ] 학습이 끝난 뒤의 손실. 처음 헤맨 손실은 연습 기록일 뿐이다 〔틀림: 다 배운 모델의 손실만 보면 모델을 보내는 비트가 빠진다. 처음 헤매며 낸 손실이 모델을 보내는 값이다.〕
[ ] 같은 자료를 여러 번 더 훑으며 낸 손실까지 모두 더한 값 〔틀림: 처음 훑을 때 이미 다 보낸 자료를 다시 센 것이다.〕

막힌 곳

짧게 적는 모델이 처음 보는 자료도 짧게 적는다는 것을 장난감 다항식에서 확인했지만, 이 장의 모델은 점 스무 개에 계수 몇 개짜리였다. 파라미터가 수백만 개인 신경망은 학습 자료를 전부 외울 만큼 큰데, 그런 신경망이 학습 자료를 아주 짧게 적었을 때 그것이 규칙을 찾아서인지 외워서인지는 무엇으로 가를 수 있을까? 그리고 「같은 원천」의 그림, 점들이 놓인 공간에서 규칙이 어떤 모양을 하고 있는지는 아직 다항식 하나로만 보았다. 수천 차원의 자료에서 가장 짧은 설명은 어떤 모양일까?