Metropolis–Hastings法

同義語:Metropolis–Hastings algorithm

概要

Metropolis–Hastings法(Metropolis–Hastings algorithm)とは、正規化の定数が分からない密度 $p\propto\tilde p$ の分布 $\pi$ について、現在の状態 $x$ から提案の密度 $q(x,\cdot)$ で候補 $y$ を引き、確率 $\min\bigl(1,\frac{p(y)q(y,x)}{p(x)q(x,y)}\bigr)$ で受理し、そうでなければ $x$ にとどまる Markov 連鎖を作る方法で、事後分布の計算に使う。$\pi$ は提案によらず定常分布になり、連鎖が既約で非周期的なら、$\pi$ についてほとんどすべての出発点から分布は $\pi$ に収束する。提案が状態によらない独立型ですべての点で $p\le Mg$ なら、全変動距離は出発点によらず $(1-1/M)^n$ 以下である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Markov連鎖, Markov連鎖モンテカルロ法, 確率密度関数, 符号付き測度

Bayes 統計では、パラメータ $\theta\in\mathbb R^d$ の事後分布の密度が、尤度と事前分布の積 $\tilde p(\theta)=L(\text{データ}\mid\theta)\,\pi_0(\theta)$ に比例する形で与えられる。$\tilde p$ の値は各点で計算できるが、正規化の定数 $Z=\int\tilde p(\theta)\,d\theta$ は $d$ 次元の積分で、$d$ が大きいと計算できない。それでも事後平均 $\int h\,\tilde p\,d\theta/Z$ を求めたい。
Metropolis–Hastings法(Metropolis–Hastings algorithm)は、候補を 1 つ提案し、比 $\tilde p(y)/\tilde p(x)$ と提案の密度だけで決まる確率で受け入れるか退けるかを決めることで、目標の分布 $\pi$ を定常分布にもつ Markov 連鎖を作る方法である。$Z$ は比の中で約分されて現れない。連鎖を走らせて時間平均をとれば、Markov連鎖モンテカルロ法 として期待値を見積もれる。
状態が有限個の場合の定義・詳細釣り合い・収束の証明は Markov連鎖モンテカルロ法 にある。この記事では、状態が $\mathbb R^d$ のような一般の空間で $\pi$ が密度で与えられる場合を扱い、次を示す。

  • 提案の密度がどんなものでも、Metropolis–Hastings 法の推移核は $\pi$ について可逆で、$\pi$ は定常分布である(thm-mh-reversible)。
  • 提案が現在の状態によらない 独立型 では、$\pi$ の密度が提案の密度の $M$ 倍以下なら、どこから出発しても $n$ 歩後の分布と $\pi$ の全変動距離は $(1-1/M)^n$ 以下である(thm-mh-independence)。逆に密度の比が非有界なら、この形の一様な評価は成り立たない(prop-mh-unbounded)。
  • 1 次元の正規分布を目標にした酔歩型の提案では、平均の受理確率が $\frac2\pi\arctan\frac2\sigma$ になる(ex-mh-gauss)。

定義と使える条件

$(E,\mathcal E)$ を可測空間、$\lambda$ をその上の $\sigma$ 有限な測度とする($E=\mathbb R^d$ と Lebesgue 測度、$E$ が可算集合と数え上げ測度が典型)。目標の分布 $\pi$ は $\lambda$ に関する確率密度 $p$ をもち、$p=\tilde p/Z$、$Z=\int\tilde p\,d\lambda\in(0,\infty)$ とする。
$E$ 上の 推移核(Markov 核)とは、写像 $P\colon E\times\mathcal E\to[0,1]$ で、各 $x$ について $P(x,\cdot)$ が確率測度、各 $A$ について $x\mapsto P(x,A)$ が可測であるものをいう。$P(x,A)$ は「状態 $x$ から 1 歩で $A$ に入る確率」である。分布 $\mu$ から 1 歩進んだ分布は $(\mu P)(A)=\int\mu(dx)\,P(x,A)$、$n$ 歩の推移核は $P^n$ で、$\pi P=\pi$ のとき $\pi$ を $P$ の 定常分布 という。

可逆性

推移核 $P$ が確率分布 $\pi$ について 可逆(または 詳細釣り合い を満たす)とは、すべての $A,B\in\mathcal E$ について
$$ \int_A\pi(dx)\,P(x,B)=\int_B\pi(dx)\,P(x,A) $$
が成り立つことをいう。$E\times E$ 上の測度として $\pi(dx)P(x,dy)=\pi(dy)P(y,dx)$ と書く。

