맨위로가기

마르코프 연쇄 몬테카를로

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

마르코프 연쇄 몬테카를로(MCMC)는 알려진 함수에 비례하는 확률 밀도를 가진 연속 확률 변수로부터 샘플을 생성하는 방법이다. 이러한 샘플을 통해 변수에 대한 적분을 기댓값 또는 분산으로 평가할 수 있으며, 무작위 컴퓨터 시뮬레이션의 일종인 몬테카를로 방법의 한 종류이다. MCMC는 평형 분포에 수렴하는 마르코프 연쇄를 생성하며, 메트로폴리스-헤이스팅스 알고리즘, 깁스 샘플링, 해밀토니안 몬테카를로 등이 주요 알고리즘으로 사용된다. 베이즈 통계, 계산 물리학, 계산 생물학 등 다양한 분야에서 활용되며, 차원의 저주와 수렴 진단 등의 한계를 극복하기 위한 연구가 진행되고 있다.

더 읽어볼만한 페이지

  • 베이즈 추정 - 최대 사후 확률
    최대 사후 확률은 모수의 사전 확률 분포와 관측된 데이터를 활용하여 사후 확률을 최대화하는 모수를 추정하는 방법으로, 최대우도 추정과 달리 사전 확률을 고려하며, 다양한 계산 방법이 있지만 재매개변수화에 불변하지 않고 다중 모드 분포에서 한계점을 가진다.
  • 베이즈 추정 - 신용 구간
    신용 구간은 확률 분포에서 계산되는 구간으로, 베이즈 신용 구간은 모수가 특정 값을 가질 확률을, 빈도주의 신뢰 구간은 신뢰 구간이 모수를 포함할 비율을 나타내며, 불필요한 변수 처리 방식 등에서 차이를 보인다.
  • 계산통계학 - 인공 신경망
  • 계산통계학 - 랜덤 포레스트
    랜덤 포레스트는 결정 트리들을 앙상블하여 분류, 회귀, 검출 등에 활용되며, 랜덤화 기술로 일반화 성능을 향상시키는 기계 학습 알고리즘이다.
  • 몬테카를로 방법 - 메트로폴리스-헤이스팅스 알고리즘
    메트로폴리스-헤이스팅스 알고리즘은 마르코프 연쇄 몬테카를로 방법으로, 확률 밀도 함수에 비례하는 함수를 알 때 원하는 확률 분포에서 난수열을 생성하며 통계 모델링, 데이터 분석 등에 응용된다.
  • 몬테카를로 방법 - 피셔-예이츠 셔플
    피셔-예이츠 셔플은 유한 집합에서 임의의 순열을 생성하는 알고리즘으로, 피셔와 예이츠가 처음 소개한 후 더스텐펠트에 의해 컴퓨터에 최적화되었으며, 구현 시 편향 요인을 주의해야 한다.
마르코프 연쇄 몬테카를로
개요
마르코프 연쇄의 그래픽 모델
마르코프 연쇄의 그래픽 모델
분야통계 물리학, 컴퓨터 과학, 통계학
관련 항목마르코프 연쇄, 몬테카를로 방법
상세 정보
유형알고리즘
문제 해결복잡한 확률 분포의 표본 추출
목표
목표확률 분포에서 표본을 추출하여 해당 분포의 속성 추정
방법
방법마르코프 연쇄를 구성하여 평형 분포가 목표 분포가 되도록 함
응용 분야
응용 분야베이즈 통계
물리학
생물학
언어학
컴퓨터 과학
공학
다른 이름
일본어マルコフ連鎖モンテカルロ法 (Marukofu rensa Monterukaruro-hō)
한국어마르코프 연쇄 몬테카를로 방법

2. MCMC의 기본 원리

마르코프 연쇄 몬테카를로(MCMC)는 특정 확률 분포(목표 분포)를 따르는 표본을 직접 얻기 어려울 때 사용하는 방법이다. MCMC의 기본 원리는 목표 분포를 정상 분포(또는 평형 분포)로 갖는 마르코프 연쇄를 인위적으로 생성하는 것이다. 마르코프 연쇄는 현재 상태에서 다음 상태로 이동할 확률이 정해진 일련의 무작위 과정으로, 충분한 시간이 지나면 특정 분포, 즉 정상 분포에 도달하게 된다.

MCMC 알고리즘은 마치 '보행자'가 확률적으로 공간을 탐색하는 과정에 비유할 수 있다. 이 보행자는 현재 위치에서 다음 위치로 이동할 때, 목표 분포에서 확률값이 더 높은 곳으로 이동할 가능성이 크도록 설계된다. 이렇게 생성된 마르코프 연쇄를 따라가면서 기록되는 보행자의 위치(상태값)들이 바로 우리가 원하는 목표 분포를 따르는 표본이 된다.

MCMC는 무작위성을 이용한다는 점에서 일종의 컴퓨터 시뮬레이션 또는 몬테카를로 방법으로 분류될 수 있다. 하지만 기존의 단순 몬테카를로 적분 등에서 사용하는 표본들이 서로 통계적 독립인 것과 달리, MCMC를 통해 생성된 표본들은 시간 순서에 따라 이전 표본의 영향을 받는 자기상관을 갖는다는 중요한 차이점이 있다. 대표적인 MCMC 알고리즘으로는 메트로폴리스-헤이스팅스 알고리즘과 깁스 표집 등이 있다.

2. 1. 마르코프 연쇄

마르코프 연쇄 몬테카를로(MCMC) 방법은 알려진 함수에 비례하는 확률 밀도를 가진 연속 확률 변수로부터 표본(sample)을 생성하는 데 사용된다. 이렇게 생성된 표본은 해당 변수에 대한 적분을 그 기댓값이나 분산으로 평가하는 데 활용될 수 있다.

