M.Sc Student | Dmitry Lifshits |
---|---|

Subject | Cross-Entropy Application for Combinatorial Optimization, Counting and Rare Events Estimation |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Emeritus Rubinstein Reuven-Yacov (Deceased) |

Full Thesis text |

We introduce a new method, called the *parametric
minimum cross-entropy *(PME) method for rare event probability estimation
and counting with a particular emphasis on the satisfiability problem. The PME
method is derived from the well known Kullback's minimum cross-entropy method,
called *MinxEnt*. It is based on the marginal distributions derived from
the optimal joint MinxEnt distribution and presents, in fact, a parametric
version of it. Similar to *cross-entropy *(CE) or *variance minimization
*(VM) method, the PME algorithm first casts the underlying counting problem
into an associated rare-event probability estimation problem, and then finds
the optimal parameters of the importance sampling distribution to estimate
efficiently the desired quantity.

We present supportive numerical results for counting the number of satisfiability assignments and compare PME with the CE or VM method. Our numerical results suggest that the PME method is superior to CE or VM and has polynomial running time in the size of the problem. This is based on the fact that for the satisfiability problem and some other ones involving separable functions the optimal parameters of the importance sampling distribution can be estimated better with the MinxEnt type procedure, rather then with indicators.

In this work we show how to resolve, at least
partially, the curse of dimensionality of likelihood ratios while using
importance sampling (IS) to estimate the performance of high-dimensional Monte Carlo simulation problems. The curse of dimensionality, which is better know under
the name, the *degeneracy *properties of likelihood ratios, is one of the
central topics in Monte Carlo simulation.

The current state-of-the art with IS can be
summarized as follows: *do not use IS in high dimensional problems because of
the degeneracy properties of likelihood ratios*. We present a simple method,
called the *screening *method, which typically allows substantial
reduction of the size of the likelihood ratio. By doing so not only we
automatically prevent from the degeneracy of the IS estimators, but at the same
time we obtain substantial variance reduction.

The main idea behind the screening algorithm is to
identify (screen out) the most important parameters of the IS estimator, the
so-called *bottleneck *parameter vector, which for typical simulation
problems are know to be of low-dimension. As soon as the bottleneck parameter
vector is identified, we replace the standard IS estimator with its new
low-dimension alternative, where the size of the LR equal to the size of the
bottleneck parameter vector. Supportive numerical results are presented.