不合格サンプリング

拒否サンプリングの視覚的な例

数値解析および計算統計において、棄却標本抽出法は分布から観測値を生成する際に用いられる基本的な手法です。これは一般に受理棄却法または「受理棄却アルゴリズム」とも呼ばれ、厳密なシミュレーション法の一種です。この手法は、密度が である任意の分布に対して適用できます。 ${\displaystyle \mathbb {R} ^{m}}$

棄却サンプリングは、1次元のランダム変数をサンプリングするために、2次元の直交座標グラフの一様ランダムサンプリングを実行し、サンプルをその密度関数のグラフの下の領域に保持できるという観察に基づいています。 ^{[ 1 ] [ 2 ] [ 3 ]}この特性はN次元関数に拡張できることに留意してください。

アルゴリズムの定義

このアルゴリズムは、ジョン・フォン・ノイマン^{[ 4 ]}によって使用され、ビュフォンと彼の針にまで遡りますが、より単純な（提案）確率密度から抽出したサンプルを使用して、 （ターゲット）確率密度関数からサンプルを抽出します。 ${\displaystyle f(x)}$ ${\displaystyle f_{\varpropto }(x)}$ ${\displaystyle g(x)}$

拒否サンプリング

入力

ターゲット密度、提案密度、すべてに対してとなる定数。${\displaystyle f(x)={\frac {f_{\varpropto }(x)}{\int f_{\varpropto }(y)dy}}}$ ${\displaystyle g(x)}$ ${\displaystyle M}$ ${\displaystyle f_{\varpropto }(x)\leq Mg(x)}$ ${\displaystyle x}$

アルゴリズム

1. サンプル${\displaystyle X\sim g(x)}$
2. サンプル、 とは独立して。${\displaystyle U\sim \mathrm {Unif} (0,1)}$ ${\displaystyle X}$
3. 尤度比を計算します。${\displaystyle W={\dfrac {f_{\varpropto }(X)}{g(X)}}}$
4. の場合は拒否して手順 1 から繰り返します。それ以外の場合は受け入れて を出力します。${\displaystyle W<M\times U}$ ${\displaystyle X}$ ${\displaystyle X}$

出力

から抽出されたサンプル。${\displaystyle X}$ ${\displaystyle f}$

アルゴリズムは、拒否の平均を取ってサンプルを取得します。 ${\displaystyle {\frac {M}{\int f_{\varpropto }(y)dy}}}$

詳細な説明

棄却サンプリングの背後にある動機を視覚的に理解するために、ランダム変数の確率密度関数（PDF）を大きな長方形のボード上にグラフ化し、そこにダーツを投げる様子を想像してみてください。ダーツはボード全体に均一に分布していると仮定します。次に、曲線の下の領域外にあるダーツをすべて取り除きます。残りのダーツは曲線の下の領域内に均一に分布し、それらのダーツの位置はランダム変数の密度に従って分布します。これは、曲線が最も高い場所にダーツが着地する余地が最も大きく、したがって確率密度が最大になるためです。 ${\displaystyle x}$

上で説明した視覚化は、「提案分布」が均一である特定の形式の棄却サンプリングに相当します。したがって、そのグラフは長方形です。一般的な形式の棄却サンプリングでは、ボードは必ずしも長方形ではなく、サンプリング方法が分かっている（例えば、反転サンプリングを使用する）何らかの提案分布（必ずしも に正規化されている必要はない）の密度に応じて形作られると仮定します。その形状は、すべての点で少なくともサンプリング元の分布と同じ高さでなければならず、前者が後者を完全に囲むようにする必要があります。そうでない場合、サンプリング元の曲線領域には到達できない部分が存在してしまいます。 ${\displaystyle 1}$

拒否サンプリングは次のように機能します。

1. 提案分布から軸上の点をサンプリングします。${\displaystyle x}$
2. この位置に、提案分布の確率密度関数の y 値まで垂直線を描きます。${\displaystyle x}$
3. この線に沿って均一にサンプリングします。サンプリングされた値がこの垂直線における目的の分布の値より大きい場合は、その値を棄却して手順1に戻ります。それ以外の場合は、その値は目的の分布からのサンプリング値です。${\displaystyle x}$ ${\displaystyle x}$