MCMC 알고리즘은 주어진 함수에 비례하는 평형 분포(equilibrium distribution)를 갖도록 설계된 마르코프 연쇄를 생성한다. 실제 적용 시에는 임의로 선택된 여러 시작점에서 출발하는 여러 연쇄들이 동시에 진행된다. 이 연쇄는 다음에 이동할 위치 중 적분에 더 크게 기여할 가능성이 높은 곳, 즉 더 높은 확률을 가진 위치를 찾아 무작위로 이동하는 '보행자'(walker)의 확률 과정이다.

많은 MCMC 방법들은 평형 분포 주변에서 비교적 작은 보폭으로 움직이며, 특정 방향으로 계속 나아가려는 경향은 적다. 이 때문에 구현과 분석은 비교적 쉽지만, 보행자가 전체 공간을 탐색하는 데 오랜 시간이 걸릴 수 있다. 보행자는 종종 같은 경로를 반복하거나 왔던 길을 되돌아가기도 한다.

메트로폴리스-헤이스팅스 알고리즘의 수렴 예시. 마르코프 연쇄 몬테카를로는 주황색 분포를 이용하여 파란색 분포를 근사하려고 시도한다.


확률적 보행을 이용하는 몬테카를로 방법은 일종의 무작위 컴퓨터 시뮬레이션 또는 몬테카를로 방법이다. 하지만 기존의 몬테카를로 적분에서 사용되는 표본들이 통계적 독립적인 것과 달리, MCMC에서 생성된 표본들은 자기 상관(autocorrelation)을 가진다. 이러한 표본 간의 상관 관계 때문에, 평균값의 오차를 추정하기 위해서는 마르코프 연쇄 중심 극한 정리를 사용해야 한다.

대표적인 무작위 행보 MCMC 방법은 다음과 같다.

  • 메트로폴리스-헤이스팅스 알고리즘: 제안된 확률 밀도와 이동 제안을 거부하는 방식을 이용하여 무작위 행보를 생성한다.
  • 깁스 표집: 목표 분포의 모든 조건 분포로부터 정확하게 표본을 추출할 수 있어야 한다. 별도의 조정(tuning)이 필요 없다는 장점 때문에 널리 사용된다.

2. 2. 정상 분포

많은 마르코프 연쇄 몬테카를로(MCMC) 방법은 평형 분포(equilibrium distribution) 주위에서 비교적 작은 보폭으로 움직인다. MCMC 알고리즘의 목표는 주어진 함수에 비례하는 확률 밀도를 가진 평형 분포를 갖도록 마르코프 연쇄를 생성하는 것이다. 이렇게 생성된 마르코프 연쇄가 충분히 진행되면 평형 상태, 즉 정상 분포(stationary distribution)에 도달하게 되며, 이 상태에서의 분포가 바로 목표로 하는 분포를 나타낸다.

2. 3. 수렴

마르코프 연쇄 몬테카를로(MCMC) 방법은 목표 확률 밀도에 비례하는 평형 분포(정상 분포)를 갖도록 마르코프 연쇄를 생성하는 것을 목표로 한다. 원하는 속성을 가진 마르코프 연쇄를 만드는 것 자체는 어렵지 않지만, 실제로 중요한 문제는 이 연쇄가 얼마나 빨리 정상 분포에 도달하는지, 즉 수렴 속도를 파악하는 것이다.[23]

좋은 마르코프 연쇄는 빠른 혼합(fast mixing) 특성을 가진다. 이는 연쇄가 어떤 초기 상태에서 시작하든 빠르게 정상 분포에 가까워진다는 의미이다. 수렴 여부를 경험적으로 확인하는 일반적인 방법은 서로 다른 시작점에서 여러 개의 독립적인 마르코프 연쇄를 동시에 실행한 후, 샘플링된 모든 변수에 대해 연쇄들 사이의 분산(between-chain variance)과 각 연쇄 내부의 분산(within-chain variance)의 비율을 계산하는 것이다. 이 비율이 1에 가까우면 수렴했다고 판단할 수 있다.[23][24]

그러나 일반적으로 MCMC 샘플링은 목표 분포를 완벽하게 재현하는 것이 아니라 근사하는 방식이다. 왜냐하면 샘플링 과정에서 초기 시작점의 영향이 완전히 사라지지 않기 때문이다. 과거로부터의 결합(coupling from the past)과 같이 더 정교한 MCMC 기반 알고리즘은 이론적으로 정확한 샘플을 생성할 수 있지만, 이를 위해서는 추가적인 계산 비용이 들고 실행 시간이 얼마나 걸릴지 예측하기 어렵다는 단점이 있다 (평균 실행 시간은 유한하지만).

많은 무작위 행보(random walk) 기반 MCMC 방법들, 예를 들어 메트로폴리스-헤이스팅스 알고리즘이나 깁스 표집 등은 평형 분포 주변에서 비교적 작은 보폭으로 움직이며 특정 방향으로 계속 나아가려는 경향이 약하다. 이런 방식은 구현과 분석이 쉽다는 장점이 있지만, 전체 공간을 탐색하는 데 오랜 시간이 걸릴 수 있다. 즉, 수렴 속도가 느릴 수 있으며, 이미 방문했던 지점을 다시 방문하는 비효율적인 움직임을 보이기도 한다.

수렴에 대한 더 자세한 이론적 배경은 마르코프 연쇄 중심 극한 정리에서 다루어진다. 특히 메트로폴리스-헤이스팅스 알고리즘의 수렴 및 정상성(stationarity)과 관련된 이론은 관련 문헌[25]에서 찾아볼 수 있다.

3. 주요 MCMC 알고리즘

다양한 마르코프 연쇄 몬테카를로(MCMC) 알고리즘이 존재하며, 각기 다른 특성과 장단점을 가진다. 많은 MCMC 방법들은 목표하는 평형 분포(equilibrium distribution) 주변에서 비교적 작은 보폭으로 움직이는 무작위 행보(random walk)의 형태를 띤다. 이러한 방식은 구현하고 분석하기는 쉽지만, 전체 상태 공간을 탐색하는 데 오랜 시간이 걸릴 수 있고, 종종 이전에 방문했던 곳을 다시 탐색하는 비효율성이 발생하기도 한다.

