טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentDmitry Lifshits
SubjectCross-Entropy Application for Combinatorial Optimization,
Counting and Rare Events Estimation
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Emeritus Rubinstein Reuven-Yacov (Deceased)
Full Thesis textFull thesis text - English Version


Abstract

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.