このアルゴリズムは、関数が1に積分されるかどうかに関わらず、任意の曲線の下の領域からサンプリングするために使用できます。実際、関数を定数でスケーリングしても、サンプリングされた位置は影響を受けません。したがって、このアルゴリズムは、正規化定数が不明な分布からのサンプリングにも使用できます。これは計算統計でよく見られます。 ${\displaystyle x}$

理論

以下の分析では、簡単にするために と仮定します 。棄却サンプリング法は、 確率密度 の提案分布を使用して、確率密度関数の対象分布からサンプリング値を生成します。その考え方は、からサンプリングを行い、 からそのサンプルを確率 で受け入れ、値が受け入れられるまで からの抽出を繰り返すことで、 からサンプル値を生成できるというものです。ここに、のサポートに対してを満たす尤度比の定数で有限の境界 があります。つまり、のすべての値に対してを満たす必要があります。これには、 のサポートに のサポートが含まれていなければならないこと、つまりの場合は常に である必要があることに注意してください。 ${\displaystyle f\equiv f_{\varpropto }}$ ${\displaystyle f(x)}$ ${\displaystyle g(x)}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle f(x)/(Mg(x))}$ ${\displaystyle g}$ ${\displaystyle M}$ ${\displaystyle f(x)/g(x)}$ ${\displaystyle M<\infty }$ ${\displaystyle f}$ ${\displaystyle M}$ ${\displaystyle f(x)\leq Mg(x)}$ ${\displaystyle x}$ ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle g(x)>0}$ ${\displaystyle f(x)>0}$

この方法の妥当性は、包絡線原理によって検証される。ペア をシミュレーションすると、 の部分グラフ上で均一なシミュレーションが生成される。 となるペアのみを受け入れると、の部分グラフ上で均一に分布するペアが生成され、したがって、限界的に からのシミュレーションが生成される。${\textstyle (x,v=u\cdot Mg(x))}$ ${\textstyle Mg(x)}$ ${\textstyle u<f(x)/(Mg(x))}$ ${\displaystyle (x,v)}$ ${\displaystyle f(x)}$ ${\displaystyle f(x).}$

これは、十分な反復回数があれば、アルゴリズムは所望の分布からサンプルを生成することを意味します。このアルゴリズムには、メトロポリスアルゴリズムなど、いくつかの拡張が存在します。 ${\displaystyle f(x)}$

この手法は、モンテカルロ法の一般分野に関連しており、これには代理分布を用いて目標分布からのシミュレーションを行うマルコフ連鎖モンテカルロアルゴリズムも含まれます。メトロポリスアルゴリズムなどのアルゴリズムの基礎となっています。 ${\displaystyle f(x)}$

無条件受理確率は、提案されたサンプルのうち受け入れられる割合であり、 であり、各時点の の値は、提案分布の 密度関数の下で生成されます。$${\displaystyle {\begin{aligned}\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)&=\operatorname {E} \mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}\\[6pt]&=\operatorname {E} \left[\operatorname {E} [\mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}|Y]\right]&({\text{by tower property }})\\[6pt]&=\operatorname {E} \left[\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}{\biggr |}Y\right)\right]\\[6pt]&=\operatorname {E} \left[{\frac {f(Y)}{Mg(Y)}}\right]&({\text{because }}\Pr(U\leq u)=u,{\text{when }}U{\text{ is uniform on }}(0,1))\\[6pt]&=\int \limits _{y:g(y)>0}{\frac {f(y)}{Mg(y)}}g(y)\,dy\\[6pt]&={\frac {1}{M}}\int \limits _{y:g(y)>0}f(y)\,dy\\[6pt]&={\frac {1}{M}}&({\text{since support of }}Y{\text{ includes support of }}X)\end{aligned}}}$$ ${\displaystyle U\sim \mathrm {Unif} (0,1)}$ ${\displaystyle Y}$ ${\displaystyle g(\cdot )}$

したがって、許容値を得るために必要なサンプル数は、平均 を持つ確率 の幾何分布に従います。直感的に言えば、はアルゴリズムの計算複雑さの尺度として、必要な反復回数の期待値です。 ${\displaystyle g}$ ${\displaystyle 1/M}$ ${\displaystyle M}$ ${\displaystyle M}$