$B=E$ とおくと $\int_A\pi(dx)P(x,E)=\pi(A)$ なので、可逆なら $\pi(A)=\int_E\pi(dx)P(x,A)=(\pi P)(A)$ であり、$\pi$ は定常分布である。

Metropolis–Hastings 法

$q\colon E\times E\to[0,\infty)$ を可測関数で、各 $x$ について $\int q(x,y)\,\lambda(dy)=1$ を満たすものとする(提案の密度、$Q(x,dy)=q(x,y)\lambda(dy)$ を 提案の核 という)。
$$ \alpha(x,y):=\begin{cases}\min\Bigl(1,\ \dfrac{p(y)\,q(y,x)}{p(x)\,q(x,y)}\Bigr)&(p(x)q(x,y)>0),\\[2mm] 1&(p(x)q(x,y)=0)\end{cases} $$
を 受理確率 とし、$r(x):=1-\int q(x,y)\alpha(x,y)\,\lambda(dy)$ とおいて、推移核を
$$ P(x,A):=\int_Aq(x,y)\,\alpha(x,y)\,\lambda(dy)+r(x)\,\mathbf 1_A(x) $$
で定める。この $P$ の Markov 連鎖を作ることを Metropolis–Hastings 法 という。

1 歩の進め方は次のとおりである。現在の状態 $x$ から $Q(x,\cdot)$ に従って候補 $y$ を引き、$[0,1]$ の一様乱数 $U$ を独立に引いて、$U\le\alpha(x,y)$ なら $y$ に移る(受理)。そうでなければ $x$ にとどまる(棄却)。$r(x)$ は棄却の確率で、$P(x,\cdot)$ は $x$ に重さ $r(x)$ の原子をもつ。$\alpha$ の中の $p(y)/p(x)$ は $\tilde p(y)/\tilde p(x)$ に等しいので、$Z$ は要らない。$p(x)=0$ の点で $\alpha=1$ とする規約は RR04 §2.1(p. 23)による。
使える条件は次のとおりである。

  1. 目標が密度をもつ:$\pi$ は $\lambda$ に関する密度 $p$ をもち、各点で $\tilde p(x)$ が計算できる。
  2. 提案から引ける:各 $x$ で $Q(x,\cdot)$ から候補を引け、$q(x,y)$ と $q(y,x)$ の比が計算できる(対称な提案なら比は $1$)。
  3. 連鎖が全体を行き来できる:収束(thm-mh-convergence)には連鎖が $\varphi$ 既約で非周期的であることが要る(反例の表の 3 行目)。
  4. 独立型の一様な収束(thm-mh-independence)には、密度の比 $p/g$ が有界であることが要る(反例の表の 2 行目)。

公式の表

方法提案の密度 $q(x,y)$受理確率 $\alpha(x,y)$条件根拠
一般の Metropolis–Hastings 法任意$\min\Bigl(1,\frac{p(y)q(y,x)}{p(x)q(x,y)}\Bigr)$条件 1・2thm-mh-reversible
Metropolis 法(対称な提案)$q(x,y)=q(y,x)$$\min\bigl(1,\frac{p(y)}{p(x)}\bigr)$同上thm-mh-reversible
酔歩型$g(y-x)$、$g(-z)=g(z)$$\min\bigl(1,\frac{p(y)}{p(x)}\bigr)$$E=\mathbb R^d$thm-mh-reversible
独立型$g(y)$$\min\bigl(1,\frac{w(y)}{w(x)}\bigr)$、$w=p/g$$g>0$ の点でthm-mh-reversible
Langevin 型(MALA)$N\bigl(x+\frac h2\nabla\log p(x),\,hI\bigr)$ の密度一般の式に $q$ を代入$p>0$ で微分可能thm-mh-reversible
Gibbs サンプリングの 1 成分の更新条件付き分布$1$直積の空間Gibbsサンプリング
独立型の全変動距離$g(y)$—すべての $y$ で $p(y)\le Mg(y)$thm-mh-independence:$(1-1/M)^n$ 以下
正規分布を目標にした酔歩型の平均受理確率$N(x,\sigma^2)$—$\pi=N(0,1)$ex-mh-gauss:$\frac2\pi\arctan\frac2\sigma$

独立型では $q(y,x)/q(x,y)=g(x)/g(y)$ なので、$\frac{p(y)g(x)}{p(x)g(y)}=\frac{w(y)}{w(x)}$ である。Langevin 型は、勾配の方向へ少し動かした点を中心に正規分布で提案するもので、提案が対称でないから $q(y,x)/q(x,y)$ の補正が要る(RR04 §2.1、p. 24)。

主定理と証明

Metropolis–Hastings 法の可逆性

def-mh-def の $P$ は $E$ 上の推移核であり、$\pi$ について可逆である。とくに $\pi$ は $P$ の定常分布である。

