Initialization and Restart in Stochastic Local Search: Computing a Most Probable Explanation in Bayesian Networks
| Autor: | David C. Wilkins, Ole J. Mengshoel, Dan Roth |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
FOS: Computer and information sciences
Mathematical optimization Computer science Initialization Computer Science::Artificial Intelligence Viterbi algorithm symbols.namesake Search algorithm Search problem Local search (optimization) Computer Engineering Cluster analysis Greedy algorithm Stochastic process business.industry Bayesian network Approximation algorithm Mixture model Stochastic programming Computer Science Applications Randomized algorithm Dynamic programming Exact algorithm Computational Theory and Mathematics 80309 Software Engineering symbols Computational problem business Algorithm Information Systems |
| DOI: | 10.1184/r1/6709961 |
| Popis: | For hard computational problems, stochastic local search has proven to be a competitive approach to finding optimal or approximately optimal problem solutions. Two key research questions for stochastic local search algorithms are: Which algorithms are effective for initialization? When should the search process be restarted? In the present work, we investigate these research questions in the context of approximate computation of most probable explanations (MPEs) in Bayesian networks (BNs). We introduce a novel approach, based on the Viterbi algorithm, to explanation initialization in BNs. While the Viterbi algorithm works on sequences and trees, our approach works on BNs with arbitrary topologies. We also give a novel formalization of stochastic local search, with focus on initialization and restart, using probability theory and mixture models. Experimentally, we apply our methods to the problem of MPE computation, using a stochastic local search algorithm known as Stochastic Greedy Search. By carefully optimizing both initialization and restart, we reduce the MPE search time for application BNs by several orders of magnitude compared to using uniform at random initialization without restart. On several BNs from applications, the performance of Stochastic Greedy Search is competitive with clique tree clustering, a state-of-the-art exact algorithm used for MPE computation in BNs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|