重要度サンプリング

重要度サンプリングは、関心のある分布とは異なる分布から生成されたサンプルのみを使用して、特定の分布の特性を評価するモンテカルロ法です。統計学への導入は、一般的に1978年のTeun KloekとHerman K. van Dijkの論文に起因するとされていますが、^[1]その前身は1949年に統計物理学で見ることができます。 ^{[2] [3]重要度サンプリングは、}計算物理学におけるアンブレラサンプリングとも関連しています。用途に応じて、この用語は、この代替分布からサンプリングするプロセス、推論のプロセス、またはその両方を指す場合があります。

をある確率空間におけるランダム変数とする。Pの下でのXの期待値を推定し、E [ X;P ]と表記する。Pに従って生成された統計的に独立したランダムサンプルがある場合、 E [ X;P ] の経験的推定値は次のようになる。${\displaystyle X\colon \Omega \to \mathbb {R} }$ ${\displaystyle (\Omega ,{\mathcal {F}},P)}$${\displaystyle x_{1},\ldots ,x_{n}}$

${\displaystyle {\widehat {\mathbf {E} }}_{n}[X;P]={\frac {1}{n}}\sum _{i=1}^{n}x_{i}\quad \mathrm {where} \;x_{i}\sim P(X)}$

この推定値の精度はXの分散に依存する。

${\displaystyle \operatorname {var} [{\widehat {\mathbf {E} }}_{n};P]={\frac {\operatorname {var} [X;P]}{n}}.}$

重要度サンプリングの基本的な考え方は、 E [ X;P ]の推定値の分散を下げるために、またはPからのサンプリングが難しい場合に、異なる分布から状態をサンプリングすることです。これは、まずE [ L ; P ] = 1でPがほぼどこでもであるようなランダム変数を選択することによって実現されます。変数Lを使用して、次の式を満たす 確率を定義します。${\displaystyle L\geq 0}$ ${\displaystyle L(\omega )\neq 0}$${\displaystyle P^{(L)}}$

${\displaystyle \mathbf {E} [X;P]=\mathbf {E} \left[{\frac {X}{L}};P^{(L)}\right].}$

変数X / LはP ^{( L )の}下でサンプリングされ、上記のようにE [ X;P ]を推定します。この推定値は次の場合に改善されます 。 ${\displaystyle \operatorname {var} \left[{\frac {X}{L}};P^{(L)}\right]<\operatorname {var} [X;P]}$

X がΩ に対して定数符号である場合、最適な変数L は明らかに であり、X / L * は検索された定数E [ X;P ] であり、その値を得るにはP ^{( L *)}の下での単一のサンプルで十分です。残念ながら、その選択はできません。E [ X;P ] はまさに探している値だからです。ただし、この理論的な最適なケースL* は、重要度サンプリングが何を行うかについての洞察を与えてくれます。 ${\displaystyle L^{*}={\frac {X}{\mathbf {E} [X;P]}}\geq 0}$

${\displaystyle {\begin{aligned}\forall a\in \mathbb {R} ,\;P^{(L^{*})}(X\in [a;a+da])&=\int _{\omega \in \{X\in [a;a+da]\}}{\frac {X(\omega )}{E[X;P]}}\,dP(\omega )\\[6pt]&={\frac {1}{E[X;P]}}\;a\,P(X\in [a;a+da])\end{aligned}}}$

右側は、E [ X ; P ] に合計される無限小要素の1つです。${\displaystyle a\,P(X\in [a;a+da])}$

${\displaystyle E[X;P]=\int _{a=-\infty }^{+\infty }a\,P(X\in [a;a+da])}$

したがって、重要度サンプリングにおける適切な確率変化P ^{( L ) は、}Xの法則を再分配し、そのサンプルの頻度がE [ X ; P ]の重みに従って直接ソートされるようにします。これが「重要度サンプリング」という名前です。

