메트로폴리스-헤이스팅스 (Metropolis-Hastings)
쉽게 풀면
산 전체의 높이 분포를 알고 싶은데 지도가 없다고 해봅시다. 대신 이렇게 할 수 있습니다. 지금 서 있는 지점에서 무작위로 한 걸음을 제안하고, 그 지점이 지금보다 더 높으면 무조건 이동하고, 더 낮으면 "낮아진 정도"에 비례한 확률로만 가끔 이동합니다. 이 과정을 아주 오래 반복하면, 내가 머물렀던 위치들의 기록이 실제 산의 높이 분포(높은 곳에 오래 머묾)를 그대로 흉내 내게 됩니다. 메트로폴리스-헤이스팅스는 바로 이 방식으로, 확률밀도 수식 자체를 몰라도 "제안하고 받아들이거나 기각하기"만 반복해서 원하는 분포의 표본을 만들어냅니다.
왜 중요한가
많은 통계·생물정보학·기계학습 모형에서 관심 있는 확률분포는 정규화 상수를 계산할 수 없을 만큼 복잡한 경우가 대부분입니다. 메트로폴리스-헤이스팅스는 그 상수를 몰라도 분포의 비율만 계산할 수 있으면 표본을 얻을 수 있게 해주므로, 베이지안 추론이 실제 데이터 분석에서 널리 쓰일 수 있게 만든 계산적 토대로 평가받습니다.
논문에서는 이렇게 쓰입니다
이 문장은 "베이지안 모형의 사후분포 수식이 너무 복잡해 계산이 불가능했기 때문에, 제안-수용/기각을 반복하는 시뮬레이션으로 그 분포를 근사해 표본을 뽑았다"는 뜻입니다.
생물정보학의 계통발생학 연구에서는 트리 위상 공간이라는 매우 복잡한 이산 공간을 탐색할 때도 메트로폴리스-헤이스팅스 방식이 적용됩니다.
기계학습 논문에서는 하이퍼파라미터나 잠재변수의 불확실성을 정량화할 때 이 알고리즘의 랜덤워크 변형이 자주 사용됩니다.
조금 더 깊게 보면
수락 확률은 제안된 지점과 현재 지점에서의 목표분포 값의 비율, 그리고 제안분포가 대칭이 아닐 경우 그 비대칭성을 보정하는 항으로 구성됩니다. 실제 적용에서는 여러 개의 독립적인 연쇄를 돌려 겔만-루빈 통계량 같은 지표로 수렴 여부를 진단하고, 연속 표본 간 상관을 낮추기 위한 씨닝, 그리고 초반 불안정한 구간을 제거하는 번인 설정이 함께 다뤄지는 경우가 많습니다.
주의할 점
제안 분포(다음 후보를 뽑는 방식)의 폭을 너무 좁게 잡으면 표본이 한곳에 머물러 움직임이 느려지고, 너무 넓게 잡으면 대부분의 제안이 기각되어 역시 비효율적입니다. 또한 초기 표본들은 아직 목표 분포에 도달하기 전이므로 깁스 표집과 마찬가지로 번인(burn-in) 구간을 버리고 분석해야 합니다.