메트로폴리스-헤이스팅스 알고리즘

통계학 및 통계물리학에서 메트로폴리스-해스팅 알고리즘은 직접 샘플링이 어려운 확률분포에서 무작위 샘플의 순서를 얻기 위한 마르코프 체인 몬테카를로(MMC) 방법이다.이 시퀀스는 분포의 근사치(예: 히스토그램 생성) 또는 적분(예: 기대값) 계산에 사용할 수 있다.일반적으로 Metropolitan-Hastings 및 기타 MCMC 알고리즘은 다차원 분포에서 추출하는 데 사용되며, 특히 차원 수가 많을 경우 더욱 그러하다.단차원 분포의 경우 일반적으로 분포에서 독립 샘플을 직접 반환할 수 있는 다른 방법(예: 적응 거부 샘플링)이 있으며, 이는 MCMC 방법에 내재된 자동 상관 표본의 문제로부터 자유롭다.

역사

이 알고리즘은 1953년 '패스트 컴퓨팅 머신에 의한 국가 계산식의 방정식'을 쓴 니콜라스 메트로폴리스가 아리안나 W. 로젠블루스, 마샬 로젠블루스, 오거스타 H와 함께 쓴 글에서 따왔다. 텔러와 에드워드 텔러.본 기사는 대칭 제안 분포의 경우에 대한 알고리즘을 제안하였고, W. K. 헤이스팅스는 1970년에 이를 보다 일반적인 사례로 확대하였다.^[1]

알고리즘 개발에 대한 신용과 관련하여 일부 논란이 존재한다.이 방법의 계산적 측면에 정통했던 메트로폴리스는 스타니스와프 울람과 함께 앞서 쓴 글에서 '몽테 카를로'라는 용어를 만들어 냈고, 1952년 실험에 사용된 '매니악 I 컴퓨터'를 설계하고 만든 이론부문에서 그룹을 이끌었다.그러나 2003년 이전에는 알고리즘의 개발에 대한 상세한 설명이 없었다.그 후, 그가 죽기 직전에 마샬 로젠블루스는 1953년 출판 50주년을 기념하여 LANL에서 열린 2003년 회의에 참석했다.이 회의에서 로젠블루스는 "통계역학을 위한 몬테카를로 알고리즘의 제네시스"라는 제목의 발표에서 알고리즘과 그 개발에 대해 설명했다.^[2]Gubernatis는 50주년 기념 콘퍼런스를 재점검하는 2005년 저널 기사에서^[3] 역사적인 추가 설명을 하고 있다.로젠블루스는 자신과 아내 아리안나가 그 일을 했고, 메트로폴리스가 컴퓨터 시간을 제공하는 것 외에는 개발에 아무런 역할도 하지 않았다는 점을 분명히 하고 있다.

이것은 1953년 기사의 5명의 작가가 "낮과 밤" 동안 함께 일했다고 그의 회고록에서 진술한 에드워드 텔러의 설명과 모순된다.^[4]이와는 대조적으로, 로젠블루스의 상세한 설명은 텔러에게 "세부적인 운동학을 따르는 대신에 통계적 역학을 활용하고 앙상블 평균을 취하라"는 중요하지만 초기 제안으로 인정한다.로젠블루스는 이것이 존 폰 노이만과 자주 논의했던 주제인 일반화된 몬테카를로 접근법에 대해 생각하기 시작했다고 말한다.아리안나 로젠블루스는 아우구스타 텔러가 컴퓨터 작업을 시작했지만, 아리안나가 직접 인수해 처음부터 코드를 작성했다고 (2003년 구베르나티스에게) 되뇌었다.로젠블루스는 죽기 직전에 기록된 구술 역사에서 텔러가 원래의 문제를 제기하고, 자신이 문제를 해결하는 것에 대해, 그리고 아리안나가 컴퓨터를 프로그래밍하는 것에 대해 다시 한 번 공로를 인정한다.^[5]평판 면에서는 로젠블루스의 계정을 의심할 이유가 거의 없다.로젠블루트의 전기적 회고록에서 프리먼 다이슨은 다음과 같이 쓰고 있다.^[6]