推移核であること。 $\alpha$ は可測関数を組み合わせたもので可測、$0\le\alpha\le1$ である。$q(x,y)\alpha(x,y)\le q(x,y)$ なので $0\le\int q\alpha\,d\lambda\le1$、よって $0\le r(x)\le1$ である。$\lambda$ が $\sigma$ 有限なので Tonelli の定理により $x\mapsto\int_Aq(x,y)\alpha(x,y)\lambda(dy)$ は可測で、$r$ も可測である。$P(x,\cdot)$ は測度で、$P(x,E)=\int q\alpha\,d\lambda+r(x)=1$ である。
可逆性。 関数
$$ k(x,y):=\min\bigl(p(x)q(x,y),\ p(y)q(y,x)\bigr) $$
は $x$ と $y$ について対称である。すべての $x,y$ で
$$ p(x)\,q(x,y)\,\alpha(x,y)=k(x,y)\qquad(1) $$
となることを示す。$p(x)q(x,y)>0$ なら、$\alpha$ の定義の $\min$ の中に $p(x)q(x,y)$ を掛けて (1) を得る。$p(x)q(x,y)=0$ なら、左辺は $0$ で、右辺も $\min(0,\ p(y)q(y,x))=0$ である。
$A,B\in\mathcal E$ をとる。$P$ の定義と (1) から
$$ \int_A\pi(dx)\,P(x,B)=\iint_{A\times B}k(x,y)\,\lambda(dx)\lambda(dy)+\int_{A\cap B}p(x)\,r(x)\,\lambda(dx) $$
である。右辺の第 2 項は $A$ と $B$ について対称である。第 1 項は、Tonelli の定理で積分の順序を入れかえ、$k$ の対称性を使うと $\iint_{B\times A}k\,d\lambda\,d\lambda$ に等しい。よって $\int_A\pi(dx)P(x,B)=\int_B\pi(dx)P(x,A)$ であり、$P$ は $\pi$ について可逆である。最後の主張は def-mh-reversible の直後の注意による。$\square$

証明は棄却の項 $r(x)\mathbf 1_A(x)$ を対角線の上の測度として別に扱い、移る部分では (1) の対称性だけを使う。提案の核 $Q$ はどんなものでもよい。ただし $\pi$ が定常であることは、連鎖が $\pi$ に近づくことを意味しない。提案が目標の支えの一部しか行き来しなければ、連鎖は出発点の近くに閉じ込められる(反例の表の 3 行目)。

収束

一般の状態空間での収束には、有限の場合の既約性と周期の概念を次のように言いかえる。推移核 $P$ が $\varphi$ 既約 とは、$E$ 上の $0$ でない $\sigma$ 有限な測度 $\varphi$ があって、$\varphi(A)>0$ となるどの $A$ とどの $x$ についても $P^n(x,A)>0$ となる $n\ge1$ があることをいう。定常分布 $\pi$ をもつ $P$ が 非周期的 とは、$d\ge2$ 個の互いに素な集合 $E_1,\dots,E_d$ で $\pi(E_1)>0$ かつ $x\in E_i$ なら $P(x,E_{i+1})=1$($E_{d+1}:=E_1$)となるものがないことをいう(RR04 pp. 31–32)。確率分布 $\mu,\nu$ の 全変動距離 を $\|\mu-\nu\|_{\mathrm{TV}}:=\sup_{A\in\mathcal E}\lvert\mu(A)-\nu(A)\rvert$ とする(混合時間 と同じ規約。この 2 倍で定める文献もある)。

一般の状態空間での収束

$\mathcal E$ が可算生成であり、推移核 $P$ が $\varphi$ 既約で非周期的、$\pi$ を定常分布にもつとする。このとき $\pi$ についてほとんどすべての $x$ で $\lim_{n\to\infty}\|P^n(x,\cdot)-\pi\|_{\mathrm{TV}}=0$ である。さらに $\int\lvert h\rvert\,d\pi< \infty$ なら、$\pi$ についてほとんどすべての出発点 $x$ から、大数の強法則 $\frac1n\sum_{i=1}^nh(X_i)\to\int h\,d\pi$(確率 $1$)も成り立つ。

所在

この記事では証明しない。前半は RR04 Theorem 4(p. 32、証明は §4.6)、後半は同 Fact 5(p. 32。Meyn–Tweedie の本の Theorem 17.0.1 として引かれている)である。$E=\mathbb R^d$ で、提案の密度 $q$ が $\mathbb R^d\times\mathbb R^d$ で正かつ連続、$\tilde p$ が至る所で有限なら、Metropolis–Hastings 法の連鎖は($\pi$ を $\varphi$ として)$\varphi$ 既約で非周期的であることが、同 pp. 31–32 で示されている。したがって正規分布の酔歩型の提案はこの定理の仮定を満たす。

