重点サンプリング法

${\displaystyle X\colon \Omega \to \mathbb {R} }$ を確率空間 ${\displaystyle (\Omega ,{\mathcal {F}},\mathbb {P} )}$ 上の確率変数とする。${\displaystyle \mathbb {P} }$ に関して ${\displaystyle X}$ の期待値 ${\displaystyle \mathbb {E} _{\mathbb {P} }[X]}$ を推定したいとする。${\displaystyle \mathbb {P} }$ に従う独立なサンプル ${\displaystyle X_{1},\ldots ,X_{n}}$ が得られれば、その期待値の経験的推定値は

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

となり、この推定の精度は ${\displaystyle X}$ の分散に依存する：

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

重点サンプリングの基本的な考え方は、${\displaystyle \mathbb {P} }$ に従って直接サンプリングするのが難しい場合や、推定値${\displaystyle \mathbb {E} _{\mathbb {P} }[X]}$の分散を減らしたい場合に、他の分布からサンプルを取得することである。

そのために、まず非負の確率変数 ${\displaystyle Y\geq 0}$ を選び、${\displaystyle \mathbb {E} _{\mathbb {P} }[Y]=1}$ かつ ${\displaystyle \mathbb {P} }$ にほとんど至る所で ${\displaystyle Y(\omega )\neq 0}$ を満たすようにする。そして、${\displaystyle Y}$ により定義される新たな確率分布 ${\displaystyle \mathbb {Q} }$ に対して

${\displaystyle \mathbb {E} _{\mathbb {P} }[X]=\mathbb {E} _{\mathbb {Q} }\left[{\frac {X}{Y}}\right].}$

が成り立つようにする。

この ${\displaystyle X/Y}$を ${\displaystyle \mathbb {Q} }$ の下でサンプリングすることで、${\displaystyle \mathbb {E} _{\mathbb {P} }[X]}$ を推定できる。この推定の分散が

${\displaystyle \operatorname {var} _{\mathbb {Q} }\left[{\frac {X}{Y}}\right]<\operatorname {var} _{\mathbb {P} }[X].}$となれば、推定はより精度の高いものになる。

${\displaystyle X}$ が常に一定の符号を持つ場合、理想的な選択は ${\displaystyle Y^{*}={\frac {X}{\mathbb {E} _{\mathbb {P} }[X]}}\geq 0}$ であり、このとき ${\displaystyle X/Y^{*}}$ は定数 ${\displaystyle \mathbb {E} _{\mathbb {P} }[X]}$となり、1つのサンプルのみで期待値が得られることになる。しかしながら、${\displaystyle \mathbb {E} _{\mathbb {P} }[X]}$が求める値である以上、このような ${\displaystyle Y^{*}}$を選ぶことは現実的ではない。この理論的な最適ケース${\displaystyle Y^{*}}$ から、重点サンプリングについて重要な洞察を得られる。それは、${\displaystyle X}$ の「重要な」値に対してサンプルを集中させ、その貢献度に応じて重みを付けていることである。すなわち、通常の分布ではなく、${\displaystyle \mathbb {E} _{\mathbb {P} }[X]}$ への貢献度に比例するように分布を再構築する。このことが「重点サンプリング」と呼ばれる理由である。

この手法は、解析的に扱うのが困難な確率モデルにおいて、事後分布や期待値の推定に頻繁に用いられる。例として、ベイジアンネットワークや、重み付き変分オートエンコーダなどがある^[4]。

Summarize Timeline Top Qs Fact Check

重点サンプリングは、モンテカルロ法における分散減少法である。重点サンプリングの背景には、シミュレーション内で入力となる確率変数の中に、推定しようとするパラメータに対して他よりも大きな影響を与えるものがあるということがある。もしそれらの重要な値をより頻繁にサンプリングするようにすれば、推定量の分散を削減することができる。したがって、重点サンプリングの基本的な手法は、重要な値を「強調する」ような分布を選択することである。このような「バイアスのある」分布をシミュレーションに直接適用すると推定量にバイアスが生じる。しかしながら、シミュレーション出力に重みを与えてこのバイアスを補正することで、新しい重点サンプリング推定量は不偏（バイアスがない）になる。この重みは、真の基礎分布に対するバイアス付きシミュレーション分布のラドン＝ニコディム導関数、すなわち尤度比によって与えられる。