대표적인 무작위 행보 기반 MCMC 방법들은 다음과 같다.


  • 메트로폴리스-헤이스팅스 알고리즘: 제안된 밀도와 제안된 이동을 거부하는 방법을 이용하여 무작위 행보를 생성하는 가장 일반적인 MCMC 방법이다.
  • 깁스 표집: 목표 분포의 모든 조건부 분포를 알고 정확하게 추출(샘플링)할 수 있어야 한다. 별도의 매개변수 조정이 필요 없어 인기가 있다.
  • 슬라이스 샘플링: 확률 밀도 함수의 곡선 아래 영역을 균일하게 샘플링하는 원리에 기반한다.
  • MTM 알고리즘 (Multiple-try Metropoliseng): 메트로폴리스-헤이스팅스 알고리즘의 변종으로, 각 지점에서 여러 번의 시도를 하여 보폭을 늘리거나 차원의 저주 문제 완화에 도움을 줄 수 있다.


무작위 행보 방식의 단점인 비효율적인 탐색(흩어지는 움직임, diffusive behavior)을 개선하기 위한 알고리즘들도 개발되었다. 이러한 알고리즘들은 구현이 더 복잡할 수 있지만, 목표 분포에 더 빠르게 수렴하여 적은 시도로도 정확한 결과를 얻을 가능성이 있다.

  • SOR 방법: 깁스 샘플링의 일종으로 간주될 수 있으며, 흩어지는 움직임을 피하도록 설계되었다.
  • 하이브리드 몬테카를로 방법 (HMC): 해밀토니언 역학의 원리를 도입하여 무작위 행보를 피하고 더 효율적인 탐색을 시도한다. 보조적인 운동량 변수를 사용한다.
  • NUTS 방법 (No-U-Turn Samplereng): HMC의 변형으로, 알고리즘의 매개변수를 자동으로 조정한다. 베이즈 통계 모델링 플랫폼인 Stan에서 사용된다.[28]
  • 슬라이스 샘플링의 일부 변형 역시 흩어지는 움직임을 회피하는 데 도움이 될 수 있다.[29]


또한, 모델의 차원 자체가 변하는 경우에 적용할 수 있는 방법도 있다.

  • 가역 점프 마르코프 연쇄 몬테카를로 (Reversible-jump Markov chain Monte Carloeng): 메트로폴리스-헤이스팅스 알고리즘을 확장하여, 서로 다른 차원을 갖는 상태 공간 사이를 이동하는 것을 가능하게 한다.[30] 이는 통계역학의 대정준 앙상블 문제나 베이즈 비모수적 모델 등에서 유용하게 사용된다.

3. 1. 메트로폴리스-헤이스팅스 알고리즘 (Metropolis-Hastings Algorithm)



메트로폴리스-헤이스팅스 알고리즘은 마르코프 연쇄 몬테카를로 (MCMC) 방법 중 가장 널리 사용되는 알고리즘 중 하나이다. 이 방법은 '제안 밀도'(proposal density|제안 밀도영어)에 따라 새로운 상태 후보를 제안하고, 특정 기준에 따라 이 후보를 수용하거나 기각하는 과정을 반복하여 마르코프 연쇄를 생성한다.[7][30] 이렇게 생성된 마르코프 연쇄는 목표하는 확률 분포를 평형 분포로 갖도록 설계된다.

이 알고리즘은 본질적으로 무작위 행보(Random Walk)의 특성을 지닌다. 즉, 현재 상태 주변에서 다음 상태를 탐색하며, 일반적으로 평형 분포 근처에서 비교적 작은 보폭으로 움직이는 경향이 있다. 이러한 특성 때문에 상태 공간 전체를 탐색하는 데 시간이 오래 걸릴 수 있으며, 탐색 과정에서 이전에 방문했던 상태를 다시 방문하는 비효율성이 나타나기도 한다.

메트로폴리스-헤이스팅스 알고리즘은 가장 초기에 개발된 MCMC 방법 중 하나로, 이후 개발된 여러 MCMC 기법들을 특별한 경우로 포함하는 일반적인 프레임워크로 여겨진다. 대표적인 예로 깁스 표집(Gibbs Sampling)이 있는데, 이는 메트로폴리스-헤이스팅스 알고리즘에서 제안된 후보를 항상 수용하는 (즉, 수용률이 1인) 특수한 경우로 볼 수 있다.[7] 깁스 샘플링은 목표 분포의 모든 조건 분포로부터 직접 표본을 추출할 수 있어야 한다는 전제가 필요하지만, 별도의 매개변수 조정(tuning) 과정이 필요 없다는 장점 때문에 인기가 있다.

3. 2. 깁스 샘플링 (Gibbs Sampling)

깁스 샘플링(Gibbs Sampling)은 대상 확률 분포가 다차원일 때 사용하는 마르코프 연쇄 몬테카를로(MCMC) 방법 중 하나이다.[7] 이 방법은 다른 모든 변수들의 값이 주어졌을 때, 특정 변수 하나를 해당 변수의 전체 조건부 분포에서 추출(샘플링)하는 과정을 각 변수에 대해 순차적으로 반복한다. 즉, 한 번에 하나의 변수만 업데이트하며, 업데이트할 때는 다른 변수들을 현재 값으로 고정한 상태에서 해당 변수의 조건부 분포를 이용한다.

깁스 샘플링을 사용하기 위해서는 대상 분포의 모든 변수에 대한 조건부 분포를 알고 있어야 하며, 이 분포들로부터 정확하게 난수를 생성할 수 있어야 한다. 이 방법은 메트로폴리스-헤이스팅스 알고리즘의 특별한 경우로 볼 수 있는데, 매 단계에서 새로 샘플링된 값이 항상 받아들여지기 때문이다(수용률 1).