独立型の一様な収束

thm-mh-convergence は収束の速さについて何も言わない。提案が現在の状態によらない独立型では、目標の密度が提案の密度で上から抑えられれば、出発点によらない指数的な評価が得られる。

独立型の一様な収束

$g$ を $\lambda$ に関する確率密度とし、提案の密度を $q(x,y)=g(y)$ とする。定数 $M$ があって、すべての $y\in E$ で $p(y)\le M\,g(y)$ が成り立つとする。このとき $M\ge1$ であり、すべての $x\in E$ と $n\ge1$ について
$$ \|P^n(x,\cdot)-\pi\|_{\mathrm{TV}}\le\Bigl(1-\frac1M\Bigr)^n $$
である。

$p\le Mg$ を $E$ で積分すると $1\le M$ である。$\varepsilon:=1/M\in(0,1]$ とおく。
段 1(下からの評価)。 すべての $x,y$ で $g(y)\alpha(x,y)\ge\varepsilon\,p(y)$ を示す。$p(x)g(y)=0$ のときは $\alpha=1$ で、$g(y)\ge\varepsilon p(y)$ は仮定そのものである。$p(x)g(y)>0$ のときは
$$ g(y)\,\alpha(x,y)=\min\Bigl(g(y),\ \frac{p(y)\,g(x)}{p(x)}\Bigr) $$
であり、$g(y)\ge\varepsilon p(y)$ と、$x$ での仮定 $g(x)\ge\varepsilon p(x)$ から $p(y)g(x)/p(x)\ge\varepsilon p(y)$ が出るので、どちらも $\varepsilon p(y)$ 以上である。したがってすべての $x$ と $A$ について
$$ P(x,A)\ge\int_Ag(y)\,\alpha(x,y)\,\lambda(dy)\ge\varepsilon\,\pi(A).\qquad(2) $$
段 2(分解)。 $\varepsilon=1$ なら、(2) と $P(x,E)=\pi(E)=1$ から $P(x,A)=\pi(A)$($A$ の補集合にも (2) を当てる)で、$n\ge1$ で左辺は $0$ である。$\varepsilon< 1$ とし、$R(x,A):=\bigl(P(x,A)-\varepsilon\pi(A)\bigr)/(1-\varepsilon)$ とおく。(2) から $R(x,A)\ge0$ で、$R(x,E)=1$ なので $R$ は推移核であり、$P=\varepsilon\pi+(1-\varepsilon)R$ と書ける($\pi$ は $x$ によらない推移核とみる)。
段 3(全変動の縮小)。 $\nu$ を $\nu(E)=0$ の有限な 符号付き測度 とする。$\nu=\nu^+-\nu^-$ を Jordan 分解(Hahnの分解定理)とすると $\nu^+(E)=\nu^-(E)=:c$ で、どの $A$ でも $-c\le-\nu^-(A)\le\nu(A)\le\nu^+(A)\le c$、正の集合 $A$ で $\nu(A)=c$ なので $\sup_A\lvert\nu(A)\rvert=c$ である。$\nu R:=\nu^+R-\nu^-R$ について、同様に $-c\le-\nu^-R(A)\le\nu R(A)\le\nu^+R(A)\le\nu^+R(E)=c$ なので
$$ \sup_A\lvert\nu R(A)\rvert\le\sup_A\lvert\nu(A)\rvert\qquad(3) $$
である。また $\nu\pi$($\pi$ を推移核とみた作用)は $\nu(E)\pi=0$ だから、$\nu P=(1-\varepsilon)\,\nu R$ である。
段 4(反復)。 $\nu_n:=P^n(x,\cdot)-\pi$ とおく。$\pi$ は定常(thm-mh-reversible)なので $\nu_{n}=P^{n-1}(x,\cdot)P-\pi P=\nu_{n-1}P$ であり、$\nu_{n-1}(E)=0$ だから段 3 と (3) により
$$ \|\nu_n\|_{\mathrm{TV}}=\sup_A\lvert(1-\varepsilon)\,\nu_{n-1}R(A)\rvert\le(1-\varepsilon)\,\|\nu_{n-1}\|_{\mathrm{TV}} $$
である。$\nu_0=\delta_x-\pi$ で $\|\nu_0\|_{\mathrm{TV}}\le1$ なので、帰納法で $\|\nu_n\|_{\mathrm{TV}}\le(1-\varepsilon)^n$ を得る。$\square$

