交叉熵方法（CEM）是一种通用的蒙特卡洛技术，用于解决困难的优化和稀有事件估计问题。它由Reuven Rubinstein于1997年提出，最初用于估计稀有事件的概率，随后很快扩展到组合优化和连续优化领域。该方法迭代地从参数化概率分布中生成随机样本，对其进行评估，并更新分布参数以集中于表现最佳的样本，即精英集。这种方法特别适用于目标函数带有噪声、不可微或具有许多局部最优解的问题。
CEM的核心思想是最小化采样分布与将所有概率质量置于最优解上的理想分布之间的交叉熵。在实践中，这通过反复执行两个步骤来实现：从当前分布中采样，以及使用精英样本的最大似然估计更新分布。该方法实现简单，需要的超参数较少，且通常收敛迅速，使其在强化学习、机器人和运筹学等领域成为热门选择。
算法框架
交叉熵方法在迭代循环中运行。初始时，在解空间上定义一个概率分布（通常是多元高斯分布或分类分布）。在每次迭代中，从该分布中抽取一批候选解。每个候选解使用评分函数进行评估，并选择表现最佳的部分（通常为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最初的动机是估计稀有事件的概率，例如系统故障或极端财务损失。在此背景下，该方法使用重要性采样来减少方差。该算法自适应地构建一个强调感兴趣区域的采样分布，从而能以远少于朴素蒙特卡洛的样本数量获得准确估计。这种双重用途，，优化和估计，，源于相同的数学基础：最小化采样分布与最优重要性采样分布之间的Kullback-Leibler散度。
扩展与变体
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（协方差矩阵自适应进化策略）有所不同，后者是一个相关但独立的算法。
参见
- evolutionary-algorithm
- monte-carlo-method
- Reinforcement learning
- black-box-optimization