깁스 샘플링은 별도의 조정(tuning) 파라미터 설정이 필요하지 않다는 장점 때문에 인기가 있다. 만약 어떤 변수의 전체 조건부 분포에서 직접 샘플링하는 것이 어렵다면, 해당 변수를 샘플링하기 위해 다른 종류의 샘플링 기법을 깁스 샘플링 단계 내부에 포함시키는 방식(sampler-within-Gibbs)을 사용하기도 한다.[8][9] 깁스 샘플링의 알고리즘 구조는 각 업데이트 단계에서 전체 조건부 분포를 활용한다는 점에서 좌표 상승 변동 추론(Coordinate Ascent Variational Inference)과 매우 유사하다.[10]

3. 3. 해밀토니안 몬테카를로 (Hamiltonian Monte Carlo, HMC)

하이브리드 몬테카를로 방법(Hybrid Monte Carlo, HMC), 또는 해밀토니안 몬테카를로(Hamiltonian Monte Carlo)는 마르코프 연쇄 몬테카를로(MCMC) 방법에서 나타나는 비효율적인 무작위 행보(random walk), 즉 흩어지는(diffusive) 움직임 문제를 개선하기 위해 고안된 알고리즘이다.[11] 이 방법은 해밀토니언 역학의 원리를 이용하여 표본 공간을 보다 효율적으로 탐색하는 것을 목표로 한다.

HMC는 부가적인 운동량 변수를 도입하고, 목표 확률 분포의 음의 로그 값에 해당하는 함수를 포텐셜 에너지 함수로 삼아 해밀토니언을 구성한다. 이후 해밀턴 방정식의 수치적 해를 따라 시스템을 이동시켜 다음 표본 후보를 제안한다. 이 과정에서 도입된 운동량 변수는 표본을 얻은 후 폐기된다. 해밀토니언 동역학을 이용한 확정적인 움직임 덕분에 HMC는 표본 공간 내에서 더 큰 단계(step)로 이동하고, 생성된 표본들 사이의 상관관계를 줄여 목표 분포에 더 빠르게 수렴할 수 있다.

HMC의 변형 알고리즘으로 NUTS(No-U-Turn Sampler)가 있다.[28] NUTS는 HMC 알고리즘의 파라미터를 자동으로 조정하여 사용성을 높인 방법으로, 베이즈 통계 모델링에 널리 사용되는 소프트웨어인 Stan에서 기본 샘플링 알고리즘으로 채택되어 있다.

3. 4. 슬라이스 샘플링 (Slice Sampling)

슬라이스 샘플링은 확률 밀도 함수의 그래프 아래 영역에서 균일하게 샘플링하면 해당 분포를 따르는 표본을 얻을 수 있다는 원리에 기반한 마르코프 연쇄 몬테카를로 알고리즘이다. 이 방법은 두 단계를 번갈아 수행한다. 먼저, 수직 방향으로 균일하게 샘플링하여 높이를 정한다. 다음으로, 현재 높이에 해당하는 수평 '슬라이스'(밀도 함수 값이 현재 높이 이상인 영역) 내에서 다시 균일하게 샘플링하여 다음 표본 위치를 결정한다.

3. 5. 가역 점프 MCMC (Reversible-Jump MCMC)

가역 점프 마르코프 연쇄 몬테카를로(Reversible-jump Markov chain Monte Carloeng)는 메트로폴리스-헤이스팅스 알고리즘을 확장한 방법으로, 서로 다른 차원을 가진 공간 사이를 이동하는(jump) 후보를 제안하고 수용할 수 있도록 한다.[12] 이 기법은 1995년 브리스톨 대학교의 피터 그린(Peter Green)에 의해 개발되었다.[30]

차원을 변경하는 마르코프 연쇄 몬테카를로 방법 자체는 이전부터 통계역학 분야에서 사용되어 왔는데, 예를 들어 대정준 앙상블처럼 시스템 내 입자 수가 변하는 경우와 같이 분포의 차원이 고정되지 않은 문제를 다룰 때 활용되었다.[12][30]

가역 점프 MCMC는 특히 비모수적 베이즈 모델 추론에 유용하게 사용된다. 예를 들어, 디리클레 과정이나 중국 음식점 과정과 관련된 모델에서 혼합 모델의 성분(component) 개수나 클러스터의 수를 데이터로부터 자동으로 추론해야 할 때 이 방법을 적용할 수 있다.[12]

4. 무작위 행보(Random Walk) 문제와 해결 방안

많은 MCMC 방법은 목표 분포인 평형 분포(equilibrium distribution) 주위에서 비교적 작은 보폭으로 움직이는 무작위 행보(random walk)의 특징을 가진다. 이러한 방식은 구현과 분석이 비교적 쉽다는 장점이 있지만, 탐색 대상 공간 전체를 효율적으로 탐색하는 데 오랜 시간이 걸릴 수 있다. 탐색 과정에서 보행자(walker)가 이미 방문했던 곳을 다시 지나가거나 주변을 배회하는 비효율적인 움직임이 자주 발생하기 때문이다.

이러한 무작위 행보의 비효율성, 즉 마르코프 연쇄가 가까운 상태들을 오가며 흩어지는(diffusive) 움직임을 개선하기 위해 여러 알고리즘이 개발되었다. 이 알고리즘들은 구현이 더 복잡할 수 있지만, 일반적으로 탐색 공간을 더 효율적으로 이동하여 더 빠른 수렴 속도를 보여준다. 즉, 더 적은 반복으로 정확한 결과를 얻을 가능성이 높다.

