Cross-Entropy Method
The cross-entropy method adaptively learns a good importance-sampling distribution for rare events by iteratively fitting to the best samples.
Adaptive proposal search
Choosing a good importance-sampling proposal by hand is hard, especially for rare events. The cross-entropy method automates it: starting from the nominal distribution, it repeatedly samples, keeps the samples closest to the rare event, and refits the proposal to those elite samples, moving the distribution toward the failure region over a few iterations.
The iteration
- Sample from the current proposal
- Rank samples by proximity to the rare event (a performance function)
- Select the top quantile (elite set)
- Update proposal parameters to maximum likelihood on the elite set
- Repeat until the rare-event threshold is reached
Why cross-entropy
Each update minimizes the KL (cross-entropy) divergence between the ideal zero-variance proposal and the chosen parametric family, hence the name. For distributions in the exponential family the update has a closed form, making each iteration cheap.
Rare-event probability
Once the proposal concentrates on the failure region, a final importance-sampling estimate with the learned proposal gives a low-variance estimate of the small probability. The intermediate thresholds create a smooth path from the nominal region to the rare event, avoiding the sample starvation of a single-shot estimate.
Cautions
The method assumes the proposal family can represent the important region; a unimodal Gaussian proposal will fail for multiple disjoint failure modes. In high dimensions the elite set can become uninformative. For structural reliability the related subset simulation is often more robust, and the two are complementary tools in the rare-event toolbox.