この証明は、1 歩の推移が出発点によらず $\pi$ の $\varepsilon$ 倍を共通に含むこと(小さい集合 の条件を状態空間全体で満たすこと)だけを使っている。一般の推移核について同じ条件 $P^{n_0}(x,\cdot)\ge\varepsilon\nu(\cdot)$ から $\|P^n(x,\cdot)-\pi\|_{\mathrm{TV}}\le(1-\varepsilon)^{\lfloor n/n_0\rfloor}$ が従うことは RR04 Theorem 8(p. 36)にあり、この定理はその $n_0=1$、$\nu=\pi$ の場合である。
密度の比が非有界なら、この形の評価は成り立たない。$w:=p/g$($g(y)=0< p(y)$ の点では $w(y)=\infty$)とおく。

密度の比が非有界な独立型

thm-mh-independence の設定で、$p\le Mg$ の仮定の代わりに $\sup_{x\in E}w(x)=\infty$ とし、さらに $\pi$ が原子をもたない(すべての $x$ で $\pi(\{x\})=0$)とする。このとき各 $n\ge1$ で $\sup_{x\in E}\|P^n(x,\cdot)-\pi\|_{\mathrm{TV}}=1$ である。

$p(x)>0$ の点 $x$ をとる。$g(y)>0$ なら $\alpha(x,y)\le w(y)/w(x)$ なので $g(y)\alpha(x,y)\le p(y)/w(x)$ であり、$g(y)=0$ なら左辺は $0$ である。$w(x)=\infty$、すなわち $g(x)=0$ のときは、$g(y)>0$ なら $\alpha(x,y)=\min\bigl(1,\,p(y)g(x)/(p(x)g(y))\bigr)=0$ なので、$1/w(x)=0$ と読めば同じ不等式が成り立つ。積分して $\int g\alpha\,d\lambda\le1/w(x)$、すなわち棄却の確率は $r(x)\ge1-1/w(x)$ である。連鎖が $n$ 歩とも棄却を続ければ $x$ にとどまるので $P^n(x,\{x\})\ge r(x)^n$ であり、
$$ \|P^n(x,\cdot)-\pi\|_{\mathrm{TV}}\ge P^n(x,\{x\})-\pi(\{x\})\ge\Bigl(1-\frac1{w(x)}\Bigr)^n $$
である。$w(x)\to\infty$ となる点の列をとれば右辺は $1$ に近づき、左辺はつねに $1$ 以下である。$\square$

$\sup w=\infty$ の点は $p(x)>0$ をみたすので、証明の $x$ はそこからとれる。この命題は、thm-mh-independence の仮定 $p\le Mg$ を外すと結論の「出発点によらない指数的な評価」が崩れることを示している。直観的には、提案がめったに出さない領域($g$ が $p$ に比べて小さい領域)に連鎖が入ると、そこから出る候補がほとんど棄却され、連鎖が長く動かなくなる。

計算の手順

Metropolis–Hastings 法で $\int h\,d\pi$ を見積もる手順は次のとおりである。

  1. 目標を定数倍を除いた形 $\tilde p$ で書き、$\log\tilde p$ を計算する関数を用意する。支えの外では $\log\tilde p=-\infty$ とする。
  2. 提案を選ぶ。酔歩型 $y=x+\sigma\xi$($\xi$ は標準正規分布)が基本である。独立型を使うなら、$p/g$ が有界になるよう、$g$ の裾を $p$ より重くする(thm-mh-independence)。対称でない提案では $\log q(y,x)-\log q(x,y)$ を計算できるようにする。
  3. 初期値 $X_0$ を $\tilde p(X_0)>0$ となるようにとり、$k=0,1,2,\dots$ について繰り返す:候補 $y$ を引き、$\ell:=\log\tilde p(y)-\log\tilde p(X_k)+\log q(y,X_k)-\log q(X_k,y)$ を計算し、一様乱数 $U$ を引いて $\log U\le\ell$ なら $X_{k+1}:=y$、そうでなければ $X_{k+1}:=X_k$ とする。
  4. 最初の $b$ 歩を捨て、$\frac1n\sum_{k=b}^{b+n-1}h(X_k)$ を見積もりとする。
  5. 受理の割合を見る。酔歩型では、$\sigma$ が小さすぎると受理の割合は $1$ に近いが 1 歩の移動が小さく、大きすぎるとほとんど棄却される(ex-mh-gauss と図)。複数の初期値から走らせた連鎖が同じ値に近づくかも確かめる。
    比を対数で計算するのは、$\tilde p$ が尤度の積で非常に小さい値や大きい値になり、そのまま計算すると桁があふれるからである。$\log U\le\ell$ は $U\le\min(1,e^\ell)$ と同じ判定である。

