導入
翻訳追跡ページ— この情報を更新します
Reuven Rubinstein によるクロスエントロピー (CE) 法は、一般的なモンテカルロ法、組み合わせ最適化法または連続最適化法です。この方法はもともと、ネットワーク セキュリティ分析、キュー モデル、電気通信システムのパフォーマンス分析など、非常に低い確率密度を正確に推定する必要がある稀なイベントのシミュレーション用に設計されました。 CE 法は、巡回セールスマン問題、二次代入問題、シーケンス アライメント問題、最大カットオフ問題、メモリ割り当て問題などの観測値にノイズが多い任意の組み合わせ最適化問題に適用でき、また、多くの局所極値を伴う連続最適化問題にも適用できます。
CE メソッドは 2 つのフェーズに分かれています。
- 特定のメカニズムに従ってデータのサンプル(軌跡、ベクトルなど) をランダムに生成します。
- 次の反復でより良いサンプルを生成するために、データ サンプルからランダム生成メカニズムのパラメーターを更新します。このステップには、クロスエントロピーまたはカルバック・ライブラー発散を最小限に抑えることが含まれます。
優先サンプリングによる推定
一般的な数量推定問題を考えてみましょう
$$ {\ell = \mathbb{E}_{\mathbf{u}}[H(\mathbf{X})] = \int H(\mathbf{x})\, f(\mathbf{x}; \mathbf{u})\, \textrm{d}\mathbf{x}} $$
ここで、 H は目的関数であり、 $$ {f(\mathbf{x};\mathbf{u})} $$
はパラメトリック確率密度です。優先サンプリングを使用すると、この数量は次のように推定できます。 $$ {\hat{\ell} = \frac{1}{N} \sum_{i=1}^N H(\mathbf{X}_i) \frac{f(\mathbf{X}_i; \mathbf{u})}{g(\mathbf{X}_i)}} $$
、 または$$ {\mathbf{X}_1,\dots,\mathbf{X}_N} $$
ランダム密度変数のサンプルです$$ {g\,} $$
。正のHの場合、確率変数の確率密度の理論的最適値は次の式で与えられます。 $$ { g^*(\mathbf{x}) = H(\mathbf{x}) f(\mathbf{x};\mathbf{u})/\ell} $$
。しかし$$ {\ell} $$
は不明なパラメータです。 CE 法は、(カルバック・ライブラーの意味で) 最適密度g *に最も近いサンプルの要素を選択することによって、最適密度に近づくことを提案しています。継続的な最適化 – 例
同じ CE アルゴリズムを最適化と推定に使用できます。たとえば、関数S ( x )を最大化する問題を考えてみましょう。
$$ {S(x) = \textrm{e}^{-(x-2)^2} + 0.8\,\textrm{e}^{-(x+2)^2}} $$
。クロスエントロピーを使用するには、まず推定に関連する確率論的問題を考慮する必要があります。 $$ {\mathbb{P}_{symbol{\theta}}(S(X)\geq\gamma)} $$
特定のレベルに対して$$ {\gamma\,} $$
、およびパラメトリック確率分布のファミリー$$ {\left\{f(\cdot;symbol{\theta})\right\}} $$
、たとえば、パラメータが平均である 1 次元の正規分布です。 $$ {\mu_t\,} $$
そしてその差異$$ {\sigma_t^2} $$
（のような$$ {symbol{\theta} = (\mu,\sigma^2)} $$
ここ）。それで、 $$ {\gamma\,} $$
与えられた場合、目的は決定することです$$ {symbol{\theta}} $$
量などの$$ {D_{\mathrm{KL}}(\textrm{I}_{\{S(x)\geq\gamma\}}\|f_{symbol{\theta}})} $$
最小化されます。これは、ステップ 3 で前述したように、KL 発散を最小化する問題のサンプリングされたバージョン (確率的対応物⇔確率的対応物) を使用して行われます。この分布の選択では、問題の確率的バージョンを最小化するパラメーターは次のとおりであることがわかります。スコア関数の値が次のような抽選で構成されるエリートサンプルの平均と経験的分散。 $$ {\geq\gamma} $$
。エリート サンプル内の最悪の要素は、次の反復のレベル パラメーターとして機能します。これにより、この問題に対して次の確率的アルゴリズムが得られます。擬似コード
1μ:=-6;シグマ2:=100; t:=0;最大値=100; // パラメータの初期化2. N:=100; Ne:=10; // 3. while t < maxits および sigma2 > epsilon // 収束しておらず、maxits を超えない限り 4. // 分布 5 から N 個のサンプルを生成します。 S = exp(-(X-2)^2) + 0.8 exp(-(X+2)^2); // 各サンプルのスコアを計算します 6. X = sort(X, S); // スコアに基づくクラス X (降順) 7. mu = means(X(1:Ne)); sigma2=var(X(1:Ne)); // 分布パラメータを更新します8. t = t+1; // 反復回数を増やします9. return mu // 最後のサンプルの平均を解として返します