上記の式を書き直すと、 となることに注意してください。上記の公式により、 は区間 内の値のみを取る確率です。が 1 に近い値に選択されると、 の比の変化が少ないほど無条件受理確率は高くなります。これは、 が尤度比 の上限であるためです。実際には、 の値が1 に近いほど、平均して拒否されるサンプルが少なくなり、アルゴリズムの反復回数が少なくなるため好まれます。この意味で、 はできる限り小さいことが好ましいとされます（ を満たしながら、これはが一般に何らかの形で似ているはずであることを示唆しています）。ただし、 は 1 に等しくなることはできないことに注意してください。そのような は、つまりターゲット分布と提案分布が実際には同じ分布であること を意味します。$${\displaystyle M={\frac {1}{\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}}}$$ ${\textstyle 1\leq M<\infty }$ ${\textstyle \mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}$ ${\displaystyle [0,1]}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\textstyle f(x)/g(x)}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle f(x)\leq Mg(x)}$ ${\displaystyle g(x)}$ ${\displaystyle f(x)}$ ${\displaystyle M}$ ${\displaystyle f(x)=g(x)}$

棄却サンプリングは、サンプリングの形式が困難である場合に最もよく使用されます。棄却アルゴリズムの1回の反復では、提案分布からのサンプリング、一様分布からの抽出、そして式の評価が必要です。したがって、これらの操作にかかるコスト（棄却サンプリングでサンプルを取得する際の期待コスト）が、他の方法でサンプルを取得する際のコストよりも低い場合、棄却サンプリングは他の方法よりも効率的です。 ${\displaystyle f(x)}$ ${\displaystyle f(x)/(Mg(x))}$ ${\displaystyle M}$

単純な方法を用いたサンプリングに比べて優れている点

拒絶サンプリングは、状況によっては単純な手法よりもはるかに効率的です。例えば、 という問題が与えられた場合、集合 、すなわち という条件付きサンプリングは、単純な手法（例えば逆変換サンプリング）を用いて簡単にシミュレートできることがあります。 ${\textstyle X\sim F(\cdot )}$ ${\displaystyle X}$ ${\displaystyle A}$ ${\textstyle X|X\in A}$ ${\textstyle X}$

• 独立してサンプルを採取し、満足のいくものを受け入れる${\textstyle X\sim F(\cdot )}$ ${\displaystyle \{n\geq 1:X_{n}\in A\}}$
• 出力: (切り捨て(統計)も参照)${\displaystyle \{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}}$

問題は、 の場合、このサンプリングが困難で非効率的になる可能性があることです。予想される反復回数は となり、これは無限大に近づく可能性があります。さらに、棄却サンプリング法を適用した場合でも、尤度比の境界を最適化することは常に困難です。が大きく、棄却率が高い場合、アルゴリズムは非常に非効率的になる可能性があります。自然指数族（存在する場合）は指数傾斜法とも呼ばれ、計算の複雑さを軽減し、 の値を低減し、計算を高速化 できる提案分布のクラスを提供します（例：自然指数族の操作を参照）。${\textstyle \mathbb {P} (X\in A)\approx 0}$ ${\displaystyle {\frac {1}{\mathbb {P} (X\in A)}}}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

指数傾斜法を用いた棄却サンプリング

確率変数 が与えられたとき、は目標分布である。簡単のため、密度関数は と明示的に書けると仮定する。提案を として選ぶ。 ${\displaystyle X\sim F(\cdot )}$ ${\displaystyle F(x)=\mathbb {P} (X\leq x)}$ ${\displaystyle f(x)}$