대표적인 무작위 행보 기반 MCMC 방법으로는 메트로폴리스-헤이스팅스 알고리즘과 깁스 표집 등이 있다. 무작위 행보의 문제를 개선하기 위해 제안된 방법들로는 Successive over-relaxation (SOR), 하이브리드 몬테 카를로 (HMC, 또는 해밀토니언 몬테 카를로), NUTS 방법[28], 그리고 특정 슬라이스 샘플링 기법[29] 등이 있다. 이러한 알고리즘들은 무작위 행보를 피하거나 줄여 표본 간의 상관관계를 낮추고 목표 분포에 더 빠르게 수렴하는 것을 목표로 한다.

4. 1. 무작위 행보 문제

많은 MCMC 방법은 목표 분포인 평형 분포(equilibrium distribution) 주위에서 비교적 작은 보폭으로 움직이는 무작위 행보(random walk)의 특성을 가진다. 이 움직임은 특정 방향으로 계속 나아가려는 경향이 적다. 이러한 방식은 구현하고 분석하기는 쉽지만, 보행자(walker)가 전체 표본 공간을 탐색하는 데 오랜 시간이 걸릴 수 있다는 단점이 있다. 또한 보행자는 종종 왔던 길을 되돌아가거나 이미 탐색했던 지점을 다시 방문하는 비효율성을 보이기도 한다.

다음은 무작위 행보를 기반으로 하는 대표적인 MCMC 방법들이다.

  • 메트로폴리스-헤이스팅스 알고리즘: 새로운 상태 후보를 제안하는 확률 분포인 제안 밀도(proposal density)를 사용하고, 제안된 이동을 특정 확률로 기각하거나 채택하는 방식을 통해 무작위 행보를 생성한다. 여러 다른 MCMC 기법들을 특별한 경우로 포함하는 가장 일반적인 방법 중 하나로 간주된다.
  • 깁스 표집: 목표 확률 분포의 모든 조건부 분포로부터 직접 표본을 추출하여 상태를 갱신한다. 이 방법은 필요한 모든 조건부 분포에서 정확하게 표본을 추출할 수 있어야 하며, 별도의 조정(tuning) 파라미터가 필요 없다는 점 때문에 널리 사용된다. 모든 제안이 항상 채택되는 특별한 경우의 메트로폴리스-헤이스팅스 알고리즘으로 볼 수도 있다.
  • 슬라이스 샘플링: 확률 밀도 함수의 그래프 아래 영역에서 균일하게 표본을 추출하면 목표 분포를 따르는 표본을 얻을 수 있다는 원리에 기반한다. 수직 방향으로 균일 표본을 추출하고, 해당 수직 위치에서 정의되는 수평 '슬라이스(slice)' 내에서 다시 표본을 추출하는 과정을 번갈아 수행한다.
  • Multiple-try Metropolis (MTM): 메트로폴리스-헤이스팅스 알고리즘의 변형으로, 각 단계에서 여러 개의 후보 상태를 생성하고 그중 하나를 선택한다. 이를 통해 더 큰 보폭으로 이동할 수 있으며, 차원의 저주와 관련된 고차원 문제에서 효율성을 높이는 데 도움이 될 수 있다.


무작위 행보 기반 방법들의 비효율성, 즉 마르코프 연쇄가 가까운 상태들 사이를 오가며 흩어지는(diffusive) 움직임을 개선하기 위해 여러 알고리즘이 개발되었다. 이러한 알고리즘들은 구현이 더 복잡할 수 있지만, 일반적으로 더 빠른 수렴 속도를 보여준다. 즉, 더 적은 반복으로 정확한 결과를 얻을 가능성이 높다.

  • Successive over-relaxation (SOR): 깁스 표집의 변형 중 하나로, 특정 조건 하에서 무작위 행보와 같은 흩어지는 움직임을 피하는 경향이 있다.
  • 하이브리드 몬테 카를로 (HMC, 또는 해밀토니언 몬테 카를로): 물리학의 해밀토니언 역학 개념을 이용한다. 추가적인 운동량(momentum) 변수를 도입하고, 목표 확률 분포의 음의 로그 값에 해당하는 포텐셜 에너지를 갖는 해밀토니언 시스템을 구성한다. 이 시스템의 동역학을 따라 상태 공간을 이동함으로써 무작위 행보를 피하고 더 효율적인 탐색을 시도한다. HMC는 확정적인 움직임을 통해 표본 공간을 더 큰 단계로 이동시키고, 생성된 표본 간의 상관관계를 줄여 목표 분포로 더 빠르게 수렴하는 것을 목표로 한다.
  • No-U-Turn Sampler (NUTS): HMC 알고리즘의 개선된 버전으로, 특히 Stan과 같은 베이즈 통계 분석 소프트웨어에서 널리 사용된다. HMC의 파라미터 설정을 자동화하여 사용 편의성을 높였다.[28]
  • 일부 슬라이스 샘플링 기법 또한 흩어지는 움직임을 피하도록 설계되어 효율성을 높일 수 있다.[29]

4. 2. 해결 방안

MCMC 방법 중 상당수는 목표 분포 주변에서 작은 보폭으로 움직이는 무작위 행보(random walk) 방식을 사용한다. 이 방식은 구현과 분석이 쉽다는 장점이 있지만, 탐색 대상 공간 전체를 살펴보는 데 시간이 오래 걸리는 단점이 있다. 탐색 과정에서 이미 방문했던 곳을 다시 지나가는 비효율적인 움직임이 자주 발생하기 때문이다. 또한, 차원의 수가 증가할수록 차원의 저주 문제에 부딪혀 확률이 높은 중요 영역을 효율적으로 탐색하기 어려워진다. 확률이 높은 영역은 늘어나는 전체 공간 속에서 상대적으로 작아져 찾기 어려워지고, 적분에 거의 기여하지 않는 영역을 탐색하는 데 많은 시간을 소모하게 된다.

