몬테칼를로(Monte-Carlo) 방식1

 

 

 

알파고의 열기 때문에 옛날에 잠깐 관심을 가진 분야를 다시 한번 관련 논문이나 책들 찾아서 한번 읽어 보고 있습니다. 제가 처음 접했을 때 이 분야가 매우 핫한 분야로 떠오르기 시작할 때입니다. 그 당시는 이게 뭐하는지 이해를 전혀 못했거든요. 이론의 맥락이 전혀 잡히지가 않아서요. 검색을 해보니 최근에는 시간이 많이 흘려 사람들이 전체적인 맥락을 많이 이해를 해서 쉽게 풀어 논 글이나 책들이 많이 있네요.

 

하여간 오늘부터 조금씩 써 나가보죠. 알파고에서 몬테칼를로 방법을 사용한다고 기사에 나온든데 아마 몬테칼를로 마코프체인(MCMC)를 이야기 할 겁니다. 이야기를 진행하기 전에 먼저 세가지 사항을 먼저 이야기 하고 싶습니다. 편견과 선입견을 먼저 깨고 진행하는 것이 바람직할 거라 봅니다.

 

 

 

1. 우리는 수학 이론이 엄청나게 발전했다고 생각합니다. 그러나 실제 계산하는 능력은 매우 부족합니다. 여러분이 고등학교 때 배운 함수를 생각해보죠. 이 함수 몇 개 안됩니다. 일차식부터 해서 다항식, 지수함수, 로그함수, 삼각함수 이게 다입니다. 기타 아주 특수한 형태의 함수도 있지만 일상적으로 거의 다루어지지 않고 있습니다.

 

 

이 몇 개 안되는 함수도 적분에 가면 거의 문제 해결이 불가능합니다. 우리는 앞에 이야기한 함수들의 합, 곱하기나 나누기 등을 해서 더 복잡한 형태의 함수를 만드는데 이런 복잡한 함수의 경우 적분값을 구하는 것이 거의 불가능하다고 봐야 합니다. 예를 들어 g(x)=x^2*cos(x)/e^x 이런 함수를 [0, 1]에서 적분값을 구할 수 있을 까요. 어떻게 적분해야 하는지도 모릅니다. 함수 모양 자체도 정확하게 그리기 힘듭니다.

 

 

 

2. 컴퓨터의 계산 능력이 엄청나게 발전하였습니다. 그러나 우리 인간의 머리로서 매우 간단한 문제도 컴퓨터에서 풀려면 엄청난 시간이 걸릴 수 있습니다. 그 대표적인 문제가 ‘여행하는 세일즈 맨’ 문제입니다. 컴퓨터학과에서는 NP 문제의 대표적인 예로 이야기하는 매우 유명한 문제입니다.

 

세일즈 맨 문제는 이렇습니다. 유럽에서 세일즈 하는 사람이 유럽 50개 도시를 돌아다닙니다. 문제는 가장 빠른 경로를 찾는 것입니다. 한번 방문한 도시는 다시 방문해서는 안되고요. 그럼 우리 머리로서는 이 문제는 초딩 문제에 불과합니다.

 

1. 가능한 모든 경로를 다 생각한다.

2. 각 경로의 거리를 계산한다.

3. 계산한 거리를 가지고 가장 짧은 경로를 답으로 한다.

 

 

 

이렇게 간단한 문제인데 이게 컴퓨터에서는 계산하기 힘든다는 것이죠. 왜냐면 가능한 경로의 수가 무지하게 많기 때문입니다. 50개 도시면 49!는 약 6곱하기 10^62입니다. 상상이 안되는 수이죠. 100개 도시, 또는 10000개 도시면 모든 경우의 경로의 수는 생각하기도 싫겠죠. 바둑의 경우의 수와 비교도 안되죠.

 

그러나 이 문제 쉽게 풀어집니다. 완전한 답은 아니지만 50개 도시 정도면 1-2초 안에 매우 근사한 답을 컴퓨터로 풀어낼 수 있습니다. 나중에 시뮬레이티드 어니링 알고리즘 이야기할 때 다시 이야기 하겠습니다.

 

이 문제는 우리가 매일 접하는 현실 문제와 매우 닮아 있습니다. 바로 내비게이션입니다. 우리가 잘 모르는 목적지를 찍으면 현재 장소에서 그 목적지까지 가는 경로를 찾아 줍니다. 그러나 이 문제를 세일즈 맨 문제 풀듯이 할까요. 대한민국내 교차로를 전부 도시라 생각하죠. 그럼 어마어마한 수의 교차로가 있습니다. 현재 위치에서 옆 동네에 가는데도 여기서 목포나 부산으로 내려가서 다시 올라와 옆동네로 가는 경로까지 전부 다 생각해야 합니다.

 