重点サンプリングシミュレーションを実装する際の基本的課題は、入力変数の重要な領域を強調するようなバイアス分布を選択することである。良いバイアス分布を選ぶことで大幅な実行時間の節約が可能になる一方で、悪い分布を選ぶと、通常のモンテカルロシミュレーションよりも長い実行時間がかかってしまう可能性がある。

${\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).}$

以下の分布 ${\displaystyle g^{*}(X)}$ がこの分散を最小にすることが示されている：

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

ただし、${\displaystyle X\geq 0}$の場合、この分散は 0 になる点に注意。

確率変数 ${\displaystyle X}$ が与えられており、その累積分布関数を ${\displaystyle F(x)}$、確率密度関数を ${\displaystyle f(x)=F'(x)\,}$（ここでプライム記号は導関数を表す）とする。イベント ${\displaystyle X\geq t}$ が生じる確率 ${\displaystyle p_{t}\,}$をシミュレーションにより推定する例を考える。独立同分布（i.i.d.）に従う長さ ${\displaystyle K}$ の列 ${\displaystyle X_{i}\,}$ を、分布 ${\displaystyle F}$ から生成し、閾値 ${\displaystyle t}$ を超える乱数の個数を ${\displaystyle k_{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 \mathbb {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\geq t\ }}$ がより頻繁に発生し、一定の推定量の分散を保ちながら必要なサンプル数 ${\displaystyle K}$ を削減できる。また、同じ ${\displaystyle K}$ に対しては、通常のモンテカルロ推定よりも小さな分散を得ることができる。

定義から、${\displaystyle p_{t}\,}$に対して以下のように ${\displaystyle f_{*}\,}$を導入できる：

${\displaystyle {\begin{aligned}p_{t}&=\mathbb {E} [1_{\{X\geq t\}}]\\[6pt]&=\int 1_{\{x\geq t\}}{\frac {f(x)}{f_{*}(x)}}f_{*}(x)\,dx\\[6pt]&=\mathbb {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_{*}}$

これは ${\displaystyle p_{t}\,}$ の重点サンプリング推定量であり、不偏である。すなわち、推定手順としては、${\displaystyle f_{*}\,}$ に従ってi.i.d.なサンプルを生成し、それらが ${\displaystyle t\,}$を超えた場合に、重み関数 ${\displaystyle W\,}$を評価してその値を加算する。結果は ${\displaystyle K\,}$回の試行で平均される。

この重点サンプリング推定量の分散は、次のように簡単に求められる：

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

さて、重点サンプリングの課題は、重点サンプリング推定量の分散が、一般的なモンテカルロ推定法の分散よりも小さくなるようなバイアス付き密度関数 ${\displaystyle f_{*}\,}$ を見つけることである。あるバイアス付き密度関数がこの分散を最小化し、さらに特定の条件下では分散をゼロにまで減らすことができる場合、そのような関数は「最適なバイアス付き密度関数（optimal biasing density function）」と呼ばれる。

重点サンプリングには様々なバイアス手法が存在するが、以下の2つの手法が最も広く応用されている。

確率変数 ${\displaystyle X\,}$ を1より大きい係数で正のスケーリングを行うことにより、イベント領域 ${\displaystyle {X\geq t\ }}$ に確率質量を移動させる。これによって、密度関数の分散（および平均）も増加し、密度の裾が重くなってイベントの発生確率が増加する。スケーリングは最も古くから知られているバイアス手法の1つであり、実務において広く使用されてきた。実装が簡単であり、他の方法と比べて堅実なシミュレーション利得をもたらすことが多い。

スケーリングによる重点サンプリングでは、スケーリングされた確率変数 ${\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)}}\,}$

スケーリングはイベント領域に確率質量を移動させるが、同時に補集合領域（すなわち${\displaystyle X<t\,}$）にも質量を押しやってしまうという副作用がある。もし ${\displaystyle X\,}$ が ${\displaystyle n\,}$ 個の確率変数の和である場合、この分布の広がりは ${\displaystyle n\,}$ 次元空間にわたって発生する。これにより、重点サンプリングの利得が ${\displaystyle n\,}$ の増加に従って減少することになり、これを「次元効果（dimensionality effect）」と呼ぶ。

スケーリングの現代的な応用例として「シグマスケーリング法（sigma-scaled sampling、SSS）」がある。これは、異なるスケーリング係数を用いて複数のモンテカルロ解析を実行するものである。SSSは、高収率推定法（例えばworst-case distances：WCD）とは異なり、次元効果の影響をあまり受けない。また、複数のモンテカルロ出力を扱っても効率が劣化しない。

