棄却法

知識マップ

モデリング・用語

ひとことで言うと

目的の分布から直接サンプリングできないとき、扱いやすい「提案分布」から点を出し、条件を満たす点だけを採択（残す）ことで目的の分布を得る乱数生成法です。逆関数法が使えない（累積分布の逆関数が求まらない）分布にも使えます。

目的の密度 $f(x)$ と包絡線 $Mg(x)$ （ $f$ を常に覆う）を重ねた図。提案分布から出した点のうち、 $f(x)$ 以下に落ちた点（緑）は採択、 $f(x)$ と $Mg(x)$ の間に落ちた点（赤）は棄却される。

数式で表すと

$U\le f(x)/(M g(x))\Rightarrow \text{採択}$

提案分布から生成し条件を満たす点だけ採択して目的分布を得る乱数生成法。

棄却法（acceptance-rejection method）は、目的の密度

f(x)

から直接サンプリングするのが難しいときに使う乱数生成法です。concept: 逆関数法は累積分布関数の逆関数

F^{-1}

が解析的に求まる分布（指数・ロジスティックなど）には使えますが、

F^{-1}

が閉じた式で書けない分布には使えません。棄却法はそうした分布にも適用できる代替手段です。やり方はこうです。まずサンプリングしやすい提案分布の密度

g(x)

と定数

M

を、すべての

x

で

f(x)\le M\,g(x)

が成り立つように選びます（

Mg(x)

は

f

を上から覆う「包絡線」）。そのうえで（1）提案分布から1点

X\sim g

をサンプルし、（2）独立に一様乱数

U\sim U(0,1)

を引き、（3）

U\le\dfrac{f(X)}{M\,g(X)}

なら

X

を採択、そうでなければ棄却して（1）からやり直す、という手続きを繰り返します。採択された

X

は、ちょうど目的の密度

f

に従います。直感的には、包絡線

Mg(x)

の下に一様に点をばらまき、

f(x)

より下に落ちた点だけを残すと、残った点の横位置の分布が

f

になる、という仕組みです。効率の鍵は定数

M

です。1回の試行で採択される確率はちょうど

1/M

になります（包絡線の下の全面積

M

のうち、

f

の下の面積が

1

だから）。したがって

M

が小さいほど採択率が高く、無駄なやり直しが減って効率が良くなります。

M

を小さくするには、提案分布

g

を目的分布

f

になるべく近い形に選ぶのが要点です（

f

と

g

が似ているほど包絡線が

f

に張りつき

M

を1に近づけられる）。逆に

g

が

f

とかけ離れていると

M

が大きくなり、ほとんどの点が棄却されて非効率になります。

試験に出る性質

目的

直接サンプリングしにくい密度 $f$ から、提案分布 $g$ 経由で乱数を生成する。

逆関数法との違い

concept: 逆関数法は $F^{-1}$ が求まる分布限定。棄却法は $F^{-1}$ が求まらない分布にも使える。

包絡線の条件

すべての $x$ で $f(x)\le Mg(x)$ となる提案密度 $g$ と定数 $M$ を選ぶ。

採択ルール

$X\sim g$ 、 $U\sim U(0,1)$ を引き、 $U\le f(X)/(Mg(X))$ なら採択、そうでなければ棄却してやり直す。

効率は1/M

1試行の採択確率は $1/M$ 。 $M$ が小さい（ $g$ が $f$ に近い）ほど効率が良い。

例で見る

$f$ を区間 $(0,1)$ 上のある山型密度、提案分布 $g$ を一様分布 $U(0,1)$ とし、 $f(x)\le M$ となる $M=1.5$ をとる。手続きは $X\sim U(0,1)$ 、 $U\sim U(0,1)$ を引き、 $U\le f(X)/1.5$ なら採択。採択率は $1/M=1/1.5\approx0.67$ 。平均して約1.5回に1回が採択される。

つまずきポイント

包絡線条件 $f(x)\le Mg(x)$ がすべての $x$ で成り立つように $M$ を選ばない（一箇所でも破れると正しい分布にならない）
採択率を $M$ そのものと思う（採択率は $1/M$ 。 $M$ が大きいほど棄却が増えて非効率）
棄却した点を“次の候補”として使い回す（棄却したら必ず最初から新しい $X,U$ を引き直す）

定着クイズ

棄却法で提案分布の密度 $g$ と定数 $M$ に課す条件は？

棄却法の採択ルールは？

1回の試行で採択される確率は？

関連：#逆関数法 #モンテカルロ

この用語を扱う問題（3）