2025-04-08 Stanford AA228V: 適応的重要度サンプリングの探求

※本記事は、スタンフォード大学のコース「AA228V：安全性重要システムの検証」の講義「適応的重要度サンプリング」の内容を基に作成されています。コースの詳細情報は https://aa228v.stanford.edu/ でご覧いただけます。また、テキストブックは https://algorithmsbook.com/validation/ で入手可能です。本記事では、講義の内容を要約しております。なお、本記事の内容は原講義の内容を正確に反映するよう努めていますが、要約や解釈による誤りがある可能性もありますので、正確な情報や文脈については、オリジナルの講義映像をご視聴いただくことをお勧めいたします。

【登壇者紹介】 シドニー・カッツ（Sydney Katz）：スタンフォード大学のポスドク研究員。詳細なプロフィールは https://sydneymkatz.com/ でご覧いただけます。

コースへの登録や詳細情報については https://online.stanford.edu/courses/a... をご参照ください。スタンフォード・オンラインを通じて、スタンフォード大学の各学部が提供する学術的・専門的教育にアクセスすることができます。

1. 重要度サンプリング (Importance Sampling) の復習

1.1 直接推定法の限界と重要度サンプリングの導入

Sydney Katz：前回の講義ではさまざまな分布について説明し、多くの概念が登場しました。今日はそれらを整理し、重要度サンプリングの核心部分を理解できるようにしたいと思います。

重要度サンプリングを導入した理由を振り返りましょう。まず直接推定アルゴリズムでは、公称軌道分布（nominal trajectory distribution）からサンプリングして確率を推定していました。しかし、この方法には大きな問題があります。失敗事象が稀である場合、サンプリングしてもまったく失敗例が得られない可能性があり、その場合は確率推定値がゼロになってしまいます。

また、直接推定の推定量の分散を見ると、失敗確率が減少するにつれて分散が増加することがわかります。つまり、失敗確率が低くなるほど推定器の精度が下がるということです。この問題を修正するには、より多くのサンプルが必要になりますが、数十億ものサンプルが必要になる可能性があり、非常に非効率的です。

そこで異なるアプローチとして、公称分布とは異なる分布からサンプリングする方法を考えました。この新しい分布を「提案分布（proposal distribution）」と呼び、Q(τ)と表記します。提案分布のアイデアは、公称分布よりも多くの失敗例を生成するような分布を選ぶことです。

例えば、ある特定のQ(τ)を選ぶと、この分布からのサンプリングで失敗例をいくつか得ることができました。しかし、ここで課題となるのは、我々が推定したいのは公称分布下での失敗確率だということです。そのため、単に失敗数をサンプル総数で割るだけでは、提案分布下での失敗確率を求めることになってしまいます。

公称分布下での失敗確率を正確に推定するためには、サンプルを公称分布下での尤度に基づいて重み付けする必要があります。具体的には、各サンプルの重みは公称分布下での尤度を提案分布下での尤度で割った値になります。

Plutoノートブックで示したように、提案分布の選択は非常に重要です。いくつかの提案分布は他よりも優れた結果をもたらします。例えば、シンプルなガウス分布で閾値が-2の場合を考えると、直接推定に比べて、失敗分布の高尤度領域に中心を置いた青い提案分布を使用すると、分散が低く精度の高い推定が可能になります。

一方で、悪い提案分布を選ぶこともあり得ます。例えば、オレンジ色の提案分布は失敗には確かにサンプリングしますが、確率質量の低い失敗に高い尤度を割り当てているため、直接推定よりも悪い結果になる可能性があります。

このように、良い提案分布を選ぶことが重要度サンプリングの成功にとって極めて重要なのです。

1.2 提案分布の選択の重要性

Sydney Katz：前節で述べたように、重要度サンプリングにおいて適切な提案分布を選択することは成功の鍵です。提案分布によって推定の精度と効率が大きく変わってきます。

重要度サンプリングの推定量の分散について見てみましょう。この分散の式を詳しく導出はしませんでしたが、式の形を見ると、特定の密度関数をQ(τ)に代入した場合、分散がゼロになり、最適な推定量が得られることがわかります。

具体的には、失敗分布をQ(τ)として使用した場合、推定量の分散はゼロになります。ここで重要なのは、失敗分布の正規化定数が、実は私たちが求めようとしている失敗確率そのものだということです。つまり、最適な提案分布を使おうとすると、既に知りたい答え（失敗確率）を知っている必要があるという循環的な問題に直面します。

これが私たちの重要な気づきです：最適な提案分布は失敗分布そのものですが、失敗分布の正規化された密度を知るためには失敗確率を知る必要があり、それは我々が推定しようとしているものです。したがって、次善の策として、私たちは密度を計算できる分布の中から、失敗分布にできるだけ近い提案分布を選ぶことを目指します。

これが、様々な重要度サンプリングアルゴリズムで行われている革新の本質です。これらのアルゴリズムは、最適な提案分布（失敗分布）から直接サンプリングできないことを知りつつ、密度を計算できる分布の中からできるだけそれに近い提案分布を選ぶことを目指しています。

提案分布を選ぶ際のもう一つの重要な注意点があります。前回の講義で質問がありましたが、当時は飛ばしてしまいました。それは、提案分布は失敗が可能なすべての軌道に対して非ゼロの確率密度を割り当てる必要があるということです。つまり、失敗分布の密度が非ゼロであるすべての場所で、提案分布の密度も非ゼロでなければなりません。

例えば、左側の例ではガウス分布を提案分布として使用していますが、ガウス分布はどこにでも非ゼロの確率を割り当てるため、この条件は満たされています。一方、右側の一様分布の例では、失敗分布の密度が非ゼロであるのに提案分布が密度を割り当てていない領域が存在する可能性があります。そのような場合、我々はその領域の失敗をサンプリングすることができず、重要度サンプリング推定量は不正確になります。

これらの条件を満たす良い提案分布を選ぶことが、重要度サンプリングを効果的に使うための鍵となります。

1.3 最適な提案分布とその限界

Sydney Katz：先ほど説明したように、推定量の分散を最小化する観点から見ると、最適な提案分布は失敗分布そのものです。しかし、この最適な提案分布を直接使用するには大きな障害があります。

失敗分布の密度は、失敗領域における公称軌道分布の密度を正規化したものですが、その正規化定数は失敗確率そのものです。つまり、最適な提案分布を知るためには、既に我々が求めようとしている失敗確率を知っていなければならないという循環的な問題が生じます。

この問題から、以下の重要な結論が導かれます：最適な提案分布は失敗分布ですが、失敗分布の正規化された密度を知るためには失敗確率が必要で、それは私たちが推定しようとしている対象そのものです。従って、次善の策として、我々は密度を計算できる分布の中から、失敗分布にできるだけ近い提案分布を選ぶことを目指します。

これが、様々な重要度サンプリングアルゴリズムに共通する革新の本質です。これらのアルゴリズムは、最適な提案分布（失敗分布）から直接サンプリングできないことを理解しつつ、密度を計算できる分布の中からできるだけそれに近い提案分布を選ぶ方法を探求しています。

この章の残りの部分では、良い提案分布を得るための様々なアプローチを見ていきます。一つの選択肢は手動で設計することです。プロジェクト1で行ったように、失敗分布がどのような形をしているかについて直感的な理解があれば、それに類似した分布を選ぶことができます。ヒントとしては、プロジェクト1で使用したファジング分布をプロジェクト2の提案分布の出発点として使うと良いでしょう。

しかし、手動設計は常に機能するわけではありません。特に複雑なシステムでは、失敗分布の形状が分からず、適切な提案分布を選ぶことが非常に難しい場合があります。そのため、より適応的または自動的なアプローチが必要になります。

前回の講義で説明したもう一つのオプションは、失敗分布からサンプルを生成し、それにパラメトリックな分布をフィッティングする方法です。失敗分布の正規化された密度は計算できなくても、マルコフ連鎖モンテカルロ法や棄却サンプリングを使って失敗分布からサンプルを生成することは可能です。そして、これらのサンプルに対して、密度を計算できる分布クラス（例えばガウス分布）をフィッティングすることで、失敗分布に近い提案分布を得ることができます。

前回の講義の最後で示したように、このアプローチは効果的です。公称分布からのサンプルと比較して、失敗分布のサンプルにフィッティングされた提案分布を使用すると、推定の精度が大幅に向上します。

しかし、このアプローチにも二つの大きな課題があります。一つ目は、失敗分布からサンプルを生成することそのものが非自明なタスクであることです。棄却サンプリングやMCMCの実装は複雑で、困難な場合があります。二つ目の課題は、高次元で複数の失敗モードを持つ複雑な失敗分布に対して、適切な分布クラスとパラメータを選ぶことが難しい場合があることです。

今日の講義では、これらの課題に対処するための様々な手法について詳しく見ていきます。特に、失敗分布からのサンプリングなしに良い提案分布を得る方法や、複雑な失敗分布に対応するための手法に焦点を当てていきます。

2. クロスエントロピー法 (Cross-Entropy Method)

2.1 初期提案分布からのサンプリング

