mcmc1

 

한분이 베이지안 MCMC에 관해서 질문을 해서 여기에 대해 좀 전반적으로 쓰려고 합니다. 상당히 여러 편을 써야 할 것 같고요. 여기에 글 있는 분들의 수준이 너무 다르기 때문에 가능하면 쉽게 쓰려고 합니다.

 

심각하게 학문적으로 나가고 싶은 분이나 아니면 이쪽 분야 연구소에 취직을 하고 싶은 분이나 앞으로 이쪽 분야에서 더 나은 실력을 갖고 싶은 분이 있으시면 일단 다음이 2개의 경우에 대해서 실제 프로그램을 하면서 짜 보세요.

    

 

Asrts & Korst의 Simulated Annealing and Boltsmann Machines의 책을 사서 처음 부분에 보면 Travelling Sales man문제가 있습니다. 컴퓨터 학과에서 NP 문제로 굉장히 유명한 문제이죠.

 

유럽의 한 영업사원의 유럽 50개 도시를 돌아다니면서 영업을 합니다. 한번 간 도시는 다시 가지는 않습니다. 문제는 가장 빠른 경로를 찾는 것입니다. 50개 도시가 100개 도시로 되면 계산 횟수가 엄청나게 늘어납니다.

 

말로는 쉽습니다. 1) 50개 도시를 도는 모든 경로를 생각한다. 2) 각 경로의 거리를 계산한다. 3) 이 중 가장 짧은 경로가 답이다.

 

그러나 앞에서 이야기했지만 이 경로의 수가 어마어마하게 많습니다. 이 책에서는 MCMC라고 불리는 Metropolis 방법에다 최소값을 구하기 위해 Simulated Annealing 방법을 첨가해 무지하게 빠른 속도로 최소 경로를 찾아 갑니다.

 

제가 옛날에 자바가 처음 나올 때 제 홈페이지에서 이걸 구현해서 돌린 적이 있습니다. 벌써 20년 전 이야기이네요. 지금은 짠 소스 파일을 없어서 올릴 수가 없네요. 그리고 이 책에 볼쯔만 머신의 원형이 잘 설명되어 있으니까 인공지능에 나오는 볼쯔만 머신에 대해 잘 모르시면 이 책을 보시면 좋고요.

    

 

그리고 Geman & Geman의 이미지 복원 논문을 보시고 거기에 나오는 예제를 실제로 구현해보세요. 이 논문은 구글에서 검색이 됩니다. 그리고 Gibbs Sampler가 처음 나온 논문이니까 꼭 읽어야 하는 논문입니다. 여기에도 metropolis와 simulated annealing이 나오니까 앞의 책에서 전반적인 개념을 아시고 그 다음 이 논문을 읽으시기 바랍니다.

 

저는 여기에 나오는 예제를 구현해보지 않았습니다. 그 당시에는 이미지파일을 숫자로 전환해주는 프로그램이 구하기 힘들어서 할 수가 없었습니다. 지금은 Matlab에서 쉽게 해준다는 이야기를 들은 적이 있습니다.

 

이미지 복원은 흔히 포트샵에서 효과 주는 것이라 개념이 다릅니다. 포토샵은 보는 사람에게 어떤 시각적 효과를 보여주려고 하는 것이 목적이고 이미지 복원은 훼손된 이미지에서 원래 이미지를 찾으려는 과학적인 방법입니다.

 

그래서 알아보기 힘든 탁본에서 원래 글자를 인식한다든지, 예를 들어 광개토대왕 탁본같은 것이 있을 수 있겠죠. 아니면 CCTV에 찍힌 사람 모습을 복원한다든지 이런 곳에 사용할 수 있습니다.

 

저는 Gemen & Gemen 예는 구현하지 못했지만 지도교수가 자신의 prior를 사용하여 MCMC 방법으로 쓴 논문이 있는데 이건 제가 C를 사용하여 컴퓨터 화면에서 구현한 적은 있습니다. 흰 배경 이미지에 검은 +, - 기호를 쓴 다음 이 이미지에서 잡음을 적당히 줘 이미지를 훼손한 다음 원래 +, - 이미지를 찾아가는 프로그램입니다. 집에 놀려온 사람들에게 보여주면 깜짝 놀랩니다. 완전하게 복원은 안 되죠. 단지 우리의 목적에 맞게 사물을 판단할 수 있는 정도면 됩니다. 그리고 이런 것은 빠른 시간에 할 필요도 없고요.

 

이 2개의 예제를 본인이 직접 프로그램을 해서 구현을 하면 단지 책에서 이론적으로 공부하는 것과 전혀 다른 수준의 실력이 됩니다.

 

단 컴퓨터 프로그램으로 구현한다는 것은 구현 과정에 대한 수학적 이해만 해도 가능하기 때문에 이론의 학문적 배경 실력과는 무관합니다. 제가 그 당시 이 프로그램을 짤 때 이 경우에 해당합니다.

 

