Mini-buckets
Authors:
Open Access
- 1 March 2003
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 50 (2) , 107-153
Abstract
This article presents a class of approximation algorithms that extend the idea of bounded-complexity inference, inspired by successful constraint propagation algorithms, to probabilistic inference and combinatorial optimization. The idea is to bound the dimensionality of dependencies created by inference algorithms. This yields a parameterized scheme, calledmini-buckets, that offers adjustable trade-off between accuracy and efficiency. The mini-bucket approach to optimization problems, such as finding the most probable explanation (MPE) in Bayesian networks, generates both an approximate solution and bounds on the solution quality. We present empirical results demonstrating successful performance of the proposed approximation scheme for the MPE task, both on randomly generated problems and on realistic domains such as medical diagnosis and probabilistic decoding.Keywords
This publication has 35 references indexed in Scilit:
- A general scheme for automatic generation of search heuristics from specification dependencies☆☆Preliminary versions of this paper were presented in [15,16,18]. This work was supported in part by NSF grant IIS-0086529 and by MURI ONR award N00014-00-1-0617.Artificial Intelligence, 2001
- Bucket elimination: A unifying framework for reasoningArtificial Intelligence, 1999
- Deterministic approximation of marginal probabilities in Bayes netsIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 1998
- Local and global relational consistencyTheoretical Computer Science, 1997
- Probabilistic conflicts in a search algorithm for estimating posterior probabilities in Bayesian networksArtificial Intelligence, 1996
- On the hardness of approximate reasoningArtificial Intelligence, 1996
- Optimal decomposition of probabilistic networks by simulated annealingStatistics and Computing, 1992
- Internist-I, an Experimental Computer-Based Diagnostic Consultant for General Internal MedicineNew England Journal of Medicine, 1982
- Synthesizing constraint expressionsCommunications of the ACM, 1978
- A simple derivation of the coding theorem and some applicationsIEEE Transactions on Information Theory, 1965