Cross-entropy method: Difference between revisions

Revision as of 18:17, 21 March 2007

Revision as of 07:30, 25 March 2007

Line 15:

==Generic CE algorithm==

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>

3. Solve for <math>\mathbf{v}^{(t)}</math>, where

<math>\mathbf{v}^{(t)} = \mathop{\textrm{argmax}}_{\mathbf{v}} \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})</math>

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 <math>f\,</math> belongs to the [[Exponential_family|natural exponential family]]

* When <math>f\,</math> is [[discrete space|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 likelihood estimator]] based on those <math>\mathbf{X}_k \in A</math>.

== Continuous optimization&mdash;example==