Sydney Katz：先ほど説明した最初の課題に対処するために、クロスエントロピー法について考えてみましょう。この方法では、失敗分布からのサンプリングという難しい問題を回避しながら、良い提案分布を見つけることを目指します。

具体的な問いとして考えてみましょう：失敗分布からのサンプリングが難しい場合に、他の分布、つまりサンプリングが容易な分布からサンプルを得て、それでも良い提案分布をフィッティングできないでしょうか？

クロスエントロピー法はこの問いに対する解決策の一つです。これは適応的重要度サンプリングの一形態であり、マイケル・コッヘンダーファー教授が特に好きな方法です。この方法に続いて、複数重要度サンプリングとその適応版である集団モンテカルロ法、そして逐次モンテカルロ法についても説明します。最後に、正規化定数の比率という発展的なトピックに簡単に触れます。これは難しいトピックでクイズには出ませんが、いくつか良いジョークがあるので簡単に紹介します。

クロスエントロピー法では、まず最初のステップとしてサンプリングしやすい初期提案分布から始めます。これは重要なポイントで、MCMCなどの複雑な方法を使わずに直接サンプリングできる分布である必要があります。

次に、これらのサンプルを使って新しい提案分布をフィッティングします。この新しい分布もサンプリングが容易なモデルクラスから選びます。フィッティングの基準としては、提案分布と失敗分布間のクロスエントロピーを最小化するようにパラメータを選びます。

クロスエントロピーとは何かを簡単に説明すると、二つの分布間の「距離」のようなものと考えることができます。クロスエントロピーを最小化することで、提案分布と失敗分布の距離を最小化することを目指します。これは我々の目標と一致しています：失敗分布にできるだけ近い提案分布を見つけることです。

多くの一般的な分布クラス、例えばガウス分布では、クロスエントロピーの最小化は実質的に重み付き最尤推定と同等になります。ガウス分布の場合、サンプルに重みを付けて、重み付き平均と重み付き標準偏差を計算するだけで済みます。

これらの重みは基本的に重要度サンプリングの重みと同じです。失敗していないサンプルの重みはゼロになります（失敗分布にマッチさせたいので、失敗でないサンプルは無視します）。そして、失敗分布の下でより高い尤度を持つサンプルほど、より高い重みを持ちます。

この方法を実装する前に、初期提案分布を選ぶ必要があります。良い選択肢は何でしょうか？

【学生】：ガウス分布はどうでしょうか。

Sydney Katz：そうですね、ガウス分布は良い選択です。特に、我々が扱っているシンプルなシステムでは、公称軌道分布がガウス分布になっています。この分布からのサンプリングは簡単で、単にロールアウト（システムの時間発展のシミュレーション）を実行するだけです。また、密度の計算も容易で、見たすべての初期状態と外乱の確率を掛け合わせるだけです。

ここで注意が必要なのは、τは一つの変数ではなく、多くのコンポーネントを持つ複雑なオブジェクトであることです。実際の計算では、これらの確率の計算や操作が実用的かどうかという考慮が必要です。ただ、私たちはP(τ)のモデルを常に持っていると仮定しています。このモデルがあれば、公称軌道分布からのサンプリングはロールアウトを行うだけで可能であり、また軌道の確率計算も可能です。

軌道が非常に長い場合は計算が課題になるかもしれませんが、通常はそれ以前に他のスケーリングの問題に直面すると思います。これから説明する方法はより複雑になっていきますが、それはシンプルなガウス分布を超えて拡張する際に発生する問題に対処するためです。

2.2 クロスエントロピー最小化による新しい提案分布の適合

Sydney Katz：それでは、クロスエントロピー法の具体的な実装について見ていきましょう。まず、公称軌道分布からサンプルを多数生成します。図で示しているのがそれらのサンプルです。

次に、これらのサンプルを重み付けして、新しい分布をフィッティングします。黒色で示されているサンプルは失敗ではないため、重みがゼロになります。黄色のサンプルは失敗サンプルで、これらに重みが付けられます。この例では、初期提案として公称分布を使用したため、すべての失敗サンプルの重みが同じになっています。

基本的に行っていることは、黄色のサンプル（失敗サンプル）に対して紫色の分布をフィッティングすることです。黒いサンプルはすべて重みがゼロなので無視されます。このプロセスは、紫色の分布と失敗分布の間のクロスエントロピーを最小化することと同等です。失敗分布は明示的には表現できませんが、サンプルを通じて暗黙的に表現されています。

この方法を使った結果を見ると、直接推定に比べて大きな改善が見られます。直接推定は大きな分散を持ちますが、このフィッティングされた提案分布を使用すると、分散が小さく、より正確な推定が得られます。

では、閾値を-2からさらに下げて、失敗事象をより稀にした場合はどうなるでしょうか？閾値を下げると、失敗サンプルの数が減少していきます。次の段階では、領域内にサンプルが全くない状況になると予想されます。この場合、アルゴリズムはどうなるでしょうか？

【学生】：何もできなくなります。

Sydney Katz：その通りです。この時点からすべての重みがゼロになり、何も進められなくなります。つまり、この方法は失敗事象が非常に稀な場合には上手く機能しません。これは、我々が繰り返し直面している問題です：公称分布からのサンプリングでは稀な失敗に対処できません。

一つの解決策としては、十分なサンプルが得られるまでサンプリングを続けることも考えられますが、もっと効率的な方法を紹介します。

公称分布から始めて、失敗分布に向かって徐々に適応していく方法を考えてみましょう。一度に大きなジャンプを試みるのではなく、公称分布から始めて、徐々に小さなジャンプで失敗分布に近づけていきます。このプロセスは「適応的重要度サンプリング」と呼ばれます。適応的という名前の理由はまさに提案分布を適応させていくからです。

このアプローチの詳細について次のセクションで説明します。

2.3 反復的な閾値調整による適応

Sydney Katz：先ほど見たように、稀な失敗事象の場合、単純なクロスエントロピー法では十分なサンプルが得られない問題があります。そこで、適応的アプローチを導入します。

最初に、適応させる初期提案分布を選びます。例えば公称軌道分布などです。また、「失敗への近さ」の尺度も必要です。これまでと同様に、ロバスト性（robustness）、つまり失敗領域までの距離を使うことができます。

ここで一つ追加の要件として、失敗軌道に対しては全て、この関数f(τ)が0以下という条件を課します。これにより、「τが失敗である条件」と「f(τ)≤0である条件」が同等になります。なぜこのように書き換えるかはすぐに明らかになります。

このセットアップの下で、理想的には提案分布と失敗分布（P(τ|f(τ)≤0)）の間のクロスエントロピーを最小化したいところです。しかし、先ほど見たように、初期分布からサンプリングした場合、すべての重みがゼロになる可能性があり、クロスエントロピー最小化が行えない状況に陥ります。

そこで代わりに反復的なプロセスを導入します。各反復で以下のステップを実行します：

1. 現在の提案分布からサンプルを生成
2. 各サンプルに対してf(τ)を計算（失敗までの距離）
3. 上位M個の「エリートサンプル」を選択（Mはアルゴリズムのハイパーパラメータ）
4. これらのエリートサンプルの中で最も悪い（失敗から最も遠い）サンプルの目的関数値を閾値γとして設定
5. この閾値γを用いて、条件付き分布P(τ|f(τ)≤γ)とQ(τ)のクロスエントロピーを最小化

ここでの重要な違いは、完全な失敗（f(τ)≤0）を条件としているわけではなく、「失敗に少し近い」（f(τ)≤γ）という緩和された条件を用いていることです。この条件の下では、少なくともMエリット個のサンプルが非ゼロの重みを持つため、分布のフィッティングが可能になります。

このプロセスを繰り返すことで、徐々に失敗分布に近づけていきます。具体的には：

1. 更新された提案分布からサンプリング
2. エリートサンプルに基づいて閾値を計算
3. サンプルを重み付けして新しい分布をフィッティング

これを何回か反復すると、最終的に閾値γが0以下になり、十分な失敗サンプルが得られたことになります。そして最終的な提案分布が得られます。

【学生】：これは基本的に閾値γを左側（失敗領域）に向かって移動させ、最終的に失敗領域全体をカバーするということですか？

Sydney Katz：その通りです。この例では具体的に左側に移動していますが、より一般的には、何らかの「失敗への近さ」の指標に基づいて、徐々に失敗に近づいていくということです。例えば振り子の場合だと、倒れることに徐々に近づいていくような感じになります。

【学生】：毎回必ず失敗に近づくことは保証されていますか？

Sydney Katz：これは確率的なアルゴリズムなので、必ずしも保証されません。運が悪いと、意図した方向に進まないこともあります。

【学生】：失敗領域に到達した後も、閾値を調整し続けますか、それとも二値的な目標に戻りますか？

Sydney Katz：閾値がゼロを下回らないようにします。実際、これは本のコードに記載されている詳細ですが、閾値γは常にゼロと比較して大きい方の値を使います。なぜなら、閾値をゼロより小さく設定すると、その分布にフィッティングすることになりますが、それは重要度サンプリングの良い提案分布にはなりません。

【学生】：もし失敗定義が単調でない場合、例えばコサイン関数のような形で、方向性が保証されなくなる問題がありますか？

