Cross-entropy method: Difference between revisions

Revision as of 04:42, 30 June 2006

Revision as of 22:05, 17 August 2006

Line 1:

The '''Crosscross-Entropyentropy (CE) method''' attributed to Reuven Rubinstein is a general [[Monte_Carlo_method|Monte Carlo]] approach to

[[Combinatorial_optimizationCombinatorial optimization|combinatorial]] and [[Continuous_optimizationContinuous optimization|continuous]] multi-extremal [[Optimization_Optimization (mathematics)|optimization]] and [[importance sampling]].

The method originated from the field of ''rare event simulation'', where

very small probabilities need to be accurately estimated, for example in network reliability analysis, queueing models, or performance analysis of telecommunication systems.

The CE method can be applied to static and noisy combinatorial optimization problems such as the [[Traveling_salesman_problem|traveling salesman problem]], the [[Quadratic_assignment_problem|quadratic assignment problem]], [[Sequence_alignment|DNA sequence alignment]], the [[Maxcut|max-cut]] problem and the buffer allocation problem, as well as continuous [[Global_optimization|global optimization]] problems with many local [[Extremaextremum|extrema]].

In a nutshell the CE method consists of two phases:

#Generate a random data sample (trajectories, vectors, etc.) according to a specified mechanism.

#Update the parameters of the random mechanism based on the data to produce a "better" sample in the next iteration. This step involves minimizing the ''Cross Entropy'' or [[Kullback-Leibler divergence|Kullback-Leibler]] divergence.

===Estimation via Importance Sampling===

Line 15 ⟶ 14:

<math> g^*(\mathbf{x}) = H(\mathbf{x}) f(\mathbf{x};\mathbf{u})/\ell</math>. This, however, depends on the unknown <math>\ell</math>. The CE method aims to approximate the optimal pdf by adaptively selecting members of the parametric family that are closest (in the [[Kullback-Leibler divergence|Kullback-Leibler]] sense) to the optimal pdf <math>g^*</math>.

===Generic CE Algorithmalgorithm===

1. Choose initial parameter vector <math>\mathbf{v}^{(0)}</math>; set t = 1.

2. Generate a random sample <math>\mathbf{X}_1,\dots,\mathbf{X}_N</math> from <math>f(\cdot;\mathbf{v}^{(t-1)})</math>

Line 25 ⟶ 24:

* When <math>f\,</math> belongs to the [[Exponential_family|natural exponential family]]

* When <math>f\,</math> is [[discrete]] with finite [[Support (mathematics)|support]]

* When <math>H(\mathbf{X}) = \mathrm{I}_{\{\mathbf{x}\in A\}}</math> and <math>f(\mathbf{X}_i;\mathbf{u}) = f(\mathbf{X}_i;\mathbf{v}^{(t-1)})</math>, then <math>\mathbf{v}^{(t)}</math> corresponds to the [[Maximum_likelihood|Maximum Likelihoodlikelihood|maximum likelihood Estimatorestimator]] based on those <math>\mathbf{X}_k \in A</math>.

=== Continuous Optimization - Exampleoptimization&mdash;example===

The same CE algorithm can be used for optimization, rather than estimation.

Suppose the problem is to maximize some function <math>S(x)</math>, for example,