앞으로 제가 쓸 몇 몇 글에서 약간의 이론적 배경에 대한 실력도 보충하시기 바랍니다.

자바 프로그램을 할 줄 아시면 한 1년 빡세게 공부하시면 상당한 수준의 실력을 갖출 수 있을 겁니다.

 

 

먼저 용어에 대한 전반적인 설명을 하고, 그리고 베이지안 추론이 뭔가 하는 것에 대해 예를 들어 설명을 하겠습니다.　그 다음 MCMC에 대해 설명을 하겠습니다. 그러나 세부적인 이론 전개에 대해서는 언급하지 않겠습니다. 전반적인 이론의 개념을 잡으면 그 다음 단계를 이해하는 것은 별 어려움이 없습니다. 예를 들어 MCMC의 변형이나 또는 수렴 문제나 이런 것은 나중에 본인이 알아서 혼자 공부하셔도 됩니다.

 

 

먼저 MCMC는 Markov Chain Monte Carlo 표본추출을 말합니다.

 

마코프 체인은 제가 잡소리에 류현진 선수의 경우를 들어 설명한 바가 있습니다. 마코프체인에 대한 쉬운 책들은 많이 있으니까 거기를 보시면 됩니다.

 

 

앞에서 쓴 적이 있는데 마코프체인은 두가지 방향에서 사용됩니다.

 

하나는 현실에 대한 모형으로, 현실을 설명하는 수학적 모형으로 사용되기도 하고 하나는 수치해석, 즉 컴퓨터 프로그램을 통해 어떤 목적을 해결하는 수치해석의 방법론으로 사용되기도 합니다.

 

 

원래 이론은 첫 번째 관점에서 나옵니다. 따라서 일반적인 마코프체인에 대한 책도 이런 관점에서 설명하고 있습니다. 즉 마코프체인에 나오는 전이행렬 M(t)가 어떤 특이한 성질을 가지고 있으면 나중에는 어떤 균형분포, 정상분포(stationary distribution)로 간다는 이론입니다. 특히 초기분포를 어떤 값을 주든 항상 같은 균형분포로 갈 때 이 경우를 ergodic 마코프 체인이라 합니다. 이게 마코프체인 이론의 꽃입니다.

 

그러나 두 번째 관점은 첫 번째 관점과 정반대 방향의 이론입니다. 이게 우리가 이야기하려는 MCMC입니다. 즉 어떤 특정 분포가 있는데 이 특정분포로 가려는 마코프체인을 발견하려는 것이 목적입니다. 이를 통해 이 특정분포에서 컴퓨터 프로그램을 통해 표본, 즉 난수를 추출하려고 하는 것입니다. 이 컴퓨터 프로그램을 통해 어떤 분포의 표본을 뽑는 것을 그냥 sampling 이라고 하기도 하고 아니면 random number simulation 이라고도 합니다.

 

임의로 주어진 초기 분포값을 h(a)라고 하고 마지막 균형분포를 s(a)라고 하면, 그리고 a는 류현진의 경우 류현진이 던지는 10가지 공의 종류를 나타내는 변수라 생각하시면 됩니다. 예를 들어 a=(높은 속구, 낮은 변화구, 오른쪽 슬라이더, 왼쪽 슬라이더,,,,)이라 생각하시면 되고 h(a)는 이 10가지 구 종류에 확률값을 여러분이 임의로 배정하신 것으로 생각하시면 됩니다. 즉 h(a)=(0.09, 0.14, 0.25, 0.087,,,,,) 이렇게 되겠습니다. 마지막 균형 분포 s(a)는 시즌이 끝난 후 류현진이 던진 공의 종류를 분석하면 정확하게 나올 수 있겠습니다. 정리하면

 

모형으로서의 MC:

 

h(a)==> M*h(a)==> M*M*h(a) ==> M*M*M*h(a) =======> s(a)

 

 

수치해석으로서의 MC:

 

최종적으로 s(a)가 나오게끔 ergodic 마코프체인의 M을 찾아라

 

 

이 MCMC는 크게 두가지 방법이 유명합니다. 하나는 Metropolis 방법이고 하나는 Geman & Geman이 이미지 복원에 관한 논문에서 제시한 Gibbs Sampler라는 방식입니다. 이 Gibbs Sampler 방식은 Metropolis 방식의 특수한 케이스인데 이 방법이 통계학에서 많이 사용됩니다. 그리고 Metropolis 방식은 여러 학자들에 의해 다양하게 발전하고 변형된 모습이 나옵니다. 그러나 앞에서 이야기했죠. 이런 것은 기본적인 개념을 충실히 이해하시면 나중에 본인이 혼자 따라갈 수 있습니다. 저야 오래전에 공부 그만 둔 사람이라 더 이상 할 생각이 없지만요.

 