Sydney Katz：難しい質問です。考えてみます。ただ、通常ロバスト性を使う場合、この問題は発生しないと思います。

【学生】：マルチモーダルな分布をフィッティングしたり、反復ごとに分布のタイプを変更することは可能ですか？

Sydney Katz：その通りです。複数の失敗モードがある場合、マルチモーダルな分布をフィッティングするのが望ましいでしょう。例えば、別の閾値が右側にもある場合、エリートサンプルは両方の領域に分かれるため、単一の分布をフィッティングするならば、混合分布（mixture）を使うのが適切でしょう。

最終的に、このプロセスが終了すると、失敗分布に近い提案分布が得られます。この例では、実際に失敗分布がどのようなものか知っているので、どれだけ近づけたかを確認できます。ガウス分布の制約の中で、かなり失敗分布に近い分布が得られています。

1次元のガウス分布から2次元のガウス分布に移行した例も見てみましょう。ここでも同様のプロセスが適用されます。公称分布は原点を中心としたガウス分布で、失敗領域は上方にあります。最初の反復では、公称分布からのサンプルが失敗領域と重ならないため、失敗領域に最も近いエリートサンプルを選択し、徐々に閾値を調整して失敗分布に近づけていきます。

2.4 エリートサンプルの選択と重み付け

Sydney Katz：クロスエントロピー法における重要な要素の一つが、エリートサンプルの選択と重み付けのプロセスです。この手法を詳しく見ていきましょう。

エリートサンプルとは、現在の提案分布から生成されたサンプルのうち、失敗に最も近いものを指します。具体的には、f(τ)の値が小さいサンプル、つまり失敗領域に最も近いM個のサンプルを選択します。ここでのMはアルゴリズムのハイパーパラメータであり、例えば上位50サンプルなどと設定します。

各反復において、現在の提案分布からサンプルを生成し、それぞれのf(τ)値（失敗までの距離）を計算します。そして、これらのサンプルをf(τ)の値でソートし、最も小さい値を持つM個のサンプルを「エリートサンプル」として選びます。

次に重要なステップは、閾値γの設定です。この閾値は、選ばれたM個のエリートサンプルの中で最も大きいf(τ)値（つまり「最も悪い」エリートサンプルの値）に設定されます。この閾値を用いることで、P(τ|f(τ)≤γ)という条件付き分布を定義します。

この条件付き分布は、完全な失敗分布P(τ|f(τ)≤0)の代わりに使用される「緩和された」分布です。完全な失敗まではいかなくても、失敗に「ある程度近い」サンプルを含む分布と考えることができます。

この条件設定により、少なくともM個のサンプル（エリートサンプル）が非ゼロの重みを持つことが保証されます。これらのサンプルを使って、重み付き最尤推定により次の提案分布をフィッティングします。

重みの計算方法は以下の通りです：

• f(τ)≤γを満たさないサンプル（エリートでないサンプル）の重みはゼロになります
• エリートサンプルの重みは、P(τ|f(τ)≤γ)に基づいて計算されます
• この重みは通常、P(τ)/Q(τ)に比例します（P(τ)は公称分布下での尤度、Q(τ)は現在の提案分布下での尤度）

このプロセスは、新しい提案分布が失敗に近いサンプルに集中するよう促します。各反復が進むにつれて、閾値γは徐々に小さくなり、提案分布は徐々に本当の失敗分布に近づいていきます。

【学生】：もし閾値γがゼロになったり、閾値以下のサンプルがなくなったりした場合はどうなりますか？

Sydney Katz：良い質問です。閾値γは常にゼロと比較して大きい方の値を使用します（γ = max(γ, 0)）。そして、十分な反復の後、エリートサンプルの中に実際の失敗サンプル（f(τ)≤0を満たすサンプル）が含まれるようになれば、それらのサンプルに基づいて最終的な提案分布をフィッティングすることができます。

【学生】：失敗の定義が単調でない場合、例えば|τ|>4のように両側に失敗領域がある場合はどうなりますか？

Sydney Katz：そのような場合は、マルチモーダルな提案分布、例えばガウス混合分布を使用することで対応できます。このようなシナリオでは、エリートサンプルが異なる失敗モード周辺に集まるため、それらをうまく表現できる分布クラスを選ぶことが重要です。

最終的に、十分な反復の後、提案分布は失敗分布により近くなります。この例では、実際の失敗分布と比較すると、ガウス形式の制約の中でかなり良い近似が得られていることがわかります。2次元ガウスの例でも、提案分布が反復を経て失敗領域に集中していく様子が確認できます。

このようにクロスエントロピー法は、直接失敗分布からサンプリングすることなく、反復的なプロセスを通じて良い提案分布を見つける効果的な方法を提供します。

3. 複数重要度サンプリング (Multiple Importance Sampling)

3.1 複数の提案分布の利用

Sydney Katz：次に紹介するのは複数重要度サンプリング（Multiple Importance Sampling）です。ここでは適応的なアプローチから少し離れて、重要度サンプリングの別のバージョンを考えます。

通常の重要度サンプリングでは、提案分布を一つだけ選ぶ必要があります。そのため、賢明に選択しなければなりません。しかし、私は決断力がないタイプなので、複数重要度サンプリングというアプローチが気に入っています。この方法では、一つではなく複数の提案分布を選ぶことができます。そうすれば選択の問題に悩む必要がなくなります。

複数重要度サンプリングでは、基本的に同じことを行いますが、複数の提案分布を使用する点が異なります。ステップは非常に似ています。まず、すべての提案分布からサンプルを生成します。各iは異なる提案分布を表し、特にQi(τ)は軌道iを生成するために使用された提案分布を示します。

例えば、Q1(τ)とQ2(τ)という2つの提案分布があるとします（もちろん2つ以上も可能です）。これらの分布からサンプルを生成します。例えば、Q1から複数のサンプルを生成し、Q2からも複数のサンプルを生成します。これらのサンプルを用いて失敗確率を推定します。

失敗確率の推定は、通常の重要度サンプリングと非常に似た方法で行います。重み付き和を取りますが、重みの計算は少し異なります。基本的には、各サンプルについて公称分布の下での密度をそのサンプルが生成された提案分布の下での密度で割ります。唯一の違いは、分母に使用する分布がそのサンプルが生成された特定の提案分布である点です。

この手法を標準複数重要度サンプリング（Standard Multiple Importance Sampling）またはSMISと呼びます。

ここで面白いのは、サンプルの重み付けには別の方法もあり、それも同様に有効だということです。このアイデアを理解するには少し時間がかかりましたが、考え方を説明します。

標準複数重要度サンプリングでは、データは特定のプロセスから生成されたと仮定しています。そのプロセスとは、まずQ1(τ)から複数のサンプルを生成し、次にQ2(τ)から複数のサンプルを生成するというものです。しかし、データが生成されるプロセスは他にも考えられます。

例えば、新しいサンプルを生成するたびに、Q1とQ2からランダムに選んでサンプリングするというプロセスも考えられます。例えば最初はQ2を選んでそこからサンプルを生成し、次のサンプルではQ1を選んでサンプルを生成し、その次はQ2を選ぶ、というように進めます。このプロセスは、Q1とQ2の混合モデル（mixture model）からサンプリングすることと同等です。この混合モデルをQmixと呼び、その密度は両方の分布の密度の平均になります。

つまり、すべてのサンプルがこの混合モデルからサンプリングされたと考えることもできるわけです。そうすると、重要度サンプルの重みは異なる形になります。この場合、サンプルの密度を計算する際に、分布の完全な混合を考慮することになります。

これは驚くべきことですが、両方の推定方法が機能します。ただし、混合モデルからサンプリングされたと仮定する後者の方法は、標準法よりも分散が低いことが示されています。そのため、場合によってはより良いパフォーマンスを発揮することがあります。

この考え方は最初は全く直感的ではありませんでしたが、両方のアプローチが理にかなっており、それぞれ異なる仮定に基づいていることを理解することが重要です。

【学生】：標準複数重要度サンプリングの式で、インデックスiとjの使い方が混乱しています。

Sydney Katz：すみません、それは私のミスです。式を修正します。ここでのインデックスiはサンプルを指し、Qiはそのサンプルが生成された特定の提案分布を示します。例えば2番目のサンプルがQ1から生成された場合、Qiはそのサンプルに対してQ1となります。スライドの表記を後で修正します。

3.2 標準複数重要度サンプリング (SMIS)

Sydney Katz：標準複数重要度サンプリング（Standard Multiple Importance Sampling、SMIS）の具体的な計算方法について詳しく説明します。

SMISでは、複数の異なる提案分布からサンプルを生成し、それらを組み合わせて失敗確率を推定します。各提案分布からのサンプルは、それぞれ別々に生成されます。例えば、Q₁(τ)から一定数のサンプルを生成し、次にQ₂(τ)から一定数のサンプルを生成します。

生成されたすべてのサンプルを用いて、失敗確率の推定を行います。この推定は以下の式で表されます：

P(failure) ≈ (1/N) × Σᵢ wᵢ × I(τᵢ ∈ failure)