그래서 내비게이션에서는 앞에 이야기한 이론적인 세일즈맨 문제를 적용할 수 없습니다. 아마 배 운항할 때 쓰는 방법을 쓸 겁니다. 즉 GPS에서 현재 위치와 목적지 좌표를 읽어 목적지가 현재 위치 보다 오른쪽 위쪽에 있다면 교차로를 만나면 위나 오른쪽으로 방향 전환을 하라는 실시간 지시를 하는 방법을 쓸 겁니다.

 

그래서 이론과 현실 문제는 매우 다른 문제입니다. 세일즈맨 문제 풀듯이 하면 아마 목적지 찍으면 가장 짧은 경로 찾는데 하루 종일 걸릴겁니다. 수 많은 사람들이 자기 목적지 가는 경로 찾아달라고 요구를 하겠죠.

 

 

 

 

3. 우리가 관심을 가지고 있는 현상의 모든 정보는 확률분포에 있습니다. 확룰분포를 알면 평균값을 알 수 있고, 또 극빈값을 알 수 있고, 또 어디에서 어디까지 나올 확률이 얼마간 되는지 계산해 낼 수 있습니다.

 

고등학교 선생이 학생들 성적 분포를 정확하게 알 수 있으면 학생들 진로 상담이 훨씬 쉽습니다. 이번 선거에서 봤듯이 우리가 확률분포를 알면 누가 당선될지 어느 정도 차이로 탈락했는지 정확하게 알 수 있습니다.

 

따라서 우리의 최종 관심은 확률분포입니다.

 

 

 

그럼 몬테카를로에 대해 이야기를 해 볼까요.

 

몬테칼르로는 제가 알기로는 모나코의 유명한 도박도시로 알고 있습니다. 이쪽에서 몬테칼를로 방식으로 했다는 것은 그냥 난수, 즉 무작위 수를 컴퓨터로 뽑아내 뭘 했다는 것입니다. 컴퓨터 프로그램하는 C나 포트란, 또는 Matlab, S, R, SAS 이런 프로그램에 난수 뽑아내는 명령문이 있습니다. 그래서 난수를 뽑아내는 방법은 걱정안해도 됩니다. 그냥 명령문 하나 치면 바로 원하는 개수 만큼 뽑아내줍니다. 전문 프로그램에서 난수를 뽑아주기는 하지만 이게 진짜 난수는 아닙니다. 가짜 난수이죠. 진짜 난수를 뽑아내는 방법은 아직 인간이 못 푸는 문제로 알려져 있습니다. 뭐 자기가 진짜 난수 뽑는 법을 밝혔다고 주장하는 사람들이 종종 있지만요.

 

하여간 이 난수 뽑는 것이 현실에서 뭔 소용이 있을까요. 여러분이 자주 하는 로또가 바로 난수의 문제입니다. 0부터 9까지 무작위로 숫자로 뽑혀야지 공정한 로토입니다. 또 처음에 이야기한 복잡한 적분값을 구하는데 사용됩니다.

 

 

 

1) 적분 값 구하기

 

앞의 예를 보죠. 우리가 원하는 값입니다.==> 아래 수식이 잘 안나왔네요. exp(x)로 나눴다고 생각하시고요. 수식이 중요한게 아니고 그냥 복잡한 수식이라 생각하세요.

 

 

 

이 값 구하기 힘들다고 해죠. 그러나 몬테칼르로 방법으로 쉽게 구할 수 있습니다. 그림을 한번 보죠

 

 

 

 

 

위 그림에서 함수를

 

 

 

 

 

라고 하죠. 그리고 0에서 1 사이에서 이 함수보다 넉넉하게 큰 값을 100이라 하고 그럼 이 사각형의 면적은 1*100=100이 됩니다.

 

 

그 다음 난수를 2개 동시에 뽑아냅니다. (x=0과 1 사이에 난수, y=0과 M인 100사이 난수) 이렇게 10만개 정도 뽑아냅니다. (x=0.731, y=15.041)... 등등

 

 

그럼 위의 그림 처럼 함수 위에 찍히는 점이 있을 것이고 함수 아래 찍히는 점이 있을 겁니다. 이 비율이 6.522:3.478라고 하죠. 그럼 이 적분값은 100*0.3478=34.78이 되는 것이죠. 참 쉽죠. 만약 난수를 백만개 뽑아 계산하면 이 적분값이 더 정확해지겠죠.

 

 

 

이렇게 이론적으로 전혀 계산할 방법이 없는 경우라도 몬테칼르로 방식을 쓰면 쉽게 구해집니다. 몬테칼르로 방식을 써서 이것보다 더 쉽게 구하는 방법이 있습니다. 이건 다음 글에 쓰고요. 더 쉽게 구하는 방법은 이 MCMC 방식을 이해하는데 매우 중요한 개념입니다. 그리고 로또 경우를 예를 들어 설명하면서 몬테칼르로 방법이 더욱 일반화되는 경우를 설명하겠습니다.