몬테 카를로 방법 (덤프버전으로 되돌리기)

[include(틀:통계학)]
[include(틀:원자력 공학)]
[목차]
== 개요 ==
{{{+1 Monte Carlo method}}}

동명의 카지노에서 따온 이름을 가진, 무작위 추출된 난수를 이용하여 함수의 값을 계산하는 [[통계학]]의 방법. [[최적화]], 수치적분, [[확률분포]]로부터의 추출 등에 쓰인다.
== 몬테 카를로 방법 ==
몬테 카를로 방법은 무작위 추출된 난수를 이용하여 원하는 함수의 값을 계산하기 위한 시뮬레이션 방법이다. [[자유도]]가 높거나 닫힌꼴(closed form)의 해가 없는 문제들에 널리 쓰이는 방법이지만, 어느 정도의 오차를 감안해야만 하는 특징이 있다.

몬테카를로 방법의 간단한 예시로 [[원(도형)#s-3.2|원의 면적]]을 구하는 것을 들 수 있다.[* 물론 [[원(도형)#s-3.2.1|원 문서의 면적을 증명하는 문단에서 보듯]] 미적분을 이용하면 닫힌 형식으로 나타낼 수 있지만, 가장 고전적으로 사용되는 예시이다.] [math( x^2 + y^2 = 1 )]이라는 식으로 표현되는 원의 면적을 구하고 싶다고 하자. 이 원은 [math( -1 \leq x \leq 1, -1 \leq y \leq 1 )]으로 표현되는, 넓이가 4인 정사각형 공간 안에 완전히 포함되는데, 이 공간 안에서 무작위로 (예를 들어) 10,000개의 난수 순서쌍 [math( (x, y) )]을 추출한다.

10,000개의 난수 순서쌍 [math( (x, y) )] 가운데에는 [math( x^2 + y^2 \leq 1 )]을 만족하여 원 안의 범위에 포함되는 것들이 있을 것이다. 그런 순서쌍들의 개수를 세어 전체 난수에 대한 비율을 계산하면 대략적인 원의 면적을 구할 수 있다. 무작위로 뽑힌 난수의 개수가 늘어날수록 더 정확한 결과를 얻을 수 있으나, 그만큼 더 많은 시간이 걸리는 것을 감안해야 한다. 또한 시뮬레이션 기반 방법이기 때문에, 해석적인 방법과 달리 항상 어느 정도 오차가 있을 수 있음을 감안해야만 한다.

{{{#!wiki style="max-width: max-content; margin: 0px auto; padding: 5px; border-radius: 3px; text-align: center; background-color: #0076a8; color: #fff;"
{{{#!wiki style="margin-bottom: -20px;"
'''[[MATLAB|{{{#fff MATLAB}}}]] 코드'''}}}
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -9px 0 -14px; text-align: left; color: #373a3c"
{{{#!syntax cpp
iter=100000

point=[rand(iter,1) rand(iter,1)];

circle_in_out=((point(:,1).^2+point(:,2).^2)<1);
circle_in_idx=find(circle_in_out==1);
circle_out_idx=find(circle_in_out==0);
circle_in_count=length(circle_in_idx);

Pi=circle_in_count/iter*4;

scatter(point(circle_in_idx,1),point(circle_in_idx,2), 'B.')
hold on
scatter(point(circle_out_idx,1),point(circle_out_idx,2), 'R.')

title('Monte-Carlo Pi')

fprintf(['=== Iteration : ' num2str(iter) ', Pi = ' num2str(Pi) ', accuracy : ' num2str((1-abs(1-(Pi/pi)))*100) '%% ===\n'])
}}}}}}}}}}}}
몬테 카를로란 이름이 붙은 이유는 이 방법이 알려지게 된 연구가 바로 로스 알라모 과학 연구소의 핵무기 개발 연구였기 때문이다. 해당 연구에는 스타니스와프 울람(Stanislaw Ulam)이 [[존 폰노이만]]과 함께 이 새로운 수치 해석 방법을 만들고 있었다. 핵무기 연구는 극비사항이라서 코드명이 필요했는데, 울람의 동료였던 [[니콜라스 메트로폴리스]]가 울람의 삼촌이 친척들에게 돈을 빌려서 자주 가던 카지노의 이름을 코드명으로 추천했고, 그것이 받아들여진 것이다. 