例題

正規分布を目標にした酔歩型の受理確率

目標を $\pi=N(0,1)$、提案を $y=x+\sigma\xi$($\xi\sim N(0,1)$、すなわち $q(x,y)$ は $N(x,\sigma^2)$ の密度)とする。連鎖が定常にあるとき($X\sim\pi$)の平均の受理確率 $A(\sigma):=\iint\pi(dx)\,q(x,y)\,\alpha(x,y)\,dy$ を求める。
使う公式:def-mh-def(Metropolis 法)、(1) の $k$。
答え:$A(\sigma)=\dfrac2\pi\arctan\dfrac2\sigma$。$\sigma=1$ で $\approx0.704833$、$\sigma=2$ で $0.5$、$\sigma=2.38$ で $\approx0.444906$、$\sigma=5$ で $\approx0.242238$。$\sigma\to0$ で $1$、$\sigma\to\infty$ で $0$ に近づく。

導出を開く

$\varphi$ を標準正規分布の密度、$\varphi_\sigma$ を $N(0,\sigma^2)$ の密度とすると、(1) から $A(\sigma)=\iint\min(\varphi(x),\varphi(y))\,\varphi_\sigma(y-x)\,dx\,dy$ である。被積分関数は $x$ と $y$ の入れかえで不変で、$\lvert x\rvert=\lvert y\rvert$ の集合は測度 $0$ なので、$A(\sigma)=2\iint_{\lvert y\rvert>\lvert x\rvert}\varphi(y)\varphi_\sigma(x-y)\,dx\,dy$ である(この領域では $\min$ は $\varphi(y)$)。これは $Y\sim N(0,1)$ と独立な $Z\sim N(0,1)$ で $X=Y+\sigma Z$ としたときの $2P(\lvert X\rvert< \lvert Y\rvert)$ に等しい。$X^2< Y^2$ は $U:=\sigma Z$ と $V:=2Y+\sigma Z$ について $UV< 0$ と同値で、$(U,V)$ は平均 $0$ の 2 次元正規分布、分散 $\sigma^2$ と $4+\sigma^2$、共分散 $\sigma^2$、相関係数 $\rho=\sigma/\sqrt{4+\sigma^2}$ である。

相関係数 $\rho$ の平均 $0$ の 2 次元正規分布では $P(UV< 0)=\frac1\pi\arccos\rho$ である。実際、独立な標準正規 $G_1,G_2$ で $U=aG_1$、$V=b(\rho G_1+\sqrt{1-\rho^2}G_2)$($a,b>0$)と書け、$(G_1,G_2)=(R\cos\Theta,R\sin\Theta)$ で $\Theta$ は $[0,2\pi)$ の一様分布、$\beta:=\arccos\rho\in[0,\pi]$ とすると $UV$ の符号は $\cos\Theta\cos(\Theta-\beta)$ の符号に等しい。二つの余弦の符号が異なる $\Theta$ の集合は長さ $2\beta$ なので、確率は $\beta/\pi$ である。

よって $A(\sigma)=\frac2\pi\arccos\frac\sigma{\sqrt{4+\sigma^2}}$。余弦が $\sigma/\sqrt{4+\sigma^2}$ の角の正接は $2/\sigma$ なので $A(\sigma)=\frac2\pi\arctan\frac2\sigma$ である。

図: 標準正規分布を目標にし、提案を N(x, σ^2) とした酔歩型の Metropolis 法の、定常での平均の受理確率。横軸は提案の標準偏差 σ(0.05 から 8)、縦軸は受理確率。実線は (2/π) arctan(2/σ)、黒い点は σ ごとに 10^5 組の Monte Carlo の推定で、実線とよく一致する。σ=2 で 0.5、σ=2.38 で約 0.445、σ=8 で約 0.156。 図: 標準正規分布を目標にし、提案を N(x, σ^2) とした酔歩型の Metropolis 法の、定常での平均の受理確率。横軸は提案の標準偏差 σ(0.05 から 8)、縦軸は受理確率。実線は (2/π) arctan(2/σ)、黒い点は σ ごとに 10^5 組の Monte Carlo の推定で、実線とよく一致する。σ=2 で 0.5、σ=2.38 で約 0.445、σ=8 で約 0.156。

二項モデルの事後分布

