Life and computing: Sampling과 Monte Carlo Methods (몬테 카를로 방법)

데이터의 차원이 아주 클 경우, 샘플링 자체가 쉽지 않은 문제가 될 수 있음. 예를 들어, 특정 문서에 등장하는 단어들이 수십만개 일 때, 어떻게 샘플링하는 게 바람직한 지 고민될 수 있음.

무작위로 추출된 난수(random number)를 이용하여, 원하는 함수의 대략적인 값을 산출하기 위한 시뮬레이션 방법.
대표적인 예시: 가로와 세로가 각각 2인 정사각형에 내접하는(즉, 반지름이 1이 되는) 원의 면적을 구할 때, 정사각형 내부를 채울 수 있는 1만개의 난수 순서쌍 (x, y)을 무작위로 추출한 뒤, 원의 범위에 포함된 비율을 계산하는 방식을 생각해 볼 수 있음.
난수의 개수를 늘릴수록 정확도는 높아지겠지만, 그만큼의 연산 시간이 소요됨.
Manhattan Project에 참여했던 Los Alamos 국립 연구소의 핵무기 개발 관련 연구에서 유래함.
Central limit theorem에 의해, MC에 의한 sampling의 분포는 normal distribution에 수렴함.
Monte Carlo sampling: 모든 샘플이 독립(independent)이면서, 추출되는 확률 또한 random임.

특정한 확률분포에 수렴하는 (다시 말하면, 특정 확률 모델로부터) 난수들을 추출하는 몬테 카를로 방법.
= Metropolis-Hasting algorithm
Markov Chain = 시간이 흘러감에 따라, 현재 상태(random state x)에서 다음의 상태로 변화하는 과정을 전이 확률(transition probability)로 표현한 것.

확률과 관련된 많은 시뮬레이션이 MCMC에 의해 수행되고 있음.
예를 들어, 내일의 날씨는 반드시 오늘의 날씨에 의해서만 결정되어야 한다는 가정에 기반하여 확률로 표현할 수 있는 데, 앞으로의 날씨를 무한히 확률 계산을 하면, 오늘의 날씨와 상관없이, 일반적으로 날이 맑거나 흐리거나 비가 오는 확률이 특정하게 수렴하여 평형 상태의 정적인 분포(stationary distribution)에 도달하게 됨.

두 개 이상의 확률변수의 결합 확률 분포로부터 일련의 표본을 생성하는 확률적 알고리즘.
(MCMC에서처럼) 다음번 추출되는 샘플은 현재 샘플에 영향을 받지만, 여러개의 확률 변수 중에서 한번에 하나의 확률 변수에만 변화를 준다는 점에서 차이가 있음.
basic 기법

Life and computing