몬테 카를로 방법은 맨해튼 계획으로 [[원자 폭탄]]을 성공적으로 개발하고 난 뒤, [[수소 폭탄]] 개발 계획을 세울 때 고안된 것이다. 이 당시에 [[제2차 세계 대전]]은 이미 끝났고 끝내주는 위력을 가진 원자 폭탄도 확보했는데, 또 막대한 예산을 들여 수소 폭탄을 개발하려니까 일단 [[핵융합]]을 실제로 일으킬 수 있는지부터 확인해 볼 필요가 있었다. 그런데 당연히 아직 수소 폭탄 제조를 위한 참고 자료가 없었기 때문에, 이것을 확인하기 위해서는 일단 많은 돈이 들어가는 실험부터 해야 한다는 [[딜레마]]에 빠지게 되었다. 그래서 1946년에 예산을 타내기 위해 당시 막 등장한 컴퓨터를 사용해서 간단한 (하지만 당시로는 복잡한) 시뮬레이션을 돌려봤는데, 이 때 사용한 알고리즘이 바로 몬테 카를로 방법이다.[* 실제 투입됐을 때가 1946년이고, 몬테 카를로 방법의 아이디어 자체는 울람이 예전부터 생각해보고 있었다고 한다.]  참고로 몬테 카를로 방법은 컨셉 디자인이 말이 되는지 확인하는데만 사용되었고, 컨셉 디자인이 통과된 이후에 실제 수소 폭탄 설계와 제작은 '엄청난 수의 연구원과 많은 예산을 갈아넣어서 될 때까지 만들어 본다'는 전통적인 [[공밀레]] 방식으로 수행되었다. 실험 없이 오직 컴퓨터 시뮬레이션만으로 수소 폭탄을 설계하는 것은 2010년대 후반의 세계 최상급의 슈퍼 컴퓨터를 써도 불가능하다.  

== 마코프 체인 몬테 카를로 방법 ==
마코프 체인 몬테 카를로 방법(Markov Chain Monte Carlo Method, 약칭 MCMC)은 몬테 카를로 방법 중에서도 특정한 확률분포에 수렴하는 난수들을 추출하고 싶을 경우에 사용하는 방법이다. 이름은 난수를 추출하는 '몬테 카를로' 방식을 사용하되 여기에 '마코프 체인'이라는 수학적 개념의 성질을 이용한 것에서 유래했다. 몬테 카를로 방법을 명명한 사람들 중 하나로 앞에서 언급되었던 니콜라스 메트로폴리스는 이 방법을 위한 알고리즘을 제안했고, 이것이 이후 윌프레드 해이스팅스(Wilfred Hastings)라는 통계학자에 의해 일반화되면서 '메트로폴리스-해이스팅스 알고리즘'이라는 이름을 갖게 되었다.

마코프 체인(Markov Chain)은 시간이 지나감에 따라 현재 상태가 다른 상태로 변화하는 과정을 확률로 표현한 것인데, 러시아 수학자인 안드레이 마코프(Andrey Markov, 1856-1922)에 의해 만들어졌다. 마코프 체인이 특정한 수학적 성질을 만족하게 되면, 체인을 무수히 반복한 뒤에는 특정한 확률 분포의 형태로 수렴하게 되는 성질이 있다.

예를 들어, 오늘 날씨가 맑다면 내일의 날씨가 맑을지, 흐릴지, 비가 올지를 확률적으로 표현할 수 있다. 오늘 날씨가 흐리거나 비가 오는 경우에도 내일 날씨가 어떨지에 대한 확률을 각각 표현할 수 있을 것이다. 단, 이 때 내일의 날씨는 반드시 오늘의 날씨에 의해서만 결정되어야 하는데, 이것이 마코프 체인의 핵심적인 성질이다.(이 확률들의 묶음은 [[행렬]]로 표현된다.)

