User talk:Botev (usurped)
The Cross-Entropy method is a Monte Carlo approach to combinatorial and continuous multi-extremal optimization and rare event simulation. The cross-entropy (CE) method has been successfully applied to static and noisy combinatorial optimization problems such as the traveling salesman problem, the quadratic assignment problem, DNA sequence alignment, the max-cut problem and the buffer allocation problem. The CE method has also been applied to global optimization problems where the objective function is continuous and has many local extrema. Other popular applications of the method include 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.
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.
The generality of the method lies in the fact that the updating rules are often simple and explicit (and hence fast), and are "optimal" in a well-defined mathematical sense.
Rare Event Estimation
[edit]Consider the weighted graph of the Figure below
with random weights . Suppose the weights are independent and exponentially distributed random variables with means , respectively. Denote the probability density function (pdf) of by ; thus,
Let be the total length of the shortest path from node A to
node B.
Of great interest is the estimation of the probability:
that is, the probability that the length of the shortest
path will
exceed some fixed . A straightforward way to estimate is to
use Crude Monte Carlo (CMC) simulation. That is, we draw a
random sample from the distribution
of and use
as the unbiased estimator of . However, for large the probability will be very small and CMC requires a very large simulation effort. Namely, needs to be very large in order to estimate accurately --- that is, to obtain a small relative error of 0.01, say. A better way to perform the simulation is to use importance sampling (IS). That is, let be another probability density such that . Using the density we can represent as
where the subscript means that the expectation is taken with respect to , which is called the Importance Sampling (IS) density. An unbiased estimator of is
where is called the importance sampling (IS) or the likelihood ratio (LR) estimator, is called the likelihood ratio, and is a random sample from , that is, are i.i.d. random vectors with density . Suppose that are independent and exponentially distributed with means . Then
The main problem now is how to select the which gives the most accurate estimate of for a given simulation effort. The CE method for rare-event simulation provides a fast and simple way to determine/estimate an optimal in some sense value for the parameter . To this end, without going into the details, a quite general CE algorithm for rare-event estimation is outlined next.
Algorithm
[edit]1. Define . Set (iteration counter).
2. Generate a random sample according to the pdf Calculate the performances for all , and order them from smallest to biggest, . Let be the sample -quantile of performances: , provided this is less than . Otherwise, put .
3. Use the same sample to calculate, for ,
4. If then proceed to Step 5; otherwise set and reiterate from Step 2.
5. Let be the final iteration. Generate a sample according to the pdf and estimate via the IS estimator
Note that in Steps 2--4 the optimal IS parameter is estimated. In
the final step (Step 5) this parameter is used to estimate the probability of interest. Note also that the
algorithm assumes availability of the parameters (typically between 0.01 and 0.1), and in advance. As an example, consider the case where the parameter
vector is given by and the probability that the minimum path is greater than has to be estimated . Crude Monte Carlo with samples gives an estimate with an estimated relative error, (RE), (that is, ) of . With samples the estimate with RE 0.03 is obtained. In contrast the CE algorithm with provides the estimated optimal parameter vector of = . The optimal is employed in the final importance sampling step of the Algorithm with and gives an estimate of with an estimated RE of . This simple example illustrates the advantage of using the CE method as compared to the naive CMC method. Typically the simulation effort (as measured by computing time) reduces dramatically and the final estimate of the quantity of interest is more accurate.
Generic CE Algorithm
[edit]A generic CE algorithm can be formulated for estimation problems of the form . Let be a member of a parametric family of distributions, and be a reference distribution from the same parametric family. (In some contexts (such as in rare-event estimation) there is a natural candidate for the reference distribution; in others, the reference distribution may correspond to an arbitrary initial distribution.) To proceed, estimate via importance sampling with , where is a random sample from . The following generic algorithm iteratively approaches the member of the given parametric family that is closest (in the Kullback-Leibler sense) to the zero variance importance sampling density (the that corresponds to a zero variance ).
1. Choose initial parameter vector ; set t = 1. 2. Generate a random sample from 3. Solve for , where 4. If convergence is reached then stop; otherwise, increase t by 1 and reiterate from step 2.
In some cases, the solution to can be found analytically. Situations in which this occurs are
- When belongs to the natural exponential family (single parameter member of the exponential family)
- When is discrete with finite support
- If and , then corresponds to the Maximum Likelihood Estimator based on those
Example (Continuous Optimization)
[edit]Suppose the problem of interest is to locate , where . Instead of proceeding directly, consider the estimation problem for a given , and parametric family (the so-called associated stochastic problem). In this example, the parametric family is taken to be a single Gaussian distribution, parameterized by its mean and variance (so here). Hence, for a given , the goal is to find so that is minimized. Further, instead of considering this KL divergence minimization problem directly, the sample version (stochastic counterpart) is considered. It turns out that parameters that minimize the stochastic counterpart for this choice of target distribution and parametric family are the mean and variance of those samples which have objective function value . This yields the following randomized algorithm for this problem.
Pseudo-code
[edit]1. mu:=-6; sigma2:=100; t:=0; maxits=100; // Initialize parameters 2. N:=100; Ne:=10; // 3. while t < maxits and sigma2 > epsilon // While not converged and maxits not exceeded 4. X = SampleGaussian(mu,sigma2,N); // Obtain N samples from current sampling distribution 5. S = exp(-(X-2)^2) 0.8 exp(-(X 2)^2); // Evaluate objective function at sampled points 6. X = sort(X,S); // Sort X by objective function values (in descending order) 7. mu = mean(X(1:Ne)); sigma2=var(X(1:Ne)); // Update parameters of sampling distribution 8. t = t 1; // Increment iteration counter 9. return mu // Return mean of final sampling distribution as solution
Related methods
[edit]See also
[edit]References
[edit]- 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., Kroese, D.P. (2004). The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning, Springer-Verlag, New York.
External links
[edit]Category:Heuristics Category:Optimization algorithms Category:Monte Carlo methods Category:Machine learning
See also
[edit]References
[edit]- 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., Kroese, D.P. (2004). The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning, Springer-Verlag, New York.
External links
[edit]Category:Heuristics Category:Optimization algorithms Category:Monte Carlo methods