表の出る確率 $\theta$ の硬貨を 10 回投げて表が 3 回出た。事前分布を $(0,1)$ の一様分布とすると、事後分布の密度は $\tilde p(\theta)=\theta^3(1-\theta)^7$($0< \theta< 1$、それ以外は $0$)に比例する。提案を $y=x+\eta$($\eta$ は $(-0.2,0.2)$ の一様分布)とする。
使う公式:def-mh-def(Metropolis 法)。
答え:$\alpha(0.3,0.4)=\bigl(\frac43\bigr)^3\bigl(\frac67\bigr)^7\approx0.805728$、$\alpha(0.3,0.2)=\bigl(\frac23\bigr)^3\bigl(\frac87\bigr)^7\approx0.754518$、$\alpha(0.1,-0.05)=0$(支えの外の候補は必ず棄却)。定常での平均の受理確率は約 $0.7177$(数値積分による値)。$X_0=0.5$ から乱数で走らせ、最初の $1000$ 歩を捨てて $10^5$ 歩の平均をとった 1 回の実行では、平均は約 $0.3339$(事後平均の正確な値は $\frac4{12}=\frac13$)、受理の割合は約 $0.719$ であった。

補足を開く

提案は対称なので受理確率は $\min(1,\tilde p(y)/\tilde p(x))$ で、比 $\frac{\tilde p(0.4)}{\tilde p(0.3)}=\bigl(\frac{0.4}{0.3}\bigr)^3\bigl(\frac{0.6}{0.7}\bigr)^7$ は $1$ より小さい。事後分布は Beta$(4,8)$ で、正規化の定数 $Z=B(4,8)=\frac{3!\,7!}{11!}=\frac1{1320}$ は知られているが、計算に使っていない。

指数分布を目標にした独立型

目標を $\pi=\mathrm{Exp}(1)$($p(y)=e^{-y}$、$y\ge0$)、提案を $\mathrm{Exp}(\lambda_0)$($g(y)=\lambda_0e^{-\lambda_0y}$)の独立型とする。
使う公式:thm-mh-independence、prop-mh-unbounded。
答え:$\lambda_0=\frac12$ では $w(y)=2e^{-y/2}\le2$ なので $M=2$ で、$\|P^n(x,\cdot)-\pi\|_{\mathrm{TV}}\le2^{-n}$($n=10$ で $\approx9.77\times10^{-4}$、$0.01$ 以下にするには $n=7$ で足りる)。$x=0$ から 1 歩では全変動距離がちょうど $\frac12$ で、$n=1$ の評価は等号になる。$\lambda_0=2$ では $w(y)=\frac12e^{y}$ が非有界で、$x=5$ からの棄却の確率は $(1-e^{-5})^2\approx0.986570$、10 歩とどまる確率は約 $0.8735$ 以上である。

途中の計算を開く

$\lambda_0=\frac12$、$x=0$:$w$ は $0$ で最大なので $\alpha(0,y)=w(y)/w(0)=e^{-y/2}$、$g(y)\alpha(0,y)=\frac12e^{-y}$ で、$P(0,\cdot)=\frac12\pi+\frac12\delta_0$ である。$A=\{0\}$ で $\lvert P(0,A)-\pi(A)\rvert=\frac12$、どの $A$ でも $\lvert\frac12\mathbf 1_A(0)-\frac12\pi(A)\rvert\le\frac12$ である。

$\lambda_0=2$:$w$ は増加なので、$y< x$ では $\alpha(x,y)=e^{y-x}$、$y>x$ では $1$ である。受理の確率は $\int_0^x2e^{-2y}e^{y-x}dy+\int_x^\infty2e^{-2y}dy=2e^{-x}(1-e^{-x})+e^{-2x}$ で、棄却の確率は $(1-e^{-x})^2$。prf-mh-unbounded の下界 $1-1/w(x)=1-2e^{-x}$ より少し大きい。

使える条件と反例

外す条件反例成り立たなくなること
受理確率の補正 $q(y,x)/q(x,y)$目標は $(0,1)$ の一様分布、提案は独立型の Beta$(1,2)$($g(y)=2(1-y)$)、受理確率を $\min(1,p(y)/p(x))$ とするthm-mh-reversible の結論($\pi$ が定常であること)。連鎖は提案の独立な列になり、定常分布は Beta$(1,2)$
thm-mh-independence の $p\le Mg$目標 $\mathrm{Exp}(1)$、提案 $\mathrm{Exp}(2)$ の独立型出発点によらない指数的な評価。各 $n$ で $\sup_x\Vert P^n(x,\cdot)-\pi\Vert_{\mathrm{TV}}=1$(prop-mh-unbounded)
thm-mh-convergence の $\varphi$ 既約性目標は $[0,1]\cup[2,3]$ の一様分布、提案は酔歩型で $\eta$ は $(-\frac12,\frac12)$ の一様分布分布の収束と時間平均の収束。$[0,1]$ から出発すると $h=\mathbf 1_{[2,3]}$ の時間平均はつねに $0$ で、$\int h\,d\pi=\frac12$ にならない
反例の確かめ
3 つの確かめを開く