오늘 날씨로 내일의 날씨가 어떨지에 대한 확률을 계산하고, 이렇게 계산한 내일 날씨의 확률로 모레의 날씨가 어떨지에 대한 확률을 계산하는 식의 작업을 충분히 많이 반복한다고 해 보자. 내일 날씨가 어떨지에 대한 확률들의 묶음(행렬)이 특정한 성질을 만족한다면, 이렇게 무한히 확률 계산을 반복하면 오늘 날씨가 어떻느냐와는 상관 없이 일반적으로 날이 맑거나 흐리거나 비가 올 확률이 특정하게 수렴하게 된다.

때문에 난수를 추출하는 과정을 마코프 체인에 의존하면 특정한 확률 분포를 모사하도록 할 수 있다. 즉, 다음과 같은 절차를 밟는 것이다.
 * 가능한 입력값을 제시한다.
 * 입력값으로부터 난수를 추출한다.
 * 새로이 만들어진 난수를 바탕으로 또 다른 난수를 추출한다.
 * 위의 과정을 통해 추출된 난수들을 모아놓고 보면 특정한 확률분포로 수렴하게 된다.[* 단, 처음에 제시한 입력값에 따라서는 안정적인 연쇄과정에 이르기까지 시간이 조금 걸릴 수도 있다. 그래서 MCMC 방법을 시행할 때 난수 추출을 시작한 뒤부터 최초의 불안정한 체인들을 조금 잘라버리기도 하는데, 이를 전문가들의 속어로 'burn-in'이라고 한다.]

마코프 체인의 개념은 1900년대에 등장하였지만, 앞의 '날씨' 사례와 같은 간단한 사례가 아니라면 보통 사람의 손으로 체인을 일일이 계산하는 것은 불가능하다. 더군다나 무수히 반복한다는 정도가 아무리 적어도 수백번, 기본적으로는 1,000번이 넘기 마련이기 때문에 컴퓨터의 도움이 필수적이다. 따라서 [[CPU]]가 어느정도 따라와야 발전하는 학문이였고, 이제서야 빛을 본다고 해도 과언이 아니다. 2000년대로 넘어서면서 확률과 관련된 거의 모든 시뮬레이션의 결과는 이 MCMC의 결과라고 봐도 될 정도로, 매우 중요한 위치를 차지하고 있다.

다만 실제로는 특정한 분포로 수렴한다고 해도 여러 가지 이슈들이 있어서 분포가 수렴되지 않는 경우도 있기 때문에, 앞에서 서술한 것처럼 간단한 기법은 아니다. 때문에 앞에서 언급한 '메트로폴리스-해이스팅스 알고리즘'부터 시작하여 난수를 추출하기 위한 알고리즘들이 많이 개발되어 왔다.

== 활용 ==
몬테 카를로 방법의 활용이 일반인들에게 가장 알려진 분야는 인공지능이다. 대표적으로 알려진, DeepMind의 바둑 AI [[알파고]]는 몬테 카를로 기법에 기반한 몬테 카를로 트리 탐색 (Monte Carlo Tree Search) 알고리즘을 기반으로 하였다. 

확률을 기반으로 하는 시뮬레이션은 거의 대부분 마코프 체인 몬테 카를로 방법을 사용한다고 해도 과언이 아니다. 특히 [[베이즈 확률론]]과 [[베이즈 정리]]를 기반으로 두는 통계학의 흐름인 '베이즈 통계학'은 실제 활용을 해야 하는 상황에서는 계산의 복잡도가 높아, 이 MCMC 방법이 없었으면 도저히 발전하지 못했을 것이라 말할 정도로 해당 기법에 많이 의존하고 있다. [* 비공액 사전분포 인해 생기는 복잡한 사후분포를 계산하는데 있어 필수이다.]