重要度サンプリングはモンテカルロ積分器としてよく使用されます。 が一様分布で のとき、E [ X ;P ] は実関数 の積分に対応します。 ${\displaystyle P}$${\displaystyle \Omega =\mathbb {R} }$${\displaystyle X\colon \mathbb {R} \to \mathbb {R} }$

このような方法は、解析的に扱うのが難しすぎる確率モデルの状態推定問題やパラメータ推定問題において事後密度や期待値を推定するために頻繁に使用されます。例としては、ベイジアンネットワークや重要度加重変分オートエンコーダなどがあります。^[4]

重要度サンプリングは、モンテカルロ法で使用できる分散削減手法です。重要度サンプリングの背後にある考え方は、シミュレーションの入力ランダム変数の特定の値が、他の値よりも推定されるパラメータに大きな影響を与えるというものです。これらの「重要な」値が、より頻繁にサンプリングすることによって強調されると、推定値の分散を削減できます。したがって、重要度サンプリングの基本的な方法論は、重要な値を「促進する」分布を選択することです。この「偏りのある」分布の使用は、シミュレーションに直接適用された場合、偏りのある推定値をもたらします。ただし、シミュレーション出力は、偏りのある分布の使用を補正するために重み付けされ、これにより、新しい重要度サンプリング推定値が偏りのないことが保証されます。重みは、尤度比、つまり、偏りのあるシミュレーション分布に対する真の基礎分布の Radon-Nikodym 導関数によって与えられます 。

重要度サンプリング シミュレーションを実装する際の基本的な問題は、入力変数の重要な領域を促進する偏りのある分布の選択です。適切な偏りのある分布を選択または設計することは、重要度サンプリングの「技術」です。適切な分布のメリットは、実行時間を大幅に節約できることです。不適切な分布のデメリットは、重要度サンプリングのない一般的なモンテ カルロ シミュレーションよりも実行時間が長くなることです。

をサンプル、を尤度比とします。ここで、は目的の分布の確率密度 (質量) 関数、はバイアス/提案/サンプル分布の確率密度 (質量) 関数です。次に、スケールされたサンプルの分散を最小化するサンプル分布を選択することで問題を特徴付けることができます。 ${\displaystyle X}$${\displaystyle {\frac {f(X)}{g(X)}}}$${\displaystyle f}$${\displaystyle g}$${\displaystyle g}$

${\displaystyle g^{*}=\min _{g}\operatorname {var} _{g}\left(X{\frac {f(X)}{g(X)}}\right).}$

以下の分布は上記の分散を最小化することが示される：^[5]

${\displaystyle g^{*}(X)={\frac {|X|f(X)}{\int |x|f(x)\,dx}}.}$

のとき、この分散は 0 になることに注意してください。 ${\displaystyle X\geq 0}$