$${\displaystyle {\begin{aligned}F_{\theta }(x)&=\mathbb {E} \left[\exp(\theta X-\psi (\theta ))\mathbb {I} (X\leq x)\right]\\&=\int _{-\infty }^{x}e^{\theta y-\psi (\theta )}f(y)dy\\g_{\theta }(x)&=F'_{\theta }(x)=e^{\theta x-\psi (\theta )}f(x)\end{aligned}}}$$

ここで、 と である。明らかに、 は自然指数族に属する。さらに、尤度比は ${\displaystyle \psi (\theta )=\log \left(\mathbb {E} \exp(\theta X)\right)}$ ${\displaystyle \Theta =\{\theta :\psi (\theta )<\infty \}}$ ${\displaystyle \{F_{\theta }(\cdot )\}_{\theta \in \Theta }}$

$${\displaystyle Z(x)={\frac {f(x)}{g_{\theta }(x)}}={\frac {f(x)}{e^{\theta x-\psi (\theta )}f(x)}}=e^{-\theta x+\psi (\theta )}}$$

は、それがキュムラント生成関数であることを意味することに注意されたい。つまり、 ${\displaystyle \psi (\theta )<\infty }$

${\displaystyle \psi (\theta )=\log \mathbb {E} {\exp(tX)}|_{t=\theta }=\log M_{X}(t)|_{t=\theta }}$ 。

提案のキュムラント生成関数、したがって提案のキュムラントを導出するのは簡単です。

${\displaystyle {\begin{aligned}\psi _{\theta }(\eta )&=\log \left(\mathbb {E} _{\theta }\exp(\eta X)\right)=\psi (\theta +\eta )-\psi (\theta )<\infty \\\mathbb {E} _{\theta }(X)&=\left.{\frac {\partial \psi _{\theta }(\eta )}{\partial \eta }}\right|_{\eta =0}\\\mathrm {Var} _{\theta }(X)&=\left.{\frac {\partial ^{2}\psi _{\theta }(\eta )}{\partial ^{2}\eta }}\right|_{\eta =0}\end{aligned}}}$

簡単な例として、、、 の場合を考えます。目標は （ただし ）をサンプリングすることです。解析は以下のようになります。 ${\displaystyle F(\cdot )}$ ${\displaystyle X\sim \mathrm {N} (\mu ,\sigma ^{2})}$ ${\textstyle \psi (\theta )=\mu \theta +{\frac {\sigma ^{2}\theta ^{2}}{2}}}$ ${\displaystyle X|X\in \left[b,\infty \right]}$ ${\displaystyle b>\mu }$

• キュムラント生成関数を次のようにして、提案分布の形を選択する。${\displaystyle F_{\theta }(\cdot )}$

${\textstyle \psi _{\theta }(\eta )=\psi (\theta +\eta )-\psi (\theta )=(\mu +\theta \sigma ^{2})\eta +{\frac {\sigma ^{2}\eta ^{2}}{2}}}$ 、

これはさらに、それが正規分布であることを意味します。${\displaystyle \mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})}$

• 提案の配布先として選択した井戸を決定します。この設定では、直感的に選択する方法は、${\displaystyle \theta ^{*}}$ ${\displaystyle \theta ^{*}}$

${\displaystyle \mathbb {E} _{\theta }(X)=\mu +\theta \sigma ^{2}=b}$ 、

つまり、提案の分布は となります。${\displaystyle \theta ^{*}={\frac {b-\mu }{\sigma ^{2}}}.}$ ${\displaystyle g_{\theta ^{*}}(x)=\mathrm {N} (b,\sigma ^{2})}$

• ターゲット、提案、可能性比率を明確に書き出す

$${\displaystyle {\begin{aligned}f_{X|X\geq b}(x)&={\frac {f(x)\mathbb {I} (x\geq b)}{\mathbb {P} (X\geq b)}}\\g_{\theta ^{*}}(x)&=f(x)\exp(\theta ^{*}x-\psi (\theta ^{*}))\\Z(x)&={\frac {f_{X|X\geq b}(x)}{g_{\theta ^{*}}(x)}}={\frac {\exp(-\theta ^{*}x+\psi (\theta ^{*}))\mathbb {I} (x\geq b)}{\mathbb {P} (X\geq b)}}\end{aligned}}}$$

• 尤度比 の境界を導出せよ。これは に対して減少する関数であるので、${\displaystyle M}$ ${\displaystyle Z(x)}$ ${\displaystyle x\in [b,\infty ]}$

$${\displaystyle M=Z(b)={\frac {\exp(-\theta ^{*}b+\psi (\theta ^{*}))}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} \left(\mathrm {N} (0,1)\geq {\frac {b-\mu }{\sigma }}\right)}}}$$

• 棄却基準: の場合、${\displaystyle U\sim \mathrm {Unif} (0,1)}$

$${\displaystyle U\leq {\frac {Z(x)}{M}}=e^{-\theta ^{*}(x-b)}\mathbb {I} (x\geq b)}$$

が成り立つ場合は の値を受け入れ、そうでない場合は受け入れるまで newと new のサンプリングを続けます。${\displaystyle X}$ ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ ${\textstyle U\sim \mathrm {Unif} (0,1)}$

