Cross-entropy method: Difference between revisions

Revision as of 23:51, 31 October 2013

Revision as of 23:53, 31 October 2013

Line 1:

{{no footnotes|date=September 2013}}

{{ref improve|date=September 2013}}

The '''cross-entropy (CE) method''' attributed to [[Reuven Rubinstein]] is a general [[Monte_Carlo_methodMonte Carlo method|Monte Carlo]] approach to

[[Combinatorial optimization|combinatorial]] and [[Continuous optimization|continuous]] multi-extremal [[Optimization (mathematics)|optimization]] and [[importance sampling]].

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

Line 10:

#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|''cross-entropy'']] or [[Kullback-LeiblerKullback–Leibler divergence]].

==Estimation via importance sampling==

Consider the general problem of estimating the quantity <math>\ell = \mathbb{E}_{\mathbf{u}}[H(\mathbf{X})] = \int H(\mathbf{x})\, f(\mathbf{x}; \mathbf{u})\, \textrm{d}\mathbf{x}</math>, where <math>H</math> is some ''performance function'' and <math>f(\mathbf{x};\mathbf{u})</math> is a member of some [[parametric family]] of distributions. Using [[importance sampling]] this quantity can be estimated as <math>\hat{\ell} = \frac{1}{N} \sum_{i=1}^N H(\mathbf{X}_i) \frac{f(\mathbf{X}_i; \mathbf{u})}{g(\mathbf{X}_i)}</math>, where <math>\mathbf{X}_1,\dots,\mathbf{X}_N</math> is a random sample from <math>g\,</math>. For positive <math>H</math>, the theoretically ''optimal'' importance sampling [[probability density function|density]] (pdf)is given by

<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-LeiblerKullback–Leibler divergence|Kullback-LeiblerKullback–Leibler]] sense) to the optimal PDF <math>g^*</math>.

==Generic CE algorithm==

Line 69:

==References==

*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--6719–67.[http://www.maths.uq.edu.au/~kroese/ps/aortut.pdf]

*Rubinstein, R.Y. (1997). Optimization of Computer simulation Models with Rare Events, ''European Journal of Operations Research'', '''99''', 89-11289–112.

*Rubinstein, R.Y., Kroese, D.P. (2004). ''The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning'', Springer-Verlag, New York.