シミュレーションによって事象 の確率を推定することを検討する。ここで は累積分布関数と確率密度関数 を持つランダム変数であり、プライムは導関数を表す。分布 から長さの独立かつ同一分布(iid) のシーケンスが生成され、しきい値を超えるランダム変数の数がカウントされる。ランダム変数は二項分布によって特徴付けられる。${\displaystyle p_{t}\,}$${\displaystyle X\geq t}$${\displaystyle X}$ ${\displaystyle F(x)}$ ${\displaystyle f(x)=F'(x)\,}$${\displaystyle K}$${\displaystyle X_{i}\,}$${\displaystyle F}$${\displaystyle k_{t}}$${\displaystyle t}$${\displaystyle k_{t}}$

${\displaystyle P(k_{t}=k)={K \choose k}p_{t}^{k}(1-p_{t})^{K-k},\,\quad \quad k=0,1,\dots ,K.}$

、および であることが示せるので、極限ではを得ることができます。 の場合、分散が低いことに注意してください。 重要度サンプリングは、シミュレーション実験に対して、通常バイアス密度と呼ばれる代替密度関数( の場合) の決定と使用に関係しています。 この密度により、イベントがより頻繁に発生するため、シーケンスの長さは、推定値の分散に対して小さくなります。 あるいは、 が与えられている場合、バイアス密度を使用すると、従来のモンテカルロ推定よりも分散が小さくなります。 の定義から、以下のように導入できます。 ${\displaystyle \operatorname {E} [k_{t}/K]=p_{t}}$${\displaystyle \operatorname {var} [k_{t}/K]=p_{t}(1-p_{t})/K}$${\displaystyle K\to \infty }$${\displaystyle p_{t}}$${\displaystyle p_{t}\approx 1}$${\displaystyle f_{*}\,}$${\displaystyle X}$${\displaystyle {X\geq t\ }}$${\displaystyle K}$${\displaystyle K}$${\displaystyle p_{t}\,}$${\displaystyle f_{*}\,}$

${\displaystyle {\begin{aligned}p_{t}&={E}[1(X\geq t)]\\[6pt]&=\int 1(x\geq t){\frac {f(x)}{f_{*}(x)}}f_{*}(x)\,dx\\[6pt]&=E_{*}[1(X\geq t)W(X)]\end{aligned}}}$

どこ

${\displaystyle W(\cdot )\equiv {\frac {f(\cdot )}{f_{*}(\cdot )}}}$

は尤度比であり、重み関数と呼ばれる。上記の式の最後の等式は推定量

${\displaystyle {\hat {p}}_{t}={\frac {1}{K}}\,\sum _{i=1}^{K}1(X_{i}\geq t)W(X_{i}),\,\quad \quad X_{i}\sim f_{*}}$

これは の重要度サンプリング推定量であり、偏りがありません。つまり、推定手順は から iid サンプルを生成することです。を超える各サンプルについて、推定値はサンプル値で評価された重みによって増加します。結果は試行ごとに平均化されます。重要度サンプリング推定量の分散は次のように簡単に示されます。 ${\displaystyle p_{t}\,}$${\displaystyle f_{*}\,}$${\displaystyle t\,}$${\displaystyle W\,}$${\displaystyle K\,}$

${\displaystyle {\begin{aligned}\operatorname {var} _{*}{\widehat {p}}_{t}&={\frac {1}{K}}\operatorname {var} _{*}[1(X\geq t)W(X)]\\[5pt]&={\frac {1}{K}}\left\{{E_{*}}[1(X\geq t)^{2}W^{2}(X)]-p_{t}^{2}\right\}\\[5pt]&={\frac {1}{K}}\left\{{E}[1(X\geq t)W(X)]-p_{t}^{2}\right\}\end{aligned}}}$

ここで、重要度サンプリング問題は、重要度サンプリング推定値の分散が一般的なモンテカルロ推定値の分散よりも小さくなるようなバイアス密度を見つけることに焦点を当てています。分散を最小化し、特定の条件下でそれをゼロに減らすバイアス密度関数は、最適バイアス密度関数と呼ばれます。 ${\displaystyle f_{*}\,}$

バイアス方法にはさまざまな種類がありますが、重要度サンプリングのアプリケーションでは次の 2 つの方法が最も広く使用されています。

ランダム変数を 1 より大きい数値で正にスケーリングして確率質量をイベント領域にシフトすると、密度関数の分散 (平均も) が増加する効果があります。これにより、密度の裾が重くなり、イベント確率が増加します。スケーリングは、おそらく最も古くから知られているバイアス方法の 1 つであり、実際に広く使用されています。実装が簡単で、通常、他の方法と比較して控えめなシミュレーション ゲインが得られます。 ${\displaystyle {X\geq t\ }}$${\displaystyle X\,}$

スケーリングによる重要度サンプリングでは、シミュレーション密度は、通常裾確率推定のためにスケーリングされたランダム変数の密度関数として選択される。変換により、 ${\displaystyle aX\,}$${\displaystyle a>1}$

${\displaystyle f_{*}(x)={\frac {1}{a}}f{\bigg (}{\frac {x}{a}}{\bigg )}\,}$

そして重み関数は

${\displaystyle W(x)=a{\frac {f(x)}{f(x/a)}}\,}$

スケーリングにより確率質量が目的のイベント領域に移動する一方で、質量が望ましくない補完領域にも押し込まれます。 がランダム変数の合計である場合、質量の拡散は次元空間で発生します。 この結果、 の増加に対する重要度サンプリング ゲインが減少することになり、次元効果と呼ばれます。 スケーリングによる重要度サンプリングの最新バージョンは、たとえば、異なるスケーリング係数を使用して複数のモンテ カルロ (MC) 分析を実行する、いわゆるシグマ スケール サンプリング (SSS) です。 他の多くの高収量推定方法 (最悪ケース距離 WCD など) とは対照的に、SSS は次元の問題にあまり悩まされません。 また、複数の MC 出力に対処しても、効率が低下しません。 一方、WCD と同様に、SSS はガウス統計変数用にのみ設計されており、WCD とは対照的に、SSS 方法は正確な統計コーナーを提供するようには設計されていません。 もう 1 つの SSS の欠点は、モデルとシミュレータの収束の問題などにより、大きなスケール係数での MC の実行が困難になる可能性があることです。さらに、SSS では、バイアスと分散のトレードオフが強く存在します。大きなスケール ファクターを使用すると、非常に安定した収量結果が得られますが、スケール ファクターが大きくなるほど、バイアス エラーも大きくなります。関心のあるアプリケーションで SSS の利点があまり重要でない場合は、他の方法の方が効率的であることがよくあります。 ${\displaystyle X<t\,}$${\displaystyle X\,}$${\displaystyle n\,}$${\displaystyle n\,}$${\displaystyle n\,}$

もう 1 つのシンプルで効果的なバイアス手法は、密度関数 (つまりランダム変数) の変換を使用して、その確率質量の大部分をまれなイベント領域に配置することです。変換は次元効果の影響を受けず、デジタル通信システムのシミュレーションに関連するいくつかのアプリケーションで効果的に使用されています。変換はスケーリングよりも優れたシミュレーション ゲインをもたらすことがよくあります。変換によるバイアスでは、シミュレーション密度は次のように表されます。

${\displaystyle f_{*}(x)=f(x-c),\quad c>0\,}$

ここで、はシフトの量であり、重要度サンプリング推定値の分散を最小化するように選択されます。 ${\displaystyle c\,}$

重要度サンプリングの基本的な問題は、システムの複雑さが増すにつれて、適切な偏りのある分布の設計が複雑になることです。複雑なシステムとは、少数の入力の複雑な処理がはるかに扱いやすいため、長いメモリを持つシステムです。この次元またはメモリは、次の 3 つの方法で問題を引き起こす可能性があります。

• 長いメモリ（深刻な符号間干渉（ISI））
• 未知のメモリ（ビタビデコーダ）
• おそらく無限のメモリ（アダプティブイコライザー）

原則として、これらの状況では重要度サンプリングの考え方は同じままですが、設計ははるかに難しくなります。この問題に対処するための効果的なアプローチは、基本的に、シミュレーションをいくつかのより小さく、より明確に定義されたサブ問題に分割することです。次に、重要度サンプリング戦略を使用して、より単純なサブ問題をそれぞれターゲットにします。シミュレーションを分割する手法の例としては、コンディショニングとエラー イベント シミュレーション (EES)、および再生シミュレーションがあります。

重要なサンプリング手法がどれぐらい効果的かを見極めるには、重要なサンプリング手法の使用による実行時間の節約を定量化できると便利です。一般的に使用されるパフォーマンス指標は で、これは重要なサンプリング推定量が MC 推定量と同じ精度を達成するまでのスピードアップ係数として解釈できます。推定量の分散は平均が扱いにくい場合は解析的に不可能な可能性が高いため、これは経験的に計算する必要があります。重要なサンプリング推定量を定量化する上で役立つその他の概念は、分散境界と漸近効率の概念です。関連する指標の 1 つに、いわゆる有効サンプル サイズ(ESS)があります。^[6]${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}$

分散はシミュレーションの唯一の可能なコスト関数ではなく、平均絶対偏差などの他のコスト関数がさまざまな統計アプリケーションで使用されます。ただし、分散は文献で主に扱われるコスト関数であり、これはおそらく信頼区間とパフォーマンス測定で分散が使用されるためでしょう。 ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}$