ここで、wᵢは各サンプルの重みであり、I(τᵢ ∈ failure)は失敗指示関数です（サンプルが失敗なら1、そうでなければ0）。

標準複数重要度サンプリングにおける重みの計算は非常に直感的です。各サンプルの重みは以下のように計算されます：

wᵢ = P(τᵢ) / Qⱼ(τᵢ)

ここで、P(τᵢ)はサンプルτᵢの公称分布下での密度であり、Qⱼ(τᵢ)はそのサンプルが生成された特定の提案分布jの下での密度です。つまり、サンプルがどの提案分布から来たかを追跡し、その特定の提案分布の下での密度を使って重みを計算します。

例えば、あるサンプルがQ₁から生成された場合、その重みはP(τᵢ)/Q₁(τᵢ)になります。別のサンプルがQ₂から生成された場合、その重みはP(τᵢ)/Q₂(τᵢ)になります。

【学生】：SMISの計算において、サンプルはそれぞれの提案分布から生成されると理解していますが、それを反映するために式の中でjではなくiを使うべきではないですか？

Sydney Katz：ご指摘ありがとうございます。表記に混乱があったようです。実際には、サンプルiがどの提案分布から来たかを示すために、Qᵢ(τᵢ)とすべきでした。ここでQᵢはサンプルiが生成された提案分布を表します。例えば、サンプル3がQ₁から生成された場合、そのサンプルの重み計算にはQ₁の密度が使われます。

この方法の重要なポイントは、各サンプルがどの提案分布から生成されたかを追跡し、その特定の提案分布の下での密度を使って重みを計算することです。これにより、複数の提案分布からサンプリングしながらも、正確な失敗確率の推定が可能になります。

SMISは通常の重要度サンプリングの自然な拡張であり、複数の提案分布を使用することで、単一の分布では捉えきれない複雑な失敗分布をより効果的に近似できるようになります。また、複数の提案分布を使うことで、どの提案分布が最適かという選択の問題を緩和することができます。

後ほど具体的な例を見ていきますが、まずは別の重み付け方法について説明します。それは決定論的混合アプローチと呼ばれるものです。

3.3 決定論的混合分布による重み付け

Sydney Katz：標準複数重要度サンプリング（SMIS）の他に、もう一つの重み付け方法があります。これは同様に有効であり、場合によってはより良い結果をもたらします。この方法は決定論的混合（deterministic mixture）アプローチと呼ばれています。

標準複数重要度サンプリングでは、データ（サンプル）が特定のプロセスから生成されたと仮定しています。そのプロセスとは、まずQ₁からいくつかのサンプルを生成し、次にQ₂からいくつかのサンプルを生成するというものです。しかし、同じデータが異なるプロセスから生成されたと考えることも可能です。

決定論的混合アプローチでは、各サンプルを生成する際に以下のプロセスを想定します：

1. 新しいサンプルを生成するたびに、Q₁とQ₂の間でランダムに選択する
2. 選ばれた分布からサンプルを生成する
3. 次のサンプルでも同様にランダムに分布を選び、サンプルを生成する
4. これを必要なサンプル数だけ繰り返す

例えば、最初のサンプルではQ₂を選んでサンプリングし、次のサンプルではQ₁を選んでサンプリング、その次はまたQ₂を選ぶといった具合です。このプロセスは実質的に、Q₁とQ₂の混合モデル（mixture model）からサンプリングしているのと同等です。この混合モデルをQ_mixと呼び、その密度は以下のように表されます：

Q_mix(τ) = (Q₁(τ) + Q₂(τ)) / 2

つまり、すべてのサンプルがこの混合モデルQ_mixからサンプリングされたと考えることができるのです。そうすると、重要度サンプルの重みは以下のように計算されます：

w_i = P(τi) / Q_mix(τi) = P(τi) / ((Q₁(τi) + Q₂(τ_i)) / 2)

この式では、サンプルの密度を計算する際に、元の分布の完全な混合を考慮しています。サンプルがどの提案分布から実際に生成されたかに関わらず、混合分布の密度を使って重みを計算します。

この考え方は最初は直感的ではありませんでしたが、両方のアプローチが理論的に正しいということを理解することが重要です。驚くべきことに、この決定論的混合アプローチは、標準複数重要度サンプリングよりも分散が低いことが示されています。つまり、同じサンプル数でより正確な推定が可能になる場合があるのです。

【学生】：SMISと比較して、サンプリングのプロセス自体は同じですが、重みの計算方法だけが異なるということですか？

Sydney Katz：その通りです。サンプリングのプロセスは同じままです。つまり、Q₁からいくつかのサンプル、Q₂からいくつかのサンプルを生成します。変わるのは、生成された後のサンプルの解釈と重み付けの方法です。決定論的混合アプローチでは、すべてのサンプルがQ_mixという混合分布から生成されたと「仮定」します。実際のサンプリングプロセスは変わりませんが、重みの計算方法が変わるのです。

【学生】：混合分布の合計が1になるように正規化する必要はないのですか？

Sydney Katz：良い質問です。実際には、混合分布の密度はQ_mix(τ) = (Q₁(τ) + Q₂(τ)) / 2のように計算されます。ここでの除算は、混合比率を考慮した正規化を行っています。この例では各分布の重みを1/2としていますが、一般的には異なる重みを持つこともあります。いずれにせよ、合計が1になるように正規化することが重要です。

決定論的混合アプローチは直感的ではないかもしれませんが、理論的に根拠があり、多くの場合において分散を減少させる効果があります。これから具体的な例を見ていくことで、この方法の有効性をより明確に理解できるでしょう。

3.4 2Dガウス分布の失敗モード例

Sydney Katz：ここで、複数重要度サンプリングの効果を示す具体的な例を見てみましょう。2次元ガウス分布の問題に戻り、今度は2つの失敗モードがある場合を考えます。

この例では、左上隅と右上隅に2つの失敗領域があります。公称軌道分布は原点を中心とした単位分散を持つガウス分布です。失敗分布は、この公称分布を失敗領域で切り取ったものになります。

この設定において失敗分布を視覚化すると、2つのコーナー部分に確率質量が集中しています。特に、これらの「前面コーナー」では尤度が非常に高くなっています。これは原点から遠ざかるほど公称分布の尤度が低くなるためです。失敗確率を正確に推定するためには、これらの高尤度領域からサンプリングすることが重要です。

ここで、重要度サンプリングと複数重要度サンプリングのアプローチを比較してみましょう。もし単一の重要度サンプリング提案分布を選ぶ場合、例えばガウス分布を使うなら、両方の失敗モードをカバーするのに十分な大きさの分布を選ぶ必要があります。

しかし、複数重要度サンプリングを使えば、複数の提案分布を選ぶことができます。この例では、重要だと思われる領域をカバーするために複数の分布を配置しています。つまり、各失敗モードに対して別々の提案分布を用意することができるのです。

結果を見ると、複数重要度サンプリングは通常の重要度サンプリングよりも優れたパフォーマンスを示しています。グラフでは、通常の重要度サンプリング推定器は灰色で示されており、大きな分散を持っています。一方、複数重要度サンプリングを使用した場合の推定器は分散が小さくなっています。

さらに興味深いことに、先ほど説明した決定論的混合法による重み付けを行うと、標準複数重要度サンプリングよりもさらに良い結果が得られる場合があります。グラフでは、決定論的混合による推定器がより良いパフォーマンスを示しています。

この例は、複数の失敗モードを持つ複雑な分布に対して、複数重要度サンプリングが効果的であることを示しています。単一の提案分布では捉えきれない複雑さを、複数の提案分布を組み合わせることで効率的に近似できるのです。

ただし、複数重要度サンプリングを使用する際の課題として、複数の提案分布をどのように選ぶかという問題があります。これは単一の提案分布を選ぶ問題より複雑になります。次のセクションでは、この課題に対処するための方法として、集団モンテカルロ法（Population Monte Carlo）について説明します。この方法では、複数重要度サンプリングの提案分布を適応的に改善することができます。

4. 集団モンテカルロ法 (Population Monte Carlo)

4.1 複数提案分布の適応的改善

Sydney Katz：クロスエントロピー法では、単一の提案分布を選ぶ際の難しさに取り組み、それを適応的に改善する方法を見てきました。同様の考え方を複数重要度サンプリングに適用することもできます。つまり、複数の提案分布を選ぶという難しさがあるなら、それを適応的に改善していくことを考えてみましょう。

集団モンテカルロ法（Population Monte Carlo）は、まさにこのアプローチを取ります。このメソッドでは、複数の提案分布全体を適応させ、より良い提案分布の集合を得ることを目指します。

基本的なアイディアは「提案分布の集団（population）」を適応的に進化させるというものです。「集団」という言葉を使うのは、多数の提案分布を同時に扱うからです。これらの提案分布は、反復的なプロセスを通じて改善されていきます。

まず視覚的に理解するために、集団モンテカルロ法の基本的なプロセスを説明します。初めに、多数の提案分布を用意します。図に示されているように、それぞれの点や楕円はひとつの提案分布を表しています。これらの分布は空間全体にばらまかれています。

最初のステップでは、各提案分布から1つずつサンプルを生成します。図では、各提案分布から生成されたサンプルを示しています。これで、提案分布の数と同じだけのサンプルが得られました。

