クロスエントロピー法 (Cross Entropy Method, CEM) は、モンテカルロ法における重点サンプリング (Importance Sampling) の一種であり、最適化問題や希少事象の確率推定に用いられるアルゴリズムです。
モンテカルロサンプリング
モンテカルロ法は、乱数を用いることで、複雑な問題の近似解を求める数値計算手法の総称です。
例えば、確率変数 $X$ が確率密度関数 $f(x)$ に従うとき、関数 $H(X)$ の期待値 $l = \mathbb{E}[H(X)] = \int H(x)f(x)dx$ を求めたいとします。 モンテカルロサンプリングでは、この期待値を $N$ 個の独立同分布なサンプル $X_1, \dots, X_N$ を用いて以下のように近似します。
$$ l_{MS} = \frac{1}{N} \sum_{i=1}^{N} H(X_i) $$
重点サンプリング (Importance Sampling)
モンテカルロサンプリングでは、期待値を計算したい確率分布 $f(x)$ から直接サンプルを生成します。しかし、もし $H(x)$ が大きな値をとる領域が $f(x)$ の確率が低い領域にある場合、効率的なサンプリングができません。
重点サンプリングでは、目的の分布 $f(x)$ ではなく、別のサンプリング分布 $g(x)$ からサンプルを生成します。そして、そのサンプルに重み $w(x) = f(x)/g(x)$ を掛けることで、期待値を推定します。
$$ l_{IS} = \frac{1}{N} \sum_{i=1}^N H(X_i) \frac{f(X_i)}{g(X_i)} = \mathbb{E}_g\left[H(X)\frac{f(X)}{g(X)}\right] $$
ここで、$X_i \sim g(x)$ です。重点サンプリングの効率は、サンプリング分布 $g(x)$ の選択に大きく依存します。特に、分散を最小化する最適なサンプリング分布 $g^(x)$ は、$g^(x) \propto |H(x)|f(x)$ の形をとることが知られています。
クロスエントロピー法 (Cross Entropy Method)
クロスエントロピー法は、この重点サンプリングにおける最適なサンプリング分布 $g^*(x)$ に近い分布を、反復的に見つけるためのアルゴリズムです。
「クロスエントロピー」は、2つの確率分布 $p$ と $q$ の間の類似度を測る尺度の一つで、以下のように定義されます。
$$ H(p, q) = -\int p(x) \log q(x) dx $$
KLダイバージェンス $KL(p||q) = \int p(x) \log \frac{p(x)}{q(x)} dx = H(p,q) - H(p)$ の関係から、真の分布 $p$ が固定されている場合、KLダイバージェンスを最小化することはクロスエントロピーを最小化することと等価になります。
CEMは、パラメータ化されたサンプリング分布 $g(x;v)$ のパラメータ $v$ を、以下の手順で最適化します。
- 初期化: パラメータ $v$ を初期化し、サンプリング分布 $g(x;v)$ を設定します。
- サンプリング: 現在のサンプリング分布 $g(x;v)$ から $N$ 個のサンプル $X_1, \dots, X_N$ を生成します。
- 評価: 各サンプル $X_i$ に対して、目的関数 $H(X_i)$ を計算します。
- エリートサンプルの選択: 目的関数値が高い（または低い、最適化の方向による）上位 $P$ パーセントのサンプルを「エリートサンプル」として選択します。
- パラメータの更新: エリートサンプルを用いて、サンプリング分布 $g(x;v)$ のパラメータ $v$ を更新します。この更新は、エリートサンプルの尤度を最大化するように行われます。これは、エリートサンプルの経験分布と $g(x;v)$ の間のクロスエントロピーを最小化することに相当します。
- 収束判定: パラメータ $v$ の変化が十分に小さくなるか、最大反復回数に達するまで、ステップ2に戻って繰り返します。
この反復プロセスにより、サンプリング分布 $g(x;v)$ は徐々に最適解の領域に集中していき、効率的な探索が可能になります。
参考文献
- Rubinstein, R. Y., & Kroese, D. P. (2013). The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning. Springer Science & Business Media.
- 漆原 勉, “モンテカルロシミュレーションにおける重点サンプリング法に対する大偏差理論の適用について”