関連する問題として、この比率は、重み関数を計算するために必要な追加の計算時間を含まないため、重要度サンプリングによる実行時間の節約を過大評価するという事実があります。そのため、さまざまな方法で純実行時間の改善を評価する人もいます。おそらく、重要度サンプリングのより深刻なオーバーヘッドは、手法を考案してプログラムし、目的の重み関数を解析的に導出するのにかかる時間です。 ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}$

異なる提案分布、を共同でサンプル抽出に使用する場合、異なる適切な重み付け関数を使用することができます（例：^{[7] [8] [9] [10]}を参照）。適応設定では、提案分布、、は適応重要度サンプリングアルゴリズムの各反復で更新されます。したがって、提案密度の母集団が使用されるため、サンプリングと重み付けスキームの適切な組み合わせをいくつか使用できます。^{[11] [12] [13] [14] [15] [16] [17]}${\displaystyle g_{n}(x)}$${\displaystyle n=1,\ldots ,N,}$${\displaystyle x_{1},\ldots ,x_{N},}$${\displaystyle g_{n,t}(x)}$${\displaystyle n=1,\ldots ,N,}$${\displaystyle t=1,\ldots ,T,}$${\displaystyle t}$

• モンテカルロ法
• 差異の削減
• 層別抽出法
• 再帰的層別抽出法
• VEGASアルゴリズム
• 粒子フィルタ- 重要度サンプリングを使用する逐次モンテカルロ法
• 補助フィールドモンテカルロ
• 拒否サンプリング
• 可変ビットレート- 重要度サンプリングの一般的なオーディオアプリケーション