이러한 무작위 행보 방식의 비효율성을 개선하고 수렴 속도를 높이기 위해 더 정교한 알고리즘들이 개발되었다. 이 알고리즘들은 구현이 더 복잡할 수 있지만, 탐색 과정에서 불필요한 왕복이나 흩어지는(diffusive) 움직임을 줄여 더 빠르게 목표 분포에 수렴하는 경향이 있다. 즉, 적은 시도로 정확한 결과를 얻을 가능성이 높아진다. 주요 해결 방안 알고리즘은 다음과 같다.

  • Successive over-relaxation (SOR): 깁스 표집의 변형으로, 흩어지는 움직임을 피하도록 설계되었다. 몬테카를로 방법을 응용한 SOR 방법은 깁스 샘플링의 일종으로 간주할 수 있다.
  • 하이브리드 몬테 카를로 (HMC): '해밀토니언 몬테 카를로'라고도 불린다. 부가적인 운동량 벡터를 도입하고, 목표 분포의 음의 대수 밀도 함수를 포텐셜 에너지로 하는 해밀토니언 역학을 이용하여 무작위 행보를 피한다. 해밀토니안 방정식을 근사적으로 풀어내는 확정적인 움직임과 운동량 벡터를 갱신하는 확률적인 움직임을 통해 후보를 생성한다. 이 확정적인 움직임 덕분에 HMC 방법은 표본 공간을 더 큰 단계로 이동하며, 상관관계가 낮은 표본을 생성하여 목표 분포에 더 빠르게 수렴할 것으로 기대된다.
  • NUTS 방법 (No-U-Turn Sampler): HMC 방법의 변형으로, 베이즈 통계학 모델링 플랫폼인 Stan에서 채택되어 널리 사용된다.[28]
  • 슬라이스 샘플링: 일부 변형은 흩어지는 움직임을 회피하는 데 도움이 될 수 있다.[29]
  • : 메트로폴리스-헤이스팅스 알고리즘의 변형으로, 각 지점에서 여러 후보를 시도하여 한 번에 더 큰 보폭으로 이동할 수 있게 한다. 이는 특히 고차원 문제 해결에 유용할 수 있다.
  • 왕-란다우 알고리즘: HMC와 마찬가지로, 적분에 더 크게 기여하는 영역에 탐색 과정을 집중시켜 자기 상관(autocorrelation)을 줄이는 방법을 사용한다.


이러한 정교한 알고리즘들은 일반적으로 더 복잡한 이론에 기반하며 구현이 어렵지만, 자기 상관을 줄이고 중요한 영역을 효율적으로 탐색하여 더 빠른 수렴 속도를 제공한다.

5. MCMC의 활용 분야

마르코프 연쇄 몬테카를로(MCMC) 방법은 그 유연성과 강력함 덕분에 다양한 과학 및 공학 분야에서 복잡한 문제를 해결하는 데 중요한 도구로 자리 잡았다. 여러 분야에서 MCMC 방법이 어떻게 활용되는지는 다음과 같다.


  • 수치 해석: 특히 다루기 어려운 다중 적분 문제를 수치적으로 근사 계산하는 데 널리 활용된다. 또한 희귀 사건 표본 추출과 같이 특정 조건의 표본을 효율적으로 생성해야 하는 문제에도 적용될 수 있다.
  • 베이즈 통계: 해석적으로 계산하기 어려운 사후 확률 분포를 추정하고 분석하는 데 핵심적인 역할을 수행하며, 복잡한 계층적 모델 분석을 가능하게 한다.[6]
  • 계산 과학: 계산 물리학,[1] 계산 생물학,[3] 계산 언어학[4][5] 등 여러 분야에서 복잡한 확률 모형을 다루거나 시뮬레이션을 수행하는 데 사용된다.


각 분야에서의 구체적인 활용 방식은 아래 하위 섹션에서 더 자세히 다룬다.

5. 1. 베이즈 통계

마르코프 연쇄 몬테카를로(MCMC) 방법은 베이즈 통계 분야에서 중요한 도구로 활용된다. 베이즈 통계에서는 관찰된 데이터를 바탕으로 모수의 사후 확률 분포를 추론하는 것이 핵심인데, 많은 경우 이 사후 분포는 해석적으로 계산하기 매우 복잡하다. MCMC 방법은 이러한 복잡한 사후 분포로부터 직접 표본을 추출하여 분포의 특성을 근사적으로 파악할 수 있게 해준다.

구체적으로, MCMC를 통해 얻어진 사후 분포의 표본들을 이용하여 분포의 모멘트(예: 평균, 분산 등)를 추정하거나, 모수에 대한 신뢰 구간을 설정하는 데 사용된다. 이는 복잡한 적분 계산을 피하면서도 원하는 통계적 추론을 가능하게 한다. 특히 MCMC 방법은 수백 개에서 수천 개에 이르는 다수의 미지 모수를 포함하는 대규모 계층적 모델 분석에 효과적이다. 이러한 모델들은 전통적인 방법으로는 계산이 거의 불가능하지만, MCMC를 이용하면 효율적으로 분석할 수 있다.[6]

5. 2. 수치 적분

MCMC 방법은 주로 수치 해석에서 다중 적분의 값을 수치적으로 근사 계산하는 데 사용된다. 예를 들어 베이즈 통계, 계산 물리학,[1] 임상 연구,[2] 계산 생물학[3] 및 계산 언어학[4][5] 등 다양한 분야에서 활용된다.

베이즈 통계 분야에서 마르코프 연쇄 몬테카를로 방법은 주로 사후 확률 분포의 모멘트나 신뢰 구간 등을 계산하는 데 쓰인다. MCMC 방법을 이용하면 수백 개에서 수천 개에 달하는 미지 매개변수에 대한 적분이 필요한 대규모 계층적 모델의 계산도 가능하다.[6]

또한 희귀 사건 표본 추출에서는 드물게 발생하는 실패 영역을 점진적으로 채워나가는 샘플을 생성하는 데에도 사용된다.

5. 3. 계산 물리학, 계산 생물학, 계산 언어학

