자주 하는 실수와 요약
자주 하는 실수
| 실수 | 나온 문제 | 바로잡는 법 |
|---|---|---|
| 두 스텝 뒤의 확률을 한 길의 곱으로만 셈 | 1 | 거쳐 가는 상태마다 길이 하나씩 있다. 길의 곱을 모두 더한다(전이 행렬의 거듭제곱) |
| 체인의 예측이 실제 글과 다르면 체인이라는 생각 자체가 틀렸다고 봄 | 2 | 체인은 첫 근사다. 어긋나면 앞 글자를 더 넣어 상태를 넓힌다 |
| 같은 상태면 다음 스텝도 같다고 봄 | 3 | 다음 스텝을 계산하는 데 필요한 것(모멘텀 버퍼 등)이 모두 상태에 들어 있는지 본다 |
| 옮겨 가는 비율이 비슷하면 정상 분포가 반반이라고 봄 | 4 | 나가는 확률 흐름과 들어오는 확률 흐름이 같아지는 곳을 푼다 |
| 표의 몇 칸만 보고 정상 분포에 거의 닿았다고 봄 | 5 | 차이는 스텝마다 두 번째 고윳값만큼 줄어든다. 그 배율로 남은 스텝을 계산한다 |
| 짝수 스텝에서만 확인하고 멈췄다고 봄 | 6 | 주기가 있으면 스텝마다 값이 맞바뀐다. 이웃한 두 스텝을 함께 본다 |
| 주기가 있으면 시간 평균도 모이지 않는다고 봄 | 7 | 주기가 깨는 것은 n스텝 뒤의 분포다. 갇힌 곳만 없으면 시간 평균은 정상 분포로 간다 |
| 서로 기대는 샘플에 독립일 때의 표준편차 식을 씀 | 8 | 상태가 둘이면 분산이 (1 + λ)/(1 − λ)배. 일반적으로는 유효 샘플 수로 나눈다 |
| 에르고드 정리가 있으니 정해진 스텝 수면 충분하다고 봄 | 9 | 서로 넘어가기 드문 상태 묶음이 있으면 정해 둔 스텝 수가 「오래」가 아니다. 출발점이 다른 체인 여럿을 견준다 |
| 분포가 멈춰 있으면 짝마다 주고받는 수도 같다고 봄 | 10 | 상태가 셋 이상이면 한 방향으로 도는 흐름이 남을 수 있다. 고리를 돌며 곱한 값이 양쪽으로 같은지 본다 |
| 정상 분포를 지키는 단계들을 이어 붙이면 세부 균형도 이어진다고 봄 | 12 | 이어 붙인 것은 정상 분포는 지키지만 세부 균형은 깨질 수 있다 |
| 확률이 낮은 쪽으로 옮겨 가는 제안을 모두 물림 | 13 | 그러면 온도 0. 확률의 비만큼 받아들여야 그 분포가 된다 |
| 제안이 대칭이 아닌데 메트로폴리스 식을 그대로 씀 | 14 | 받아들일 확률에 돌아오는 제안 확률 ÷ 가는 제안 확률을 곱한다(헤이스팅스) |
| 사후분포에서 뽑으려면 증거(정규화 상수)부터 구해야 한다고 봄 | 15 | 받아들일 확률은 비만 쓴다. 정규화 상수는 지워진다 |
| 맨 위 카드를 끼울 때마다 맨 아래 카드가 한 칸씩 올라온다고 봄 | 16 | 맨 아래 카드보다 아래에 끼울 때만 올라온다. 기대 횟수 n(1 + 1/2 + … + 1/n) |
| 리플 셔플 한 번이면 모든 순서가 나올 수 있다고 봄 | 17 | 한 번에 오르는 줄은 많아야 둘. 거꾸로 된 순서는 나오지 않는다 |
| 샘플이 많으면 그만큼 독립인 샘플이라고 봄 | 18 | 유효 샘플 수 n(1 − ρ)/(1 + ρ) |
| 솎아 내면 평균이 더 정확해진다고 봄 | 18 | 솎아 내기는 유효 샘플 수를 늘리지 않는다. 저장 공간을 아낄 뿐이다 |
| 오늘만 보는 체인으로 만들려고 어제에 따른 두 확률을 그냥 평균 냄 | 19 | 어제가 무엇이었을 확률로 가중 평균해야 하고, 그래도 다음은 오늘만으로 정해지지 않는다. (어제, 오늘)을 한 상태로 묶는다 |
| 늘 가장 큰 확률만 고르면 가장 그럴듯한 글이 나온다고 봄 | 20 | 그것은 결정론적인 체인이라 유한한 상태에서 반드시 고리에 갇힌다. 확률대로 뽑아야 고리를 벗어난다 |
요약
이 장에서 한 일을 정리해 보자. 다음 상태를 뽑는 확률이 지금 상태에만 달린 과정이 마르코프 체인이고, 그 확률을 모은 전이 행렬 P를 n번 곱하면 n스텝 뒤의 확률이 나온다. 한 스텝을 더 가도 바뀌지 않는 분포가 정상 분포 π = πP이고, 갇힌 곳과 주기가 없는 체인은 어디서 시작하든 이 분포로 간다. 처음과의 차이는 스텝마다 두 번째 고윳값만큼 줄어든다. 페이지랭크는 웹을 떠도는 사람의 정상 분포이고, 디퓨전 모델의 노이즈 섞기는 정규분포를 정상 분포로 갖도록 설계한 체인이다.
이 장의 첫 물음, 서로 기대는 샘플의 평균도 참값으로 모이느냐에 대한 답은 에르고드 정리다. 갇힌 곳 없이 모든 상태를 오가는 체인에서는 시간 평균이 정상 분포에 대한 평균으로 간다. 마르코프가 네크라소프에게 보인 대로 큰 수의 법칙은 독립 없이도 성립한다. 다만 시간 평균이 모이는 속도는 샘플끼리 얼마나 닮았는지에 달려 있어, 같은 상태에 머무르려는 체인은 더 오래 돌려야 한다. 서로 넘어가기 어려운 상태 묶음이 있으면 에르고드 정리는 성립해도 실제로 돌린 길이가 「오래」가 아닐 수 있다.
둘째 물음, Z 없이 볼츠만 분포에서 뽑는 법에 대한 답은 세부 균형과 메트로폴리스 알고리즘이다. 짝마다 오가는 흐름이 같으면 그 분포는 정상 분포이고, 세부 균형 조건은 확률의 비만 요구한다. 옆 상태를 제안하고 min(1, e^(−βΔE))로 받아들이면 Z가 지워진 채 세부 균형이 성립한다. 제안이 대칭이 아니면 제안 확률의 비를 곱해 바로잡는다. 체인이 처음을 잊는 데 걸리는 스텝 수가 섞임 시간이고, 카드 52장의 리플 셔플은 다섯 번에서 여덟 번 사이에 급히 섞인다. 앞을 여럿 보는 과정도 앞 k개를 한 상태로 묶으면 체인이고, 언어 모델은 상태가 10^4814가지인 체인의 전이 행렬을 신경망으로 계산한다.
막힌 곳
이제 우리는 정규화 합 Z를 몰라도 볼츠만 분포에서 샘플을 뽑을 수 있고, 그 샘플의 시간 평균이 분포에 대한 평균으로 간다는 것도 안다. 평균 에너지, 자화, 사후 평균처럼 샘플마다 값이 하나씩 있는 양은 이 방법으로 모두 잴 수 있다. 그런데 Z 자체는 어떨까? 메트로폴리스는 Z를 지워서 작동했으므로, 그렇게 뽑은 샘플 어디에도 Z는 남아 있지 않다. 볼츠만 분포를 처음 세울 때 나눗셈에 쓰고 버린 이 합에는 샘플 하나하나의 평균으로는 꺼낼 수 없는 무엇이 담겨 있을까? 그리고 그것이 꼭 필요한 물음이 있다면, 그 물음에는 어떻게 답해야 할까?