クロスエントロピー法

クロスエントロピー( CE )法は、重要度サンプリングと最適化のためのモンテカルロ法です。静的またはノイズのある目的を持つ、 組み合わせ問題と連続問題の両方に適用できます。

この方法は、2つの段階を繰り返すことで最適な重要度サンプリング推定値を近似する：^[1]

1. 確率分布からサンプルを抽出します。
2. この分布とターゲット分布間のクロスエントロピーを最小化して、次の反復でより良いサンプルを生成します。

ルーベン・ルビンシュタインは、ネットワーク信頼性分析、待ち行列モデル、通信システムのパフォーマンス分析など、小さな確率を推定する必要がある稀なイベントのシミュレーションのコンテキストでこの方法を開発しました。この方法は、巡回セールスマン、二次割り当て、DNA配列アラインメント、最大カット、バッファ割り当ての問題にも適用されています。

量を推定する一般的な問題を考えてみましょう

${\displaystyle \ell =\mathbb {E} _{\mathbf {u} }[H(\mathbf {X} )]=\int H(\mathbf {x} )\,f(\mathbf {x} ;\mathbf {u} )\,{\textrm {d}}\mathbf {x} }$、

ここで、は何らかのパフォーマンス関数であり、は何らかのパラメトリック分布族のメンバーである。重要度サンプリングを使用すると、この量は次のように推定できる。 ${\displaystyle H}$${\displaystyle f(\mathbf {x} ;\mathbf {u} )}$

${\displaystyle {\hat {\ell }}={\frac {1}{N}}\sum _{i=1}^{N}H(\mathbf {X} _{i}){\frac { f(\mathbf {X} _{i};\mathbf {u} )}{g(\mathbf {X} _{i})}}}$、

ここで はからのランダムサンプルです。 が正の場合、理論的に最適な重要度サンプリング密度(PDF) は次のように与えられます。 ${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$${\displaystyle g\,}$${\displaystyle H}$

${\displaystyle g^{*}(\mathbf {x} )=H(\mathbf {x} )f(\mathbf {x} ;\mathbf {u} )/\ell }$。

しかし、これは未知の に依存します。CE 法は、最適な PDF に最も近い ( Kullback-Leibler の意味で) パラメトリック ファミリのメンバーを適応的に選択することによって、最適な PDF を近似することを目的としています。 ${\displaystyle \ell}$${\displaystyle g^{*}}$

1. 初期パラメータベクトルを選択し、t = 1 に設定します。${\displaystyle \mathbf {v} ^{(0)}}$
2. ランダムサンプルを生成する${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$${\displaystyle f(\cdot ;\mathbf {v} ^{(t-1)})}$
3. を解きます。ここで${\displaystyle \mathbf {v} ^{(t)}}$
   ${\displaystyle \mathbf {v} ^{(t)}=\mathop {\textrm {argmax}} _{\mathbf {v} }{\frac {1}{N}}\sum _{i=1} ^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}}\log f(\mathbf {X} _{i};\mathbf {v} )}$
4. 収束に達した場合は停止します。そうでない場合は、t を 1 増やして手順 2 から繰り返します。

いくつかのケースでは、ステップ3の解は解析的に見つけることができます。これが発生する状況は次のとおりです。

• 自然指数族に属する場合${\displaystyle f\,}$
• が有限のサポートを持つ離散である場合${\displaystyle f\,}$
• およびのとき、 はそれら に基づく最大尤度推定量に対応します。${\displaystyle H(\mathbf {X} )=\mathrm {I} _{\{\mathbf {x} \in A\}}}$${\displaystyle f(\mathbf {X} _{i};\mathbf {u} )=f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}$${\displaystyle \mathbf {v} ^{(t)}}$${\displaystyle \mathbf {X} _{k}\in A}$

同じ CE アルゴリズムは、推定ではなく最適化にも使用できます。問題が何らかの関数、たとえば を最大化するものであるとします。CE を適用するには、まず、平均と分散(ここでは )によってパラメータ化された1 次元 ガウス分布 などの、与えられたレベル 、およびパラメトリック ファミリ について を推定する関連する 確率的問題を 検討します。したがって、与えられた について、が 最小化される を見つけることが目標と なります。これは、上記の手順 3 のように、KL ダイバージェンス最小化問題のサンプル バージョン (確率的対応物) を解くことによって行われます。このターゲット分布とパラメトリック ファミリの選択について確率的対応物を最小化するパラメータは、目的関数値 を持つサンプルであるエリート サンプル に対応するサンプル平均とサンプル分散であることがわかります。これにより、分布推定アルゴリズムである、いわゆる多変量正規分布推定アルゴリズム (EMNA) と一致する次のランダム化アルゴリズムが生成されます。 ${\displaystyle S}$${\displaystyle S(x)={\textrm {e}}^{-(x-2)^{2}}+0.8\,{\textrm {e}}^{-(x+2)^{2}}}$${\displaystyle \mathbb {P} _{\boldsymbol {\theta }}(S(X)\geq \gamma )}$ ${\displaystyle \gamma \,}$${\displaystyle \left\{f(\cdot ;{\boldsymbol {\theta }})\right\}}$${\displaystyle \mu_{t}\,}$${\displaystyle \sigma_{t}^{2}}$${\displaystyle {\boldsymbol {\theta }}=(\mu ,\sigma ^{2})}$${\displaystyle \gamma \,}$${\displaystyle {\boldsymbol {\theta }}}$${\displaystyle D_{\mathrm {KL} }({\textrm {I}}_{\{S(x)\geq \gamma \}}\|f_{\boldsymbol {\theta }})}$${\displaystyle \geq \gamma }$

// パラメータを初期化する
μ := −6
σ2 := 100
t := 0
最大値 := 100
100 の場合
ネ = 10

// t < maxitsかつσ2 > εである間は、maxits を超えず収束しません// 現在のサンプリング分布から N 個のサンプルを取得します
    
    X := サンプルガウス(μ, σ2, N)
    // サンプルポイントで目的関数を評価する
    S := exp(−(X − 2) ^ 2) + 0.8 exp(−(X + 2) ^ 2)
    // Xを目的関数の値で降順で並べ替える
    X := ソート(X, S)
    // エリートサンプルを介してサンプリング分布のパラメータを更新します                  
    μ := 平均(X(1:Ne))
    σ2 := var(X(1:Ne))
    t := t + 1
// 最終的な標本分布の平均を解として返す
return μ

• シミュレーテッドアニーリング
• 遺伝的アルゴリズム
• ハーモニー検索
• 分布推定アルゴリズム
• タブー検索
• 自然進化戦略
• 蟻コロニー最適化アルゴリズム

• クロスエントロピー
• カルバック・ライブラー距離
• ランダム化アルゴリズム
• 重要度サンプリング

• De Boer, P.-T., Kroese, DP, Mannor, S. and Rubinstein, RY (2005). クロスエントロピー法のチュートリアルAnnals of Operations Research , 134 (1), 19–67.[1]
• Rubinstein, RY (1997). 稀なイベントを伴うコンピュータシミュレーションモデルの最適化、European Journal of Operational Research、99、89–112。

• CEoptim R パッケージ
• Novacta.Analytics .NET ライブラリ