次に、これらのサンプルに対して重要度重みを計算します。失敗領域にないサンプルはすべて重みがゼロになります。失敗領域内のサンプルについては、公称分布の下での密度をそのサンプルが生成された提案分布の下での密度で割ったものが重みになります。図では、明るい色のサンプルほど高い重みを持っています。公称分布の密度が高い領域（原点に近い部分）ほど明るく表示されています。

これらの重みに基づいて、サンプルのリサンプリングを行います。重みが高いサンプル、つまり失敗領域内で公称分布の密度が高いサンプルほど高い確率で選ばれます。失敗領域外のサンプルは全て重みがゼロなので、リサンプリングでは選ばれません。

図を見ると、リサンプリング後のサンプル数が大幅に減ったように見えますが、実際にはサンプル数は同じです。重みの高いサンプルが複数回選ばれ、いくつかのサンプルが重なっているため、このように見えるのです。例えば、重要度の高い場所にあるひとつのサンプルが5回リサンプリングされると、その場所に5つのサンプルが重なって表示されます。

最後に、これらのリサンプルされたポイントに新しい提案分布を「配置」します。具体的には、各リサンプルされたサンプルを中心として、ある一定の分散を持つ新しい提案分布を作成します。図では、各サンプルの場所に新しい提案分布が配置されているのが分かります。

この時点で、我々は元の数と同じだけの提案分布を持っていますが、それらはより失敗領域に集中しています。そして、このプロセス全体を繰り返すことで、提案分布はさらに改善されていきます。

興味深いことに、この方法で自動的に見つけた提案分布の集合は、前に手動で設計した複数重要度サンプリングの提案分布とよく似ています。これは、この方法が効果的に良い提案分布を見つけることができることを示しています。

この適応的なアプローチにより、複数の提案分布を手動で選ぶ難しさが軽減され、効率的な重要度サンプリングが可能になります。

4.2 提案分布の集団の初期化

Sydney Katz：集団モンテカルロ法の最初のステップは、提案分布の初期集団を設定することです。この初期集団は、可能な軌道の空間全体をカバーするように広く分布させることが重要です。

具体的には、多数の初期提案分布を用意し、それらが探索空間全体に広がるようにします。これらの分布は、サンプリングが容易であり、密度計算も可能なものである必要があります。例えば、さまざまな場所に中心を持つガウス分布の集合などが適切な選択となります。

ここで特に強調したいのは、初期提案分布の集団が可能性の空間を可能な限り広くカバーすることの重要性です。もし初期分布が失敗領域をまったくカバーしていない場合、すべてのサンプルの重みがゼロになってしまい、クロスエントロピー法で見たのと同じ問題に直面することになります。失敗が非常に稀な場合、この問題は特に顕著になります。

実際、初期提案分布が空間全体を十分にカバーするようにすることは非自明なタスクであり、かなり難しい課題となることがあります。これは特に高次元空間や複雑な失敗モードを持つシステムで顕著になります。そのため、初期分布の選択には注意が必要です。

一般的なアプローチとしては、以下のような方法が考えられます：

1. 公称軌道分布を中心として、それよりも広い分散を持つ分布を複数用意する
2. 既知の失敗モードがある場合は、それらの領域に分布を配置する
3. システムの物理的な制約や特性に基づいて分布を配置する
4. ラテン超方格法（Latin Hypercube Sampling）などの空間充填手法を使って分布を配置する

これらのアプローチを組み合わせることで、空間を効果的にカバーする初期提案分布の集団を作成することができます。

この初期化プロセスは、集団モンテカルロ法の成功において極めて重要です。十分な初期カバレッジがなければ、アルゴリズムは失敗領域を見つけることができず、効果的な適応ができなくなります。特に稀な失敗事象を扱う場合には、初期分布の選択に十分な注意を払う必要があります。

初期提案分布の集団が適切に設定されたら、次のステップであるサンプリングとリサンプリングのプロセスに進むことができます。

4.3 重要度重みに基づくリサンプリング

Sydney Katz：集団モンテカルロ法の中心的なステップの一つが、重要度重みに基づくリサンプリングです。このプロセスにより、提案分布は徐々に失敗領域に集中していきます。

まず、各提案分布からサンプルを生成します。前述のように、初期集団の各提案分布から1つずつサンプルを得ます。これらのサンプルに対して重要度重みを計算します。重みの計算式は以下の通りです：

w_i = P(τi) / Q_i(τi) × I(τ_i ∈ failure)

ここで、P(τi)はサンプルτiの公称分布下での密度、Q_i(τi)はそのサンプルが生成された提案分布の下での密度、I(τi ∈ failure)は失敗指示関数です。失敗領域にないサンプルの重みはすべてゼロになります。

この重みには2つの重要な特性があります：

1. 失敗領域内のサンプルのみが非ゼロの重みを持ちます。これにより、リサンプリングは必ず失敗領域内のサンプルに集中します。
2. 公称分布下での密度が高いサンプルほど、より高い重みを持ちます。これは、重要度サンプリングの目的である「失敗確率の推定」に直接関連しています。公称分布下で高い確率を持つ失敗が、最終的な失敗確率に大きく寄与するからです。

これらの重みを計算した後、重みに比例した確率でサンプルのリサンプリングを行います。具体的には、N個のサンプルから重みに基づいて復元抽出でN個のサンプルを選びます。重みが高いサンプルは複数回選ばれる可能性が高く、重みがゼロのサンプル（失敗領域外のサンプル）は選ばれません。

このリサンプリングプロセスにより、元のサンプル集合から「良質な」サンプル、つまり失敗領域内にあり公称分布下で高い密度を持つサンプルに集中した新しいサンプル集合が生成されます。図を見ると、サンプル数が減少したように見えますが、実際には同数のサンプルがあり、多くのサンプルが同じ場所に重なっているだけです。

このリサンプリングステップは、集団モンテカルロ法の適応メカニズムの核心部分です。これにより、次の世代の提案分布が自動的に重要な領域に集中するよう導かれます。特に、複数の失敗モードがある場合、リサンプリングはそれぞれの失敗モードの相対的な重要性に応じてサンプルを分配します。より多くの確率質量を持つ失敗モードには、より多くのリサンプルされたサンプルが集まります。

このリサンプリングプロセスは、遺伝的アルゴリズムの選択フェーズに似ています。「適合度」（ここでは重要度重み）の高い個体（サンプル）が次世代の親として選ばれる確率が高くなります。この類似性から、集団モンテカルロ法は進化的計算の一種と見なすこともできます。

リサンプリングにより得られた新しいサンプル集合は、次のステップである新しい提案分布の生成のための基盤となります。

4.4 新しい提案分布の生成

Sydney Katz：リサンプリングステップにより重要な領域に集中したサンプル集合を得た後、次は新しい提案分布を生成する段階です。このステップでは、リサンプルされた各サンプルを基にして新しい提案分布を作成します。

基本的なアプローチは非常にシンプルです。リサンプルされた各サンプルに対して、そのサンプルを中心とした提案分布を配置します。例えば、ガウス分布を使用する場合、各リサンプルされたサンプルτをガウス分布の平均として、一定の分散を持つ新しい分布N(τ, σ²)を作成します。

この方法は直感的に理解できます。重要な領域からリサンプルされたサンプルの周辺を探索するために、それらのサンプルを中心とした新しい提案分布を配置するのです。これにより、次の反復でも重要な領域に集中しつつ、その周辺も探索することができます。

新しい提案分布の分散σ²の選択は重要なハイパーパラメータです。この分散が大きすぎると、提案分布が広範囲をカバーし、効率的な探索ができなくなります。逆に小さすぎると、局所的な領域に集中しすぎて、他の重要な領域を見逃す可能性があります。

【学生】：サンプルごとに新しい分布を追加していくと、分布の数が増えていきませんか？

Sydney Katz：良い質問です。実際には、提案分布の数を一定に保ちます。リサンプリングでは元のサンプル数と同じ数のサンプルを選びます。そして、それぞれのリサンプルされたサンプルに対して1つの新しい提案分布を作成します。したがって、世代ごとの提案分布の数は変わりません。

リサンプリングにより、一部のサンプルは複数回選ばれる可能性がありますが、その場合でも各リサンプルされたインスタンスに対して別々の提案分布を作成します。そのため、同じサンプルを中心とした複数の提案分布が生成されることもあります。図では、これらの提案分布が互いに重なって見えることがあります。

このプロセスにより、提案分布の集団は徐々に重要な領域に集中していきます。特に、複数の失敗モードがある場合、提案分布はそれぞれの失敗モードの重要性に応じて分布します。

新しい提案分布の集合が生成されたら、再びサンプリング、重み付け、リサンプリング、新しい分布の生成というサイクルを繰り返します。このサイクルは満足のいく結果が得られるまで、または設定した反復回数に達するまで続けられます。

最終的に得られた提案分布の集合を用いて、複数重要度サンプリングを実行し、失敗確率を推定します。この方法の優れている点は、失敗分布の形状や場所に関する事前知識がなくても、適応的なプロセスを通じて効果的な提案分布の集合を自動的に見つけることができる点です。

