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

クロスエントロピー法は，モンテカルロ法における重点サンプリング法の一種であり、最適化問題において確率分布の近似を行うアルゴリズムである。

モンテカルロサンプリング

モンテカルロ法は，乱数を用いる数値計算法の総称である．

問題設定として，$X$を確率変数，$H$を目的の関数，$f$を$H$の$X$における確率密度関数とした場合，期待値

$$l=\int H(x)f(x)dx = E[H(X)]$$

を知りたいとする．モンテカルロサンプリングでは，以下のようにこれを近似する．

$$l_{MS}=\frac{1}{N}\sum_{i=1}^{N}(X_i)$$

重点サンプリングでは，モンテカルロサンプリングより効率よくサンプリングを行うために，分散の小さい分布からサンプリングすることを考える．

重点サンプリングでは，$g(x)=0$のとき$H(x)f(x)=0$となる，確率密度関数$g$を用意して以下のように推定量の近似を行う．

$$l_{IS}=\frac{1}{N}\sum_{i=1}^NH(X_i)\frac{f(X_i)}{g(X_i)}=E[H(X)\frac{f(X)}{g(X)}]$$

クロスエントロピー法では，重点サンプリングでの$g$の最適分布$g^*$と近い分布を用いることを考える．

ここで，確率分布間の距離を測る指標としてクロスエントロピーを用いる．クロスエントロピー$D$は，以下の式で表される．

$$D(g,h)=\int \log \frac{g(x)}{h(x)}g(x)dx$$

$D(g^\ast,h)$を最小にする$h$を求めれば，$g^\ast$に近い分布，つまり分散の小さい分布が獲得可能である．

$$l_{CEM}=E[H(X)\frac{f(X;u)}{g(X;v)}]$$

$$v^{\ast}=arg min_v D[g^{\ast},g(x;v)]$$

Tags: