交差エントロピー法

交差エントロピー法（CEM）は、希少事象の推定や組合せ最適化・連続最適化のための反復型確率的最適化手法であり、重要度サンプリングとエリートサンプルに基づくパラメータ更新を用いる。

交差エントロピー法（CEM）は、困難な最適化問題や希少事象の推定問題を解くための汎用的なモンテカルロ手法である。この手法は、1997年にReuven Rubinsteinによって希少事象の確率を推定する方法として導入され、すぐに組合せ最適化や連続最適化へと拡張された。この手法は、パラメータ化された確率分布からランダムサンプルを反復的に生成し、それらを評価し、最良のサンプル群（エリート集合と呼ばれる）に集中するように分布パラメータを更新する。このアプローチは、目的関数がノイズを含む、非微分可能、または多くの局所最適解を持つ問題に対して特に効果的である。

CEMの核となる考え方は、サンプリング分布と、最適解にすべての確率質量を置く理想的な分布との間の交差エントロピーを最小化することである。実際には、これは現在の分布からのサンプリングと、エリートサンプルの最尤推定を用いた分布の更新という2つのステップを繰り返すことで達成される。この手法は実装が簡単で、ハイパーパラメータが少なく、しばしば迅速に収束するため、強化学習、ロボティクス、オペレーションズリサーチなどの分野で人気のある選択肢となっている。

アルゴリズムの枠組み

交差エントロピー法は反復ループで動作する。最初に、解空間上で確率分布（多くの場合、多変量ガウス分布またはカテゴリカル分布）が定義される。各反復では、この分布から候補解のバッチが抽出される。各候補はスコアリング関数を用いて評価され、上位の割合（通常10%から20%）がエリート集合として選択される。その後、分布パラメータはこれらのエリートサンプルに適合するように更新され、典型的にはガウス分布の場合は標本平均と分散を、カテゴリカル分布の場合は経験的な頻度を計算する。

早期収束を防ぐために、平滑化パラメータが導入されることが多く、新しいパラメータと以前のパラメータをブレンドする。この平滑化は探索を維持し、局所最適解に陥るのを防ぐのに役立つ。このプロセスは、最大反復回数や最良スコアの変化が無視できるなどの停止基準が満たされるまで繰り返される。

機械学習における応用

Machine learningにおいて、CEMはハイパーパラメータ最適化、ニューラルアーキテクチャ探索、Reinforcement learningの文脈でのポリシー訓練に使用されてきた。例えば、Deep learningでは、CEMはバックプロパゲーションなしで小さなNeural networkの重みを最適化でき、勾配が利用できない場合や高価な場合に有用である。また、Large language modelの微調整における離散的なプロンプト最適化にも適用されており、そこでは探索空間が組合せ的である。

Artificial intelligenceの研究では、CEMは進化的戦略やStochastic Gradient Descent Variantsとしばしば比較される。勾配ベースの手法とは異なり、CEMは目的関数が微分可能であることを必要とせず、ブラックボックス最適化に適している。Roboticsでは軌道最適化に、自動運転システムではパラメータ調整に使用されてきた。

希少事象推定との関係

CEMの元々の動機は、システム障害や極端な金融損失などの希少事象の確率を推定することであった。この文脈では、この手法は重要度サンプリングを用いて分散を低減する。アルゴリズムは関心領域を強調するサンプリング分布を適応的に構築し、単純なモンテカルロよりもはるかに少ないサンプルで正確な推定を可能にする。この二重の用途（最適化と推定）は、同じ数学的基盤、すなわちサンプリング分布と最適な重要度サンプリング分布との間のカルバック・ライブラー発散の最小化に由来する。

拡張と変種

CEMのいくつかの拡張が開発されている。連続版はガウス分布またはガウス混合分布を使用し、離散版は巡回セールスマン問題などの組合せ問題を扱う。注目すべき変種として、改良交差エントロピー法があり、過去のエリートサンプルの記憶を取り入れて更新を安定化させる。もう一つの拡張は、モデルベース強化学習でのCEMの使用であり、学習された世界モデル上で行動のシーケンスを最適化することで計画を行う。このアプローチは、最近のDeep Reinforcement Learningアルゴリズム、例えばModel-Based Policy Optimization（MBPO）フレームワークで普及している。

CEMはまた、サンプルの難易度を徐々に上げるCurriculum Learningや、ロバスト最適化のためのData Augmentationと組み合わせられている。Bayesian Optimizationでは、CEMは獲得関数の最適化器として機能することができる。

実践的な考慮事項

CEMを適用する際、分布族の選択とエリート割合が重要である。エリート割合が小さすぎると早期収束につながり、大きすぎると進行が遅くなる。平滑化パラメータは、しばしば0.5から0.9の間に設定され、探索と活用のバランスを取る。高次元の問題では、各反復のサンプル数をそれに応じて増やす必要があり、計算コストが高くなることがある。これらの課題にもかかわらず、CEMの単純さと頑健性は、最適化ツールボックスにおける定番となっている。

実際には、CEMは研究論文でベースラインとしてよく使用され、その性能は多くのベンチマーク問題でBayesian Optimizationのようなより複雑な手法に匹敵する。これは、Python用のcmaパッケージを含むいくつかのオープンソースライブラリに実装されているが、古典的なCEMはCMA-ES（共分散行列適応進化戦略）とは異なり、これは関連するが別のアルゴリズムである。