핵 및 입자물리학에서도 광범위하게 활용된다. 여기서는 난수 하나를 만드는 게 아니라 아예 충돌 이벤트 자체를 만든다. 예를 들어 [[LHC]]에서의 충돌 실험에서 검출된 전자들의 에너지를 모아다 그 분포를 보고 싶다고 하자. 이 분포에 대한 이론적 예측과 실험과의 비교가 필요할텐데, 사실 입자물리에서 어떤 이론적 예측을 계산하는 건 결코 쉬운 일이 아니다. 입자가 두세 개 생성되는 거면 모를까, 고에너지 충돌에서 생성되는 입자 수는 엄청나게 많다. 거기다 충돌 과정 그 자체도 굉장히 복잡하거니와 검출기 자체도 너무 복잡해서 손으로 계산할 만한 일이 절대 아니다. 이 상황에서 물리학자들은 이론적 예측을 시뮬레이션으로 해결한다. 즉 충돌이라든가 입자 간의 상호작용 및 붕괴, 검출기와의 상호작용 같은 중요한 부분들을 따로 쪼개어 이들 각각에서의 확률 분포를 계산한 다음, 이 확률들을 토대로 하여 몬테 카를로 시뮬레이션을 돌리는 것이다.[* [[부루마불]] 같은 주사위 게임을 생각하면 쉽다. 각 분기 별로 주사위를 던지고, 나온 수에 따라 어디로 간 다음, 거기서 다음 분기를 만나 또 주사위를 던지는 식이다. 예를 들어 시물레이션에서 [[힉스 입자]] 하나가 생성되었다고 하자. 이 분기에서 생성된 난수(주사위 수)가 얼마냐에 따라 이 힉스 입자가 아래 쿼크 두 개로 쪼개질지, 타우온 두 개로 쪼개질지, Z 보손 두 개로 쪼개질지 결정하는 것이다. (여기서 난수를 더 발생시켜서 어느 각도로 쪼개져서 날아갈 건지 같은 것도 결정한다.) 그러면 그 다음 단계에서 또 주사위를 던져 그 다음을 따른다. 아래 쿼크의 경우, 아래 쿼크 하나가 이제 어떤 식으로 강한 상호작용을 할 것인지, 타우온의 경우, 타우온이 (타우온 중성미자와) 다른 렙톤-중성미자로 쪼개질지 아니면 쿼크 두 개로 쪼개질지, Z 보손의 경우, Z로부터 렙톤 두 개가 쌍생성될 지 아니면 쿼크 두 개가 쌍생성될 지 결정하는 것이다. 이걸 (검출기에 도달할 수 있을 정도로) 안정한 입자들로 다 붕괴할 때까지 반복하는 것이다. 그러고 나서 이 최종 입자들이 검출기에 도달했을 때 검출기와 상호작용할 때에도 또 분기와 난수를 적용시켜서 검출기 내에서 어떻게 반응하는가를 결정한다.] 말 그대로 무작위 가상 실험을 하는 것이다. 실험 한 번으로는 별 의미가 없지만 이걸 '''수십, 수백억 번''' 반복한 다음 이것들을 모아 [[히스토그램]]을 그리면 비로소 원하는 확률 분포를 얻을 수 있을 것이다. 괜히 LHC 같은 실험에서 고성능 컴퓨터가 많이 필요한 것이 아니다. [* 게다가 검출기에서 나온 신호를 분석하는 것 또한 연산량이 장난 아니기 때문에 (언급했다시피 검출기 자체가 복잡하기도 하고 입자가 너무 많이 나와서 대충 계산해서는 입자들의 제대로 된 경로 및 에너지를 정확하게 얻을 수 없다) 그쪽에도 슈퍼컴퓨터가 많이 필요하다.] 이 가상 실험 결과물들을 가지고 전자들만 골라내어 그 에너지를 히스토그램으로 그린 것이 바로 우리가 원하는 이론적 예측이 되는 것이다. 그 복잡함이라든가 몬테 카를로 기법이 어떻게 쓰이는 지에 대한 자세한 내용은 [[LHC]] 항목을 참고하면 좋다. LHC만 설명했는데, 사실 대부분의 대형 실험에서는 이와 같은 방식으로 몬테 카를로 기법을 애용하다시피 한다. 아예 이론적 예측 혹은 가상 실험 결과들을 모은 걸 가지고 몬테 카를로, 아니면 MC(Monte Carlo)라고 지칭하기도 한다.[* 예: 실험이랑 몬테 카를로랑 비교해 봤어요?]

[[분류:수학]][[분류:통계학]][[분류:미적분]]
몬테 카를로 방법 (덤프버전으로 되돌리기)

캡챠
