ACMD Seminar: Stochastic Enumeration with Importance Sampling

Alathea Jensen
Doctoral Candidate, George Mason University and Guest Researcher, ACMD, NIST

Monday, December 11, 2017, 15:00 - 16:00
Building 222, Room B-263
Gaithersburg

Monday, December 11, 2017, 13:00 - 14:00
Room 1-4058
Boulder

Slides: Adobe PDF

Host: Isabel Beichl

Abstract: A great many varied problems in the computational sciences can be solved by summing a cost function over the nodes of a decision tree, and many approximation algorithms exist to estimate such sums. One of the most recent of these algorithms is Stochastic Enumeration (SE), introduced in 2013 by Rubinstein. In 2015, Vaisman and Kroese provided a rigorous analysis of the variance of SE, and also showed that SE can be extended to a fully polynomial randomized approximation scheme for certain cost functions on random trees. However, no one has yet incorporated an importance function into SE to allow non-uniform selection of tree nodes. This talk will present an algorithm that incorporates an importance function into SE, and will provide theoretical analysis including proof of correctness and bounds on the variance of estimates produced by the algorithm. The talk will also present the results of numerical experiments to measure the variance of applications of the algorithm to practical problems, such as counting linear extensions of a poset.

Bio: Alathea is a doctoral candidate at George Mason University, planning to graduate in the spring. Her adviser is Jim Lawrence, and for the past year and a half she has been working as a guest researcher at NIST, under the guidance of Isabel Beichl, with whom she have been working on sequential importance sampling algorithms.