메트로폴리스-해스팅스 알고리즘은 널리 알려진 알고리즘입니다. MCMC 방법 확률 분포에서 직접 샘플링이 어려운 경우, 일련의 무작위 샘플을 얻기 위한 방법입니다. 각 반복 단계에서 현재 샘플을 기반으로 다음 샘플 후보를 생성합니다. 이 후보는 특정 확률로 수락되거나 거부되어, 결과적으로 생성되는 샘플 체인이 원하는 분포로 수렴하도록 합니다.
메트로폴리스-헤이스팅스 알고리즘
1970
- Nicholas Metropolis
- Arianna W. Rosenbluth
- Marshall N. Rosenbluth
- Augusta H. Teller
- Edward Teller
- W. Keith Hastings
(설명을 위한 생성된 이미지입니다)
The algorithm works by constructing a Markov chain whose stationary distribution is the target distribution [latex]P(x)[/latex]. Let the current state be [latex]x_t[/latex]. First, a candidate state [latex]x'[/latex] is generated from a proposal distribution [latex]Q(x’|x_t)[/latex], which can be any distribution that is easy to sample from (e.g., a Gaussian centered at [latex]x_t[/latex]). Second, an acceptance probability [latex]\alpha(x’, x_t)[/latex] is calculated: [latex]\alpha(x’, x_t) = \min\left(1, \frac{P(x’)Q(x_t|x’)}{P(x_t)Q(x’|x_t)}\right)[/latex]. A random number [latex]u[/latex] is drawn from a uniform distribution on [latex][0, 1][/latex]. If [latex]u \le \alpha[/latex], the candidate is accepted, and the next state is set to [latex]x_{t+1} = x'[/latex]. Otherwise, the candidate is rejected, and the chain remains at the current state, [latex]x_{t+1} = x_t[/latex].
이 수용 비율의 탁월함은 비례 상수까지만 알면 된다는 점입니다. 왜냐하면 모든 정규화 상수는 분수 [latex]frac{P(x’)}{P(x_t)}[/latex]에서 상쇄되기 때문입니다. 이는 사후 분포가 다루기 어려운 주변 가능도까지만 알려져 있는 경우가 많은 베이지안 통계에서 매우 중요합니다. 원래의 메트로폴리스 알고리즘(1953)은 제안 분포 [latex]Q[/latex]가 대칭인 특수한 경우, 즉 [latex]Q(x’|x_t) = Q(x_t|x’)[/latex]인 경우이며, 이 경우 수용 확률은 [latex]minleft(1, frac{P(x’)}{P(x_t)}right)[/latex]로 단순화됩니다. Hastings’ 1970년의 일반화는 비대칭 제안 분포를 허용하여 알고리즘의 적용 범위와 효율성을 크게 넓혔습니다.
UNESCO Nomenclature: 1209
통계
유형
소프트웨어/알고리즘
분열
상당한
용법
널리 사용됨
전구체
- 메트로폴리스 알고리즘(1953)
- 마르코프 체인의 상세 균형 이론
- Monte Carlo integration
- 베이지안 확률 이론
응용 프로그램
- simulating the boltzmann distribution in statistical mechanics
- 머신러닝에서의 베이지안 추론
- 시뮬레이티드 어닐링을 통해 복잡한 최적화 문제 해결
- 위험 모델링을 위한 계산 금융
- signal processing and image reconstruction
특허:
NA
잠재적 혁신 아이디어
현재 하루 4만 건이 넘는 봇 트래픽을 차단하기 위해 이 콘텐츠는 커뮤니티 회원만 이용할 수 있습니다.
> 로그인 < 또는 >등록 < 이 콘텐츠를 비롯한 모든 제한된 콘텐츠와 도구는 (100% 무료로) 이용할 수 있습니다.
관련 개념: 메트로폴리스-해스팅스 알고리즘, MCMC, 베이지안 통계, 수락-거부, 제안 분포, 정상 분포, 마르코프 체인, 샘플링, 통계 역학, 시뮬레이티드 어닐링.
역사적 맥락
메트로폴리스-헤이스팅스 알고리즘
(날짜를 알 수 없거나 관련이 없는 경우, 예를 들어 "유체역학"의 경우, 주목할 만한 등장 시기를 대략적으로 추정하여 제공합니다.)
