Cross-entropy Method（简称CEM）虽然是一种基于交叉熵的算法，但并不是我们熟知的监督学习中的交叉熵方法，与其说它是一种基于交叉熵的算法，倒不如说是一种基于蒙特卡洛和进化策略的算法。CEM算法不仅可以用作评估，也可以作为一种有效的优化算法，与进化算法（EAs）类似CEM是一种完全免梯度（gradients free）的算法。

这里引用维基百科上对Cross-entropy Method的解释[1]：

The cross-entropy (CE) method is a Monte Carlo method for importance sampling and optimization. It is applicable to both combinatorial and continuous problems, with either a static or noisy objective.

CEM算法的迭代训练过程可以分为两个阶段：

Importance sampling

CEM要解决的是这样一种问题，假设我们需要估计一个事件$H(x)$发生的期望：

$$mathbb{E}_{u}[H(x)]=int H(x)f(x;u)dx$$

最简单的方法就是利用朴素蒙特卡洛采样从真实概率密度函数$f(x;u)$中采样一些样本$x^{"}$，然后通过求均值估计期望，即：

$$mathbb{E}_{u}[H(x)]=frac{1}{N}sum_{i=1}^{N}x_{i}^{"}$$

但如果事件$H(x)$是一种小概率事件，那么朴素蒙特卡洛模拟需要采样非常多的样本才能准确估计期望。针对这个问题，CEM算法引入了重要性采样（importance sampling）。

Importance sampling[2]的主要思想如下：

首先通过一个类似于目标概率分布的采样概率分布$f(x;v)$（其中$v$被称为reference parameter）来进行采样，则期望变为：

$$mathbb{E}_{u}[H(x)]=frac{1}{N}sum_{i=1}^{N}x_{i}^{"}frac{f(x;u)}{f(x;v)}$$

于是现在的目标变成了如何找到一个最优的采样概率函数$f(x;v^{*})$去指导采样出一些少量的样本来准确地估计期望。CEM在每次迭代中通过选取较好的采样样本（Elite samples）来更新采样概率函数的参数$v$，目的是减小当前采样概率函数$f(x;v)$与最优采样概率函数$f(x;v^{*})$的分布差距（即KL散度，相对熵）（PS：paper最后只用到了交叉熵，所以取名为CEM）。

Pseudo-code of CEM

下面给出一个以高斯分布作为采样概率分布的CEM伪代码：

# Step1: initialization初始化采样概率分布参数：mu, sigma；初始化当前迭代次数t=0，设置最大迭代次数max_its，样本个数N，精英样本个数Ne，以及采样方差的误差范围epsilon；for t in range(0, max_its):# Step2: 使用高斯分布进行随机采样X = SampleGaussian(mu, sigma, N)# Step3: 评估样本S = EvaluateSamples(X)# Step4: 重要性采样X = sort(X, S)mu = mean(X[0:Ne-1])sigma = var(X[0:Ne-1])if sigma > epsilon:break# Step5: 返回精英样本的均值return mu

CEM && RL

注：以下内容引自博文《进化策略优化算法CEM(Cross Entropy Method)》[3]。

CEM也可以用来求解马尔可夫决策过程，也就是强化学习问题。我们知道，强化学习也是一种动态规划过程，在某个状态下选择某个动作就像在某个节点选择路径一样，整个过程就是一个从初始状态到末状态的路径规划问题，只不过我们希望得到一条能最大化收益的路径。在这种考虑下，就可以用CEM建模了，我们让一条完整的路径成为一个样本$x=(s_0,a_0,s_1,a_1,…,s_n,a_n)$，路径获得的总收益为$S(x)=sum_{i=0}^{N} r(s_i,a_i)$，目标是最大化这个$S(x)$，那么如何采样出这些样本呢？我们可以构建一个$p$矩阵：矩阵行表示状态，列表示动作，如$p_{ij}$表示在状态$s_i$下执行$a_j$动作的概率，我们通过对这个$p$矩阵进行多次采样就可以获得多个样本，然后选出$S(x)$较高的样本用来更新$p$矩阵，不断迭代，最终找到最优$hat{p}$矩阵。

这是一种类似于策略迭代(policy iteration)的强化学习方法：通过$p$矩阵找到在每一步状态下各个动作的概率来形成决策策略，但参数更新并没有用到梯度。从另外一个角度，你也可以认为这是一种值迭代(value iteration)的强化学习方法，此时$p$矩阵就是经典Q-learning中的$Q$矩阵，只不过$Q$矩阵中第$i$行第$j$列元素表示的是状态$s_i$下动作$a_j$的未来收益的期望，基于贝尔曼方程(Bellman equation)来更新Q值；而$p$矩阵表示的是概率值，通过交叉墒来更新。

Reference

[1] 维基百科：Cross-entropy Method

[2] 维基百科：Importance sampling

[3] 进化策略优化算法CEM(Cross Entropy Method)