멀티 트라이 메트로폴리스

MTM(Multiple-try Metropolitis, MTM)은 2000년 류, 량, 웡이 처음 제시한 메트로폴리스-해스팅 방식의 변형된 표본 추출법이다.스텝 사이즈와 합격률을 모두 높여 샘플링 궤적이 더 빨리 수렴할 수 있도록 설계됐다.

배경

메트로폴리스-헤이스팅스 문제

마르코프 체인 몬테카를로에서는 메트로폴리스-해스팅 알고리즘(MH)을 사용하여 직접 샘플링하기 어려운 확률 분포에서 샘플링할 수 있다.그러나 MH 알고리즘은 사용자가 제안서 배포를 제공하도록 요구하는데, 이는 비교적 임의적일 수 있다.In many cases, one uses a Gaussian distribution centered on the current point in the probability space, of the form ${\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};\sigma ^{2}I)\,}$. This proposal distribution is convenient to sample from and may be the best choice if one has little knowledge about the target distribution, ${\displaystyle \pi (x)\,}$. If desired, one can use the more general multivariate normal distribution, ${\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};\mathbf {\Sigma } )}$, where ${\displaystyle \mathbf {\Sigma } }$ is the covaria사용자가 목표 분포와 유사하다고 생각하는 NCE 매트릭스.