先ほど見た2Dガウスの例で考えると、我々がそれまで手動で設計していた提案分布の配置に、この方法を使って自動的に近づくことができました。これは、集団モンテカルロ法が効果的に良い提案分布を見つけることができることを示しています。

5. 逐次モンテカルロ法 (Sequential Monte Carlo)

5.1 非パラメトリックアプローチ

Sydney Katz：集団モンテカルロ法を見てきましたが、それをさらに発展させた逐次モンテカルロ法（Sequential Monte Carlo、SMC）について説明します。この方法は、より複雑な失敗分布に対応するための非パラメトリックなアプローチを提供します。

集団モンテカルロ法では、サンプルを持っていましたが、それらのサンプルの周りに明示的なパラメトリック分布（例えばガウス分布）を配置していました。これには課題があります。講義の冒頭で述べた二つ目の課題に関連しますが、高次元で複数の失敗モードを持つ複雑な失敗分布に対して、適切な分布クラスとパラメータを選ぶことが難しい場合があります。

逐次モンテカルロ法では、この問題に対する解決策として、パラメトリック分布を全く使わないアプローチを取ります。具体的には、サンプルだけを保持し、明示的な分布形式（ガウス分布など）は一切使用しません。

基本的なアイデアは、公称分布からのサンプルを取り、それらを失敗分布に向かって「移動」させることです。そして、サンプルが公称分布から失敗分布へと移動する経路に基づいて、失敗確率を推定します。

このアプローチが魔法のように聞こえるかもしれませんが、徐々に詳細を説明していきます。まず、どうやってサンプルを公称分布から失敗分布へ移動させるのかという問題について考えましょう。

通常、この移動は一連の中間分布を通じて行われます。つまり、公称分布から失敗分布まで直接ジャンプするのではなく、その間にいくつかのステップを置き、徐々に移動していくのです。

では、公称分布から失敗分布への中間分布のシリーズをどのように得るのでしょうか？ここでマルコフ連鎖モンテカルロ（MCMC）を行った際に使用したスムージング（smoothing）のアイデアを使います。

スムージングを初めて導入したときは、実は逆方向の変換を行っていました。つまり、スムージングパラメータεがゼロのとき、分布は失敗分布の非正規化密度と完全に一致すると言いました。εの値を増やすにつれて、ゼロ確率だった領域にも非ゼロの確率を割り当て始めます。これはインジケータ関数を、ガウス正規分布（その分散がε）で置き換えることで実現しました。εをさらに増やしていくと、失敗分布から公称分布に移動していきます。

今回の目標は逆です。公称分布から失敗分布に移動したいのです。そこで、このプロセスを逆にします。εを無限大から始めて、徐々に減少させていき、最終的にはゼロに近づけることで、公称分布から失敗分布へと移行します。

2次元の問題でこれを視覚化すると、原点を中心としたガウス分布（公称分布）から始まり、徐々に上方の失敗領域に集中した分布（失敗分布）へと変形していきます。中間ステップでは、「涙滴」型の分布が形成されることがわかります。

このアプローチの優れている点は、明示的なパラメトリック形式を仮定することなく、サンプルだけを使って複雑な高次元の失敗分布を表現できることです。特に複数の失敗モードを持つ分布や、高次元空間での分布など、パラメトリックな形式で表現するのが難しい場合に威力を発揮します。

この非パラメトリックなアプローチにより、集団モンテカルロ法の「提案分布をサンプルに適合させる」という課題を回避し、より柔軟に複雑な失敗分布に対応することができます。

5.2 中間分布を通じたサンプル移動

Sydney Katz：公称分布から失敗分布への中間分布のシリーズを得る方法がわかりました。では次に、これらの中間分布を通じてサンプルをどのように移動させるかを考えましょう。

まず重要なのは、これらの中間分布の密度が非正規化されていることです。スムージングを適用したとき、失敗分布の非正規化密度に対して操作を行いました。そのため、中間分布の密度も非正規化されています。非正規化密度からサンプリングする方法としては、マルコフ連鎖モンテカルロ（MCMC）が適しています。

具体的なプロセスは以下の通りです。まず公称分布からサンプルを生成します。これは比較的簡単にできます。次に、最初の中間分布（εを無限大から少し小さくした分布）を目標分布として、各サンプルからMCMCチェーンを開始します。

例えば、青色の分布（公称分布）からのサンプルがあるとします。各サンプルからMCMCチェーンを開始し、紫色の分布（最初の中間分布）を目標分布として設定します。MCMCは各サンプルを「揺らぎ」ながら移動させ、最終的に目標分布の高尤度領域に集中させます。

具体的には、各サンプルに対して別々のMCMCチェーンを開始し、一定回数（例えば50回）のMCMCステップを実行します。各ステップで、サンプルは少しずつ動き、徐々に目標分布からのサンプルのように見えるようになります。

このプロセスを最初の中間分布に対して完了したら、次の中間分布に対しても同様のことを行います。先ほどのMCMCで得られたサンプルを初期点として、次の中間分布（εをさらに小さくした分布）を目標としたMCMCチェーンを開始します。このプロセスを繰り返し、最終的には失敗分布からのサンプルが得られます。

【学生】：各中間ステップでリサンプリングしますか、それとも単に移動したサンプルを使い続けますか？

Sydney Katz：今お見せしている例では、単に移動したサンプルをそのまま使い続けています。具体的には、あるサンプルを取り、それを中間分布を目標としたMCMCで移動させ、その移動後のサンプルを次のMCMCの初期点としています。しかし、しばしば人々はリサンプリングステップも導入します。これについては後ほど触れますが、一般的にMCMCをより効率的にする効果があります。

【学生】：分布全体でゼロ密度の領域がある場合、MCMCは自力でそこに到達できるのでしょうか？

Sydney Katz：良い質問です。MCMCは現在の点の近くを探索するので、ゼロ密度の領域を越えて離れた高密度領域に移動するのは難しいことがあります。これが中間分布を使う理由の一つです。直接失敗分布を目標にするのではなく、徐々に変化する一連の分布を通じて移動することで、このような問題を回避します。

【学生】：適切なεのシーケンスを選ぶのは難しそうです。特に、問題について多くの知識がない場合はどうすればいいですか？

Sydney Katz：確かに、適切なεのシーケンスを選ぶのは簡単ではありません。Michael Kochenderfer教授がこの点について詳しいので、彼に相談するのも良いでしょう。一般的には、最終的なサンプルを観察することで評価できます。後ほど振り子の例をお見せしますが、最終段階でサンプルが失敗に向かって移動しているかを確認できます。最後のステップと実際の失敗分布の間に大きなギャップがある場合は、εの選択を見直す必要があるかもしれません。つまり、ある程度の試行錯誤が必要です。

この中間分布を通じたサンプル移動のプロセスは、複雑な失敗分布への滑らかな移行を可能にし、直接失敗分布に向かおうとするよりも効率的です。次に、このサンプル移動プロセスがどのように失敗確率の推定に役立つかを見ていきましょう。

5.3 スムージングによる分布の連続的変化

Sydney Katz：中間分布を生成する方法について、より詳細に説明しましょう。私たちは公称分布から失敗分布へと滑らかに移行する一連の分布を作成したいと考えています。

スムージングパラメータεを使った方法を思い出してください。失敗領域のインジケータ関数を、中心が失敗境界上にあり分散がεのガウス関数で置き換えることで、失敗分布を「スムーズ化」しました。

εがゼロに近いとき、このガウス関数は非常に鋭くなり、ほぼインジケータ関数と同じになります。εが大きくなるにつれて、ガウス関数は広がり、より多くの領域に確率質量を割り当てるようになります。εが無限大に近づくと、ほぼ均一な分布になり、公称分布に近づきます。

逐次モンテカルロ法では、このプロセスを逆方向に使います。εを非常に大きな値（理論的には無限大）から始め、徐々に小さくしていきます。これにより、公称分布からスタートし、段階的に失敗分布に近づけていくことができます。

具体的には、いくつかの異なるε値を選んで、それぞれが公称分布と失敗分布の間の中間状態を表す分布を作成します。例えば、ε = [∞, 100, 10, 1, 0.1, 0]といった具合に、徐々に小さくなる値のシーケンスを選びます。

これらのε値に対応する分布のシリーズを視覚化してみましょう。一次元のケースでは、εが最も大きい分布は公称分布（この例ではガウス分布）と一致しています。εが小さくなるにつれて、分布は徐々に失敗領域（この例では閾値以下の領域）に集中していきます。最終的に、ε = 0では、分布は完全に失敗領域内に制限されます。

二次元の例では、このプロセスがさらに視覚的に明確になります。εが大きいときは原点中心のガウス分布（公称分布）になっています。εが小さくなるにつれて、分布は「涙滴」形に変形し、失敗領域（この例では上部の領域）に向かって伸びていきます。最終的に、ε = 0では、分布は完全に失敗領域内に制限されます。

【学生】：この図はPlutoノートブックで生成されたものですか？コードを見ることはできますか？