마르코프 연쇄 몬테카를로(MCMC) 방법은 주로 수치 해석 분야에서 다중 적분의 수치 근사값을 계산하는 데 사용된다. 특히 계산 물리학,[1] 계산 생물학,[3] 계산 언어학[4][5] 등 다양한 과학 분야에서 복잡한 확률 모형을 분석하고 시뮬레이션하기 위해 이 방법을 활용한다.

6. MCMC 관련 소프트웨어

다음은 MCMC 샘플링 기능을 제공하는 몇 가지 소프트웨어 프로그램이다.


  • ParaMonte: C, C++, Fortran, MATLAB, 파이썬 등 다양한 프로그래밍 언어를 지원하는 병렬 몬테카를로 소프트웨어이다.
  • BUGS 모델 언어 방언을 사용하는 패키지:
  • * WinBUGS / OpenBUGS / MultiBUGS
  • * JAGS
  • MCSim
  • 줄리아 언어 기반 패키지:
  • * Turing.jl
  • * DynamicHMC.jl
  • * AffineInvariantMCMC.jl
  • * Gen.jl
  • * StanJulia 저장소의 패키지들
  • 파이썬 패키지:
  • * Blackjax
  • * emcee[26]
  • * NumPyro[27]
  • * PyMC
  • R 패키지: adaptMCMC, atmcmc, BRugs, mcmc, MCMCpack, ramcmc, rjags, rstan 등이 있다.
  • Stan
  • TensorFlow Probability: TensorFlow 기반의 확률적 프로그래밍 라이브러리이다.
  • Korali: 베이즈 추론 기반 불확실성 정량화(UQ), 최적화, 강화 학습을 위한 고성능 프레임워크이다.
  • MacMCMC: macOS용 무료 소프트웨어로, 고급 기능을 제공한다 (causaScientia 제공).

7. MCMC의 한계와 극복

마르코프 연쇄 몬테카를로(MCMC) 방법은 복잡한 확률 분포를 다루는 데 유용하지만, 몇 가지 주요한 한계에 직면하기도 한다. 대표적인 어려움 중 하나는 분석하려는 데이터의 차원이 높아질수록 계산 효율성이 크게 떨어지는 차원의 저주 문제이다. 또한, MCMC 알고리즘을 통해 생성된 표본(sample)들이 실제로 목표하는 확률 분포에 충분히 수렴했는지 확인하고 진단하는 것도 중요한 과제이다.

이러한 문제점들을 해결하고 MCMC 방법의 성능을 개선하기 위해 다양한 접근법들이 연구되고 있다. 고차원 공간에서의 탐색 효율을 높이거나 더 빠른 수렴을 유도하는 알고리즘들이 개발되었으며, 생성된 연쇄의 수렴 여부를 통계적으로 평가하는 여러 진단 기법들도 함께 사용된다.

7. 1. 차원의 저주

마르코프 연쇄 몬테카를로(MCMC) 방법은 일반적인 몬테카를로 알고리즘보다 다차원 문제를 더 효과적으로 해결하기 위해 고안되었지만, 차원의 수가 증가하면 이러한 방법들 역시 차원의 저주 문제에 직면하는 경향이 있다. 확률적으로 중요한 영역(확률이 높은 영역)은 차원이 늘어남에 따라 방대해지는 전체 공간 속에서 상대적으로 매우 작은 부분을 차지하게 되어 찾기 어려워지며, 이는 적분 계산 등의 효율성을 저하시킨다.

이 문제를 해결하기 위한 한 가지 단순한 접근법은 MCMC 알고리즘에서 이동하는 단계(step)의 크기를 줄이는 것이다. 이렇게 하면 확률이 높은 영역에서 벗어날 가능성은 줄어들지만, 탐색 과정이 유사한 상태에 오래 머무르는 경향(높은 자기 상관성)이 강해진다. 결과적으로 정확한 결과를 얻기 위해 훨씬 더 많은 계산 단계가 필요하게 되어 비용이 증가하는 단점이 있다.

보다 정교한 방법들은 이러한 한계를 극복하기 위해 개발되었다. 예를 들어 해밀토니안 몬테카를로나 왕-란다우 알고리즘과 같은 방법들은 확률적으로 중요한 영역에 탐색 과정을 집중시키면서도 자기 상관성을 줄이는 다양한 전략을 사용한다. 이러한 알고리즘들은 일반적으로 더 복잡한 이론에 기반하고 구현이 까다롭지만, 수렴 속도는 더 빠른 경향이 있다.

또 다른 접근 방식으로는 상호작용 MCMC 방법론이 있다. 이는 평균장 입자 방법의 한 종류로, 샘플링 복잡성이 점진적으로 증가하는 일련의 확률 분포에서 무작위 표본을 효율적으로 얻기 위해 설계되었다.[13] 이러한 방법론이 적용될 수 있는 확률 모델의 예로는 시간 지평선이 길어지는 경로 공간 상태 모델, 부분적인 관측 데이터만 주어진 경우의 사후 분포, 조건부 분포에 대한 제약 조건이 점차 강화되는 경우, 또는 볼츠만-깁스 분포와 관련된 온도를 점진적으로 낮추는 일정 등이 있다.

원칙적으로 어떤 MCMC 샘플러라도 상호작용 MCMC 샘플러로 변환될 수 있다. 이 상호작용 샘플러들은 여러 개의 MCMC 샘플러를 병렬로 실행하면서 서로 정보를 교환하는 방식으로 이해할 수 있다. 예를 들어, 상호작용 모의 담금질 알고리즘은 독립적인 메트로폴리스-헤이스팅스 이동과 선택-재샘플링(selection-resampling) 메커니즘을 순차적으로 결합하여 작동한다. 기존 MCMC 방법과 달리, 이 상호작용 MCMC 샘플러의 정밀도는 주로 병렬로 실행되는 샘플러의 수에 의해 결정된다는 특징이 있다. 이러한 고급 입자 방법론은 파인만-카츠(Feynman-Kac) 입자 모델의 한 부류로 분류되며,[14][15] 베이즈 추론이나 신호 처리 분야에서는 시퀀셜 몬테카를로(Sequential Monte Carlo, SMC) 또는 입자 필터 방법으로도 알려져 있다.[16] 또한, 상호작용 MCMC 방법은 MCMC 방식의 변이(mutation) 단계를 포함하는 돌연변이-선택 기반의 유전 입자 알고리즘으로 해석될 수도 있다.