이 방법은 무한 표본 크기의 한계에서 고정 분포로 수렴해야 하지만, 실제로는 진행 속도가 매우 느릴 수 있다.$\sigma {\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ $displaystyle \sigma ^{2}\,}$이(가) 너무 크면 MH 알고리즘에 따른 거의 모든 단계가 거부된다.반면 $\sigma {\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ $displaystyle \sigma ^{2}\}}$이(가) 너무 작으면 거의 모든 단계가 받아들여지고, 마르코프 체인은 확률 공간을 무작위로 걷는 것과 비슷해진다.단순한 $Q{\displaystyle ({}^{};;}$ ${\displaystyle x^{}}$t${\displaystyle }$) = ${\displaystyle N(x^{}}$t ;${\displaystyle I}$ )의 경우, ${\$$I{\displaystyle }$$)\backslash ,\}\backslash ,\}$$우리$는 N {\$displaystyle$ N$\,}$의 $스텝$이 N $displaystyle${\$sqrt{N},}$의 거리만 데려다 준다는 것을 알 수 있다$.$ 이 경우, 마르코프 체인은 적당한 시간 내에 확률 공간을 완전히 탐구하지는 않을 것이다.따라서 MH 알고리즘은 스케일 ${\displaystyle {파라미터\mathrm{}}^{}}$( reasonable 2 $displaystyle \sigma ^{2}\,}$ 또는$$ $\sigma {\displaystyle \mathbf{}}$ ${\$의 적절한 조정이 필요하다.$$

차원성이 높은 문제

스케일 파라미터가 잘 조정되더라도 문제의 차원성이 증가함에 따라 진척은 여전히 지나치게 느리게 유지될 수 있다.이를 보려면 $Q{\displaystyle ({}^{}\prime ;}$ ${\displaystyle {}^{}}$ ${\displaystyle t^{}}$)${\displaystyle }$= ${\displaystyle N(x^{}}$ t${\displaystyle {}^{}}$; ${\displaystyle I}$) ${\$$I$ 한 차원에서는 평균이 0이고 분산이 1인 가우스 분포에 해당한다.한 차원에 대해 이 분포의 평균 단계는 0이지만 평균 제곱 단계 크기는 다음과 같다.

${\displaystyle \langle x^{2}\angle =\int _{-\\inflant }^{}}{{-\sqrt{2\pi }}e^{-{\x^{2}}=1}$

차원 수가 증가하면 예상 단계 크기는 점점 커진다.$N{\displaystyle }$ ${\$ 치수에서$$ 반경 거리 $r{\displaystyle }$ ${\$의 이동 확률은 Chi 분포와 관련이 있으며$$, 다음과 같이 지정된다.

${\displaystyle P_{n}(r)\propto r^{n-1}e^{-r^{2}/2}}$

이 분포는${\displaystyle r\sqrt{}}$ =${\displaystyle \sqrt{\mathrm{N}}}$$$- 1 {\$displaystyle$r$sqrt{N-1},$ 큰$$ $N{\displaystyle }$ {\sqrt${N$}, 큰 N {\$displaystyle N\,}$에 대해${\displaystyle }$n N ${\sqrt{N}\}$에서 정점을 이룬다$.$이것은 단계 크기가 치수 수의 대략 제곱근만큼 증가한다는 것을 의미한다.MH 알고리즘의 경우 대형 스텝은 거의 항상 확률이 낮은 지역에 착륙하므로 거부된다.

If we now add the scale parameter ${\displaystyle \sigma ^{2}\,}$ back in, we find that to retain a reasonable acceptance rate, we must make the transformation ${\displaystyle \sigma ^{2}\rightarrow \sigma ^{2}/N}$. In this situation, the acceptance rate can now be made reasonable, but the exploration of확률 공간이 점점 더 느려진다.이를 확인하려면 문제의 한 측면을 따라 슬라이스를 생각해 보십시오.위의 척도 변환을 통해 예상되는 단계 크기는 어느 한 차원이라도 $\sigma {\displaystyle }$ ${\$이 아니라$$ ${\displaystyle \sigma \sqrt{}}$/ N ${\$ 이 단계 크기는 확률 분포의 "진정한" 척도보다 훨씬 작기 때문에$({\$ \$sigma$\sigma \sigma$$ $\}).$알고리즘은 모든 매개변수를 따라 무작위 보행을 실행한다.

다중 시도 메트로폴리스 알고리즘

$Q{\displaystyle }$( ${\displaystyle x\mathbf{}}$, ${\displaystyle y\mathbf{}}$) ${\displaystyle Q(\mathbf {x},\mathbf {y})$가 임의 제안 함수라고 가정합시다.We require that ${\displaystyle Q(\mathbf {x} ,\mathbf {y} )>0}$ only if ${\displaystyle Q(\mathbf {y} ,\mathbf {x} )>0}$. Additionally, ${\displaystyle \pi (\mathbf {x} )}$ is the likelihood function.

Define ${\displaystyle w(\mathbf {x} ,\mathbf {y} )=\pi (\mathbf {x} )Q(\mathbf {x} ,\mathbf {y} )\lambda (\mathbf {x} ,\mathbf {y} )}$ where ${\displaystyle \lambda (\mathbf {x} ,\mathbf {y} )}$ is a non-negative symmetric function in ${\displaystyle \$사용자가$$ 선택할 수 있는 $mathbf {x}$ 및 $y$ ${\$

현재 상태가 $x{\displaystyle \mathbf{}}$ ${\$이라고 가정합시다$.$ MTM 알고리즘은 다음과 같다.

1) Draw k independent trial proposals ${\displaystyle \mathbf {y} _{1},\ldots ,\mathbf {y} _{k}}$ from ${\displaystyle Q(\mathbf {x} ,.)}$. Compute the weights ${\displaystyle w(\mathbf {y} _{j},\mathbf {x} )}$ for each of these.

2) 가중치에 비례하는 확률로$$ $y{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ ${\$에서 y ${\$을(를) 선택하십시오.

3) Now produce a reference set by drawing ${\displaystyle \mathbf {x} _{1},\ldots ,\mathbf {x} _{k-1}}$ from the distribution ${\displaystyle Q(\mathbf {y} ,.)}$. Set ${\displaystyle \mathbf {x} _{k}=\mathbf {x} }$ (the current point).

4) 확률로$$ $y{\displaystyle \mathbf{}}$ ${\$ 수용

${\displaystyle r={\text{min}}\left(1,{\frac {w(\mathbf {y} _{1},\mathbf {x} )+\ldots +w(\mathbf {y} _{k},\mathbf {x} )}{w(\mathbf {x} _{1},\mathbf {y} )+\ldots +w(\mathbf {x} _{k},\mathbf {y} )}}\right)}$

이 방법은 상세 균형 특성을 만족하고 따라서 $\pi {\displaystyle }$( ${\displaystyle x\mathbf{}}$) ${\displaystyle \pi (\mathbf {x})}$을(를) 고정 분포로$$ 하여 가역형 마르코프 체인을 생성함을 보여줄 수 있다.

If ${\displaystyle Q(\mathbf {x} ,\mathbf {y} )}$ is symmetric (as is the case for the multivariate normal distribution), then one can choose ${\displaystyle \lambda (\mathbf {x} ,\mathbf {y} )={\frac {1}{Q(\mathbf {x} ,\mathbf {y} )}}}$ which gives ${\displaystyle w(\mathbf{x},\mathbf{y})=\pi (\mathbf{x}}$${\displaystyle )}$ ${\displaystyle w(\mathbf {x},\mathbf {y} )=\pi(\mathbf {x}$ $)\}.$

단점들

다중 시도 메트로폴리스에서는 매 단계마다 ${\displaystyle \mathrm{2k}}$- 1$${\${\displaystyle \mathrm{디스플레이}}$ $스타일 2k-1$}개의$$다른 상태의 에너지를 계산해야 한다.프로세스의 느린 부분이 에너지를 계산하는 것이라면 이 방법은 더 느릴 수 있다.프로세스의 느린 부분이 주어진 점의 인접점을 찾거나 임의의 숫자를 생성하는 것이라면, 이 방법은 더 느릴 수 있다.이 방법은 메트로폴리스-헤이스팅스보다 훨씬 더 많은 연산을 "단일화"에 투입하기 때문에 더 빨리 나타날 뿐이라고 주장할 수 있다.

참고 항목

• 마르코프 체인 몬테카를로
• 메트로폴리스-헤이스팅스 알고리즘
• 상세잔액

참조

• 류, J, 량, F, W. H. (2000)미국통계협회지, 95(449): 121–134 JSTOR 표본 추출의 다중 시도 방법과 국소 최적화