上記の例では、効率の尺度として、自然指数族に基づく棄却サンプリング法の反復の予想回数は のオーダー、つまり ですが、ナイーブな方法では反復の予想回数は であり、これははるかに非効率的です。 ${\displaystyle b}$ ${\displaystyle M(b)=O(b)}$ ${\textstyle {\frac {1}{\mathbb {P} (X\geq b)}}=O(b\cdot e^{\frac {(b-\mu )^{2}}{2\sigma ^{2}}})}$

一般に、提案分布のパラメトリッククラスを指数傾斜させると、提案分布を直接特徴付ける有用な特性により、最適化問題を簡便に解決できます。この種の問題において、単純な分布のクラスの中でを条件付きでシミュレートするには、自然指数族を使用することが鍵となります。これにより、複雑さをある程度制御し、計算を大幅に高速化できます。実際、自然指数族を使用するには、深い数学的理由があります。 ${\displaystyle X}$ ${\displaystyle X\in A}$

欠点

拒否サンプリングでは、ターゲットの分布 (具体的には、任意の時点でターゲット PDF を評価する機能) を知っている必要があります。

棄却サンプリングは、サンプリング対象の関数が特定の領域に高度に集中している場合（例えば、ある場所でスパイクを持つ関数など）、不要なサンプルを大量に採取してしまう可能性があります。多くの分布において、この問題は適応拡張（適応棄却サンプリングを参照）を用いるか、一様分布比法を用いて変数を適切に変更することで解決できます。さらに、問題の次元が大きくなるにつれて、埋め込み体積と埋め込み体積の「角」の比はゼロに近づくため、有用なサンプルが生成される前に多くの棄却が行われる可能性があり、アルゴリズムは非効率的かつ非実用的になります。次元の呪いを参照してください。高次元では、異なるアプローチ、典型的にはメトロポリスサンプリングやギブスサンプリングなどのマルコフ連鎖モンテカルロ法を使用する必要があります。（ただし、多次元サンプリング問題を一連の低次元サンプルに分解するギブスサンプリングでは、そのステップの1つとして棄却サンプリングが使用される場合があります。）

再生除去サンプリング

条件を満たす有限定数が 存在しない場合、または適切な有限定数を計算するのがあまりにも難しい場合は、次のように、拒否サンプリングアルゴリズムの修正版を使用して、ターゲットから（近似的に）シミュレートすることができます。^{[ 5 ]}${\displaystyle M}$ ${\displaystyle M\geq \sup _{x}{\frac {f_{\varpropto }(x)}{g(x)}}}$ ${\displaystyle M<\infty }$ ${\displaystyle f}$

再生除去サンプリング

入力

ターゲット密度、提案密度、大きな定数 。${\displaystyle f(x)={\frac {f_{\varpropto }(x)}{\int f_{\varpropto }(y)dy}}}$ ${\displaystyle g(x)}$ ${\displaystyle M}$

アルゴリズム

カウンターを設定します。 ${\displaystyle t\leftarrow 0}$

1. サンプルと増分。${\displaystyle X\sim g(x)}$ ${\displaystyle t\leftarrow t+1}$
2. 尤度比を計算します。${\displaystyle W_{t}={\dfrac {f_{\varpropto }(X)}{g(X)}}}$
3. の場合は拒否して手順 1 から繰り返します。それ以外の場合は受け入れて を出力します。${\displaystyle W_{1}+\cdots +W_{t}<M}$ ${\displaystyle X}$ ${\displaystyle X}$

出力

およそ から抽出されたサンプル。${\displaystyle X}$ ${\displaystyle f}$

上記の再生バージョンと従来の棄却サンプリングとの唯一の違いは、受け入れの決定が、現在の尤度比が を超えるかどうか(つまり) ではなく、 すべての尤度比の累積和が を超えるかどうか(つまり) に基づいて行われるという点です。 ${\displaystyle W_{1}+\cdots +W_{t}}$ ${\displaystyle M}$ ${\displaystyle W_{1}+\cdots +W_{t}>M}$ ${\displaystyle W_{t}}$ ${\displaystyle M\times U}$ ${\displaystyle W_{t}>M\times U}$

のとき、アルゴリズムの出力変数は 密度 で目的のターゲットに分布収束することが示される。^{[ 5 ]}${\displaystyle M\rightarrow \infty }$ ${\displaystyle X=X_{M}}$ ${\displaystyle f}$