그래서 여러분이 만약 특정 분야에서 위에 나오는 MCMC 방법을 사용하시면 구태여 ergodic MC를 증명할 필요가 없지만(이미 다 알려져 있죠. 다만 논문에서 언급만 하시면 됩니다) 기존의 방법과 약간 변형된 방법을 사용하시면 여러분이 논문에 사용된 변형된 방식이 ergodic MC라는 것을 증명을 하셔야 합니다. 이 정도의 수준만 되어도 굉장한 수준의 논문이 되고 이 분야에서의 어느 정도 대가의 대접을 받을 수 있습니다.

 

 

그럼 여기서 2가지 의문점이 생깁니다.

 

1. 특정분포 f(a)에서 simulation 하는데 왜 MCMC 방법을 사용하는가?

 

2. 특정분포 f(a)에서 simulation 해서 뭘 하려고?

 

 

그래서 앞의 2가지 MC의 개념과 위의 2가지 질문을 계속 가지면서 공부하시면 이 MCMC 이론을 공부하는데 큰 도움이 될 겁니다.

 

간단하게 설명하면

 

1. 왜 MCMC를 사용해서 꼭 난수(random numer)를 simulation을 해야 하는가?

 

특정분포에서 컴퓨터로 데이터를 표본추출하는 방법은 무지하게 많이 있습니다. 고전적인 책으로 Devroye의 책이 있습니다. 아마 몇 백페이지 정도 될겁니다. 이런 책은 공부를 하는 것이 아니고 나중에 필요할 때 마다 참고로 보는 것이죠. 기본적인 입문서을 공부하는 것만 해도 충분합니다.

 

문제는 기존의 방식대로 해도 잘 안되니까 MCMC를 쓰는 것입니다.

 

특히 베이지안은 사전분포(prior)가 들어가서 사후분포(posterior)가 매우 복잡해집니다. beta 분포, Gamma, inverse Gamma, inverse Chi 분포 등 평소 통계학 책에서 거의 보지 못하는 분포가 나와 이걸 일반적인 방법으로 난수를 simulation 하기가 힘듭니다.

사실 우리가 아는 난수는 균등분포에사 나오는 난수입니다. 그러나 완벽하게 균등분포에서 나오는 난수도 아직 인류에게 알려져 있지 않습니다. 유명한 난제의 하나입니다. 흔히 컴퓨터 프로그램에 이 균등분포에서 나오는 난수가 Library로 제공되어 있어 함수만 부르면 자동적으로 난수가 생성됩니다. 이게 실제 균등분포에서 나오는 난수가 아니라 비슷하게 뽑아 내는 난수입니다.

 

 

2. 특정분포 f(a)에서 simulation 해서 뭘 하려고?

 

우리는 확률적인 세계에 살고 있습니다. 이런 확률적 세계의 정보는 그 현상 A의 확률분포 f(a)안에 다 있습니다. 그 이상은 우리가 할 수 없습니다. 이 f(a)만 알 수 있다면 우리는 여기서 다양한 정보를 뽑아낼 수 있습니다. 예를 들어

 

 

이걸 정확하게 계산하기 힘들면 f(a)에서 난수를 몇 개 뽑습니다. 그래서 E[A]의 근사치로 이 난수들의 평균값을 구하면 됩니다.

 

즉, f(a)에서 뽑은 값이 3, 4, 5라고 하면 E[X]의 근사치는 (3+4+5)/3=4가 됩니다. 물론 이 뽑은 값이 많으면 많을수록 평균한 값이 정확하게 E[A]와 일치되겠죠.

 

그럼 어는 정도 예상은 해겠지만 일반적인 A의 함수 g(A)의 기대값도쉽게 근사치를 구할 수 있습니다. 예를 들어 분산 같은 것이 될 수 있겠죠.

 

 

 

즉 뽑힌 난수 a(i)를 g(a) 함수에 대입하여 평균을 구하면 됩니다. 이것도 난수의 개수 n이 커지면 정확하게 E[g(a)]에 접근하게 됩니다.

 

또 A가 하나의 변수이거나 A=(A1, A2) 등 2개의 변수이면 그래픽 방법으로 이 f(a)의 최대값, 즉 mode를 알 수 있고, 아니면 density estimation 방법, 또는 구간을 범주화해서 각 구간에 비율을 계산해서 mode 등을 구해 낼 수 있습니다.

 

앞에서 언급한 점을 계속 기억하신 다음 공부를 계속 하시면 좋을 것 같습니다. 다음은 simulation이 뭔가 간단히 설명하고, 그리고 모형으로서 MC의 예를 설명하고, 그리고 베이지 추론을 어떻게 하는지 가장 간단한 모형을 통해서 설명하겠습니다.