Sydney Katz：はい、これはPlutoノートブックで生成されたものです。コードは少々乱雑かもしれませんが、スライド上に表示されています。正規化の部分は見栄えを良くするためだけのものなので無視してください。これは公称分布であり、スムージングバージョンのインジケータ関数の分散がεとなっています。

εの値を適切に選ぶことで、公称分布から失敗分布への滑らかな遷移を実現できます。ここでお見せしているのは、選択した一連のε値に対応する中間分布です。これらの分布が公称分布から失敗分布へとなめらかに変化していくのが分かります。

なお、中間分布を生成するための別の方法もあります。クロスエントロピー法で行ったように、失敗までの距離に対する閾値を指定し、その閾値を徐々に下げていくというアプローチも可能です。これも効果的な方法ですが、今回はスムージングを用いたアプローチに焦点を当てています。

これらの中間分布のシリーズが定義されれば、次のステップはこれらの分布を通じてサンプルを移動させることです。これにより、公称分布からのサンプルを失敗分布からのサンプルへと変換していきます。

5.4 マルコフ連鎖モンテカルロ (MCMC) による移行

Sydney Katz：中間分布のシリーズを定義したら、次はこれらの分布を通じてサンプルを移動させる方法を考えます。先に説明したように、これらの中間分布は非正規化密度を持っています。非正規化密度からサンプリングする標準的な方法はマルコフ連鎖モンテカルロ（MCMC）です。

具体的なプロセスを詳しく見ていきましょう。まず、公称分布からサンプルを生成します。これは比較的簡単で、例えばガウス分布であれば直接サンプリングできます。次に、最初の移行ステップを考えます。つまり、青色の分布（公称分布）から紫色の分布（最初の中間分布）への移行です。

各サンプル（例えば図に示されているこのサンプル）から、MCMCチェーンを開始します。このMCMCチェーンの目標分布は、最初の中間分布になります。一般的には、メトロポリス・ヘイスティングスアルゴリズムなどのMCMC法を使用します。

各サンプルに対して別々のMCMCチェーンを実行します。それぞれのチェーンは一定数のイテレーション（例えば50回）を行い、徐々に目標分布からのサンプルのように見えるようになります。

これを視覚化したものがアニメーションです。各サンプルが少しずつ動いていくのが分かります。各動きは1回のMCMCステップに対応しています。この例では50回のMCMCステップを実行し、最終的にサンプルは中間分布からのサンプルの特性を持つようになります。

このプロセスが最初の中間分布に対して完了したら、同じことを次の中間分布に対して行います。先ほどのMCMCで得られたサンプルを初期点として、次の中間分布（εをさらに小さくした分布）を目標としたMCMCチェーンを開始します。

アニメーションに示されているように、サンプルはさらに移動し、次の中間分布の高確率領域に集中していきます。このプロセスを、すべての中間分布を通じて繰り返します。最終的には、サンプルは失敗分布からのサンプルのように見えるようになります。

【学生】：各MCMCステップでは何が起きているのですか？

Sydney Katz：各MCMCステップでは、サンプルの新しい候補位置を提案し、目標分布（この場合は中間分布）の下での現在位置と新しい位置の確率密度を比較します。この比較に基づいて、新しい位置に移動するか、現在位置にとどまるかを確率的に決定します。これがメトロポリス・ヘイスティングスアルゴリズムの基本的な考え方です。

【学生】：中間分布が単調でない場合、例えばマルチモーダルである場合、MCMCは異なるモード間を移動できますか？

Sydney Katz：これは重要な指摘です。標準的なMCMCアルゴリズムは、確かに離れたモード間の移動が苦手です。特に、モード間に低確率領域がある場合は顕著です。これが中間分布を使用する理由の一つです。直接大きなジャンプをするのではなく、徐々に変化する一連の分布を通じて移動することで、MCMCがモード間を効率的に移動する可能性が高まります。それでも困難な場合は、パラレルテンパリングなどのより高度なMCMC法を検討する必要があるかもしれません。

このMCMCによる移行プロセスの美しさは、明示的なパラメトリック形式を仮定することなく、サンプルを公称分布から失敗分布へと効率的に移動させることができる点です。これにより、集団モンテカルロ法などのパラメトリックな方法では扱いにくい複雑な失敗分布に対しても有効に働きます。

5.5 確率推定のための重み計算

Sydney Katz：ここまでで、公称分布からのサンプルを中間分布を通じて失敗分布に移動させる方法を説明しました。しかし、最終的な目標は失敗確率を推定することです。では、このサンプル移動プロセスから失敗確率をどのように推定できるのでしょうか？

実は、各サンプルが辿った経路を追跡することで、失敗確率の推定が可能になります。具体的な方法を説明します。

まず、中間分布にラベルを付けます。G₁は常に公称軌道分布で、GNは失敗分布です（この例ではG₅）。各サンプルに対して重みを追跡します。すべての重みを1で初期化し、ある分布から次の分布に移行するたびに、重みを更新します。

更新式は以下のようになります：

w_i^{(j)} = w_i^{(j-1)} × [G_j(τi^{(j)}) / G{j-1}(τ_i^{(j)})]

ここで、w_i^{(j)}はサンプルiの分布jでの重み、τ_i^{(j)}は分布jでのサンプルiの位置、G_j(τ)は分布jの密度関数です。

この式が直感的に理解できるとは限りません。実際、これがなぜ機能するかの証明は非常に複雑です。本にこの証明を含めることも検討しましたが、あまりにも詳細だったため断念しました。もし興味があれば、本に参照されている論文を読むことをお勧めします。ここでは、この方法が理論的に正しいことを信じてください。

重要なのは、最終的なイテレーションでのすべての重みの平均を取ると、失敗確率の推定値が得られるということです：

P(failure) ≈ (1/N) × Σᵢ w_i^{(N)}

これは非常に強力な結果です。サンプルを公称分布から失敗分布に移動させる過程を追跡するだけで、失敗確率を推定することができるのです。

このアプローチには、いくつかの注意点があります：

1. 集団モンテカルロ法で行ったように、各遷移の前にリサンプリングステップを導入することが一般的です。本にはリサンプリングを含めた例が視覚化されています。リサンプリングを行うと、MCMCがより効率的になり、次の分布への移行前に重みの高いサンプルにリソースを集中させることができます。
2. SMCの大きな利点は非パラメトリックであることです。パラメトリックな分布を選ぶ必要がなく、すべてをサンプルだけで実行できます。これは、複雑なマルチモーダルな失敗分布や高次元空間での分布など、パラメトリックな形式で表現するのが難しい場合に特に有用です。

これを具体的に示すために、2次元ガウスの例から振り子の例に移りましょう。振り子の例は約50次元と高次元であり、各サンプルは軌道全体を表します。ここでは、一連のεを選び、MCMCを使ってサンプルを徐々に失敗分布に向かって移動させています。初期サンプルから始めて、徐々に失敗分布に近づけていくことができます。

このように、逐次モンテカルロ法は、高次元の複雑な失敗分布に対しても効果的に失敗確率を推定できる強力な手法です。特に、パラメトリックな分布では適切に表現できない複雑な分布に対して有効です。

6. 正規化定数の比率 (Ratio of Normalizing Constants)

6.1 一般的な問題としての重要度サンプリング

Sydney Katz：これまで様々な重要度サンプリングの手法を紹介してきましたが、最後にもう少し発展的な話題として、正規化定数の比率（Ratio of Normalizing Constants）について簡単に触れておきます。これは高度なトピックで、クイズには出ませんが、興味深い概念なので手短に説明します。

実は、これまで説明してきた重要度サンプリングは、より一般的な問題の特殊なケースとして捉えることができます。その一般的な問題とは、二つの分布間の正規化定数の比率を決定することです。

この考え方がなぜ理にかなっているのかを理解するために、失敗確率が失敗分布の正規化定数であることを思い出してください。特定の方法でこの比率を決定すると、重要度サンプリング推定器に行き着くことになります。

しかし、この問題をより一般的な「正規化定数の比率を決定する問題」として捉えると、他のタイプの推定器も導出できることが非常に興味深いのです。つまり、重要度サンプリングから少し離れて、正規化定数の比率という一般的な問題に目を向けると、新しい推定手法が見えてくるのです。

本の中では、自己正規化重要度サンプリング（Self-normalized Importance Sampling）、ブリッジサンプリング（Bridge Sampling）、アンブレラサンプリング（Umbrella Sampling）といった手法について説明しています。これらはすべて非常に興味深いアプローチです。

これらの概念は学術的な数学論文から抽出し整理する必要があり、かなり難解ですが、本の中ではこれらを分かりやすく説明することに努めました。もし関心があれば、ぜひ本を読んでみてください。

しかし、今日の講義ではやるべきことが多く時間が限られているため、これ以上詳しく掘り下げることはできません。本当はもっと皆さんにお見せしたかったのですが、時間的制約がありますので割愛せざるを得ません。

ただ、本の中の特に図7.12は私にとって特別なものなので、簡単に触れておきたいと思います。この図は、アンブレラサンプリングに似た手法を使う際の自己正規化重要度サンプリングの最適提案分布を示しています。これは専門的で難解な内容ですが、この図には個人的なエピソードがあります。