• Arouna , Bouhari (2004). 「適応型モンテカルロ法、分散削減テクニック」。モンテカルロ法とその応用。10 (1): 1–24。doi :10.1515/156939604323091180。S2CID 21949573  。
• Bucklew, James Antonio (2004)。『稀少事象シミュレーション入門』ニューヨーク: Springer-Verlag。
• Doucet, A.; de Freitas, N.; Gordon, N. (2001).シーケンシャルモンテカルロ法の実践. Springer. ISBN 978-0-387-95146-1。
• Ferrari, M.; Bellini, S. (2001). 「ターボ積コードの重要度サンプリングシミュレーション」ICC 2001. IEEE 国際通信会議。会議記録 (カタログ番号 01CH37240)。第 9 巻。pp. 2773–2777。doi :10.1109/ ICC.2001.936655。ISBN 978-0-7803-7097-5. S2CID  5158473。
• マゾンカ、オレグ（2016）。「 Easy as Pi：重要度サンプリング法」。ジャーナルオブリファレンス。16 。
• Oberg, Tommy (2001)。変調、検出、およびコーディング。ニューヨーク: John Wiley & Sons。
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)。「セクション 7.9.1 重要度サンプリング」。数値レシピ: 科学計算の技法(第 3 版)。ニューヨーク: Cambridge University Press。ISBN 978-0-521-88068-8. 2011年8月11日時点のオリジナルよりアーカイブ。2011年8月12日閲覧。
• Ripley, BD (1987)。確率的シミュレーション。Wiley & Sons。
• Smith, PJ; Shafi, M.; Gao, H. (1997). 「クイックシミュレーション: 通信システムにおける重要度サンプリング手法のレビュー」. IEEE Journal on Selected Areas in Communications . 15 (4): 597–613. doi :10.1109/49.585771.
• Srinivasan, R. (2002).重要度サンプリング - 通信と検出への応用. ベルリン: Springer-Verlag.

• ケンブリッジ大学のシーケンシャル モンテ カルロ法 (粒子フィルタリング) のホームページ
• 稀少イベントシミュレーションにおける重要度サンプリングの紹介、European journal of Physics。PDF ドキュメント。
• 稀少事象シミュレーションのための適応型モンテカルロ法 冬季シミュレーション会議