유향 비순환 그래프(DirectedAcydicGraph, DAQ) 알고리즘을
이용한 IOTA 블록체인기술의 Distributed Ledger Technology
근본적으로블록체인과동일한분산데이터베이스및 P2P네트워크를이루고합의와 확인(Consensus&Validation)메커니즘보유
MCMC 마코프 체인 몬테카를로
Nov 29, 2014
MCMC(Markov Chain Monte Carlo)는 어떤 목표 확률분포(Target Probability Distribution)로부터 랜덤 샘플을 얻는 방법이다. 샘플링에 뭐 이런 거창한 방법이 필요하냐고 할 수도 있는데, 데이터의 차원이 커지면 샘플링이 간단한 문제가 아니게 된다. LDA 파라미터 추정의 경우, 각 단어 주제의 사후확률분포 P(Z | W)에는 문서에 등장하는 단어 토큰수 만큼의 차원이 있는 것이다. 10만, 100만, 그 이상이 될 수도 있다.
어려운 부분은 빼고 MCMC의 원리만 간단히 살펴보자. 일단 이름에 들어간 용어에서부터 시작한다.
몬테카를로
몬테카를로 방법은, 수식만으로 계산하기 어려운 문제가 있을 때 데이터의 무작위 샘플을 얻은 뒤 그 샘플을 이용해서 답을 구하는 방법이다. 예를 들어, 반지름이 1인 원의 넓이를 구하는 문제를 생각해보자. 아래의 절차를 따르면 직관적으로 답을 구할 수 있다.
1.2차원 좌표계 위에 원점을 중심으로 가로와 세로 길이가 2인, 넓이 4짜리 정사각형을 그린다.
2.이 사각형 안에 무작위로 점을 찍는다.
3.그 점들 중에서 원점으로부터의 거리가 1이하인 점(이게 바로 원의 정의다)의 비율을 계산한다.
4.이 비율을 사각형의 넓이 4에 곱하면, 우리가 원하는 반지름 1짜리 원의 넓이 추정값이 된다.
점을 찍는 시도가 많아질수록 추정치는 실제값에 가까워진다. 컴퓨터는 이런 지루한 작업도 아무 불평없이 빠르게 수행해줄 것이다.
마코프 체인
그럼 마코프 체인은 무엇인가? 체인은 상태값의 시퀀스라고 생각하면 된다. 체인이라는 말에서 연상되듯이 각각의 상태는 서로 독립이 아니라 이전의 상태에 영향을 받는다. 오늘의 날씨는 어제, 그제의 날씨와 무관하지 않다. 하루 전에 화창했다면, 하루 전 비가 왔을 때에 비해서, 오늘 맑을 확률이 더 높을 것이다. 조건부 확률로 표현하면 이렇게 된다.
P(X k |X k−1 ,X k−2 ,...,X 1 ,X 0 )
P(Xk|Xk−1,Xk−2,...,X1,X0)
여기서 X k
Xk
는 시간이 k인 시점에서의 상태값(여기서는 “맑음”, “비” 둘 중 하나)이다. 여기에 마코프라는 조건이 붙으면, 각 상태는 바로 이전의 사태에”만” 영향을 받는다고 가정한다. 다시 말해, 내일의 날씨는 오늘의 날씨와만 관련이 있고, 어제 이전의 날씨와는 독립이라고 보는 것이다. 그러면 위의 수식은 아래와 같이 고쳐쓸 수 있다.
P(X k |X k−1 ,X k−2 ,...,X 1 ,X 0 )=P(X k |X k−1 )
P(Xk|Xk−1,Xk−2,...,X1,X0)=P(Xk|Xk−1)
마코프 체인의 흥미로운 특성 한 가지는, 몇 가지 추가 조건이 만족한다면, k가 충분히 커지면 X k
Xk
의 분포는 특정한 값으로 수렴한다는 점이다. 이게 무슨 뜻인가?
우리의 날씨 마코프 체인에는 총 4가지의 상태 전이확률(Transition Probabilities)이 있다. P(맑음 | 맑음), P(비 | 맑음), P(맑음 | 비), P(비 | 비). 그리고 P(맑음 | 맑음) + P(비 | 맑음) = P(맑음 | 비) + P(비 | 비) = 1이라고 하자. 오늘 날씨가 맑다면, 이 전이확률을 이용해서 내일 맑을 확률과 비가 올 확률을 계산할 수 있다. 그리고 다시 그 값을 이용해서 모레의 날씨의 확률분포를 계산할 수 있다. 이 과정을 계속 반복하다 보면 어느 순간부터 그날의 날씨 확률분포가 그 전날과 같아지는 때가 온다. (다시 강조하는데, 모든 마코프 체인이 그런 것은 아니고 수렴하는 조건이 따로 있다. 자세한 건 참고자료를 참고) 이렇게 평형 상태에 도달한 날씨의 확률분포를 Stationary Distribution이라고 부른다. (Stationary은 고정된, 움직이지 않는다는 뜻이다)
더 멋진 것은 이 Stationary Distribution은 초기값에 연연하지 않는다는 점이다. 위에서는 시뮬레이션을 시작할 때 오늘이 맑다고 가정했지만, 비가 온다고 가정했더라도 최종적으로 수렴하는 확률분포는 동일하다.
마코프 체인 몬테카를로
MCMC 알고리즘은 우리가 샘플을 얻으려고 하는 목표분포를 Stationary Distribution으로 가지는 마코프 체인을 만든다. 이 체인의 시뮬레이션을 가동하고, 초기값에 영향을 받는 burn-in period를 지나고 나면, 목표분포를 따르는 샘플이 만들어진다.
문제는 어떻게 그런 마코프 체인을 만들 수 있냐는 건데, 잘 알려진 방법으로 Metropolis와 이를 일반화한 Metropolis-Hastings, 그리고 깁스 샘플링(Gibbs Sampling)이 있다. 날씨 마코프 체인에서 전이확률을 이용해 다음날의 날씨를 예측했듯이, 이들 알고리즘들은 현재 상태에 기반해서 다음 샘플을 만드는 나름의 방법을 제시한다.
Metropolis는 마코프 체인의 현재 상태 x에서 다음 상태를 결정할 때 1) 제안분포(Proposal Distribution)로부터 랜덤 샘플 y를 뽑고, 2) 목표분포에서 현재값 x와 신규값 y의 확률을 비교한다. 2-1) 신규값 y의 확률이 더 크면, y를 다음 상태로 받아들인다. 2-2) 현재값 x의 확률이 크면, 그 차이에 따라서 현재 상태를 그대로 유지할지, y를 받아들일지 결정한다. 말로 늘어놓으니까 어려운데 위키피디아 설명을 보면 별로 어렵지 않다.
깁스 샘플링은, 다음 상태를 뽑을 때 한꺼번에 모든 변수(차원)의 값을 정하는 것이 아니라 변수 하나씩 값을 선택한다. LDA에서 각 단어 토큰의 주제를 결정하는 방식을 생각하면 되는데, 다른 모든 변수는 현재값으로 고정되어 있다고 가정하고, 그랬을 때 이 변수가 가질 수 있는 값의 조건부 분포로부터 하나를 샘플링하는 것이다. 이 과정을 모든 변수에 대해서 반복하면 하나의 새로운 상태가 만들어진다. (수식이 어렵다고 하지만 같은 내용을 말로 풀어서 설명해보면 수식이 얼마나 효과적인 표현 도구인지 알 수 있다..;)
아무튼 결과적으로는 이렇게 간단하게 쓸 수 있지만, 그건 방법론을 만든 사람들이 이 절차만 따르면 마코프 체인이 목표분포로 수렴한다는 것을 모두 증명해놓은 덕분이다.
참고자료
•An Introduction to MCMC for Machine Learning
•All of Statistics: A Concise Course in Statistical Inference, Larry Wasserman, 2004
•Markov Chain Monte Carlo로 암호 해독하기 - MCMC의 재미난 응용을 소개하는 글