여러 번 로젠블루스에 와서 [...] 질문을 하고 2분 만에 대답을 받았다.그렇다면 왜 로젠블루스의 대답이 옳았는지 자세히 이해하려면 보통 일주일간의 고된 노력이 필요할 것이다.그는 복잡한 육체적 상황을 꿰뚫어보고 육체적 논쟁으로 정답을 찾아내는 놀라운 능력을 가지고 있었다.엔리코 페르미는 내가 알고 있는 다른 물리학자들 중 유일하게 로젠블루스와 동등한 물리학자가 물리학에 대한 직관적인 이해력이었다.

직감

밀도 $P{\displaystyle }$ ${\displaystyle P}$에 비례하는$$ $함수{\displaystyle }$ f${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle f(x)}$을 알고 $있고{\displaystyle }$ f${\displaystyle }$( x${\displaystyle }$) ${\displaystyle f(x)}$ 값을 계산할 수 있다면$$ Metropolitanis-Hastings 알고리즘은 확률 밀도 $P{\displaystyle }$( ${\displaystyle x}$) ${\displaystylean P(x)$를 가진 확률 분포에서 표본을 추출할 수 있다$.$$f{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle f(x)}$은(는) 밀도에만 비례해야 한다는$$ 요구사항은 필요한 표준화 인자를 계산하는 것이 실무에서 매우 어려운 경우가 많기 때문에 Metropolitan-Hastings 알고리즘을 특히 유용하게 만든다.

Metropolitan-Hastings 알고리즘은 샘플 값이 점점 더 많이 생산될수록 값의 분포가 원하는 분포에 더 가깝게 되도록 샘플 값의 순서를 생성함으로써 작동한다.이러한 샘플 값은 반복적으로 생성되며, 다음 샘플의 분포는 현재의 샘플 값에만 의존한다(즉, 샘플의 순서를 마르코프 체인으로 만든다).특히, 각 반복에서 알고리즘은 현재 샘플 값에 기초하여 다음 샘플 값의 후보를 선택한다.그런 다음 어느 정도 확률로 후보를 수용하거나(${\displaystyle 이}$ 경우 후보 값을 다음 반복에서 사용하고, 현재 값을 다음 반복에서 재사용하는 경우), 즉 f(x ){\$displayst$ 함수 $값$을 비교하여 합격 확률을 결정한다$.$원하는 분포와 관련하여 현재 및 후보 표본 값의$$ $yle f(x)}.$

예시를 위해, 제안 함수가 대칭인 메트로폴리스-해스팅 알고리즘의 특별한 사례인 메트로폴리스 알고리즘을 아래에 기술한다.

메트로폴리스 알고리즘(대칭 제안 분포)

$f{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle f(x)}$을(를) 원하는 확률밀도함수 $P{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle P(x)}($대상 분포)에 비례하는 함수로 한다$$.^[a]

1. 초기화:표본의 첫 번째 관측치가 될$$ 임의 ${\displaystyle {점}_{}}$ $x{\displaystyle {}_{}}$ t ${\$을 $선택$하고 다음 표본 $값{\displaystyle }$ x {\$displaystyle$ g$(x\mid$ y$)}($$때로는{\displaystyle }$ Q${\displaystyle (xy}$ y${\displaystyle }$)$${\$displaystyle$ Q$(x\mid$ y$)\})$를 선택하여 다음 표본 값 x ${\displaysty x}$에 대한 후보를 제시하십시오.n the previous sample value ${\displaystyle y}$. In this section, ${\displaystyle g}$ is assumed to be symmetric; in other words, it must satisfy ${\displaystyle g(x\mid y)=g(y\mid x)}$. A usual choice is to let ${\displaystyle g(x\mid y)}$ be a Gaussian distribution centered at ${\displaystyle }$$y{\displaystyle }$ ${\displaystyle y}$에 더 가까운 지점이 다음에 방문될 가능성이 높으므로$$ 표본의 순서가 무작위 보도로^[b] 된다$.$$g$ ${\displaystyle g}$ 함수를 제안 밀도 또는 점프 분배라고 한다.
2. 각 반복 t:
   • 분포 $g{\displaystyle ({}^{}}$ ${\displaystyle {\prime }^{}}$ ${\displaystyle \mid }$ ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$) ${\displaystyle g(x'\mid x_{t})$에서 선택하여 다음 샘플에 사용할$$ 후보 $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ x$'}$을(를) 생성하십시오$.$
   • 후보^[c] 수락 여부를 결정하는 데 사용할 합격 비율 ${\displaystyle \alpha }$= f${\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$)${\displaystyle }$/ ${\displaystyle f}$( ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$) ${\displaystyle \alpha =f(x')/f(x_{t}}}}$을 계산한다$.$f는 P의 밀도에 비례하기 때문에 $\alpha {\displaystyle }$= ${\displaystyle f}$( x${\displaystyle {}^{}}$′${\displaystyle }$)${\displaystyle }$/ f${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$)${\displaystyle }$= ${\displaystyle P}$( ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$)${\displaystyle }$/ ${\displaystyle P}$( x ${\displaystyle t_{}}$ )${\displaystyle \alpha =f(x')/f(x_{t})=P(x_${t})/$P(x_{t})}}}}$가 있다$.$
   • 승인 또는 거부:
     • $[0,1]$에서 균일한 난수 $u{\displaystyle \in [}$ ${\displaystyle 0,}$ 1 ${\displaystyle ]}$ ${\displaystyle u\\in$ [0,1]}을(를) 생성하십시오$.$
     • $u{\displaystyle \alpha }$ ${\displaystyle u\leq \alpha$ $\}$인 경우 x t${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$= ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$을(를) 설정하여 후보자를 수락하십시오$.$
     • > ${\displaystyle u>\alpha }$인 경우 후보를 거부하고 ${\displaystyle {대신}_{}}$ $x{\displaystyle {}_{}}$ t${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$= ${\displaystyle x_{}}$ t ${\$를 설정하십시오$$.

이 알고리즘은 무작위로 샘플 공간을 이동하려고 시도하며, 때로는 이동을 수용하고 때로는 제자리에 유지함으로써 진행된다.합격률 $\alpha {\displaystyle }$ ${\displaystyle \alpha }$은(는) $밀도$가 P${\displaystyle }$( x${\displaystyle }$)$${\$displaystyle P$(x$)}$인 분포에 따라 현재 표본과 관련하여 새로 제안된 표본의 개연성이 어느$$ 정도인지 표시한다는 점에 유의하십시오$.$ 기존 지점보다 개연성이 높은 지점(즉, 더 높은 지점).> {\$displaystyle \alpha >1\geq$u}에$$ $해당$하는${\displaystyle }$y 영역$,$ 우리는 항상 이 이동을 수용한다.그러나 개연성이 낮은 지점으로 옮기려 하면 때로는 거부를 할 것이고 개연성의 상대적 하락이 클수록 새로운 지점은 거부를 할 가능성이 높다.따라서, 우리는 가끔 저밀도 지역을 방문하는 동안에만 $P{\displaystyle }$(${\displaystyle }$x $){\displaystyle$ P$(x)}$의 고밀도 지역에 머물며 많은 수의 표본을 반환하는 경향이 있을 것이다$.$직관적으로 이 알고리즘이 작용하고 밀도 $P{\displaystyle }$ (${\displaystyle x}$) ${\displaystyle P(x)}$을(를) 사용하여 원하는 분포를 따르는 표본을 반환하는 이유가 여기에 있다$.$

분포로부터 독립 샘플을 직접 생성하는 적응 거부 샘플링과^[7] 같은 알고리즘에 비해 Metropolitude-Hastings 및 기타 MCMC 알고리즘에는 다음과 같은 여러 단점이 있다.

• 그 샘플들은 상관관계가 있다.장기간에 걸쳐 $그들$은 ${\displaystyle P}$($$x${\displaystyle }$) {\$displaystyle P(x)}$을(를) 올바르게 따르지만$,$ 근처의 샘플 세트는 서로 상관관계가 있고 분포를 올바르게 반영하지 못할 것이다.이는 유효 시료 크기가 실제 채취한 시료 수보다 현저히 낮아져 오차가 클 수 있다는 것을 의미한다.
• 마르코프 체인은 결국 원하는 분포로 수렴되지만, 특히 시작점이 밀도가 낮은 지역에 있는 경우 초기 표본은 매우 다른 분포를 따를 수 있다.따라서 일반적으로 초기 샘플 수가 버려지는 연소 기간이 필요하다.^[8]

반면, 대부분의 간단한 거부 표본 추출 방법은 "차원의 수" 함수로서 거부 확률이 기하급수적으로 증가하는 "차원의 곡선"에 시달린다.Metropolitan-Hastings는 다른 MCMC 방법과 함께 이러한 문제를 가지고 있지 않기 때문에 표본 추출할 분포의 치수 수가 높을 때 사용할 수 있는 유일한 해결책이 되는 경우가 많다.결과적으로, MCMC 방법은 종종 많은 분야에서 오늘날 사용되는 계층적 베이지안 모델과 다른 고차원 통계 모델에서 샘플을 생산하기 위한 선택 방법이 된다.

다변량 분포에서 위에서 설명한 전형적인 메트로폴리스-해스팅 알고리즘은 새로운 다차원 샘플 포인트를 선택하는 것을 포함한다.치수의 수가 많을 때는 개별 치수의 동작이 매우 다르기 때문에 사용하기에 적합한 점프 분포를 찾기가 어려울 수 있으며, 점프 폭(위 참조)은 지나치게 느린 혼합을 피하기 위해 모든 치수에 대해 한 번에 "정확하게" 해야 한다.흔히 Gibbs 샘플링이라고 알려진 그러한 상황에서 더 잘 작동하는 대안적 접근법에는 모든 차원에 대해 한 번에 표본을 선택하는 것이 아니라 다른 차원과 별도로 각 차원에 대해 새로운 표본을 선택하는 것이 포함된다.그렇게 하면 잠재적으로 고차원적인 공간으로부터의 표본 추출 문제는 작은 차원성에서 표본을 추출할 수 있는 문제의 집합으로 줄어들 것이다.^[9]이것은 특히 다변량 분포가 대부분의 일반적인 계층적 모형에서와 같이, 각 변수가 소수의 다른 변수에 대해서만 조건화되는 개별 랜덤 변수 집합으로 구성된 경우에 적용된다.그런 다음 개별 변수를 한 번에 하나씩 표본으로 추출하고 각 변수는 다른 모든 변수의 가장 최근의 값으로 조건화한다.다변량 분포의 정확한 형태에 따라 다양한 알고리즘을 사용하여 이러한 개별 샘플을 선택할 수 있다. 적응 거부 샘플링 방법,^[7] 적응 거부 Metropolitanis 샘플링 알고리즘,^[10] 단순한 1차원 Metropolitan-Hastings 단계 또는 슬라이스 샘플링 등이 가능하다.

형식 파생

Metropolitan-Hastings 알고리즘의 목적은 원하는 ${\displaystyle \mathrm{분포}}$ P${\displaystyle }$( x${\displaystyle }$) ${\displaystyle P(x)}$에 따라 상태 컬렉션을 생성하는 것이다$.$ 이를 위해 알고리즘은 마르코프 프로세스를 사용하며, 마르코프 프로세스는 $\pi {\displaystyle }$( x${\displaystyle }$)${\displaystyle }$= P${\displaystyle }$(${\displaystyle x)}$와 같은 고유한 고정 분포 $\pi {\displaystyle }$(${\displaystyle x}$ ) ${\displaystysty \pi (x)$에 무증가 도달한다.${\displaystyle )}$ ${\displaystyle \pi(x)=P(x)}$^[11].

마르코프 프로세스는 그 전환 $확률{\displaystyle }$ $P{\displaystyle }$(${\displaystyle x{}^{}\prime }$x $){\displaystyle$ $P$$(x'\mid$ x$)\},$ 주어진 상태 x ${\displaystyle$ x$}$에서 다른 상태 $x{\displaystyle {}^{}}$ $′$ ${\$으)로$$ 전환될 확률에 의해 고유하게 정의된다$.$ 마르코프 프로세스는 $when$ ${\displaystyle (x}$) ${\displaystatyption statypi(x)$가 있다.e 다음 두 가지 조건이 충족된다.^[11]

1. 고정 분포의 존재: 고정 분포 ${\displaystyle \pi }$( x${\displaystyle }$) ${\displaystyle \pi (x)}$이(가) 있어야 한다$.$ 충분하지만 필요하지 않은 조건은 세부 균형이다. 이 조건은 각 $전환{\displaystyle }$x → ${\displaystyle {}^{}}$′$${\$displaystyle$ x$\to$ x$'}$이(가) 가역할 수 있어야 한다: $각{\displaystyle }$ 상태 x${\displaystyle }$, x ${\displaystyle {\prime }^{}}$ ${\$ x, x, x,$x$ 프로브ability of being in state ${\displaystyle x}$ and transitioning to state ${\displaystyle x'}$ must be equal to the probability of being in state ${\displaystyle x'}$ and transitioning to state ${\displaystyle x}$, ${\displaystyle \pi (x)P(x'\mid x)=\p$$i(x')P(x\mid$ x$\text{'})\}.$
2. 고정 분포의 고유성: 고정 분포 $\pi {\displaystyle }$( ${\displaystyle x}$) ${\displaystyle \pi (x)}$은(는) 고유해야 한다$$.이는 마르코프 프로세스의 에고다이컬리티에 의해 보장되며, 여기에는 (1) 모든 상태가 주기적이어야 하며, 시스템은 고정된 간격으로 동일한 상태로 되돌아가지 않아야 하며, (2) 양의 반복이어야 한다. 동일한 상태로 복귀하기 위한 예상 단계 수는 제한적이다.

Metropolitan-Hastings 알고리즘에는 위의 두 조건을 만족하는 Markov 프로세스 설계(전환 확률을 구성함)가 포함되며, 정지 분포 $\pi {\displaystyle }$ ${\displaystyle (}$${\displaystyle x}$$){\displaystyle \pi (x)}$가 $P{\displaystyle }$( x$){\displaystyle P(x)}$로 선택된다$.$알고리즘의 도출은 상세 균형상태로 시작한다.

${\displaystyle P(x'\mid x)P(x)=P(x\mid x')P(x'),}$

로 다시 쓰여진.

${\displaystyle {\p(x'\mid x)}{P(x\mid x')}}{\frac {P(x')}}}$

접근방식은 제안과 수용 거부라는 두 가지 하위 단계로 전환을 분리하는 것이다.제안 분포 $g{\displaystyle ({}^{}}$′ ${\displaystyle \mid }$ ${\displaystyle x}$) ${\displaystyle g$$($$x'\mid x)}$은 $x{\displaystyle }$ ${\displaystyle x}$을(를) $제안$할 조건부 확률이고, 합격 분포$$$$$x$ ${\displaystyle {\prime }^{}}$, ${\displaystyle x}$′ , x${\displaystyle }$) ${\displaystysty$ x $st$ {\\displayste$)$는 제안된 상태 $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$$x$를 수락 확률이다.$yle$ x$\text{'}\}.$전환 확률은 이들의 산물로 기록될 수 있다.

${\displaystyle P(x'\mid x)=g(x'\mid x)A(x',x)}$

이 관계를 이전 방정식에 삽입하면

${\displaystyle {\frac {A(x'),x}}{A(x,x')}}}}={\frac {P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}}}}}}.}$

파생의 다음 단계는 위의 조건을 충족하는 합격 비율을 선택하는 것이다.한 가지 일반적인 선택은 메트로폴리스의 선택이다.

${\displaystyle A(x',x)=\min \left(1,{\frac {P(x')}{P(x)(x)(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}}\오른쪽)).}$

이 Metroposition ratio $A{\displaystyle }$ ${\displaystyle A$${\displaystyle \}}$의$$${\displaystyle \mathrm{경우},}$ A$($ ${\displaystyle {\prime }^{}}$,${\displaystyle }$x ) = ${\displaystyle 1}$ ${\displaystyle$ A$(x')=1}$ $또는$ A(${\displaystyle {}^{},}$x ${\displaystyle {\prime }^{}}$)${\displaystyle }$= ${\displaystyle 1}$ ${\displaystystyle A(x')=1}$ 중$$ 어느 쪽이든 조건이 충족된다.

따라서 메트로폴리스-해스팅 알고리즘은 다음과 같이 작성할 수 있다.

1. 초기화하다
   1. ${\displaystyle {초기\mathrm{}}_{}}$ 상태 $x{\displaystyle {}_{}}$ 0 ${\$을 선택하십시오$.$
   2. $t{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle t=0}$을(를) 설정하십시오$.$
2. 반복하다
   1. $g{\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\displaystyle \mid }$ ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle g(x'\mid x_{t}})$에 따라$$ 임의 후보 상태 $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$을(를) 생성하십시오$.$
   2. Calculate the acceptance probability ${\displaystyle A(x',x_{t})=\min \left(1,{\frac {P(x')}{P(x_{t})}}{\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}\right)}$.
   3. 승인 또는 거부:
      1. 균일한 난수 $u{\displaystyle }$∈${\displaystyle }$[ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle u\in [0,1$
      2. $u{\displaystyle \le }$ ${\displaystyle A(}$ ${\displaystyle {}^{}}$′${\displaystyle }$, x ${\displaystyle t_{}}$) ${\displaystyle u\leq A(x',x_{t}}}$인 경우$,$ 새 상태를 수락하고 x ${\displaystyle t_{}}$+ ${\displaystyle 1_{}}$= ${\displaystyle {}^{}}$ t + 1 = x ${\displaystyle {\prime }^{}}$ ${\$
      3. > ( x , t) ${\displaystyle u>A(x',x_{t}}}$인 경우 새 상태를 거부하고 이전 상태 x ${\displaystyle t_{}}$+ ${\displaystyle 1_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\$을(를) 복사하십시오$.$
   4. 증분: $t{\displaystyle }$= ${\displaystyle t}$+ ${\displaystyle 1}$을 설정$(\backslash$$displaystyle t=t+1}.$

지정된 조건이 충족될 경우 ${\displaystyle {저장}_{}}$된 $상태$의 경험적 분포는 x ${\displaystyle {0\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, x T {\displaystyle $x_{0},\ldots ,x_{{}$$T}}$이$($ $P{\displaystyle }$( x ){\displaystyle $P(x)}$ 에 접근한다$.$$P{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle P(x)}$을(를) 효과적으로 추정하는 데 필요한 반복 횟수(${\displaystyle }$ ${\displaystyle T}$)는 ${\displaystyle P}$( x${\displaystyle }$) ${\displaystyle P(x)$와 제안 분포 및 원하는 추정 정확도를 포함한 요인 수에 따라 달라진다$$.^[12]이산 상태 공간의 분포는 마르코프 프로세스의 자기 상관 시간 순서가 되어야 한다.^[13]

일반적인 문제에서 어떤 분포 $(x$ ${\displaystyle {\prime }^{}}$ $x$)를 사용해야$$ 하는지$$또는 적절한 추정에 필요한 $반복 횟수$가 무엇인지 명확하지 않은 점에 유의해야 한다. 두 가지 모두 방법의 자유 매개변수로서, 당면한 특정 문제에 맞춰 조정해야 한다.

수치적 통합에 사용

메트로폴리스-해스팅 알고리즘의 일반적인 용도는 적분을 계산하는 것이다.Specifically, consider a space ${\displaystyle \Omega \subset \mathbb {R} }$ and a probability distribution ${\displaystyle P(x)}$ over ${\displaystyle \Omega }$, ${\displaystyle x\in \Omega }$. Metropolis–Hastings can estimate an integral of the form of

${\displaystyle P(E)=\int _{\Oomega }A(x)P(x)\,dx,}$

${\displaystyle \mathrm{여기}}$서 $A{\displaystyle }$( x${\displaystyle }$) ${\displaystyle A(x)}$은(측정 가능한) 관심 함수다$$.

예를 들어, ${\displaystyle \mathrm{통계}}$ $E{\displaystyle }$( x${\displaystyle }$) ${\displaystyle E(x)}$ 및 통계량 $분포{\displaystyle }$ P${\displaystyle }$( ${\displaystyle E}$) ${\displaystyle P(E)}$을(를) 고려하십시오$.$ 이 분포는 한계 분포입니다.$P{\displaystyle (E)}$ ${\displaystyle P(E)}$의 꼬리에 있는$$ $E{\displaystyle }$ ${\displaystyle E}$에 대한 $P{\displaystyle (E)}$ ${\displaystyle$ P$(E)}$을(를) 추정하는 것이 목표라고 가정합시다$.$ 정식으로 $P{\displaystyle (E)}$ ${\displaystystyle P(E)}$을(E)로 작성할 수 있다$$.

${\displaystyle P(E)=\int _{\Omega }P(E\mid x)P(x)\,dx=\int _{\Omega }\delta {\big (}E-E(x){\big )}P(x)\,dx=E{\big (}P(E\mid X){\big )}}$

and, thus, estimating ${\displaystyle P(E)}$ can be accomplished by estimating the expected value of the indicator function ${\displaystyle A_{E}(x)\equiv \mathbf {1} _{E}(x)}$, which is 1 when ${\displaystyle E(x)\in [E,E+\Delta E]}$ and zero otherwise.Because ${\displaystyle E}$ is on the tail of ${\displaystyle P(E)}$, the probability to draw a state ${\displaystyle x}$ with ${\displaystyle E(x)}$ on the tail of ${\displaystyle P(E)}$ is proportional to ${\displaystyle P(E)}$, which is small by definition.여기서 Metropolitan-Hastings 알고리즘을 사용하여 상태를 더 잘 샘플링(레이어)할 수 있으며, $따라서{\displaystyle }$ 꼬리에$$ P${\displaystyle (E}$ $){\displaystyle P($E)}를 추정하는 데 사용되는 샘플의 수를 늘릴 수 있다.예를 들어 샘플링 ${\displaystyle \mathrm{분포}}$ $\pi {\displaystyle }$( x${\displaystyle }$) ${\displaystyle \pi (x)}$을 사용하여$$ 해당 상태를 선호할 수 있다(${\displaystyle {예}^{}}$: $\pi {\displaystyle }$ ( ${\displaystyle x}$ ) e${\displaystyle )}$ ${\$ e$^{a$).$e$에 0이$($) ${\displaystyle a>0}$이(가) 표시됨.

단계별 지침

가장 최근에 샘플링된 값이 ${\displaystyle x_{}}$ t ${\$라고 가정해 봅시다$.$ Metropolitan-Hastings 알고리즘을 따르려면 다음에 $확률밀도{\displaystyle }$ g${\displaystyle (x_{}{\prime }^{}}$ ${\displaystyle {}_{}}$ t $){\displaystyle g(x'\mid x_{t})$를 가진$$ 새로운 제안 $상태{\displaystyle {}^{}}$ x$′{\$를 그려서$$ 값을 계산한다.

${\displaystyle a=a_{1}a_{2},}$

어디에

${\displaystyle a_{1}={\frac {P(x')}{P(x_{t})}}}$

제안된 샘플 $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ x$'}$과(와) 이전 샘플 $x{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\$ 사이의 확률(예: 베이지안 후방) 비율이며$,$

${\displaystyle a_{2}={\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}{g(x'\mid x_{t})}}}}$

제안 밀도의 $두{\displaystyle {}_{}}$ $($x t {\$displaystyle$ x_${t}$부터 $display$ {\$displaystyle$ x$'}$까지)의 비율이다.제안 밀도가 대칭인 경우 이는 1과 같다.그런 다음 다음 다음 규칙에 따라 새로운 ${\displaystyle {상태}_{}}$ $x{\displaystyle {}_{}}$ t${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$ ${\$를 선택한다$$.

${\displaystyle \ge }$ $1{\displaystyle }$: ${\$ 1${:$$}}$

${\displaystyle x_{t+1}=x',}$

기타:

${\displaystyle x_{t+1}={\displaystyle{case}x'&{\text{probability}a,\x_{t}&{\text}{probable{probility{1}-a.\end{case}}}$

마르코프 체인은 임의의 초기 값 $x{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$에서$$시작되며, 알고리즘은 이 초기 상태가 "잊혀질" 때까지 많은 반복에 대해 실행된다.버려지는 이 샘플들은 번인(burn-in)이라고 알려져 있다.$x{\displaystyle }$ ${\displaystyle x}$의 나머지 허용 값 집합은 $분포{\displaystyle }$ P${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle P(x)}$의 표본을 나타낸다$$$.$

The algorithm works best if the proposal density matches the shape of the target distribution ${\displaystyle P(x)}$, from which direct sampling is difficult, that is ${\displaystyle g(x'\mid x_{t})\approx P(x')}$. If a Gaussian proposal density ${\displaystyle g}$ is used, the variance 매개 변수 $\sigma {\displaystyle {}^{}}$ ${\$번 화상입력 기간 동안 튜닝해야 한다$$.이는 일반적으로 마지막 $N{\displaystyle }$ ${\displaystyle N}$ 샘플의$$ 창에서 수용되는 제안 샘플의 비율인 합격률을 계산하여 이루어진다.원하는 합격률은 목표 분포에 따라 다르지만 이론적으로는 1차원 가우스 분포의 이상적인 합격률이 약 50%이며, N ${\displaystyle N$} - 차원$$ 가우스 표적 분포의 경우 약 23%로 감소한다는 것이 밝혀졌다.^[14]이러한 지침은 번스타인-본 미세스 정리를 사용하여 설정할 수 있는 다변량 정규 분포를 따르는 경우가 많기 때문에 충분히 정규 베이시안 포스터에서 표본을 추출할 때 잘 작동할 수 있다.^[15]

$\sigma {\displaystyle {}^{}}$ ${\$개가 너무$$ 작으면 체인이 천천히 섞이게 된다(즉, 수용률은 높겠지만, 연속적인 샘플은 천천히 공간을 이동하게 되고 체인은 천천히 $P{\displaystyle }$(${\displaystyle x}$ ) ${\displaysty$ P$(x)}$에 수렴하게 된다).$$한편 $\sigma {\displaystyle {}^{}}$ ${\$}가 너무$$ 크면, 제안이 훨씬 낮은 확률밀도의 지역에 상륙할 가능성이 높기 때문에 수용률은 매우 낮을 것이므로 ${\displaystyle {1\mathrm{}}_{}}$ ${\$}는 매우 작을 것이고$$, 다시 체인점들은 매우 천천히 수렴할 것이다.하나는 일반적으로 앞의 단락에서 언급한 이론적 추정치에 따라 알고리즘이 전체 표본의 30%의 순서를 받아들이도록 제안 분포를 조정한다.

참고 항목

• 상세잔액
• 유전 알고리즘
• 깁스 샘플링
• 평균장 입자법
• 메트로폴리스 조정 랑게빈 알고리즘
• 메트로폴리스 광수송
• 멀티 트라이 메트로폴리스
• 평행 템퍼링
• 전제 조건 크랭크-니콜슨 알고리즘
• 순차 몬테카를로
• 시뮬레이션 어닐링

참조

메모들

추가 읽기

• 베른트 A. 버그. 마르코프 체인 몬테카를로 시뮬레이션과 그들의 통계 분석.싱가포르, 월드 사이언티픽, 2004.
• 싯다르타 치브와 에드워드 그린버그: "메트로폴리스-해스팅 알고리즘의 이해"미국 통계학자, 49(4), 327–335, 1995
• 데이비드 D. L. 민과 도 레민. "헤이스팅스 알고리즘의 이해."통계에서의 통신 - 시뮬레이션 및 연산, 44:2 332-349, 2015
• 볼스타드, 윌리엄 M. (2010) 컴퓨터 베이시안 통계 이해, 존 와일리 & 선스 ISBN 0-470-04609-0