Summary
- CE 方法逐步更新采样分布 \(Q\)，使其更接近目标分布 \(P^*\)，从而最小化两者之间的交叉熵
- 这一过程不仅有助于找到最优解，还能够在高维和复杂问题中有效地进行优化
- 注：在工业实践中，CEM 方法很容易使用
交叉熵基础定义
- Cross Entropy 方法中的 “Cross Entropy” 这个名字来源于信息论中的一个概念
- 在信息论中，交叉熵（Cross Entropy）是用来衡量两个概率分布之间的差异的一个指标，通常用于评估一个概率模型对真实数据分布的拟合程度
- 给定两个概率分布 \(P\) 和 \(Q\)，其中 \(P\) 代表真实的概率分布，而 \(Q\) 代表模型预测的概率分布，那么 \(P\) 和 \(Q\) 之间的交叉熵定义为：
$$ H(P, Q) = -\sum_x P(x) \log Q(x) $$ - 这里的 \(H(P, Q)\) 就是 \(P\) 相对于 \(Q\) 的交叉熵。当 \(Q\) 完美地匹配 \(P\) 时，即 \(P=Q\)，交叉熵达到最小值，此时等于 \(P\) 的熵 \(H(P)\)
- 如果 \(Q\) 与 \(P\) 不同，那么交叉熵会比 \(P\) 的熵大，表示了额外的信息损失或误差
交叉熵损失函数
- 在优化和机器学习领域，交叉熵经常被用作损失函数，特别是在分类任务中，比如使用神经网络进行图像分类
- 在这种情况下， \(P\) 通常是样本的真实标签分布（例如，对于二分类问题，正类可以表示为 [1, 0]，负类为 [0, 1]），而 \(Q\) 是模型预测的概率分布
- 通过最小化交叉熵损失函数，可以训练模型更好地拟合训练数据
交叉熵方法名字的来源
- Cross Entropy 方法本身是一种用于优化和采样的算法，它最初是从稀有事件模拟中发展出来的
- 该方法通过迭代地从候选解集中采样，并根据这些样本计算出一个精英集的概率分布，然后利用这个分布来指导下一步的采样过程
- 在这个过程中，算法实际上是在尝试最小化目标分布（最优解的分布）和当前采样分布之间的交叉熵，因此得名“Cross Entropy 方法”
- 这种方法能够有效地解决一些复杂的优化问题，尤其是在高维空间中寻找最优解的问题
交叉熵方法的核心思想
- 在 Cross Entropy (CE) 方法中，最小化目标分布 \(P^*\) （最优解的分布）和当前采样分布 \(Q\) 之间的交叉熵是一个核心思想
- 这个过程可以通过以下步骤来理解：
定义目标
- 首先定义目标是找到一个分布 \(Q\)，使得 \(Q\) 尽可能接近目标分布 \(P^*\)
- 这里 \(P^*\) 通常是一个难以直接求解的分布，因为它对应于所有可能解中的最优解
交叉熵作为度量
- 使用交叉熵 \(H(P^*, Q)\) 作为度量 \(P^*\) 和 \(Q\) 之间差异的标准，交叉熵定义为：
$$ H(P^*, Q) = -\sum_x P^*(x) \log Q(x) $$ - 这里 \(x\) 表示解空间中的一个点， \(P^*(x)\) 是 \(x\) 属于最优解的概率，而 \(Q(x)\) 是 \(x\) 被当前采样分布选中的概率
精英集的选择
- 在 CE 方法中，我们并不直接计算 \(P^*\)，而是通过迭代过程逐步逼近 \(P^*\)
- 每一步，我们从当前的分布 \(Q\) 中随机采样一组解，然后选择表现最好的一部分解（称为精英集）
- 假设我们采样了 \(N\) 个解，并选择了其中表现最好的 \(N_e\) 个解作为精英集
更新分布
- 接下来，基于精英集来更新分布 \(Q\)
- 目标：希望新的 \(Q\) 更好地拟合精英集中的解
- 这可以通过计算精英集的统计特性（如均值和协方差）来实现
- 如果 \(Q\) 是一个高斯分布，我们可以计算精英集的均值 \(\mu_e\) 和协方差矩阵 \(\Sigma_e\)，并用它们来更新 \(Q\) 的参数：
$$ \mu_{\text{new}} = \frac{1}{N_e} \sum_{i=1}^{N_e} x_i \\
\Sigma_{\text{new}} = \frac{1}{N_e} \sum_{i=1}^{N_e} (x_i - \mu_{\text{new}})(x_i - \mu_{\text{new}})^T $$
重复迭代
- 上述过程构成了 CE 方法的一个迭代步骤。我们重复执行采样、选择精英集和更新分布的过程，直到 \(Q\) 收敛到一个接近 \(P^*\) 的分布，或者满足某个停止条件（如达到最大迭代次数或分布变化小于某个阈值）
最小化交叉熵的直观解释
- 通过选择精英集并更新分布，CE 方法实际上是在逐步减少 \(P^*\) 和 \(Q\) 之间的交叉熵
- 这是因为每次迭代后，新的分布 \(Q\) 更加集中在那些表现好的解上，从而更接近 \(P^*\)
- 从数学上看，选择精英集并更新分布的过程可以看作是在最小化 \(P^*\) 和 \(Q\) 之间的 KL 散度（Kullback-Leibler divergence），而 KL 散度与交叉熵密切相关：
$$ D_{\text{KL}}(P^* | Q) = H(P^*, Q) - H(P^*) $$ - 由于 \(H(P^*)\) 是常数，最小化 \(D_{\text{KL}}(P^* | Q)\) 等价于最小化 \(H(P^*, Q)\)