154강 문제 2에서 이상한 것을 보았습니다. 초기분포를 세 가지로 완전히 다르게 잡았는데 걸음 뒤에는 모두 같은 분포에 있었습니다.
출발점을 잊습니다. 그리고 문제 4에서 의 모든 행이 이 분포로 수렴하는 것을 확인했습니다.
한 걸음 걸어도 변하지 않는 분포가 있고, 연쇄가 그곳으로 갑니다. 이 강의는 세 가지를 밝힙니다.
| 질문 | 답 |
|---|---|
| 그 분포를 어떻게 구하는가 | 고유값 의 왼쪽 고유벡터 |
| 언제 존재하고 언제 유일한가 | 존재는 언제나, 유일성은 기약성 |
| 얼마나 빨리 가는가 | 두 번째 고유값이 정합니다 |
계산이 전부 선형대수입니다. 84강의 고유값, 85강의 대각화, 86강의 스펙트럼 정리가 여기서 확률의 결론을 냅니다.
그리고 마지막 문제가 157강의 문을 엽니다. 지금까지는 가 주어지고 를 구했는데, 를 정해 놓고 를 만들 수 있다면 원하는 분포에서 표본을 뽑을 수 있습니다.
문제. 154강 날씨 연쇄의 정상분포를 구합니다.
(1) 선형계, 고유벡터, 거듭제곱 세 방법으로 구하세요.
(2) 분수로 나타내세요.
(3) 정상분포가 반드시 존재하는 이유를 쓰세요.
생각의 실마리. 는 이므로 의 고유값 에 대한 고유벡터를 찾는 문제입니다.
풀이. (1)(2) 검산 결과입니다.
| 방법 | 결과 |
|---|---|
| 선형계 | |
| 고유벡터 | |
| 의 첫 행 | |
| 분수 |
**세 방법의 최대 차이가 **이고, 와 의 차이가 입니다.
(3) 확률행렬은 각 행의 합이 입니다. 그러면 이므로 이 오른쪽 고유벡터의 고유값입니다.
고유값은 와 가 같으므로 왼쪽에도 고유값 이 있고, 페론-프로베니우스 정리가 그 고유벡터를 음이 아니게 잡을 수 있다고 보장합니다.
이 문제에서 배우는 것: 정상분포.
정상분포. 이고 , 인 행벡터입니다.
| 구하는 방법 | 계산 |
|---|---|
| 선형계 | 에 을 붙여 풉니다 |
| 고유벡터 | 의 고유값 고유벡터를 정규화합니다 |
| 거듭제곱 | 의 한 행을 씁니다 |
| 상세균형 | 문제 5의 방정식을 풉니다 |
첫째 줄이 실무의 기본입니다. 방정식이 하나 남아돌므로 정규화 조건으로 대체하며, 검산에서는 최소제곱으로 풀었습니다.
정상분포의 뜻이 둘입니다. 하나는 "여기서 출발하면 계속 여기 머문다"이고, 다른 하나는 "오래 걸으면 여기 있을 확률"입니다.
둘이 같아지려면 조건이 필요합니다. 앞의 것은 언제나 성립하지만 뒤의 것은 문제 2의 조건을 요구합니다.
바로 확인 1.
확인 1-1. 정상분포의 정의식을 쓰세요.
답. 이며 성분의 합이 입니다.
확인 1-2. 고유값 이 반드시 있는 이유를 쓰세요.
답. 행합이 이라 이기 때문입니다.
확인 1-3. 날씨 연쇄의 정상분포를 분수로 쓰세요.
답. 입니다.
문제. 기약성과 비주기성을 하나씩 깨 봅니다.
(1) 기약이 아닌 연쇄에서 무엇이 달라지는지 보세요.
(2) 주기가 있는 연쇄에서 무엇이 달라지는지 보세요.
(3) 두 조건이 각각 무엇을 보장하는지 쓰세요.
생각의 실마리. 154강 문제 4에서 두 조건을 이미 만났습니다. 여기서는 각각이 정확히 무엇을 담당하는지 나눕니다.
풀이. (1) 두 덩어리가 아예 끊긴 연쇄입니다.
| 출발 | 걸음 뒤 |
|---|---|
| 앞 덩어리 | |
| 뒤 덩어리 |
출발점에 따라 다른 곳으로 갑니다. 두 분포의 어떤 볼록결합도 정상분포이므로 정상분포가 무한히 많습니다.
(2) 주기 인 연쇄입니다.
| 항목 | 값 |
|---|---|
| 정상분포 | |
| P^ | |
| P^ | |
| 정상분포에서 걸음 뒤 |
정상분포는 유일하게 있습니다. 그런데 은 수렴하지 않고, 다른 곳에서 출발하면 영원히 진동합니다.
정상분포에서 출발하면 그대로 머뭅니다. 정상성의 정의가 그것이므로 당연합니다.
(3) 두 조건이 서로 다른 것을 담당합니다.
이 문제에서 배우는 것: 존재와 유일성과 수렴은 별개입니다.
| 결론 | 필요한 조건 |
|---|---|
| 정상분포의 존재 | 유한 상태이면 언제나 |
| 정상분포의 유일성 | 기약 |
| 기약이고 비주기 | |
| 시간평균의 수렴 | 기약 (비주기는 불필요) |
넷째 줄이 중요합니다. 주기 연쇄에서 은 진동하지만, 시간평균은 여전히 로 수렴합니다. 홀수와 짝수를 섞어 평균하기 때문입니다.
에르고딕 정리(예고). 기약이면 시간평균이 정상분포의 기댓값으로 수렴합니다. 비주기성은 필요 없습니다.
문제 4의 주제이며, 157강의 MCMC가 시간평균을 쓰는 이유입니다.
실무의 진단이 분명합니다. 정상분포가 여러 개로 나오면 기약성이 깨진 것이고, 결과가 진동하면 주기가 있는 것입니다. 154강 문제 4에서 본 대로 자기 전이 하나가 후자를 고칩니다.
바로 확인 2.
확인 2-1. 정상분포의 유일성에 필요한 조건을 쓰세요.
답. 기약성입니다.
확인 2-2. 의 수렴에 필요한 조건을 쓰세요.
답. 기약성과 비주기성입니다.
확인 2-3. 시간평균의 수렴에 필요한 조건을 쓰세요.
답. 기약성만 있으면 됩니다.
문제. 세 연쇄에서 수렴 속도를 잽니다.
(1) 두 번째 고유값과 혼합 시간을 구하세요.
(2) 전변동거리가 기하급수적으로 줄어드는지 확인하세요.
(3) 스펙트럼 상한과 실제를 견주세요.
생각의 실마리. 를 대각화하면 입니다. 항이 정상분포이고 나머지가 오차이므로, 오차의 크기는 이 정합니다.
풀이. (1) 세 연쇄를 견줍니다.
| 연쇄 | 스펙트럼 간격 | 혼합 시간 | |
|---|---|---|---|
| 날씨 상태 | |||
| 느린 상태 | |||
| 빠른 상태 |
느린 연쇄는 두 덩어리를 확률 로만 오갑니다. 간격이 로 작고 혼합 시간이 네 배 이상 깁니다.
빠른 연쇄는 모든 전이가 균등이라 이고 한 걸음에 끝납니다.
(2) 느린 연쇄의 전변동거리입니다.
| 전변동거리 | \lvert\lambda_{2}\rvert^ | 비 | |
|---|---|---|---|
비가 정확히 로 일정합니다. 상한의 모양 이 맞고 입니다.
(3) 스펙트럼 상한과 견줍니다.
| 연쇄 | 스펙트럼 상한 | 실제 혼합 시간 |
|---|---|---|
| 날씨 상태 | ||
| 느린 상태 | ||
| 빠른 상태 |
상한이 실제의 두 배에서 네 배입니다. 정확한 값은 주지 않지만 어느 연쇄가 느린지는 정확히 맞힙니다.
이 문제에서 배우는 것: 스펙트럼 간격이 속도를 정합니다.
전변동거리. 두 분포의 거리를 다음으로 잽니다.
어떤 사건에서 두 분포가 가장 크게 어긋나는지를 재며, 확률의 자연스러운 거리입니다.
혼합 시간. 이며 관례로 를 씁니다.
스펙트럼 상한.
를 스펙트럼 간격이라 부르며 그 역수가 시간 단위입니다. 간격이 절반이 되면 혼합 시간이 두 배가 됩니다.
| 느린 연쇄가 되는 상황 | 예 |
|---|---|
| 덩어리가 약하게 연결 | 병목이 있는 상태공간 |
| 다봉 분포 | 봉우리 사이를 못 넘습니다 |
| 고차원 | 방향이 많아 헤맵니다 |
| 제안이 너무 작음 | 조금씩만 움직입니다 |
| 제안이 너무 큼 | 기각이 잦습니다 |
둘째 줄이 157강의 실무 문제입니다. 149강 문제 4의 다봉 우도에서 MCMC를 돌리면 한 봉우리에 오래 갇히며, 겉보기에는 수렴한 것처럼 보입니다.
넷째와 다섯째 줄이 짝입니다. 제안의 크기에 최적점이 있으며, 157강에서 수용률 라는 지침이 나오는 배경입니다.
바로 확인 3.
확인 3-1. 전변동거리의 정의를 쓰세요.
답. 확률 차이 절댓값 합의 절반이며 사건에 대한 최대 차이와 같습니다.
확인 3-2. 수렴 속도를 정하는 양을 쓰세요.
답. 두 번째 고유값의 크기이며 가 스펙트럼 간격입니다.
확인 3-3. 검산에서 전변동거리와 의 비를 쓰세요.
답. 로 일정합니다.
문제. 한 궤적을 만 걸음 걷습니다.
(1) 비의 시간평균이 정상분포로 가는지 보세요.
(2) 자기상관을 재세요.
(3) 유효 표본 크기를 계산하세요.
생각의 실마리. 142강의 큰 수의 법칙은 독립을 요구했습니다. 연쇄의 표본은 독립이 아닌데도 시간평균이 수렴합니다.
풀이. (1) 검산 결과입니다.
| 비의 시간평균 | 정상분포 값 | 차이 | |
|---|---|---|---|
| 10^ | |||
| 10^ | |||
| 2\times10^ |
한 궤적만으로 정상분포를 얻습니다. 여러 번 다시 시작할 필요가 없습니다.
(2)(3) 자기상관을 잽니다.
| 항목 | 값 |
|---|---|
| \rho_ | |
| \rho_ | |
| \rho_ | |
| 적분 자기상관 시간 | |
| 유효 표본 크기 |
만 개가 독립 표본 만 개의 값어치입니다. 절반 이하입니다.
블록 평균으로도 재 봅니다. 블록 분산이 이고 독립 가정 분산이 이라 비가 입니다. 자기상관에서 얻은 와 표본오차 범위에서 맞습니다.
이 문제에서 배우는 것: 에르고딕 정리.
에르고딕 정리. 기약인 유한 연쇄에서 어떤 초기분포에서 출발해도
142강의 강한 큰 수의 법칙의 종속판입니다. 독립이 아니어도 되고 비주기성도 필요 없습니다.
분산은 달라집니다.
142강 심화 2에서 예고한 유효 표본 크기이며, 가 그 보정 인자입니다.
| 상황 | |
|---|---|
| 독립 | |
| 양의 자기상관 | 보다 큽니다 |
| 음의 자기상관 | 보다 작을 수 있습니다 |
| 느리게 섞이는 연쇄 | 매우 큽니다 |
셋째 줄이 뜻밖입니다. 음의 자기상관을 만들면 독립보다 나을 수 있으며, 대립변수와 같은 원리입니다.
넷째 줄이 문제 3과 이어집니다. 스펙트럼 간격이 작으면 가 크고, 대략 입니다. 날씨 연쇄에서 이며 측정한 와 같은 크기입니다.
를 재지 않으면 오차 막대가 틀립니다. 147강 문제 5에서 유효 표본 크기를 보지 않아 조용히 틀렸던 것과 같은 문제이며, MCMC 결과를 보고할 때 반드시 함께 냅니다.
바로 확인 4.
확인 4-1. 에르고딕 정리를 쓰세요.
답. 기약이면 시간평균이 정상분포의 기댓값으로 수렴합니다.
확인 4-2. 적분 자기상관 시간을 쓰세요.
답. 입니다.
확인 4-3. 검산에서 만 표본의 유효 표본 크기를 쓰세요.
답. 약 만 개입니다.
문제. 정상성의 충분조건을 찾습니다.
(1) 날씨 연쇄가 상세균형을 만족하는지 보세요.
(2) 상세균형 없이 정상분포를 갖는 예를 만드세요.
(3) 목표분포를 정해 놓고 전이를 설계하세요.
생각의 실마리. 는 각 상태에서 들어오는 흐름과 나가는 흐름이 같다는 뜻입니다. 쌍마다 균형을 맞추면 전체 균형이 따라옵니다.
풀이. (1)(2) 검산 결과입니다.
| 연쇄 | 상세균형 최대 위반 | 정상분포 |
|---|---|---|
| 날씨 | ||
| 한쪽으로 도는 연쇄 |
둘 다 상세균형을 만족하지 않습니다. 그런데 도는 연쇄에서도 와 의 차이가 으로 정상분포가 맞습니다.
상세균형은 충분조건이지 필요조건이 아닙니다.
(3) 목표분포 를 정해 놓고 메트로폴리스로 전이를 만듭니다.
| 상태 | 전이확률 |
|---|---|
| 확인 | 값 |
|---|---|
| 상세균형 최대 위반 | 1.39\times10^ |
| 목표분포 | |
| 의 첫 행 |
정확히 목표분포가 정상분포입니다.
이 문제에서 배우는 것: 상세균형과 설계.
상세균형. 모든 쌍에서 다음이 성립하면 가 정상분포입니다.
증명이 한 줄입니다. 에 대해 더하면 왼쪽이 이고 오른쪽이 의 합이 되어 가 나옵니다.
메트로폴리스 전이. 제안 가 대칭이면
상세균형이 자동으로 성립합니다. 이며 와 를 바꿔도 같습니다.
| 성질 | 내용 |
|---|---|
| 정규화 상수 불필요 | 비 만 씁니다 |
| 자기 전이가 생김 | 기각하면 제자리, 비주기성을 줍니다 |
| 기약성 | 제안이 모든 곳에 닿으면 됩니다 |
| 대칭 제안 | 아니면 헤이스팅스 보정이 필요합니다 |
첫째 줄이 결정적입니다. 150강에서 사후분포의 정규화 상수를 계산할 수 없어 격자로 우회했는데, 메트로폴리스는 그 상수를 아예 요구하지 않습니다.
둘째 줄이 154강 문제 4의 요령입니다. 기각이 곧 자기 전이라 주기가 자동으로 깨집니다. 검산에서 대각 성분이 부터 까지 나왔습니다.
방향이 뒤집혔습니다. 지금까지는 가 주어지고 를 구했는데, 이제 를 주고 를 만듭니다. 그것이 157강 마르코프 연쇄 몬테카를로의 전부입니다.
바로 확인 5.
확인 5-1. 상세균형 조건을 쓰세요.
답. 입니다.
확인 5-2. 상세균형이 필요조건인지 쓰세요.
답. 아니며 충분조건일 뿐입니다.
확인 5-3. 메트로폴리스가 정규화 상수를 요구하지 않는 이유를 쓰세요.
답. 비 만 쓰기 때문입니다.
| 개념 | 식 |
|---|---|
| 정상분포 | , |
| 오른쪽 고유벡터 | P\mathbf{1}=\mathbf |
| 전변동거리 | |
| 수렴 속도 | C\lvert\lambda_{2}\rvert^ |
| 스펙트럼 간격 | |
| 혼합 시간 상한 | |
| 에르고딕 정리 | |
| 적분 자기상관 시간 | \tau=1+2\sum_{k\ge1}\rho_ |
| 유효 표본 크기 | |
| 상세균형 | \pi_{i}P_{ij}=\pi_{j}P_ |
| 메트로폴리스 |
| 결론 | 필요한 조건 |
|---|---|
| 정상분포의 존재 | 유한 상태이면 언제나 |
| 유일성 | 기약 |
| 의 수렴 | 기약이고 비주기 |
| 시간평균의 수렴 | 기약 |
| 세 연쇄 | 혼합 시간 | |
|---|---|---|
| 날씨 상태 | ||
| 느린 상태 | ||
| 빠른 상태 |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 정상분포가 언제나 유일하다고 봅니다 | 기약이어야 합니다 |
| 정상분포가 있으면 수렴한다고 봅니다 | 비주기성도 필요합니다 |
| 시간평균에 비주기성이 필요하다고 봅니다 | 기약성만 있으면 됩니다 |
| 상세균형이 필요조건이라 봅니다 | 충분조건일 뿐입니다 |
| 자기상관을 무시하고 오차를 냅니다 | 유효 표본 크기로 보정합니다 |
| 겉보기 수렴을 수렴이라 봅니다 | 느린 연쇄는 갇혀 있을 수 있습니다 |
문제 6. 정상분포의 정의식을 쓰세요.
답. 이며 성분의 합이 입니다.
문제 7. 고유값 이 반드시 있는 이유를 쓰세요.
답. 행합이 이라 이기 때문입니다.
문제 8. 날씨 연쇄의 정상분포를 분수로 쓰세요.
답. 입니다.
문제 9. 유일성과 수렴에 각각 필요한 조건을 쓰세요.
답. 기약성과, 기약성에 비주기성을 더한 것입니다.
문제 10. 시간평균의 수렴에 필요한 조건을 쓰세요.
답. 기약성만 있으면 됩니다.
문제 11. 전변동거리의 정의를 쓰세요.
답. 확률 차이 절댓값 합의 절반입니다.
문제 12. 수렴 속도를 정하는 양과 그 이름을 쓰세요.
답. 두 번째 고유값의 크기이며 를 스펙트럼 간격이라 합니다.
문제 13. 혼합 시간의 스펙트럼 상한을 쓰세요.
답. 입니다.
문제 14. 에르고딕 정리를 쓰세요.
답. 기약이면 시간평균이 정상분포의 기댓값으로 수렴합니다.
문제 15. 적분 자기상관 시간과 유효 표본 크기를 쓰세요.
답. 이며 유효 표본 크기가 입니다.
문제 16. 상세균형 조건과 그것이 주는 것을 쓰세요.
답. 이며 가 정상분포임을 보장합니다.
문제 17. 상세균형이 필요조건인지 쓰고 반례를 쓰세요.
답. 아니며 한쪽으로 도는 연쇄가 반례입니다.
문제 18. 메트로폴리스 전이확률과 그 이점을 쓰세요.
답. 이며 정규화 상수를 요구하지 않습니다.
심화 1. 페론-프로베니우스 정리를 정리하세요.
정상분포의 존재와 유일성이 행렬 이론에서 나옵니다.
페론-프로베니우스 정리. 성분이 모두 양수인 정사각행렬은 양수인 최대 고유값을 갖고, 그 고유값은 단순하며 고유벡터의 성분이 모두 양수입니다.
| 조건 | 얻는 것 |
|---|---|
| 성분이 모두 양수 | 고유값 이 단순, 나머지가 |
| 기약이고 비주기 | 어떤 에서 이 모두 양수 |
| 기약이지만 주기 | 크기 인 고유값이 개 |
| 기약이 아님 | 고유값 의 중복도가 소통류 개수 |
셋째 줄이 문제 2의 주기 연쇄입니다. 고유값이 과 이며, 이 진동을 만듭니다.
넷째 줄이 문제 2의 첫 예입니다. 소통류가 둘이라 고유값 의 중복도가 이고, 그래서 정상분포가 무한히 많습니다.
84강의 고유값과 88강의 계수 정리가 확률의 구조를 정확히 설명합니다.
심화 2. 정상분포의 다른 얼굴을 정리하세요.
| 해석 | 내용 |
|---|---|
| 불변 분포 | 한 걸음 걸어도 그대로입니다 |
| 극한 분포 | 오래 걸으면 여기 있습니다 |
| 시간 비율 | 전체 시간 중 에 머문 비율 |
| 되돌아오는 시간 | |
| 흐름의 균형 | 들어오는 만큼 나갑니다 |
넷째 줄이 유용한 공식입니다. 상태 에서 출발해 다시 로 돌아오는 기대 시간이 입니다.
날씨 연쇄에서 비가 다시 오기까지 평균 일이며, 154강 문제 3의 첫걸음 조건화로도 같은 값이 나옵니다.
다섯째 줄이 물리적 해석입니다. 정상 상태에서는 각 상태로 들어오는 확률 흐름과 나가는 흐름이 같으며, 상세균형은 그것을 쌍마다 요구하는 더 강한 조건입니다.
심화 3. 수렴 속도를 재는 다른 방법을 정리하세요.
| 방법 | 내용 | 특징 |
|---|---|---|
| 스펙트럼 간격 | 가역이면 정확합니다 | |
| 전도도 | 병목의 좁기 | 기하적 직관 |
| 결합 | 두 궤적을 붙입니다 | 상한을 줍니다 |
| 강한 정상 시각 | 정확히 정상이 되는 시각 | 상한을 줍니다 |
| 경험적 진단 | 여러 사슬의 분산 비교 | 실무의 기본 |
둘째 줄이 기하적 그림을 줍니다. 상태공간을 둘로 나누는 가장 좁은 목의 흐름을 재며, 치거 부등식이 그것을 스펙트럼 간격과 잇습니다.
문제 3의 느린 연쇄가 정확히 병목의 예입니다. 두 덩어리 사이 흐름이 뿐이라 가 작고, 그래서 간격도 작습니다.
다섯째 줄이 실무의 도구입니다. 여러 초기값에서 사슬을 돌려 사슬 사이 분산과 사슬 안 분산의 비를 보며, 그 값이 에 가까우면 수렴한 것으로 봅니다.
심화 4. 무한 상태 연쇄를 정리하세요.
유한 상태에서는 정상분포가 언제나 있었습니다. 무한하면 없을 수도 있습니다.
| 분류 | 내용 | 예 |
|---|---|---|
| 양재귀 | 되돌아오는 기대 시간이 유한 | 정상분포 존재 |
| 영재귀 | 돌아오지만 기대 시간이 무한 | 정상분포 없음 |
| 일시적 | 돌아오지 못할 수 있습니다 | 정상분포 없음 |
대칭 무작위 걸음이 차원에 따라 갈립니다.
| 차원 | 성질 |
|---|---|
| 차원 | 영재귀 |
| 차원 | 영재귀 |
| 차원 이상 | 일시적 |
**"술취한 사람은 집에 돌아오지만 술취한 새는 못 돌아온다"**는 말이 이것이며, 156강에서 다시 다룹니다.
대기행렬에서 이 분류가 실무 조건이 됩니다. 도착률이 서비스률보다 작아야 양재귀이고 그때만 정상 상태가 존재하며, 그렇지 않으면 대기열이 무한히 길어집니다.
심화 5. 수렴 진단에서 흔히 저지르는 실수를 정리하세요.
| 실수 | 결과 |
|---|---|
| 한 사슬만 보고 판단 | 갇힌 봉우리를 못 봅니다 |
| 궤적이 안정되면 수렴이라 봅니다 | 느린 연쇄는 안정되어 보입니다 |
| 자기상관을 무시 | 오차를 크게 과소평가 |
| 초기 구간을 안 버림 | 편향이 남습니다 |
| 표본을 너무 많이 솎아 냄 | 정보를 버립니다 |
| 유효 표본 크기를 보고 안 함 | 재현이 불가능합니다 |
둘째 줄이 가장 위험합니다. 문제 3의 느린 연쇄를 걸음만 보면 전변동거리가 인데 궤적은 이미 한 덩어리에서 안정되어 보입니다. 겉보기 수렴과 진짜 수렴이 다릅니다.
다섯째 줄이 흔한 오해입니다. 자기상관을 없애려고 걸음마다 하나씩 취하는 것은 분산을 늘립니다. 저장 공간이 문제가 아니면 전부 쓰는 것이 낫습니다.
넷째 줄의 대책은 여러 초기값입니다. 서로 다른 곳에서 시작한 사슬들이 같은 곳에 모이면 초기 구간을 얼마나 버릴지 판단할 수 있습니다.
심화 6. 기계학습에서 정상분포가 쓰이는 자리를 정리하세요.
| 자리 | 무엇이 정상분포인가 | 관련 강의 |
|---|---|---|
| MCMC | 목표 사후분포 | 157강 |
| 페이지랭크 | 페이지의 중요도 | 155강 |
| 확률경사하강의 극한 | 잡음이 만드는 분포 | 236강 |
| 볼츠만 머신 | 에너지 기반 분포 | 213강 |
| 대조발산 | 짧게 돌린 사슬 | 213강 |
| 랜덤워크 임베딩 | 그래프 위의 방문 분포 | 224강 |
| 강화학습의 정책 평가 | 상태 방문 분포 | 274강 |
셋째 줄이 깊습니다. 확률경사하강을 오래 돌리면 한 점에 수렴하지 않고 잡음이 만드는 정상분포를 떠돕니다. 119강 심화 5의 확률미분방정식이 그 극한이며, 학습률이 그 분포의 폭을 정합니다.
다섯째 줄이 실용적 타협입니다. 볼츠만 머신의 학습에는 정상분포에서의 기댓값이 필요한데 수렴을 기다릴 수 없으므로, 몇 걸음만 돌린 사슬로 근사합니다. 편향이 남지만 실용적으로 작동합니다.
일곱째 줄이 274강의 기초입니다. 정책을 고정하면 마르코프 연쇄가 되고, 그 정상분포가 각 상태를 얼마나 자주 방문하는지를 줍니다. 정책경사의 기댓값이 그 분포에 대한 것입니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 정상분포 | 인 행벡터입니다 | |
| \lambda_ | 두 번째 고유값 | 수렴 속도를 정합니다 |
| 스펙트럼 간격 | 클수록 빨리 섞입니다 | |
| 전변동거리 | 두 분포의 최대 차이입니다 | |
| 혼합 시간 | 거리가 아래가 되는 시각입니다 | |
| 적분 자기상관 시간 | 유효 표본 크기의 보정 인자입니다 | |
| 에르고딕 | ergodic | 시간평균이 공간평균과 같습니다 |
| 상세균형 | detailed balance | 쌍마다 흐름이 균형입니다 |
| 페론-프로베니우스 | Perron-Frobenius | 최대 고유값의 성질입니다 |
| 전도도 | conductance | 병목의 좁기입니다 |
| 치거 부등식 | Cheeger inequality | 전도도와 간격을 잇습니다 |
| 양재귀 | positive recurrent | 되돌아오는 기대 시간이 유한합니다 |
| 메트로폴리스 | Metropolis | 목표분포로 전이를 설계합니다 |
다음은 156강 랜덤워크와 확산입니다. 이 강의는 상태가 유한하고 시간이 이산이었습니다.
156강이 그 세 단계를 밟습니다. 심화 4에서 예고한 차원별 재귀성을 확인하고, 걸음 폭을 줄이며 극한을 취하면 143강의 중심극한정리가 연속시간 과정을 만들어 냅니다.
119강 심화 5의 확률미분방정식이 그 극한이며, 261강의 확산모형이 그 위에서 돌아갑니다.
import numpy as np
rng = np.random.default_rng(20260823)
P = np.array([[0.7, 0.2, 0.1],
[0.3, 0.4, 0.3],
[0.2, 0.3, 0.5]])
def stat_solve(M):
k = M.shape[0]
A = np.vstack([M.T - np.eye(k), np.ones(k)])
b = np.zeros(k + 1)
b[-1] = 1.0
return np.linalg.lstsq(A, b, rcond=None)[0]
def tv(a, b):
return 0.5 * float(np.sum(np.abs(a - b)))
# --- 문제 1: 정상분포를 어떻게 구하는가 ---------------------------------
print(" 154강 날씨 연쇄의 정상분포를 세 방법으로 구합니다")
pi_lin = stat_solve(P)
w, V = np.linalg.eig(P.T)
i1 = int(np.argmin(np.abs(w - 1.0)))
pi_eig = np.real(V[:, i1])
pi_eig = pi_eig / pi_eig.sum()
pi_pow = np.linalg.matrix_power(P, 200)[0]
print(" 선형계 (%.10f %.10f %.10f)" % (pi_lin[0], pi_lin[1], pi_lin[2]))
print(" 고유벡터 (%.10f %.10f %.10f)" % (pi_eig[0], pi_eig[1], pi_eig[2]))
print(" P^200 (%.10f %.10f %.10f)" % (pi_pow[0], pi_pow[1], pi_pow[2]))
print(" 분수로 21/46 = %.10f, 13/46 = %.10f, 12/46 = %.10f"
% (21 / 46, 13 / 46, 12 / 46))
print(" 세 방법의 최대 차이 %.2e"
% max(float(np.max(np.abs(pi_lin - pi_eig))), float(np.max(np.abs(pi_lin - pi_pow)))))
print(" pi P 와 pi 의 최대 차이 %.2e" % float(np.max(np.abs(pi_lin @ P - pi_lin))))
print(" 정상분포는 고유값 1 의 왼쪽 고유벡터를 합이 1 이 되게 정규화한 것입니다")
print(" 확률행렬은 행합이 1 이라 오른쪽 고유벡터가 언제나 1 벡터입니다")
print(" P 를 1 벡터에 곱한 결과 (%.1f %.1f %.1f)" % tuple(P @ np.ones(3)))
print(" 그래서 고유값 1 이 반드시 있고 정상분포도 반드시 있습니다")
# --- 문제 2: 존재하고 유일한가 -----------------------------------------
print(" 기약성과 비주기성을 하나씩 깨 보며 무엇이 달라지는지 봅니다")
A1 = np.array([[0.5, 0.5, 0.0, 0.0],
[0.5, 0.5, 0.0, 0.0],
[0.0, 0.0, 0.3, 0.7],
[0.0, 0.0, 0.6, 0.4]])
print(" 기약이 아닌 연쇄입니다. 두 덩어리가 아예 끊겨 있습니다")
for lab, p0 in [("앞 덩어리에서 출발", np.array([1.0, 0, 0, 0])),
("뒤 덩어리에서 출발", np.array([0, 0, 1.0, 0]))]:
v = p0 @ np.linalg.matrix_power(A1, 300)
print(" %-18s -> (%.6f %.6f %.6f %.6f)" % (lab, v[0], v[1], v[2], v[3]))
print(" 정상분포가 하나가 아닙니다. 두 덩어리의 어떤 혼합도 정상분포입니다")
A2 = np.array([[0.0, 1.0], [1.0, 0.0]])
pi2 = stat_solve(A2)
print(" 주기 2 인 연쇄의 정상분포 (%.6f %.6f)" % (pi2[0], pi2[1]))
print(" 그런데 P^n 은 [[%.0f %.0f][%.0f %.0f]] 과 [[%.0f %.0f][%.0f %.0f]] 을 오갑니다"
% (tuple(np.linalg.matrix_power(A2, 99).ravel())
+ tuple(np.linalg.matrix_power(A2, 100).ravel())))
print(" 정상분포에서 출발하면 그대로 머뭅니다. 다른 곳에서 출발하면 진동합니다")
v = pi2 @ np.linalg.matrix_power(A2, 77)
print(" 정상분포에서 77 걸음 뒤 (%.6f %.6f)" % (v[0], v[1]))
print(" 정상분포의 존재는 기약성도 비주기성도 요구하지 않습니다")
print(" 유일성이 기약성을, P^n 의 수렴이 비주기성을 요구합니다")
# --- 문제 3: 얼마나 빨리 수렴하는가 -------------------------------------
print(" 수렴 속도를 두 번째 고유값으로 예측합니다")
eps = 0.02
Slow = np.array([[0.5 - eps, 0.5 - eps, eps, eps],
[0.5 - eps, 0.5 - eps, eps, eps],
[eps, eps, 0.5 - eps, 0.5 - eps],
[eps, eps, 0.5 - eps, 0.5 - eps]])
Fast = np.full((4, 4), 0.25)
chains = [("날씨 3 상태", P), ("느린 4 상태", Slow), ("빠른 4 상태", Fast)]
print(" 연쇄 두 번째 고유값 크기 스펙트럼 간격 혼합 시간(TV<=1/4)")
for name, M in chains:
ev = np.sort(np.abs(np.linalg.eigvals(M)))[::-1]
l2 = float(ev[1])
pi = stat_solve(M)
n, d = 0, 1.0
Mn = np.eye(M.shape[0])
while d > 0.25 and n < 5000:
Mn = Mn @ M
n += 1
d = max(tv(Mn[i], pi) for i in range(M.shape[0]))
print(" %-14s %18.8f %16.8f %18d" % (name, l2, 1 - l2, n))
print(" 스펙트럼 간격이 작을수록 오래 걸립니다. 느린 연쇄는 두 덩어리를 잘 오가지 못합니다")
print(" 전변동거리가 실제로 기하급수적으로 줄어드는지 봅니다. 느린 연쇄입니다")
piS = stat_solve(Slow)
l2S = float(np.sort(np.abs(np.linalg.eigvals(Slow)))[::-1][1])
print(" n 전변동거리 |lambda2|^n 비")
Mn = np.eye(4)
for n in range(1, 61):
Mn = Mn @ Slow
if n in [5, 10, 20, 40, 60]:
d = tv(Mn[0], piS)
print(" %9d %15.10f %15.10f %10.4f" % (n, d, l2S ** n, d / l2S ** n))
print(" 비가 일정해집니다. 상한 C |lambda2|^n 이 정확한 모양을 맞춥니다")
print(" 스펙트럼 상한 log(1/(eps pi_min)) / (1 - |lambda2|) 와 실제를 견줍니다")
print(" 연쇄 스펙트럼 상한 실제 혼합 시간")
for name, M in chains:
l2 = float(np.sort(np.abs(np.linalg.eigvals(M)))[::-1][1])
pm = float(np.min(stat_solve(M)))
ub = np.log(1.0 / (0.25 * pm)) / (1 - l2)
pi_ = stat_solve(M)
n, d = 0, 1.0
Mn = np.eye(M.shape[0])
while d > 0.25 and n < 5000:
Mn = Mn @ M
n += 1
d = max(tv(Mn[i], pi_) for i in range(M.shape[0]))
print(" %-14s %16.2f %16d" % (name, ub, n))
print(" 상한이 실제보다 두 배에서 네 배 큽니다. 방향은 정확히 맞습니다")
# --- 문제 4: 시간평균이 공간평균과 같은가 -------------------------------
print(" 한 궤적을 오래 걸어 시간평균을 봅니다. 날씨 연쇄입니다")
pi = stat_solve(P)
C = np.cumsum(P, axis=1)
N4 = 2000000
s = np.zeros(N4, dtype=int)
u = rng.random(N4)
for t in range(1, N4):
s[t] = int(np.searchsorted(C[s[t - 1]], u[t]))
print(" n 비의 시간평균 정상분포 값 차이")
for n in [1000, 10000, 100000, 2000000]:
f = float((s[:n] == 2).mean())
print(" %9d %16.8f %15.8f %10.6f" % (n, f, pi[2], abs(f - pi[2])))
print(" 한 궤적의 시간평균이 정상분포로 갑니다. 에르고딕 정리입니다")
print(" 독립 표본이 아니므로 오차는 1/sqrt(n) 보다 큽니다. 자기상관을 잽니다")
ind = (s == 2).astype(float)
ind = ind - ind.mean()
v0 = float((ind * ind).mean())
rho = [float((ind[:-k] * ind[k:]).mean()) / v0 for k in range(1, 40)]
tau = 1 + 2 * float(np.sum(rho))
print(" 자기상관 rho1 = %.6f, rho2 = %.6f, rho5 = %.6f" % (rho[0], rho[1], rho[4]))
print(" 적분 자기상관 시간 tau = %.6f" % tau)
print(" 즉 표본 %d 개가 독립 표본 %.0f 개의 값어치입니다" % (N4, N4 / tau))
blk = 20000
bm = ind.reshape(-1, blk).mean(1)
print(" 블록 평균으로 잰 분산 %.4e, 독립 가정 분산 %.4e, 비 %.4f"
% (float(bm.var()) * blk, v0, float(bm.var()) * blk / v0))
# --- 문제 5: 상세균형으로 설계할 수 있는가 ------------------------------
print(" 상세균형을 확인합니다. pi_i P_ij 와 pi_j P_ji 를 견줍니다")
D = np.abs(pi[:, None] * P - (pi[:, None] * P).T)
print(" 날씨 연쇄의 최대 위반 %.8f" % float(np.max(D)))
Cyc = np.array([[0.0, 0.9, 0.1],
[0.1, 0.0, 0.9],
[0.9, 0.1, 0.0]])
pic = stat_solve(Cyc)
Dc = np.abs(pic[:, None] * Cyc - (pic[:, None] * Cyc).T)
print(" 한쪽으로 도는 연쇄의 정상분포 (%.6f %.6f %.6f)" % (pic[0], pic[1], pic[2]))
print(" 그 연쇄의 상세균형 최대 위반 %.8f" % float(np.max(Dc)))
print(" pi P 와 pi 의 차이는 %.2e 로 여전히 정상분포입니다"
% float(np.max(np.abs(pic @ Cyc - pic))))
print(" 상세균형은 정상성의 충분조건이지 필요조건이 아닙니다")
print(" 이제 원하는 분포를 정해 놓고 전이를 만들어 봅니다. 메트로폴리스입니다")
target = np.array([0.1, 0.2, 0.3, 0.4])
k = 4
Q = np.full((k, k), 1.0 / (k - 1))
np.fill_diagonal(Q, 0.0)
Mp = np.zeros((k, k))
for i in range(k):
for j in range(k):
if i != j:
Mp[i, j] = Q[i, j] * min(1.0, target[j] / target[i])
Mp[i, i] = 1.0 - Mp[i].sum()
print(" 만든 전이행렬")
for i in range(k):
print(" [%.6f %.6f %.6f %.6f]" % tuple(Mp[i]))
Dm = np.abs(target[:, None] * Mp - (target[:, None] * Mp).T)
print(" 상세균형 최대 위반 %.2e" % float(np.max(Dm)))
print(" 목표분포 (%.6f %.6f %.6f %.6f)" % tuple(target))
print(" P^500 의 첫 행 (%.6f %.6f %.6f %.6f)"
% tuple(np.linalg.matrix_power(Mp, 500)[0]))
print(" 대각 성분이 %.6f 부터 %.6f 까지입니다. 기각이 자기 전이가 됩니다"
% (float(np.min(np.diag(Mp))), float(np.max(np.diag(Mp)))))
print(" 목표분포를 넣기만 하면 그것을 정상분포로 갖는 연쇄가 나옵니다")
print(" 정규화 상수를 몰라도 됩니다. 비 target[j]/target[i] 만 쓰기 때문입니다")
print(" 이것이 157강 마르코프 연쇄 몬테카를로의 뼈대입니다")
# 154강 날씨 연쇄의 정상분포를 세 방법으로 구합니다
# 선형계 (0.4565217391 0.2826086957 0.2608695652)
# 고유벡터 (0.4565217391 0.2826086957 0.2608695652)
# P^200 (0.4565217391 0.2826086957 0.2608695652)
# 분수로 21/46 = 0.4565217391, 13/46 = 0.2826086957, 12/46 = 0.2608695652
# 세 방법의 최대 차이 7.22e-16
# pi P 와 pi 의 최대 차이 2.22e-16
# 정상분포는 고유값 1 의 왼쪽 고유벡터를 합이 1 이 되게 정규화한 것입니다
# 확률행렬은 행합이 1 이라 오른쪽 고유벡터가 언제나 1 벡터입니다
# P 를 1 벡터에 곱한 결과 (1.0 1.0 1.0)
# 그래서 고유값 1 이 반드시 있고 정상분포도 반드시 있습니다
# 기약성과 비주기성을 하나씩 깨 보며 무엇이 달라지는지 봅니다
# 기약이 아닌 연쇄입니다. 두 덩어리가 아예 끊겨 있습니다
# 앞 덩어리에서 출발 -> (0.500000 0.500000 0.000000 0.000000)
# 뒤 덩어리에서 출발 -> (0.000000 0.000000 0.461538 0.538462)
# 정상분포가 하나가 아닙니다. 두 덩어리의 어떤 혼합도 정상분포입니다
# 주기 2 인 연쇄의 정상분포 (0.500000 0.500000)
# 그런데 P^n 은 [[0 1][1 0]] 과 [[1 0][0 1]] 을 오갑니다
# 정상분포에서 출발하면 그대로 머뭅니다. 다른 곳에서 출발하면 진동합니다
# 정상분포에서 77 걸음 뒤 (0.500000 0.500000)
# 정상분포의 존재는 기약성도 비주기성도 요구하지 않습니다
# 유일성이 기약성을, P^n 의 수렴이 비주기성을 요구합니다
# 수렴 속도를 두 번째 고유값으로 예측합니다
# 연쇄 두 번째 고유값 크기 스펙트럼 간격 혼합 시간(TV<=1/4)
# 날씨 3 상태 0.47320508 0.52679492 2
# 느린 4 상태 0.92000000 0.08000000 9
# 빠른 4 상태 0.00000000 1.00000000 1
# 스펙트럼 간격이 작을수록 오래 걸립니다. 느린 연쇄는 두 덩어리를 잘 오가지 못합니다
# 전변동거리가 실제로 기하급수적으로 줄어드는지 봅니다. 느린 연쇄입니다
# n 전변동거리 |lambda2|^n 비
# 5 0.3295407616 0.6590815232 0.5000
# 10 0.2171942271 0.4343884542 0.5000
# 20 0.0943466646 0.1886933292 0.5000
# 40 0.0178025862 0.0356051725 0.5000
# 60 0.0033592293 0.0067184585 0.5000
# 비가 일정해집니다. 상한 C |lambda2|^n 이 정확한 모양을 맞춥니다
# 스펙트럼 상한 log(1/(eps pi_min)) / (1 - |lambda2|) 와 실제를 견줍니다
# 연쇄 스펙트럼 상한 실제 혼합 시간
# 날씨 3 상태 5.18 2
# 느린 4 상태 34.66 9
# 빠른 4 상태 2.77 1
# 상한이 실제보다 두 배에서 네 배 큽니다. 방향은 정확히 맞습니다
# 한 궤적을 오래 걸어 시간평균을 봅니다. 날씨 연쇄입니다
# n 비의 시간평균 정상분포 값 차이
# 1000 0.27100000 0.26086957 0.010130
# 10000 0.25230000 0.26086957 0.008570
# 100000 0.26193000 0.26086957 0.001060
# 2000000 0.26133950 0.26086957 0.000470
# 한 궤적의 시간평균이 정상분포로 갑니다. 에르고딕 정리입니다
# 독립 표본이 아니므로 오차는 1/sqrt(n) 보다 큽니다. 자기상관을 잽니다
# 자기상관 rho1 = 0.323911, rho2 = 0.133881, rho5 = 0.014166
# 적분 자기상관 시간 tau = 2.145248
# 즉 표본 2000000 개가 독립 표본 932293 개의 값어치입니다
# 블록 평균으로 잰 분산 3.5553e-01, 독립 가정 분산 1.9304e-01, 비 1.8417
# 상세균형을 확인합니다. pi_i P_ij 와 pi_j P_ji 를 견줍니다
# 날씨 연쇄의 최대 위반 0.00652174
# 한쪽으로 도는 연쇄의 정상분포 (0.333333 0.333333 0.333333)
# 그 연쇄의 상세균형 최대 위반 0.26666667
# pi P 와 pi 의 차이는 2.78e-16 로 여전히 정상분포입니다
# 상세균형은 정상성의 충분조건이지 필요조건이 아닙니다
# 이제 원하는 분포를 정해 놓고 전이를 만들어 봅니다. 메트로폴리스입니다
# 만든 전이행렬
# [0.000000 0.333333 0.333333 0.333333]
# [0.166667 0.166667 0.333333 0.333333]
# [0.111111 0.222222 0.333333 0.333333]
# [0.083333 0.166667 0.250000 0.500000]
# 상세균형 최대 위반 1.39e-17
# 목표분포 (0.100000 0.200000 0.300000 0.400000)
# P^500 의 첫 행 (0.100000 0.200000 0.300000 0.400000)
# 대각 성분이 0.000000 부터 0.500000 까지입니다. 기각이 자기 전이가 됩니다
# 목표분포를 넣기만 하면 그것을 정상분포로 갖는 연쇄가 나옵니다
# 정규화 상수를 몰라도 됩니다. 비 target[j]/target[i] 만 쓰기 때문입니다
# 이것이 157강 마르코프 연쇄 몬테카를로의 뼈대입니다