ただし、WCDとは異なり、SSSはガウス統計変数のみを対象として設計されており、統計的な「コーナー」を正確に再現するようには設計されていない。さらに、スケーリング係数が大きい場合、モデルやシミュレータの収束問題によりシミュレーションが困難になることがある。

また、SSSには「バイアスと分散のトレードオフ」問題がある：スケーリング係数を大きくすれば結果は安定するが、バイアス誤差も増大する。もし特定の応用においてSSSの利点が重要でない場合、他の手法のほうが効率的である可能性が高い。

もう一つの単純かつ効果的なバイアス付け手法は、確率密度関数（したがって確率変数）を平行移動することで、その確率質量の大部分をまれな事象の領域に配置するものである。平行移動は次元効果の影響を受けず、データ転送システムのシミュレーションなど、いくつかの応用において成功裏に使用されてきた。この方法はしばしば、スケーリングよりも優れたシミュレーション上の利得をもたらす。

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

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

重点サンプリングにおける根本的な課題は、システムの複雑さが増すにつれて、良好なバイアス分布を設計することがますます困難になることである。複雑なシステムとは、入力数が少なくても複雑な処理を行う「長期記憶」を持つシステムを指す。この次元性（または記憶）によって、以下の3つの側面で問題が生じる可能性がある：

• 過去の入力が現在の出力に影響する(深刻な符号間干渉)
• 入力系列の全体を見ないと出力を決められない
  • 例：ビタビ復号器（英語版）
• メモリが（理論上）無限になる可能性がある
  • 例：適応等化器（英語版）

原理的には、こうした状況でも重点サンプリングの基本的な考え方は変わらないが、設計はより困難になる。この問題に対する有効なアプローチの1つは、シミュレーション全体を、より明確に定義された複数の小さな問題に分割することである。その後、それぞれの単純化された問題に対して重点サンプリング戦略を適用する。シミュレーションを分割するための手法としては、「条件付け（conditioning）」や「エラー事象シミュレーション（error-event simulation, EES）」、「再生シミュレーション（regenerative simulation）」などがある。

重点サンプリング手法の有効性を特定するには、重点サンプリングを使用したことによる実行時間の節約量を定量化できることが有用である。一般的に用いられる性能指標は、${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}$であり、これは、重点サンプリング推定器が、通常のモンテカルロ推定器と同じ精度を達成するのに必要な速度向上係数として解釈される。この値は、推定量の平均が解析的に求まらない場合が多いため、経験的に算出する必要がある。重点サンプリング推定器を評価する上で有用な他の概念としては、分散の上限や、漸近効率性（asymptotic efficiency）の概念がある。これに関連する指標として、「有効サンプルサイズ（Effective Sample Size、ESS）」がある^[5]。

シミュレーションの損失関数は一つではないが、多くの文献では、損失関数として分散が用いられている。

分散を損失関数に用いる場合の問題として、比率 ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}$ は、重み関数を計算するために必要な追加の計算時間を含まないため、重点サンプリングによる実行時間の節約を過大評価してしまうことが挙げられる。したがって、実際の実行時間の改善を評価するために、さまざまな他の手法が用いられる場合がある。それには重点サンプリングにおける重大なオーバーヘッド、すなわち技術の考案やプログラミングに必要な時間、および目的とする重み関数を解析的に導出するために必要な時間を考慮する必要がある。

異なる提案分布 ${\displaystyle g_{i}(x)}$, ${\displaystyle i=1,\ldots ,n,}$を用いてサンプル${\displaystyle x_{1},\ldots ,x_{n},}$ を同時に生成する場合、さまざまな適切な重み付け関数を使用することができる（参照^[6][7][8][9]）。

適応的な設定では、提案分布 ${\displaystyle g_{i,t}(x)}$, ${\displaystyle i=1,\ldots ,n,}$ ${\displaystyle t=1,\ldots ,T,}$が、適応的な重点サンプリングアルゴリズムの各イテレーション t で更新される。つまり、複数の提案密度を使用するため、サンプリングと重み付けスキームの適切な組み合わせがいくつも採用可能となる。これにより、提案分布の多様性を活かした柔軟な重点サンプリングが可能になり、特に高次元問題や複雑な分布に対して効率的な推定が行える^{[10][11][12][13][14][15][16]}。

• モンテカルロ法
• 分散減少法
• 層化抽出法
• モンテカルロ積分
• 粒子フィルタ
• 可変ビットレート