昨年初め頃、私はサンディエゴの母の家で結婚式の招待状をデザインしていました。私は暗いテーマの招待状を作りたいと思っていたのですが、当時の婚約者（現在の夫）がそれを見て「葬式の招待状みたいだから絶対ダメだ」と言ったのです。がっかりして本の作業に戻っていると、ちょうどこの図を作成していました。そこに母が通りかかり「これいいじゃない、これを使ったら？」と提案してくれたのです。

結局、結婚式の招待状には、参列者の99%が気づかないであろう、自己正規化重要度サンプリングの最適分布の図が使われました。おそらく結婚式の招待状にPGFプロットを使った数少ない例の一つでしょう。

この話から言いたいのは、もし本自体に興味を持てなくても、少なくとも図はいい装飾になるということです（笑）。皆さんもぜひ試してみてください。

以上で今日の講義を終わります。予定より少し早く終わりましたが、これで重要度サンプリングの適応的手法についての講義を完了します。

6.2 自己正規化重要度サンプリング

Sydney Katz：自己正規化重要度サンプリング（Self-normalized Importance Sampling）は、正規化定数の比率を決定する問題の文脈で理解できる重要な手法です。

標準的な重要度サンプリングでは、サンプルの重みは公称分布の密度を提案分布の密度で割ったものでした。しかし、これらの重みが大きくばらつく場合、少数の非常に大きな重みを持つサンプルが推定値を支配してしまい、分散が大きくなる問題が生じることがあります。

自己正規化重要度サンプリングでは、この問題に対処するために重みを正規化します。具体的には、各サンプルの重みをすべての重みの合計で割ります。つまり：

w_i^{normalized} = w_i / Σ_j w_j

ここで、w_iは標準的な重要度重み P(τi)/Q(τi) です。

この正規化により、重みの合計は常に1になります。これにより、少数の外れ値が推定値に与える影響を軽減し、より安定した推定が可能になります。

自己正規化重要度サンプリングの背後にある理論は、正規化定数の比率の観点から理解できます。標準的な重要度サンプリングが公称分布と提案分布の正規化定数の比率を直接推定するのに対し、自己正規化バージョンはこの比率を推定する別の方法を提供します。

この手法の最も興味深い側面の一つは、最適な提案分布が標準的な重要度サンプリングの場合と異なることです。標準的な重要度サンプリングでは、最適な提案分布は失敗分布そのものですが、自己正規化バージョンでは、最適な提案分布は少し異なる形をしています。

特に、アンブレラサンプリングのような手法と組み合わせると、図7.12に示したような興味深い形状の最適提案分布が導出されます。この分布は数学的に美しいだけでなく、実用的にも優れた性能を発揮することがあります。

自己正規化重要度サンプリングは、複雑な高次元分布や、重みが極端に偏る可能性のある設定で特に有用です。正規化によって重みのばらつきを抑制するため、より安定した推定が可能になります。

この手法は理論的に複雑ですが、実装は比較的簡単です。標準的な重要度サンプリングを実装した後、重みを正規化するステップを追加するだけです。しかし、理論的な背景を理解することで、この手法がなぜ有効なのか、また最適な提案分布がどのようなものかについての洞察が得られます。

本の中では、この手法についてより詳細に説明していますので、興味のある方はぜひ参照してください。正規化定数の比率という視点から重要度サンプリングを捉え直すことで、より広範な推定手法の体系的な理解が可能になります。

6.3 ブリッジサンプリングとアンブレラサンプリング

Sydney Katz：正規化定数の比率を推定するための他の重要な手法として、ブリッジサンプリング（Bridge Sampling）とアンブレラサンプリング（Umbrella Sampling）があります。これらの手法は、標準的な重要度サンプリングや自己正規化重要度サンプリングを超えて、より効率的で安定した推定を提供することができます。

ブリッジサンプリングでは、二つの分布間に「橋」を架けるような第三の分布を導入します。この「橋」となる分布は、両方の元の分布の高密度領域を効果的にカバーするように選ばれます。具体的には、P(τ)とQ(τ)の正規化定数の比率を推定する際に、新しい分布R(τ)を導入します。これにより、比率の推定において分散を大幅に減少させることができます。

ブリッジサンプリングの基本的なアイデアは、両方の分布からサンプルを得て、それらを「橋」となる分布を通じて効果的に結びつけることです。これにより、特に二つの分布の重複が小さい場合でも、より正確な比率推定が可能になります。

アンブレラサンプリングはさらに進んだ手法で、複数の中間分布（「アンブレラ」）を使用して、二つの大きく異なる分布間の移行をより滑らかにします。これは、逐次モンテカルロ法で使用した中間分布の考え方と概念的に似ていますが、目的が異なります。

アンブレラサンプリングでは、各中間分布からサンプルを生成し、隣接する分布間の正規化定数の比率を推定します。これらの比率を掛け合わせることで、元の二つの分布間の全体的な比率を得ることができます。この方法は、橋を一つだけ架けるよりも、複数の小さな橋を連続して架けるようなイメージです。

両手法の最大の利点は、分布間の重複が小さい場合でも効果的に機能することです。標準的な重要度サンプリングでは、提案分布が公称分布と大きく異なる場合、非常に大きな分散を持つ推定になる可能性があります。ブリッジサンプリングとアンブレラサンプリングは、この問題に対処するための洗練された方法を提供します。

これらの手法は、特に以下のような状況で有用です：

• 複雑な高次元分布
• 複数のモードを持つ分布
• 分布間の重複が非常に小さい場合
• 失敗確率が極めて小さい場合

例えば、物理学や化学の分野では、アンブレラサンプリングは分子動力学シミュレーションにおいて広く使用されています。稀なイベント（たとえば分子の構造変化）の確率を推定する際に、直接シミュレーションでは何十億回のシミュレーションが必要になる場合でも、アンブレラサンプリングを用いれば効率的に推定できることがあります。

これらの方法の詳細な数学的背景は複雑ですが、正規化定数の比率という一般的な問題設定から派生した統一的な枠組みで理解できることが重要です。本の中では、これらの手法とその理論的背景について詳しく説明していますので、興味のある方はぜひ参照してください。

6.4 最適提案分布の応用例（講演者の結婚式招待状のデザイン）

Sydney Katz：この発展的なトピックを締めくくるにあたり、正規化定数の比率に関する研究から生まれた美しい数学的表現の、予想外の実世界での応用例をお話ししたいと思います。それは私自身の個人的なエピソードです。

本の中の図7.12は私にとって特別な意味を持っています。この図は、自己正規化重要度サンプリングをアンブレラサンプリングのようなアプローチと組み合わせた場合の最適提案分布を示しています。この詳細は専門的で複雑なので、すべてを理解する必要はありません。重要なのは、この数学的に導出された分布が美しい視覚的パターンを生み出すということです。

昨年の初め頃、私はサンディエゴの母の家で結婚式の招待状をデザインしていました。数学者らしく、私はダークテーマの結婚式招待状を作りたいと思っていました。しかし、当時の婚約者（現在の夫）がそのデザインを見て、「これは葬式の招待状のように見える。ダークテーマの結婚式招待状は絶対に使えない」と言ったのです。

がっかりした私は、本の執筆作業に戻り、ちょうどこの図7.12に取り組んでいました。そこに母が通りかかり、「これ、かっこいいじゃない。これを使ったら？」と提案してくれたのです。

こうして、おそらく参列者の99%が気づかなかったと思いますが、私の結婚式の招待状には自己正規化重要度サンプリングの最適分布の図が使われることになりました。おそらく結婚式の招待状にPGFプロット（LaTeXのグラフ作成ツール）を使った数少ない例の一つではないかと思います。

このエピソードが示すのは、高度な数学的概念が思いがけない形で日常生活に美を持ち込むことがあるということです。本のこの章で説明している概念が難解に感じられたとしても、それらが生み出す美しいパターンは、純粋に視覚的な観点からも価値があるのです。

「もし本の内容自体にそれほど興味が持てなくても、少なくとも図は良い装飾になりますよ」と冗談めかして言いたいところです。皆さんも自分で試してみてください。

この小さなエピソードは、理論的な数学と現実世界の間の予期せぬ架け橋を示しています。正規化定数の比率の理論が、結婚式の招待状のデザインに影響を与えるとは、誰が想像したでしょうか。これは、私たちが研究している抽象的な概念が、時に予想外の形で私たちの生活に影響を与えることを思い出させてくれます。

以上で今日の講義を終わります。予定より少し早く終わりましたが、これで重要度サンプリングの適応的手法についての講義を完了します。皆さんの理解に役立つことを願っています。

Stanford AA228V I Validation of Safety Critical Systems I Adaptive Importance Sampling

To follow along with the course, visit the course website: https://aa228v.stanford.edu/ Textbook: https://algorithmsbook.com/validation/ Sydney Katz, Postdoctoral Scholar, Stanford University More about the speaker: https://sydneymkatz.com/ Mykel Kochenderfer, Associate Professor of Aeronautics and Astronautics and, by courtesy, of Computer Science, Stanford University More about the speaker: https://mykel.kochenderfer.com/ To learn more and enroll in the course: https://online.stanford.edu/courses/aa228v-validation-safety-critical-systems

youtu.be