1 行目:$p\equiv1$ なので誤った受理確率はつねに $1$ で、連鎖は Beta$(1,2)$ に従う独立な列であり、時間平均は $\frac13$ に近づく(目標の平均は $\frac12$)。正しい受理確率は $\min\bigl(1,\frac{g(x)}{g(y)}\bigr)=\min\bigl(1,\frac{1-x}{1-y}\bigr)$ である。外した条件は受理確率の補正だけで、提案の核と目標は thm-mh-reversible の仮定を満たす。

2 行目:$w(y)=\frac12e^{y}$ は非有界で、$\pi$ は原子をもたないので prop-mh-unbounded が当てはまる。ex-mh-indep のとおり $x=5$ でも 10 歩後の距離は約 $0.8735$ 以上で、$x$ を大きくすれば $1$ に近づく。

3 行目:$x\in[0,1]$ からの候補は $(-\frac12,\frac32)$ にあり、$(1,\frac32)$ と $(-\frac12,0)$ の候補は $\tilde p=0$ なので棄却される。よって連鎖は $[0,1]$ から出ない。$[2,3]$ から出発しても同様で、$[0,1]$ の一様分布と $[2,3]$ の一様分布はどちらも定常である。$\pi$ は定常で(thm-mh-reversible)、$[0,1]$ に制限した連鎖は非周期的なので、外れているのは既約性だけである。

よくある誤り

誤り正しくはなぜ
対称でない提案(独立型、Langevin 型)で $\min(1,p(y)/p(x))$ を使う$q(y,x)/q(x,y)$ を掛ける反例の表の 1 行目
支えの外の候補を、支えに入るまで引き直す支えの外の候補は棄却して、現在の状態をもう一度数える引き直すと提案の密度が $q(x,y)/Q(x,S)$ に変わり、対称でなくなる。補正の因子 $Q(x,S)/Q(y,S)$ を落とすと $\pi$ が定常でない
受理の割合は高いほどよいとする酔歩型では、受理の割合が $1$ に近いのは 1 歩が小さすぎるしるしex-mh-gauss で $\sigma\to0$
独立型の提案を目標より裾の軽い分布にする裾を目標より重くし、$p/g$ を有界にするprop-mh-unbounded
走らせながら連鎖の履歴で提案の分散を変え続ける調整は予備の実行で済ませ、本番では提案を固定する履歴に依存する調整は $\pi$ の定常性を壊しうる(RR04 §6.3、p. 62)
$\tilde p$ の比をそのまま計算する対数の差で計算し、$\log U$ と比べる尤度の積は桁があふれる

補足

提案の大きさの目安。 目標が同じ 1 次元の密度 $f$ の $d$ 個の独立な積で、連鎖が定常から始まるとき、酔歩型の提案 $N(x,(\ell^2/d)I)$ について $d\to\infty$ で最も速く混ざるのは平均の受理確率が約 $0.234$ になる $\ell$ であり、Langevin 型では提案の分散を $d^{-1/3}$ に比例させて受理確率が約 $0.574$ になるときである(RR04 §6.1–6.2、pp. 60–61。この記事では証明しない)。強い仮定のもとの漸近的な結果だが、実用の目安として使われる。1 次元の ex-mh-gauss では $\sigma=2.38$ で約 $0.445$ である。
ほかの方法との関係。 成分の条件付き分布を提案にすると受理確率はつねに $1$ になり、Gibbsサンプリング になる。$\pi$ を定常分布にもつ推移核を順に合成したもの・平均したものも $\pi$ を定常分布にもつので、成分ごとに Metropolis–Hastings 法と Gibbs サンプリングを混ぜて使える(RR04 §2.2、p. 25)。状態が有限個の場合の収束の定量的な評価は Markov連鎖モンテカルロ法 と 混合時間 にある。
名前。 対称な提案の方法は Metropolis・Rosenbluth・Rosenbluth・Teller・Teller(1953)、一般の提案への拡張は Hastings(1970)による(RR04 の文献 [53]・[37])。

関連項目

参考文献

[1]
Gareth O. Roberts, Jeffrey S. Rosenthal, General state space Markov chains and MCMC algorithms, Probability Surveys, 2004, pp. 20–71。§2.1–2.2(pp. 23–25、受理確率の規約・Proposition 2・Langevin 型・推移核の合成)、pp. 31–32(φ 既約・非周期の定義、Running Example、Theorem 4、Fact 5)、Theorem 8(p. 36)、§6.1–6.3(pp. 60–62)、文献 [37]・[53]。arXiv:math/0404033v4

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する