最適な境界定数の知識を必要としないもう一つのアプローチは 、経験的最大拒絶サンプリング法である。^{[ 6 ]}${\displaystyle \sup _{x}{\frac {f_{\varpropto }(x)}{g(x)}}}$

適応的除去サンプリング

多くの分布において、与えられた分布を多くの無駄な空間を残さずに包含する提案分布を見つけることは困難です。この困難を克服し、様々な分布（密度関数が対数凹型であること、これは一般的な分布のほとんどに当てはまります。密度関数自体が凹型でないものも含みます）から効率的にサンプリングするために使用できる棄却サンプリングの拡張は、適応棄却サンプリング（ARS）として知られています。

1992年にギルクスによって最終的に導入されたこの技術には、3つの基本的な考え方があります。^{[ 7 ]}

1. もし役に立つなら、エンベロープ分布を対数空間（例えば対数確率や対数密度）で定義してみてください。つまり、直接ではなく、 を使って定義するということです。 ${\displaystyle h\left(x\right)=\log g\left(x\right)}$ ${\displaystyle g\left(x\right)}$
   • 多くの場合、代数的に複雑な密度関数を持つ分布は、比較的単純な対数密度関数を持ちます (つまり、代数的に複雑な場合は、扱いやすくなるか、少なくとも区分線形に近くなります)。${\displaystyle f\left(x\right)}$ ${\displaystyle \log f\left(x\right)}$
2. 単一の均一なエンベロープ密度関数の代わりに、区分線形密度関数をエンベロープとして使用します。
   • サンプルを棄却しなければならないたびに、評価した の値を用いて区分近似値 を改善できます。これにより、次回の試行が棄却される可能性が低くなります。漸近的には、サンプルを棄却しなければならない確率はゼロに収束するはずであり、実際には非常に急速に収束することがよくあります。${\displaystyle f\left(x\right)}$ ${\displaystyle h\left(x\right)}$
   • 提案されているように、拒否される点を選択するたびに、選択した点と同じ x 座標を持つ点で曲線に接する別の線分を使用してエンベロープを引き締めます。
   • 提案対数分布の区分線形モデルは、区分指数分布の集合（すなわち、1つまたは複数の指数分布の線分を端から端まで接続したもの）を生成します。指数分布は振る舞いがよく​​、よく理解されています。指数分布の対数は直線であるため、この手法は基本的に、密度の対数を一連の線分で囲むことを意味します。これが対数凹制約の起源です。分布が対数凹である場合、その対数は凹型（逆U字型）であり、曲線に接する線分は常に曲線の上を通過します。
   • 対数空間で作業しない場合は、区分線形密度関数を三角分布でサンプリングすることもできる^{[ 8 ]}
3. (対数)凹面要件をさらに活用することで、サンプルが受け入れられたときの評価コストを回避できる可能性があります。 ${\displaystyle f\left(x\right)}$
   • 現在の拒否チェーンで評価する必要があったの値を使用して区分線形上限 (「エンベロープ」関数) を構築できるのと同様に、これらの値を使用して区分線形下限 (「スクイージング」関数) も構築できます。${\displaystyle h\left(x\right)}$
   • サンプルが受け入れられるかどうか（潜在的に高価）を評価する前に、利用可能な（理想的には安価な） （またはこの場合）スクイーズ機能と比較することで、サンプルが受け入れられるかどうかをすでに知ることができる場合があります。${\displaystyle f\left(x\right)}$ ${\displaystyle g_{l}\left(x\right)}$ ${\displaystyle h_{l}\left(x\right)}$
   • この圧縮ステップは、Gilks​​が提案している場合でもオプションです。せいぜい、（煩雑で高コストな）目標密度の余分な評価を1回削減できるだけです。しかし、特に高コストな密度関数の場合（そして棄却率が急速にゼロに収束すると仮定した場合）、最終的な実行時間に大きな違いが生じる可能性があります。

この手法は、本質的には、一定数の線分（場合によっては接線1本のみ）から始めて、曲線の上にあるまま対数に近似する直線部分の包絡線を順次決定していくというものです。切り捨て指数型確率変数からのサンプリングは簡単です。適切な間隔とそれに応じた切り捨てを持つ一様確率変数の対数を取るだけです。

