06단원까지 관측은 언제나 독립이었습니다.
큰 수의 법칙도 중심극한정리도 호에프딩 부등식도 독립을 전제로 세웠고, 149강의 우도를 곱으로 쓴 것도 독립 덕분이었습니다.
그런데 시간이 들어오면 그 전제가 깨집니다. 오늘의 날씨는 어제와 무관하지 않고, 이 문장의 다음 단어는 앞 단어에 달려 있으며, 로봇의 다음 위치는 지금 위치에서만 갈 수 있는 곳입니다.
독립을 버리되 최소한만 버립니다. 과거 전체가 아니라 바로 직전 하나만 필요하다는 이 성질이 마르코프 성질이며, 그것만으로 계산이 가능해집니다.
| 이 단원이 여는 것 | 관련 강의 |
|---|---|
| 시간에 따라 변하는 확률 | 154~157강 |
| 사후분포에서 표본 뽑기 | 157강, 150강의 미완 |
| 고차원 표집 | 147강 문제 4가 무너진 자리 |
| 강화학습의 환경 모형 | 274강 마르코프 결정과정 |
| 언어모형의 다음 토큰 | 298강 자기회귀 |
계산 도구는 선형대수입니다. 전이확률을 행렬로 놓으면 걸음 뒤의 분포가 행렬 거듭제곱 하나로 나오며, 84~89강의 고유값이 155강에서 수렴을 설명합니다.
문제. 날씨 세 상태의 전이행렬로 만 걸음을 걷습니다.
(1) 한 걸음 전이 빈도가 전이행렬과 맞는지 확인하세요.
(2) 전전날을 함께 조건으로 걸어 보세요.
(3) 결과가 무엇을 뜻하는지 쓰세요.
생각의 실마리. 조건을 더 걸었는데 답이 달라지지 않는다면, 더 건 조건이 정보를 주지 않는다는 뜻입니다. 124강의 조건부 독립과 같은 구조입니다.
풀이. (1) 전이행렬은 다음과 같습니다.
| 상태 | 맑음으로 | 흐림으로 | 비로 |
|---|---|---|---|
| 맑음 | |||
| 흐림 | |||
| 비 |
검산의 빈도가 각 행에서 최대 오차 안쪽으로 맞습니다.
(2) 전전날을 함께 조건으로 겁니다. 오늘이 비일 확률입니다.
| (전전날, 어제) | 조건부 확률 | 어제만 볼 때 | 차이 |
|---|---|---|---|
| (맑음, 맑음) | |||
| (맑음, 비) | |||
| (흐림, 흐림) | |||
| (비, 맑음) | |||
| (비, 비) |
(3) 전전날을 알아도 예측이 달라지지 않습니다. 어제가 같으면 전전날이 무엇이든 오늘의 분포가 같습니다.
이 문제에서 배우는 것: 마르코프 성질.
마르코프 성질. 미래는 현재만 주어지면 과거와 조건부 독립입니다.
**"기억이 없다"가 아니라 "현재가 기억을 다 담고 있다"**입니다. 어제의 날씨 안에 필요한 과거 정보가 전부 요약되어 있습니다.
전이행렬. 이며 각 행의 합이 입니다.
| 성질 | 내용 |
|---|---|
| 확률행렬 | 성분이 음이 아니고 행합이 입니다 |
| 시간동질 | 가 에 의존하지 않습니다 |
| 행이 조건부분포 | 행이 일 때의 분포입니다 |
| 곱이 합성 | 두 걸음은 행렬 곱입니다 |
136강의 결합분포를 조건부로 쪼갠 것이 전이행렬이며, 137강의 조건부분포가 행마다 하나씩 놓인 셈입니다.
131강의 지수분포가 이 성질의 연속판입니다. "이미 기다린 시간이 남은 대기에 영향을 주지 않는다"는 무기억성이 마르코프 성질의 연속시간 형태이며, 156강에서 다시 나옵니다.
바로 확인 1.
확인 1-1. 마르코프 성질을 쓰세요.
답. 미래가 현재만 주어지면 과거와 조건부 독립입니다.
확인 1-2. 전이행렬의 두 조건을 쓰세요.
답. 성분이 음이 아니고 각 행의 합이 입니다.
확인 1-3. 전이행렬의 한 행이 무엇인지 쓰세요.
답. 그 상태에서 출발할 때의 조건부분포입니다.
문제. 걸음 전이확률을 조사합니다.
(1) 의 성분이 실제 빈도와 맞는지 보세요.
(2) 채프먼-콜모고로프 등식을 확인하세요.
(3) 여러 초기분포에서 걸음 뒤를 비교하세요.
생각의 실마리. 두 걸음에 에서 로 가려면 중간 상태 를 하나 거칩니다. 그 에 대해 더하면 되고, 그것이 행렬 곱의 정의입니다.
풀이. (1) 맑음에서 출발해 걸음 뒤 비일 확률입니다.
| 의 성분 | 수치 빈도 | 차이 | |
|---|---|---|---|
(2) 채프먼-콜모고로프 등식입니다.
| 등식 | 최대 차이 |
|---|---|
| P^{5}=P^{2}P^ | 1.11\times10^ |
| P^{10}=P^{4}P^ | 5.55\times10^ |
| P^{20}=P^{7}P^ | 5.55\times10^ |
기계 정밀도까지 성립합니다. 행렬 곱의 결합법칙이므로 당연하지만, 확률의 언어로는 전혀 자명하지 않은 사실입니다.
(3) 초기분포를 바꿔 봅니다.
| 초기분포 | |||
|---|---|---|---|
| 맑음에서 출발 | |||
| 비에서 출발 | |||
| 균등하게 출발 |
에서 세 줄이 같습니다. 출발점이 전혀 다른데 같은 분포에 이르렀습니다.
이 문제에서 배우는 것: 행렬 거듭제곱이 시간 전개입니다.
채프먼-콜모고로프 등식.
중간 시점에서 어디에 있었는지로 나눠 더한 것이며, 121강의 전체 확률 법칙입니다.
분포의 전개. 초기분포를 행벡터 으로 놓으면
| 대상 | 표기 | 계산 |
|---|---|---|
| 한 걸음 | 주어집니다 | |
| 걸음 | P^ | 행렬 거듭제곱 |
| 걸음 뒤 분포 | \boldsymbol\pi_{0}P^ | 벡터 곱하기 행렬 |
| 극한 | \lim P^ | 155강 |
행벡터를 왼쪽에 곱합니다. 확률론의 관례이며, 62강의 열벡터 관례와 반대이므로 주의합니다.
을 직접 곱하지 않아도 됩니다. 를 대각화하면 이라 고유값의 제곱만 계산하면 되며, 85강의 고유값 분해가 그대로 쓰입니다. 155강에서 그 고유값이 수렴 속도를 정합니다.
바로 확인 2.
확인 2-1. 채프먼-콜모고로프 등식을 쓰세요.
답. 입니다.
확인 2-2. 걸음 뒤 분포를 쓰세요.
답. 이며 행벡터를 왼쪽에 곱합니다.
확인 2-3. 을 빠르게 계산하는 방법을 쓰세요.
답. 대각화해 고유값만 제곱합니다.
문제. 도박꾼의 파산을 봅니다. 목표 , 한 판 이길 확률 입니다.
(1) 파산 확률을 이론과 수치로 구하세요.
(2) 기대 판수도 구하세요.
(3) 같은 문제를 선형방정식으로 푸세요.
생각의 실마리. 자금이 이나 에 닿으면 게임이 끝납니다. 그 두 상태에서는 나갈 수 없으며, 나머지 상태와 성격이 완전히 다릅니다.
풀이. (1)(2) 검산 결과입니다.
| 시작 자금 | 파산 확률 이론 | 수치 | 기대 판수 이론 | 수치 |
|---|---|---|---|---|
일 때 파산 확률은 다음과 같습니다.
기대 판수가 단조가 아닙니다. 에서 로 가장 길고 양쪽 끝에 가까울수록 짧습니다. 경계에 가까우면 빨리 끝나기 때문입니다.
(3) 선형방정식으로도 풉니다.
| 선형계 해 | 값 |
|---|---|
이론 공식과 완전히 같습니다. 첫걸음 조건화로 세운 방정식이며, 137강의 전체 기댓값 법칙을 상태마다 적용한 것입니다.
이 문제에서 배우는 것: 상태의 분류.
| 개념 | 뜻 |
|---|---|
| 도달가능 | 에서 로 갈 확률이 양수입니다 |
| 소통 | 서로 도달가능합니다 |
| 기약 | 모든 상태가 하나의 소통류를 이룹니다 |
| 재귀 | 확률 로 되돌아옵니다 |
| 일시적 | 되돌아오지 못할 확률이 양수입니다 |
| 흡수 | 이라 나갈 수 없습니다 |
| 주기 | 되돌아오는 걸음 수의 최대공약수 |
도박꾼의 연쇄는 기약이 아닙니다. 과 이 각각 자기만의 소통류이고 나머지 부터 가 또 하나의 류인데, 그 류에서 나가면 돌아오지 못합니다.
첫걸음 조건화. 한 걸음을 어디로 갔는지로 나누면 미지량 사이의 선형방정식이 나옵니다.
흡수 확률뿐 아니라 기대 도달 시간도 같은 방법으로 나옵니다. 기대 시간이면 우변에 을 더합니다.
274강 벨만 방정식이 정확히 이 꼴입니다. 보상을 더하고 할인율을 곱하면 강화학습의 가치함수 방정식이 되며, 첫걸음 조건화가 그 전부입니다.
바로 확인 3.
확인 3-1. 흡수 상태의 정의를 쓰세요.
답. 이라 한 번 들어가면 나갈 수 없는 상태입니다.
확인 3-2. 재귀와 일시적의 차이를 쓰세요.
답. 확률 로 되돌아오면 재귀이고 그렇지 않으면 일시적입니다.
확인 3-3. 첫걸음 조건화가 주는 것을 쓰세요.
답. 흡수 확률과 기대 시간에 대한 선형방정식입니다.
문제. 이 수렴하는지 봅니다.
(1) 날씨 연쇄에서 의 행들이 어떻게 되는지 보세요.
(2) 주기가 인 연쇄에서는 어떻게 되는지 보세요.
(3) 주기를 깨면 무엇이 달라지는지 보세요.
생각의 실마리. 문제 2에서 초기분포가 달라도 이면 같아졌습니다. 의 모든 행이 같아진다는 뜻입니다.
풀이. (1) 날씨 연쇄입니다.
| 행들의 최대 차이 | 맑음 성분 | |
|---|---|---|
차이가 대략 걸음마다 배로 줄어듭니다. 기하급수적 수렴이며, 155강에서 그 비율이 두 번째 고유값임을 밝힙니다.
**가 **입니다. 155강의 정상분포입니다.
(2) 주기가 인 연쇄입니다.
| Q^ | |
|---|---|
수렴하지 않습니다. 홀수와 짝수에서 값이 정반대이며, 아무리 걸어도 진동이 사라지지 않습니다.
(3) 자기 자신으로 가는 확률을 만 넣습니다.
| 의 성분 | |
|---|---|
작은 자기 전이 하나가 주기를 깹니다.
이 문제에서 배우는 것: 수렴의 두 조건.
수렴 정리(예고). 유한 상태 연쇄가 기약이고 비주기이면 의 모든 행이 같은 분포 로 수렴합니다.
| 조건 | 없으면 |
|---|---|
| 기약 | 갇힌 부분마다 다른 극한 |
| 비주기 | 진동하며 수렴하지 않습니다 |
두 조건 모두 필요합니다. 도박꾼의 연쇄는 기약이 아니라 출발점에 따라 극한이 다르고, 주기 연쇄는 기약인데 비주기가 아니라 진동합니다.
비주기성을 만드는 가장 쉬운 방법은 자기 전이입니다. 어떤 상태에 이면 그 상태의 주기가 이고, 기약이면 모든 상태의 주기가 같으므로 전체가 비주기가 됩니다.
157강의 MCMC가 이 요령을 씁니다. 메트로폴리스 알고리즘은 제안을 기각하면 제자리에 머무는데, 그 기각이 자기 전이라 비주기성을 공짜로 줍니다.
바로 확인 4.
확인 4-1. 이 수렴하기 위한 두 조건을 쓰세요.
답. 기약성과 비주기성입니다.
확인 4-2. 주기가 있으면 어떻게 되는지 쓰세요.
답. 진동하며 수렴하지 않습니다.
확인 4-3. 비주기성을 만드는 쉬운 방법을 쓰세요.
답. 어떤 상태에 자기 전이 확률을 넣습니다.
문제. 오늘이 어제와 그저께에 함께 의존하는 과정을 만듭니다.
(1) 어제만 조건으로 걸면 무엇이 보이는지 보세요.
(2) 그저께까지 걸면 어떻게 달라지는지 보세요.
(3) 상태를 확장해 마르코프로 만드세요.
생각의 실마리. 마르코프 성질은 과정의 성질이 아니라 상태를 어떻게 정의했느냐의 성질입니다.
풀이. 오늘이 일 확률이 어제와 그저께가 다르면 , 같으면 입니다.
(1) 어제만 조건으로 겁니다.
| 어제 | 오늘이 일 확률 |
|---|---|
둘 다 입니다. 어제만 보면 아무 정보가 없어 보입니다.
(2) 그저께까지 함께 겁니다.
| (그저께, 어제) | 조건부 확률 | 참값 |
|---|---|---|
전혀 다릅니다. 예측이 거의 확실해집니다.
| 모형 | 평균 로그손실 |
|---|---|
| 차로 본 경우 | |
| 차로 본 경우 | |
| 이론 엔트로피 |
**은 **입니다. 차 모형은 동전 던지기와 정확히 같은 수준이며, 정보를 통째로 버렸습니다.
(3) 상태를 (그저께, 어제) 쌍으로 확장합니다.
| 상태 | 전이확률 |
|---|---|
각 행에 이 두 개씩 있습니다. 새 쌍의 앞자리가 이전 쌍의 뒷자리로 정해져 있으므로 갈 수 있는 곳이 둘뿐입니다.
이 문제에서 배우는 것: 상태 확장.
차 마르코프 연쇄는 상태를 개 묶으면 차가 됩니다.
| 확장 | 상태 개수 | 대가 |
|---|---|---|
| 차, 상태 개 | 없습니다 | |
| 차 | m^ | 지수적으로 늘어납니다 |
| 은닉 상태 | 관측 불가 | 추정이 필요합니다 |
대가가 상태 폭발입니다. 어휘가 만인 언어에서 차 마르코프를 쓰면 상태가 개이며, 298강의 언어모형이 신경망으로 그 문제를 우회합니다.
관측할 수 없는 상태도 있습니다. 진짜 상태가 숨어 있고 그 함수만 관측되면 은닉 마르코프 모형이며, 414강에서 다룹니다.
실무의 교훈이 분명합니다. "이 자료는 마르코프가 아니다"라고 말하기 전에 상태를 제대로 정의했는지 먼저 봅니다. 위치만 상태로 쓰면 마르코프가 아닌 물체의 운동이 위치와 속도를 함께 쓰면 마르코프가 됩니다.
바로 확인 5.
확인 5-1. 차 마르코프를 차로 만드는 방법을 쓰세요.
답. 최근 개를 묶어 하나의 상태로 씁니다.
확인 5-2. 상태 확장의 대가를 쓰세요.
답. 상태 개수가 으로 지수적으로 늘어납니다.
확인 5-3. 검산에서 차 모형의 로그손실을 쓰세요.
답. 이며 와 같습니다.
| 개념 | 식 |
|---|---|
| 마르코프 성질 | |
| 전이행렬 | , 행합 |
| 채프먼-콜모고로프 | P^{(m+n)}=P^{m}P^ |
| 분포의 전개 | \boldsymbol\pi_{n}=\boldsymbol\pi_{0}P^ |
| 첫걸음 조건화 | |
| 기대 도달 시간 | |
| 도박꾼의 파산 | , |
| 상태 확장 |
| 상태의 분류 | 뜻 |
|---|---|
| 도달가능 | 갈 확률이 양수입니다 |
| 소통 | 서로 도달가능합니다 |
| 기약 | 모두 하나의 소통류입니다 |
| 재귀 | 확률 로 돌아옵니다 |
| 일시적 | 돌아오지 못할 수 있습니다 |
| 흡수 | 나갈 수 없습니다 |
| 주기 | 돌아오는 걸음 수의 최대공약수 |
| 수렴 | 조건 |
|---|---|
| 의 모든 행이 같아짐 | 기약이고 비주기 |
| 갇힌 부분마다 다른 극한 | 기약이 아닐 때 |
| 진동 | 주기가 있을 때 |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 마르코프를 "기억이 없다"로 읽습니다 | 현재가 기억을 다 담고 있습니다 |
| 열벡터에 오른쪽 곱을 합니다 | 행벡터를 왼쪽에 곱합니다 |
| 기약이면 수렴한다고 봅니다 | 비주기성도 필요합니다 |
| 흡수 상태가 있는데 정상분포를 찾습니다 | 기약이 아닙니다 |
| 마르코프가 아니라고 결론짓습니다 | 상태 정의를 먼저 봅니다 |
| 차 확장의 비용을 무시합니다 | 상태가 으로 폭발합니다 |
문제 6. 마르코프 성질을 쓰세요.
답. 미래가 현재만 주어지면 과거와 조건부 독립입니다.
문제 7. 전이행렬의 두 조건을 쓰세요.
답. 성분이 음이 아니고 각 행의 합이 입니다.
문제 8. 채프먼-콜모고로프 등식을 쓰세요.
답. 입니다.
문제 9. 걸음 뒤의 분포를 쓰세요.
답. 이며 행벡터를 왼쪽에 곱합니다.
문제 10. 을 빠르게 계산하는 방법을 쓰세요.
답. 대각화해 고유값만 제곱합니다.
문제 11. 흡수 상태와 일시적 상태를 각각 쓰세요.
답. 나갈 수 없는 상태와 되돌아오지 못할 확률이 양수인 상태입니다.
문제 12. 첫걸음 조건화로 나오는 두 방정식을 쓰세요.
답. 와 입니다.
문제 13. 도박꾼의 파산 확률 공식을 쓰세요.
답. 일 때 입니다.
문제 14. 기대 판수가 시작 자금에 대해 단조인지 쓰세요.
답. 아니며 가운데에서 가장 길고 경계에 가까울수록 짧습니다.
문제 15. 이 수렴하기 위한 두 조건을 쓰세요.
답. 기약성과 비주기성입니다.
문제 16. 비주기성을 만드는 쉬운 방법을 쓰세요.
답. 어떤 상태에 자기 전이 확률을 넣습니다.
문제 17. 차 마르코프를 차로 만드는 방법과 대가를 쓰세요.
답. 최근 개를 묶으며 상태가 으로 늘어납니다.
문제 18. 검산에서 차 모형과 차 모형의 로그손실을 쓰세요.
답. 과 이며 앞쪽이 입니다.
심화 1. 흡수 연쇄를 행렬로 정리하세요.
흡수 상태가 있으면 전이행렬을 블록으로 나눌 수 있습니다.
가 일시적 상태끼리, 이 일시적에서 흡수로 가는 부분입니다.
| 양 | 식 |
|---|---|
| 기본행렬 | N=(I-Q)^ |
| 기대 방문 횟수 | N_ |
| 기대 흡수 시간 | N\mathbf |
| 흡수 확률 |
****이며 18강의 등비급수를 행렬로 쓴 것입니다. 의 스펙트럼 반지름이 보다 작아야 수렴하는데, 일시적 상태에서는 언제나 그렇습니다.
문제 3의 두 계산이 이 공식의 특수한 경우입니다. 이 흡수 확률이고 이 기대 시간입니다.
78강의 역행렬 계산이 여기서 확률을 줍니다. 상태가 많아지면 선형계를 푸는 것이 시뮬레이션보다 훨씬 정확하고 빠릅니다.
심화 2. 마르코프 연쇄가 나타나는 자리를 정리하세요.
| 자리 | 상태 | 특징 |
|---|---|---|
| 랜덤워크 | 정수 위치 | 156강 |
| 대기행렬 | 대기 인원 | 태어남과 죽음 |
| 유전자 빈도 | 대립유전자 수 | 라이트-피셔 |
| 페이지랭크 | 웹 페이지 | 155강의 정상분포 |
| 강화학습 | 환경 상태 | 274강 |
| 언어모형 | 최근 토큰들 | 298강 |
| MCMC | 표집 공간 | 157강 |
넷째 줄이 유명한 응용입니다. 웹의 링크 구조를 전이행렬로 보고 정상분포를 페이지의 중요도로 씁니다. 링크가 없는 페이지 때문에 기약성이 깨지므로 모든 페이지로 가는 작은 확률을 더하는데, 그것이 감쇠 인자이며 문제 4의 자기 전이와 같은 역할입니다.
다섯째 줄이 이 강의를 강화학습으로 잇습니다. 행동을 고르면 전이행렬이 정해지는 구조이며, 마르코프 결정과정이라 부릅니다. 첫걸음 조건화가 벨만 방정식이 되고, 문제 3에서 푼 선형계가 정책 평가입니다.
심화 3. 마르코프 연쇄를 자료에서 추정하는 방법을 정리하세요.
전이확률을 모르면 자료에서 추정해야 합니다.
149강의 최대우도추정입니다. 우도가 이고 각 행이 독립적으로 다항분포이므로, 148강 문제 5의 베르누이 계산이 행마다 반복됩니다.
| 문제 | 대처 |
|---|---|
| 관측되지 않은 전이 | 150강의 디리클레 사전, 평활화 |
| 상태가 많음 | 축소, 저계수 근사 |
| 시간에 따라 변함 | 비동질 연쇄, 변화점 탐지 |
| 차수를 모름 | 정보기준으로 고릅니다 |
첫째 줄이 실무에서 반드시 나옵니다. 이면 이 되어 그 전이가 영원히 불가능하다고 단정하게 되며, 150강 심화 6의 평활화가 그 문제를 고칩니다.
넷째 줄이 문제 5와 이어집니다. 차수를 늘리면 우도는 반드시 올라가므로, 153강 문제 3의 결정계수와 같은 이유로 벌점이 필요합니다.
심화 4. 시간을 거꾸로 돌리면 무엇이 되는지 정리하세요.
역방향 연쇄. 정상상태에 있는 연쇄를 거꾸로 보면 그것도 마르코프 연쇄이며
이면 가역이라 하며, 그 조건이 상세균형입니다.
| 성질 | 가역 연쇄 |
|---|---|
| 정상분포 | 상세균형을 풀면 나옵니다 |
| 전이행렬 | 대칭으로 만들 수 있습니다 |
| 고유값 | 모두 실수입니다 |
| 예 | 무작위 걸음, 메트로폴리스 |
셋째 줄이 86강의 스펙트럼 정리입니다. 이 대칭이 되므로 고유값이 실수이고 고유벡터가 직교하며, 155강의 수렴 속도 분석이 그 위에서 이루어집니다.
157강의 메트로폴리스 알고리즘이 상세균형을 일부러 만듭니다. 원하는 분포 를 정해 놓고 그것을 만족하는 전이를 설계하며, 그러면 정상분포가 자동으로 가 됩니다.
심화 5. 마르코프 가정이 깨지는 실무의 자리를 정리하세요.
| 상황 | 왜 깨지는가 | 대처 |
|---|---|---|
| 관측이 부분적 | 진짜 상태가 숨어 있습니다 | 은닉 마르코프 |
| 장기 기억 | 먼 과거가 남습니다 | 고차, 순환신경망 |
| 시간에 따라 변함 | 전이 자체가 바뀝니다 | 비동질, 변화점 |
| 개체마다 다름 | 이질성 | 계층모형, 혼합 |
| 시간 간격이 불규칙 | 이산 걸음이 안 맞습니다 | 연속시간, 156강 |
첫째 줄이 가장 흔합니다. 사용자의 진짜 의도는 관측되지 않고 클릭만 보이므로, 관측만으로는 마르코프가 아닙니다. 414강의 은닉 마르코프 모형이 그 구조를 다룹니다.
둘째 줄이 언어에서 결정적입니다. 문장의 첫 단어가 마지막 단어에 영향을 주는 일이 흔하므로 유한 차수로는 부족하며, 300강의 어텐션이 그 문제를 정면으로 다룹니다.
진단이 문제 1의 계산입니다. 조건을 하나 더 걸었을 때 예측이 달라지는지 보면 되며, 달라지면 마르코프가 아닙니다.
심화 6. 기계학습에서 마르코프 연쇄가 쓰이는 자리를 정리하세요.
| 자리 | 어떻게 쓰이는가 | 관련 강의 |
|---|---|---|
| MCMC 표집 | 정상분포를 목표로 설계 | 157강 |
| 강화학습 | 마르코프 결정과정 | 274강 |
| 자기회귀 생성 | 조건부 분포의 연쇄 | 298강 |
| 확산모형 | 잡음을 더하는 마르코프 사슬 | 261강 |
| 은닉 마르코프 | 숨은 상태의 추론 | 414강 |
| 페이지랭크 | 정상분포가 중요도 | 155강 |
| 탐색 알고리즘 | 무작위 재시작 | 216강 |
넷째 줄이 최근 생성모형의 뼈대입니다. 확산모형의 순방향 과정은 각 단계에서 정규잡음을 더하는 마르코프 사슬이고, 141강의 재생성 덕분에 여러 단계를 건너뛴 조건부분포도 정규입니다. 학습하는 것은 그 사슬을 거꾸로 도는 전이입니다.
셋째 줄이 마르코프의 확장판입니다. 자기회귀 언어모형은 문맥 전체를 조건으로 쓰므로 엄밀히는 마르코프가 아니지만, 문맥 창을 상태로 보면 문제 5의 상태 확장과 같은 구조입니다.
일곱째 줄이 실용적 요령입니다. 최적화가 국소해에 갇히면 무작위로 다시 시작하는데, 이것을 마르코프 연쇄로 보면 기약성을 인위적으로 만드는 일입니다. 149강 문제 4의 다봉 우도가 그 배경입니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| P_ | 전이확률 | 에서 로 갈 확률입니다 |
| P^ | 걸음 전이행렬 | 행렬 거듭제곱입니다 |
| \boldsymbol\pi_ | 시점의 분포 | 행벡터입니다 |
| 채프먼-콜모고로프 | Chapman-Kolmogorov | 중간 시점으로 나눠 더합니다 |
| 기약 | irreducible | 모두 하나의 소통류입니다 |
| 비주기 | aperiodic | 주기가 입니다 |
| 재귀 | recurrent | 확률 로 돌아옵니다 |
| 일시적 | transient | 돌아오지 못할 수 있습니다 |
| 흡수 | absorbing | 나갈 수 없습니다 |
| 첫걸음 조건화 | first-step analysis | 한 걸음으로 나눠 세웁니다 |
| 기본행렬 | fundamental matrix | 입니다 |
| 상세균형 | detailed balance | \pi_{i}P_{ij}=\pi_{j}P_ |
| 가역 | reversible | 거꾸로 봐도 같습니다 |
| 상태 확장 | state augmentation | 과거를 상태에 넣습니다 |
다음은 155강 정상분포와 수렴입니다. 문제 2와 문제 4에서 의 모든 행이 로 수렴하는 것을 보았습니다.
그 분포가 고유값 의 왼쪽 고유벡터이며, 84~89강의 고유값 분해가 확률의 결론을 냅니다. 155강은 그 분포를 구하는 방법, 존재와 유일성의 조건, 그리고 수렴이 얼마나 빠른지를 두 번째 고유값으로 정량화합니다.
수렴 속도가 157강의 실무 문제와 직결됩니다. MCMC를 얼마나 오래 돌려야 하는지, 앞의 몇 걸음을 버려야 하는지가 그 값에 달려 있습니다.
import numpy as np
rng = np.random.default_rng(20260822)
P = np.array([[0.7, 0.2, 0.1],
[0.3, 0.4, 0.3],
[0.2, 0.3, 0.5]])
names = ["맑음", "흐림", "비"]
# --- 문제 1: 어제만 알면 충분한가 ---------------------------------------
print(" 날씨 세 상태의 전이행렬로 100 만 걸음을 걸어 봅니다")
N = 1000000
s = np.zeros(N, dtype=int)
u = rng.random(N)
C = np.cumsum(P, axis=1)
for t in range(1, N):
s[t] = int(np.searchsorted(C[s[t - 1]], u[t]))
print(" 한 걸음 전이 빈도가 전이행렬과 맞는지 봅니다")
print(" 상태 맑음으로 흐림으로 비로 행의 최대 오차")
for i in range(3):
m = s[:-1] == i
row = np.array([float((s[1:][m] == j).mean()) for j in range(3)])
print(" %-6s %10.6f %10.6f %10.6f %14.6f"
% (names[i], row[0], row[1], row[2], float(np.max(np.abs(row - P[i])))))
print(" 전전날을 함께 조건으로 걸어도 결과가 바뀌지 않는지 봅니다")
print(" (전전날, 어제) -> 오늘이 비일 확률 어제만 볼 때 차이")
for k in range(3):
for i in range(3):
m = (s[:-2] == k) & (s[1:-1] == i)
p2 = float((s[2:][m] == 2).mean())
print(" (%s, %s) %20.6f %18.6f %10.6f"
% (names[k], names[i], p2, P[i, 2], abs(p2 - P[i, 2])))
print(" 전전날을 알아도 예측이 달라지지 않습니다. 이것이 마르코프 성질입니다")
# --- 문제 2: n 걸음 뒤의 분포 -------------------------------------------
print(" n 걸음 전이행렬이 P 의 n 제곱인지 확인합니다")
print(" n P^n 의 (맑음->비) 성분 수치 빈도 차이")
for n in [1, 2, 5, 20]:
Pn = np.linalg.matrix_power(P, n)
m = s[:-n] == 0
emp = float((s[n:][m] == 2).mean())
print(" %9d %20.8f %14.6f %10.6f" % (n, Pn[0, 2], emp, abs(Pn[0, 2] - emp)))
print(" 채프먼-콜모고로프 등식을 확인합니다")
for a, b in [(2, 3), (4, 6), (7, 13)]:
lhs = np.linalg.matrix_power(P, a + b)
rhs = np.linalg.matrix_power(P, a) @ np.linalg.matrix_power(P, b)
print(" P^%d 와 P^%d P^%d 의 최대 차이 %.2e" % (a + b, a, b, float(np.max(np.abs(lhs - rhs)))))
print(" 초기분포를 바꿔 가며 n 걸음 뒤의 분포를 봅니다")
print(" 초기분포 n=1 n=5 n=30")
for lab, p0 in [("맑음에서 출발", np.array([1.0, 0, 0])),
("비에서 출발", np.array([0, 0, 1.0])),
("균등하게 출발", np.ones(3) / 3)]:
r = []
for n in [1, 5, 30]:
v = p0 @ np.linalg.matrix_power(P, n)
r.append(v)
print(" %-14s (%.4f %.4f %.4f) (%.4f %.4f %.4f) (%.4f %.4f %.4f)"
% (lab, r[0][0], r[0][1], r[0][2], r[1][0], r[1][1], r[1][2],
r[2][0], r[2][1], r[2][2]))
print(" 출발점이 달라도 30 걸음이면 거의 같은 분포에 이릅니다. 155강의 주제입니다")
# --- 문제 3: 상태를 어떻게 분류하는가 -----------------------------------
print(" 도박꾼의 파산을 봅니다. 목표 10, 한 판 이길 확률 0.45 입니다")
Ng, pw = 10, 0.45
q = 1 - pw
r = q / pw
print(" 시작 자금 파산 확률 이론 수치 기대 판수 이론 수치")
T = 40000
for i0 in [2, 5, 8]:
ruin_th = ((r ** i0) - r ** Ng) / (1 - r ** Ng)
dur_th = i0 / (q - pw) - (Ng / (q - pw)) * (1 - r ** i0) / (1 - r ** Ng)
ruin, dur = 0, 0
for _ in range(T):
x, t = i0, 0
while 0 < x < Ng:
x += 1 if rng.random() < pw else -1
t += 1
ruin += 1 if x == 0 else 0
dur += t
print(" %11d %15.6f %10.6f %15.4f %10.4f"
% (i0, ruin_th, ruin / T, dur_th, dur / T))
print(" 상태 0 과 10 은 한 번 들어가면 나오지 못하는 흡수 상태입니다")
print(" 나머지 상태는 일시적입니다. 언젠가 반드시 떠나 돌아오지 않습니다")
print(" 같은 문제를 선형방정식으로도 풉니다. h(i) = p h(i+1) + q h(i-1) 입니다")
A = np.zeros((Ng + 1, Ng + 1))
b = np.zeros(Ng + 1)
A[0, 0] = A[Ng, Ng] = 1.0
b[0] = 1.0
for i in range(1, Ng):
A[i, i] = 1.0
A[i, i + 1] = -pw
A[i, i - 1] = -q
h = np.linalg.solve(A, b)
print(" 선형계 해 h(2) = %.6f, h(5) = %.6f, h(8) = %.6f" % (h[2], h[5], h[8]))
# --- 문제 4: 언제 어디로 가는가 -----------------------------------------
print(" 기약이고 비주기인 연쇄에서 P^n 이 어떻게 되는지 봅니다")
print(" n P^n 행들의 최대 차이 맑음 성분")
for n in [1, 2, 5, 10, 20, 40]:
Pn = np.linalg.matrix_power(P, n)
print(" %9d %20.10f %12.8f" % (n, float(np.max(Pn.max(0) - Pn.min(0))), Pn[0, 0]))
print(" 모든 행이 같아집니다. 출발점을 잊는다는 뜻입니다")
print(" 주기가 2 인 연쇄에서는 어떻게 되는지 봅니다")
Q = np.array([[0.0, 1.0], [1.0, 0.0]])
print(" n Q^n")
for n in [1, 2, 3, 4, 99, 100]:
Qn = np.linalg.matrix_power(Q, n)
print(" %9d [[%.1f %.1f] [%.1f %.1f]]" % (n, Qn[0, 0], Qn[0, 1], Qn[1, 0], Qn[1, 1]))
print(" 홀수와 짝수에서 값이 다릅니다. 주기가 있으면 수렴하지 않습니다")
print(" 자기 자신으로 가는 확률을 조금만 넣으면 주기가 깨집니다")
Q2 = np.array([[0.05, 0.95], [0.95, 0.05]])
for n in [10, 50, 200]:
Qn = np.linalg.matrix_power(Q2, n)
print(" n = %3d 에서 Q2^n = [[%.8f %.8f] [%.8f %.8f]]"
% (n, Qn[0, 0], Qn[0, 1], Qn[1, 0], Qn[1, 1]))
# --- 문제 5: 마르코프인 척하지만 아닌 경우 ------------------------------
print(" 오늘이 어제와 그저께에 함께 의존하는 과정을 만듭니다")
M5 = 2000000
x = np.zeros(M5, dtype=int)
x[0], x[1] = 0, 1
uu = rng.random(M5)
for t in range(2, M5):
pr = 0.9 if x[t - 1] != x[t - 2] else 0.1
x[t] = 1 if uu[t] < pr else 0
print(" 어제만 조건으로 걸면 오늘이 1 일 확률")
for i in range(2):
m = x[1:-1] == i
print(" 어제 = %d 일 때 %.6f" % (i, float((x[2:][m] == 1).mean())))
print(" 그저께까지 함께 걸면 전혀 다릅니다")
for k in range(2):
for i in range(2):
m = (x[:-2] == k) & (x[1:-1] == i)
print(" (그저께 %d, 어제 %d) 일 때 %.6f (참값 %.1f)"
% (k, i, float((x[2:][m] == 1).mean()), 0.9 if k != i else 0.1))
p1 = np.array([float((x[2:][x[1:-1] == i] == 1).mean()) for i in range(2)])
ll1 = float(np.mean(np.log(np.where(x[2:] == 1, p1[x[1:-1]], 1 - p1[x[1:-1]]))))
pr2 = np.where(x[:-2] != x[1:-1], 0.9, 0.1)
ll2 = float(np.mean(np.log(np.where(x[2:] == 1, pr2, 1 - pr2))))
h = -(0.9 * np.log(0.9) + 0.1 * np.log(0.1))
print(" 1 차로 본 평균 로그손실 %.6f, 2 차로 본 %.6f, 이론 엔트로피 %.6f"
% (-ll1, -ll2, h))
print(" 1 차로 보면 예측이 동전 던지기 수준입니다. 정보를 통째로 버립니다")
print(" 상태를 (그저께, 어제) 쌍으로 확장하면 다시 1 차 마르코프가 됩니다")
pair = x[:-1] * 2 + x[1:]
Pp = np.zeros((4, 4))
for a in range(4):
m = pair[:-1] == a
for bb in range(4):
Pp[a, bb] = float((pair[1:][m] == bb).mean())
print(" 확장한 전이행렬")
for a in range(4):
print(" (%d,%d) -> [%.6f %.6f %.6f %.6f]"
% (a // 2, a % 2, Pp[a, 0], Pp[a, 1], Pp[a, 2], Pp[a, 3]))
print(" 각 행에 0 이 두 개씩 있습니다. 쌍의 앞자리가 이미 정해져 있기 때문입니다")
print(" 마르코프냐 아니냐는 과정이 아니라 상태를 어떻게 정의하느냐의 문제입니다")
# 날씨 세 상태의 전이행렬로 100 만 걸음을 걸어 봅니다
# 한 걸음 전이 빈도가 전이행렬과 맞는지 봅니다
# 상태 맑음으로 흐림으로 비로 행의 최대 오차
# 맑음 0.701230 0.199394 0.099376 0.001230
# 흐림 0.300657 0.400703 0.298640 0.001360
# 비 0.198611 0.300951 0.500439 0.001389
# 전전날을 함께 조건으로 걸어도 결과가 바뀌지 않는지 봅니다
# (전전날, 어제) -> 오늘이 비일 확률 어제만 볼 때 차이
# (맑음, 맑음) 0.099213 0.100000 0.000787
# (맑음, 흐림) 0.299640 0.300000 0.000360
# (맑음, 비) 0.494763 0.500000 0.005237
# (흐림, 맑음) 0.099345 0.100000 0.000655
# (흐림, 흐림) 0.298653 0.300000 0.001347
# (흐림, 비) 0.502002 0.500000 0.002002
# (비, 맑음) 0.100438 0.100000 0.000438
# (비, 흐림) 0.297457 0.300000 0.002543
# (비, 비) 0.501407 0.500000 0.001407
# 전전날을 알아도 예측이 달라지지 않습니다. 이것이 마르코프 성질입니다
# n 걸음 전이행렬이 P 의 n 제곱인지 확인합니다
# n P^n 의 (맑음->비) 성분 수치 빈도 차이
# 1 0.10000000 0.099376 0.000624
# 2 0.18000000 0.178485 0.001515
# 5 0.25212000 0.251783 0.000337
# 20 0.26086945 0.260443 0.000426
# 채프먼-콜모고로프 등식을 확인합니다
# P^5 와 P^2 P^3 의 최대 차이 1.11e-16
# P^10 와 P^4 P^6 의 최대 차이 5.55e-17
# P^20 와 P^7 P^13 의 최대 차이 5.55e-17
# 초기분포를 바꿔 가며 n 걸음 뒤의 분포를 봅니다
# 초기분포 n=1 n=5 n=30
# 맑음에서 출발 (0.7000 0.2000 0.1000) (0.4685 0.2794 0.2521) (0.4565 0.2826 0.2609)
# 비에서 출발 (0.2000 0.3000 0.5000) (0.4429 0.2862 0.2708) (0.4565 0.2826 0.2609)
# 균등하게 출발 (0.4000 0.3000 0.3000) (0.4537 0.2834 0.2629) (0.4565 0.2826 0.2609)
# 출발점이 달라도 30 걸음이면 거의 같은 분포에 이릅니다. 155강의 주제입니다
# 도박꾼의 파산을 봅니다. 목표 10, 한 판 이길 확률 0.45 입니다
# 시작 자금 파산 확률 이론 수치 기대 판수 이론 수치
# 2 0.923304 0.926600 12.3304 12.2208
# 5 0.731717 0.733950 23.1717 23.1155
# 8 0.381920 0.384150 18.1920 18.2593
# 상태 0 과 10 은 한 번 들어가면 나오지 못하는 흡수 상태입니다
# 나머지 상태는 일시적입니다. 언젠가 반드시 떠나 돌아오지 않습니다
# 같은 문제를 선형방정식으로도 풉니다. h(i) = p h(i+1) + q h(i-1) 입니다
# 선형계 해 h(2) = 0.923304, h(5) = 0.731717, h(8) = 0.381920
# 기약이고 비주기인 연쇄에서 P^n 이 어떻게 되는지 봅니다
# n P^n 행들의 최대 차이 맑음 성분
# 1 0.5000000000 0.70000000
# 2 0.2400000000 0.57000000
# 5 0.0255600000 0.46848000
# 10 0.0006065280 0.45680544
# 20 0.0000003415 0.45652190
# 40 0.0000000000 0.45652174
# 모든 행이 같아집니다. 출발점을 잊는다는 뜻입니다
# 주기가 2 인 연쇄에서는 어떻게 되는지 봅니다
# n Q^n
# 1 [[0.0 1.0] [1.0 0.0]]
# 2 [[1.0 0.0] [0.0 1.0]]
# 3 [[0.0 1.0] [1.0 0.0]]
# 4 [[1.0 0.0] [0.0 1.0]]
# 99 [[0.0 1.0] [1.0 0.0]]
# 100 [[1.0 0.0] [0.0 1.0]]
# 홀수와 짝수에서 값이 다릅니다. 주기가 있으면 수렴하지 않습니다
# 자기 자신으로 가는 확률을 조금만 넣으면 주기가 깨집니다
# n = 10 에서 Q2^n = [[0.67433922 0.32566078] [0.32566078 0.67433922]]
# n = 50 에서 Q2^n = [[0.50257689 0.49742311] [0.49742311 0.50257689]]
# n = 200 에서 Q2^n = [[0.50000000 0.50000000] [0.50000000 0.50000000]]
# 오늘이 어제와 그저께에 함께 의존하는 과정을 만듭니다
# 어제만 조건으로 걸면 오늘이 1 일 확률
# 어제 = 0 일 때 0.497304
# 어제 = 1 일 때 0.499967
# 그저께까지 함께 걸면 전혀 다릅니다
# (그저께 0, 어제 0) 일 때 0.099425 (참값 0.1)
# (그저께 0, 어제 1) 일 때 0.900204 (참값 0.9)
# (그저께 1, 어제 0) 일 때 0.899497 (참값 0.9)
# (그저께 1, 어제 1) 일 때 0.099677 (참값 0.1)
# 1 차로 본 평균 로그손실 0.693140, 2 차로 본 0.324751, 이론 엔트로피 0.325083
# 1 차로 보면 예측이 동전 던지기 수준입니다. 정보를 통째로 버립니다
# 상태를 (그저께, 어제) 쌍으로 확장하면 다시 1 차 마르코프가 됩니다
# 확장한 전이행렬
# (0,0) -> [0.900575 0.099425 0.000000 0.000000]
# (0,1) -> [0.000000 0.000000 0.099796 0.900204]
# (1,0) -> [0.100503 0.899497 0.000000 0.000000]
# (1,1) -> [0.000000 0.000000 0.900323 0.099677]
# 각 행에 0 이 두 개씩 있습니다. 쌍의 앞자리가 이미 정해져 있기 때문입니다
# 마르코프냐 아니냐는 과정이 아니라 상태를 어떻게 정의하느냐의 문제입니다