A Bayesian Approach to Tackling Hard Computational Problems
Eric Horvitz, Yongshao Ruan, Carla Gomes, Henry Kautz, Bart Selman, David Chickering
We are developing a general framework for using learned Bayesian models for decision-theoretic control of search and reasoningalgorithms. We illustrate the approach on the specific task of controlling both general and domain-specific solvers on a hard class of structured constraint satisfaction problems. A successful strategyfor reducing the high (and even infinite) variance in running time typically exhibited by backtracking search algorithms is to cut off and restart the search if a solution is not found within a certainamount of time. Previous work on restart strategies have employed fixed cut off values. We show how to create a dynamic cut off strategy by learning a Bayesian model that predicts the ultimate length of a trial based on observing the early behavior of the search algorithm. Furthermore, we describe the general conditions under which a dynamic restart strategy can outperform the theoretically optimal fixed strategy.
PDF Link: /papers/01/p235-horvitz.pdf
AUTHOR = "Eric Horvitz
and Yongshao Ruan and Carla Gomes and Henry Kautz and Bart Selman and David Chickering",
TITLE = "A Bayesian Approach to Tackling Hard Computational Problems",
BOOKTITLE = "Proceedings of the Seventeenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-01)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2001",
PAGES = "235--244"