残念ながら、ARS は対数凹面のターゲット密度からのサンプリングにしか適用できません。このため、非対数凹面のターゲット分布に対処するための ARS の拡張が文献でいくつか提案されています。^{[ 9 ] [ 10 ] [ 11 ]}さらに、自己調整型提案密度（ターゲットに対して自動的に構築され適応された提案）を構築する汎用サンプラーを取得するために、ARS とメトロポリス-ヘイスティングス法のさまざまな組み合わせが設計されています。このクラスの方法は、適応型拒絶メトロポリスサンプリング (ARMS) アルゴリズムと呼ばれることがよくあります。^{[ 12 ] [ 13 ]}結果として得られる適応型手法は常に適用できますが、この場合、生成されたサンプルは相関しています（ただし、反復回数が増えると相関はすぐにゼロになります）。

参照

• 逆変換サンプリング
• 制服の割合
• 擬似乱数サンプリング
• ジッグラトアルゴリズム

参考文献

1. Casella, George; Robert, Christian P.; Wells, Martin T. (2004).一般化受理拒否サンプリング法. 数理統計研究所. pp.  342– 347. doi : 10.1214/lnms/1196285403 . ISBN 9780940600614。
2. Neal, Radford M. (2003). 「スライスサンプリング」 . Annals of Statistics . 31 (3): 705– 767. doi : 10.1214/aos/1056562461 . MR 1994729. Zbl 1051.65007 .  
3. ビショップ、クリストファー (2006). 「11.4: スライスサンプリング」.パターン認識と機械学習.シュプリンガー. ISBN 978-0-387-31073-2。
4. Forsythe, George E. (1972). 「正規分布およびその他の分布からのランダムサンプリングのためのフォン・ノイマン比較法」 .計算数学. 26 (120): 817– 826. doi : 10.2307/2005864 . ISSN 0025-5718 . JSTOR 2005864 .  
5. Botev, Zdravko I.; Kroese, Dirk P.; Taimre, Thomas (2025). 『データサイエンスと機械学習：数学的・統計的手法（第2版）』 ボカラトン; ロンドン: CRC Press. pp.  81– 84. ISBN 978-1-032-48868-4。
6. Caffo, Brian S.; Booth, James G.; Davison, AC (2002). 「経験的至上拒絶サンプリング」 . Biometrika . 89 (4): 745– 754. ISSN 0006-3444 . 
7. Gilks​​, WR; Wild, P. (1992). 「ギブスサンプリングのための適応的棄却サンプリング」.英国王立統計学会誌. シリーズC (応用統計). 41 (2): 337– 348. doi : 10.2307/2347565 . JSTOR 2347565 . 
8. Thomas, DB; Luk, W. (2007). 「区分線形近似による非一様乱数生成」. IET Computers & Digital Techniques . 1 (4): 312– 321. doi : 10.1049/iet-cdt:20060188 .
9. Hörmann, Wolfgang (1995-06-01). 「T凹分布からのサンプリングにおける棄却法」. ACM Trans. Math. Software . 21 (2): 182– 193. CiteSeerX 10.1.1.56.6055 . doi : 10.1145/203082.203089 . ISSN 0098-3500 .  
10. Evans, M.; Swartz, T. (1998-12-01). 「変換された密度の凹面特性を用いたランダム変数生成」. Journal of Computational and Graphical Statistics . 7 (4): 514– 528. CiteSeerX 10.1.1.53.9001 . doi : 10.2307/1390680 . JSTOR 1390680 .  
11. Görür, Dilan; Teh, Yee Whye (2011-01-01). 「Concave-Convex Adaptive Rejection Sampling」. Journal of Computational and Graphical Statistics . 20 (3): 670– 691. doi : 10.1198/jcgs.2011.09058 . ISSN 1061-8600 . 
12. Gilks​​, WR; Best, NG ; Tan, KKC (1995-01-01). 「ギブスサンプリングにおける適応的棄却メトロポリスサンプリング」.英国王立統計学会誌. シリーズC (応用統計). 44 (4): 455– 472. doi : 10.2307/2986138 . JSTOR 2986138 . 
13. マイヤー, レナーテ; カイ, ボー; ペロン, フランソワ (2008-03-15). 「2次ラグランジュ補間多項式を用いた適応的棄却メトロポリスサンプリング」.計算統計とデータ分析. 52 (7): 3408– 3423. doi : 10.1016/j.csda.2008.01.005 .

さらに読む

• Robert, CP; Casella, G. (2004).モンテカルロ統計手法（第2版）. ニューヨーク: Springer-Verlag.