Cross-entropy method

Generic CE algorithm

1. Choose initial parameter vector ${\displaystyle {\mathbf{v}}^{(0)}}$; set t = 1.
2. Generate a random sample ${\displaystyle {\mathbf{X}}_1,\dots ,{\mathbf{X}}_N}$ from ${\displaystyle f(\cdot ;{\mathbf{v}}^{(t-1)})}$
3. Solve for ${\displaystyle {\mathbf{v}}^{(t)}}$, where
   ${\displaystyle {\mathbf{v}}^{(t)}=\underset{\mathbf{v}}{\text{argmax}}\frac{1}{N}\sum _{i=1}^{N}H({\mathbf{X}}_i)\frac{f({\mathbf{X}}_i;\mathbf{u})}{f({\mathbf{X}}_i;{\mathbf{v}}^{(t-1)})}\log f({\mathbf{X}}_i;\mathbf{v})}$
4. If convergence is reached then stop; otherwise, increase t by 1 and reiterate from step 2.

In several cases, the solution to step 3 can be found analytically. Situations in which this occurs are

• When ${\displaystyle f}$ belongs to the natural exponential family
• When ${\displaystyle f}$ is discrete with finite support
• When ${\displaystyle H(\mathbf{X})={\mathrm{I}}_{\{\mathbf{x}\in A\}}}$ and ${\displaystyle f({\mathbf{X}}_i;\mathbf{u})=f({\mathbf{X}}_i;{\mathbf{v}}^{(t-1)})}$, then ${\displaystyle {\mathbf{v}}^{(t)}}$ corresponds to the maximum likelihood estimator based on those ${\displaystyle {\mathbf{X}}_k\in A}$.

Continuous optimization—example

The same CE algorithm can be used for optimization, rather than estimation. Suppose the problem is to maximize some function ${\displaystyle S}$, for example, ${\displaystyle S(x)={\text{e}}^{-(x-2{)}^2}+0.8{\text{e}}^{-(x+2{)}^2}}$. To apply CE, one considers first the associated stochastic problem of estimating ${\displaystyle {\mathbb{P}}_{\mathit{\theta }}(S(X)\ge \gamma )}$ for a given level ${\displaystyle \gamma }$, and parametric family ${\displaystyle \left\{f(\cdot ;\mathit{\theta })\right\}}$, for example the 1-dimensional Gaussian distribution, parameterized by its mean ${\displaystyle {\mu }_t}$ and variance ${\displaystyle {\sigma }_t^2}$ (so ${\displaystyle \mathit{\theta }=(\mu ,{\sigma }^2)}$ here). Hence, for a given ${\displaystyle \gamma }$, the goal is to find ${\displaystyle \mathit{\theta }}$ so that ${\displaystyle D_{\mathrm{K}\mathrm{L}}({\text{I}}_{\{S(x)\ge \gamma \}}\Vert f_{\mathit{\theta }})}$ is minimized. This is done by solving the sample version (stochastic counterpart) of the KL divergence minimization problem, as in step 3 above. It turns out that parameters that minimize the stochastic counterpart for this choice of target distribution and parametric family are the sample mean and sample variance corresponding to the elite samples, which are those samples that have objective function value ${\displaystyle \ge \gamma }$. The worst of the elite samples is then used as the level parameter for the next iteration. This yields the following randomized algorithm that happens to coincide with the so-called Estimation of Multivariate Normal Algorithm (EMNA), an estimation of distribution algorithm.

Pseudocode

<i id="mwbQ">// Initialize parameters</i> <span typeof="mw:Entity" id="mwbg">μ</span> := −6 <span typeof="mw:Entity" id="mwbw">σ</span>2 := 100 t := 0 maxits := 100 N := 100 Ne := 10 <i id="mwcA">// While maxits not exceeded and not converged</i> <b id="mwcQ">while</b> t < maxits <b id="mwcg">and</b> <span typeof="mw:Entity" id="mwcw">σ</span>2 > <span typeof="mw:Entity" id="mwdA">ε</span> <b id="mwdQ">do</b> <i id="mwdg">// Obtain N samples from current sampling distribution</i> X := SampleGaussian(<span typeof="mw:Entity" id="mwdw">μ</span>, <span typeof="mw:Entity" id="mweA">σ</span>2, N) <i id="mweQ">// Evaluate objective function at sampled points</i> S := exp(−(X − 2) ^ 2) + 0.8 exp(−(X + 2) ^ 2) <i id="mweg">// Sort X by objective function values in descending order</i> X := sort(X, S) <i id="mwew">// Update parameters of sampling distribution via elite samples</i> <span typeof="mw:Entity" id="mwfA">μ</span> := mean(X(1:Ne)) <span typeof="mw:Entity" id="mwfQ">σ</span>2 := var(X(1:Ne)) t := t + 1 <i id="mwfg">// Return mean of final sampling distribution as solution</i> <b id="mwfw">return</b> <span typeof="mw:Entity" id="mwgA">μ</span>

Related methods

• Simulated annealing
• Genetic algorithms
• Harmony search
• Estimation of distribution algorithm
• Tabu search
• Natural Evolution Strategy
• Ant colony optimization algorithms

Journal papers

• De Boer, P.-T., Kroese, D.P., Mannor, S. and Rubinstein, R.Y. (2005). A Tutorial on the Cross-Entropy Method. Annals of Operations Research, 134 (1), 19–67.
• Rubinstein, R.Y. (1997). Optimization of Computer Simulation Models with Rare Events, European Journal of Operational Research, 99, 89–112.

Software implementations

• CEopt Matlab package
• CEoptim R package
• Novacta.Analytics .NET library