Mini-buckets: a general scheme for approximating inference
作者： Rina Dechter , Irina Rish
DOI:
关键词:
摘要: The paper presents a class of approximation algorithms that extend the idea bounded-complexity inference, inspired by successful constraint propagation algorithms, to probabilistic inference and combinatorial optimization. is bound dimensionality dependencies created algorithms. This yields parameterized scheme, called mini-buckets, offers adjustable trade-off between accuracy efficiency. minibucket approach optimization problems, such as finding most probable explanation (MPE) in Bayesian networks, generates both an approximate solution bounds on quality. We present empirical results demonstrating performance proposed scheme for MPE task, randomly generated problems realistic domains medical diagnosis decoding.
参考文章(75)
M. A. Shwe, D. E. Heckerman, M. Henrion, E. J. Horvitz, H. P. Lehmann, G. F. Cooper, B. Middleton, Probabilistic diagnosis using a reformulation of the INTERNIST-1/QMR knowledge base. I. The probabilistic model and inference algorithms. Methods of Information in Medicine. ,vol. 30, pp. 241- 255 ,(1991) , 10.1055/S-0038-1634846
Eric J. Horvitz, Reasoning under varying and uncertain resource constraints national conference on artificial intelligence. pp. 111- 116 ,(1988)
Geoffrey E. Hinton, Brendan John Frey, Bayesian networks for pattern classification, data compression, and channel coding University of Toronto. ,(1997)
D. J. C. Mackay, Introduction to Monte Carlo methods Proceedings of the NATO Advanced Study Institute on Learning in graphical models. pp. 175- 204 ,(1998) , 10.1007/978-94-011-5014-9_7
Kalev Kask, Rina Dechter, A general scheme for automatic generation of search heuristics from specification dependencies Artificial Intelligence. ,vol. 129, pp. 91- 131 ,(2001) , 10.1016/S0004-3702(01)00107-2
Michael I Jordan, Zoubin Ghahramani, Tommi S Jaakkola, Lawrence K Saul, None, An introduction to variational methods for graphical models Machine Learning. ,vol. 37, pp. 105- 161 ,(1999) , 10.1023/A:1007665907178
Michael P. Wellman, Chao-Lin Liu, State-Space Abstraction for Anytime Evaluation of Probabilistic Networks Uncertainty Proceedings 1994. pp. 567- 574 ,(1994) , 10.1016/B978-1-55860-332-5.50077-8
Kalev Kask, None, New Search Heuristics for Max-CSP principles and practice of constraint programming. pp. 262- 277 ,(2000) , 10.1007/3-540-45349-0_20
Eric J. Horvitz, Reasoning about beliefs and actions under computational resource constraints uncertainty in artificial intelligence. pp. 429- 447 ,(1987)
Rina Dechter, Mini-buckets: a general scheme for generating approximations in automated reasoning international joint conference on artificial intelligence. pp. 1297- 1302 ,(1997)