한편, 메트로폴리스-헤이스팅스 알고리즘의 변형 중 하나인 다중 시도 메트로폴리스(Multiple-try Metropoliseng, MTM) 알고리즘은 각 단계에서 여러 개의 후보 상태를 시도하는 방식으로 작동한다. 이 방법은 일반적으로 더 큰 보폭으로 이동할 수 있게 하여, 차원의 저주와 관련된 고차원 문제의 어려움을 완화하는 데 도움이 될 수 있다.

7. 2. 수렴 진단

원하는 속성을 가진 마르코프 연쇄를 만드는 것 자체는 보통 어렵지 않다. 하지만 실제 문제는 생성된 연쇄가 허용 가능한 오차 범위 내에서 정상 분포(stationary distribution)에 수렴하기까지 얼마나 많은 단계를 거쳐야 하는지를 결정하는 것이다.[23] 좋은 연쇄는 빠른 혼합(fast mixing) 특성을 가지는데, 이는 어떤 상태에서 시작하든 빠르게 정상 분포에 도달한다는 의미이다. 수렴 여부를 경험적으로 평가하는 일반적인 방법 중 하나는 서로 독립적인 여러 개의 마르코프 연쇄를 동시에 실행하고, 샘플링된 모든 매개변수에 대해 연쇄들 사이의 분산(between-chain variance)과 각 연쇄 내부의 분산(within-chain variance) 비율을 계산하는 것이다. 이 비율이 1에 가까워지면 수렴했다고 판단할 수 있다.[23][24]

일반적으로 마르코프 연쇄 몬테카를로 방법으로 얻은 샘플은 목표 분포를 근사할 뿐인데, 이는 시작점의 영향이 완전히 사라지지 않기 때문이다. 하지만 과거로부터의 결합(coupling from the past)과 같이 더 정교한 알고리즘을 사용하면, 계산 비용이 더 많이 들고 실행 시간이 정해져 있지 않다는 단점(기댓값은 유한함)에도 불구하고 정확한 샘플을 생성하는 것이 가능하다.

많은 랜덤 워크(random walk) 기반 몬테카를로 방법들은 평형 분포 주변에서 비교적 작은 단계로 움직이며, 특정 방향으로 계속 나아가는 경향이 적다. 이런 방법들은 구현하고 분석하기는 쉽지만, 탐색 대상 공간 전체를 돌아다니는 데 오랜 시간이 걸릴 수 있다는 단점이 있다. 탐색 과정에서 이미 방문했던 지점을 다시 방문하며 시간을 허비하는 경우가 많기 때문이다.

수렴에 대한 더 자세한 내용은 마르코프 연쇄 중심 극한 정리에서 찾아볼 수 있다. 메트로폴리스-헤이스팅스 알고리즘의 수렴 및 정상성(stationarity)과 관련된 이론적 논의는 참고 문헌[25]에서 확인할 수 있다.

참조

[1] 논문 Retrieving fields from proton radiography without source profiles 2019-09
[2] 논문 Improving cancer patient outcomes and cost-effectiveness: a Markov simulation of improved early detection, side effect management, and palliative care. 2023
[3] 논문 Comparison of Parameter Estimation Methods in Stochastic Chemical Kinetic Models: Examples in Systems Biology 2014-04
[4] 문서 Gill 2008
[5] 문서 Robert & Casella 2004
[6] 서적 Hierarchical Modeling and Analysis for Spatial Data CRC Press 2014-09-12
[7] 논문 Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images https://ieeexplore.i[...] 1984-11
[8] 논문 Adaptive Rejection Sampling for Gibbs Sampling 1992-01-01
[9] 논문 Adaptive Rejection Metropolis Sampling within Gibbs Sampling 1995-01-01
[10] 논문 Gibbs sampler and coordinate ascent variational inference: A set-theoretical review
[11] 문서 Stramer 1999
[12] 문서 Green 1995
[13] 서적 Mean field simulation for Monte Carlo integration http://www.crcpress.[...] Chapman & Hall/CRC Press
[14] 서적 Feynman–Kac formulae. Genealogical and interacting particle approximations https://www.springer[...] Springer
[15] 서적 Séminaire de Probabilités XXXIV http://archive.numda[...] 2000
[16] 논문 Sequential Monte Carlo samplers
[17] 논문 Beating Monte Carlo https://iiif.library[...]
[18] 논문 On quasi-monte carlo integrations
[19] 논문 Consistency of Markov chain quasi-Monte Carlo on continuous state spaces
[20] 간행물 Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences Stanford University
[21] 논문 A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains https://hal.inria.fr[...]
[22] 논문 Sorting Methods and Convergence Rates for Array-RQMC: Some Empirical Comparisons
[23] 논문 Inference from iterative simulation using multiple sequences (with discussion) http://www.stat.duke[...] 1992
[24] 논문 Markov chain Monte Carlo convergence diagnostics: a comparative review 1996
[25] 논문 Stationarity and Convergence of the Metropolis-Hastings Algorithm: Insights into Theoretical Aspects
[26] 논문 emcee: The MCMC Hammer 2013-11-25
[27] 간행물 Composable Effects for Flexible and Accelerated Probabilistic Programming in NumPyro 2019-12-24
[28] 논문 The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo http://jmlr.org/pape[...] 2014-04
[29] 논문 Slice sampling https://doi.org/10.1[...] Institute of Mathematical Statistics
[30] 논문 Reversible jump Markov chain Monte Carlo computation and Bayesian model determination https://doi.org/10.1[...] 1995-12


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com