More Web Proxy on the site http://driver.im/

article

Mini-buckets: A general scheme for bounded inference

Authors:

Irina RishAuthors Info & Claims

Journal of the ACM (JACM), Volume 50, Issue 2

Pages 107 - 153

https://doi.org/10.1145/636865.636866

Published: 01 March 2003 Publication History

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, called mini-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.

References

[1]

Arnborg, S. A. 1985. Efficient algorithms for combinatorial problems on graphs with bounded decomposability---A survey. BIT 25, 2--23.]]

Digital Library

[2]

Berrou, G., Glavieux, A., and Thitimajshima, P. 1993. Near Shannon limit error-correcting coding: Turbo codes. In Proceedings of the 1993 International Conference on Communications (Geneva, May).]]

[3]

Bertele, U., and Brioschi, F. 1972. Nonserial Dynamic Programming. Academic Press, New York.]]

Digital Library

[4]

Boddy, M., and Dean, T. L. 1989. Solving time-dependent planning problems. In Proceedings of the 11th International Joint Conference on Artificial Intelligence. pp. 979--984.]]

[5]

Bodlaender, H. L. 1997. Treewidth: Algorithmic techniques and results. In Proceedings of 22nd International Symposium on Mathematical Foundations of Computer Science (MFCS'97). Lecture Notes in Computer Science, vol. 1295. Springer-Verlag, New York, pp. 19--36.]]

Digital Library

[6]

Bodlaender, H. L., Koster, A. M., Eijkhof, F. V., and Van der Gaag, L. C. 2001. Pre-processing for triangulation of probabilistic networks. In Proceedings of 17th Annual Conference of Uncertainty in Artificial Intelligence (UAI01). pp. 32--39.]]

Digital Library

[7]

Boyen, X., and Koller, D. 1998. Tractable inference for complex stochastic processes. In Proceedings of 14th annual conference on Uncertainty in AI (UAI) (Madison, Wisc). pp. 33--42.]]

[8]

Cannings, C., Thompson, E. A., and Skolnick, H. H. 1978. Probability functions on complex pedigrees. Adv. Appl. Prob. 10, 26--61.]]

[9]

Cheng, J.-F. 1997. Iterative decoding. Ph.D. dissertation. Caltech, Pasadena, Calif.]]

Digital Library

[10]

Cooper, G. F. 1990. The computational complexity of probabilistic inference using Bayesian belief networks. Artif. Intel. 42, 2--3, 393--405.]]

Digital Library

[11]

Dagum, P., and Luby, M. 1993. Approximating probabilistic inference in Bayesian belief networks is NP-hard. Artif. Intel. 60, 1, 141--155.]]

Digital Library

[12]

D'Ambrosio, B. 1994. Symbolic probabilistic inference in large BN2O networks. In Proceedings of the 10th Conference on Uncertainty in Artificial Intelligence. pp. 128--135.]]

[13]

Davis, M., and Putnam, H. 1960. A computing procedure for quantification theory. J. ACM 7, 3.]]

Digital Library

[14]

Dean, T. L., and Boddy, M. 1988. An analysis of time-dependent planning. In Proceedings of the 7th National Conference on Artificial Intelligence. PP. 49--54.]]

[15]

Dechter, R. 1992. Constraint networks. In Encyclopedia of Artificial Intelligence, 2nd ed. Wiley, New York, pp. 276--285.]]

[16]

Dechter, R. 1996. Bucket elimination: A unifying framework for probabilistic inference. In Proceedings of 12th Conference on Uncertainty in Artificial Intelligence (UAI-96). pp. 211--219.]]

[17]

Dechter, R. 1997a. Bucket elimination: A unifying framework for processing hard and soft constraints. CONSTRAINTS: An Int. J. 2, 51--55.]]

Digital Library

[18]

Dechter, R. 1997b. Mini-buckets: A general scheme for generating approximations in automated reasoning. In Proceedings of the 15th International Joint Conference of Artificial Intelligence (IJCAI-97) (Japan). pp. 1297--1302.]]

[19]

Dechter, R. 1998. Constraint satisfaction. In MIT Encyclopedia of the Cognitive Sciences (MITECS). MIT Cambridge, Mass.]]

[20]

Dechter, R. 1999. Bucket elimination: A unifying framework for reasoning. Artif. Intel. 113, 41--85.]]

Digital Library

[21]

Dechter, R., and Frost, D. 1997. Backtracking algorithms for constraint satisfaction problems, a tutorial survey. Tech. rep., UCI.]]

[22]

Dechter, R., Kask, K., and Mateescu, R. 2002. Iterative join-graph propagation. In Proceedings of UAI-02.]]

[23]

Dechter, R., and Pearl, J. 1987. Network-based heuristics for constraint satisfaction problems. Artif. Intel. 34, 1--38.]]

Digital Library

[24]

Dechter, R., and Rish, I. 1994. Directional resolution: The Davis--Putnam procedure, revisited. In Principles of Knowledge Representation and Reasoning (KR-94). pp. 134--145.]]

[25]

Dechter, R., and Rish, I. 1997. A scheme for approximating probabilistic inference. In Proceedings of the 13th Conference on Uncertainty in Artificial Intelligence (UAI97).]]

[26]

Dechter, R., and van Beek, P. 1997. Local and global relational consistency. Theoret. Comput. Sci. pp. 283--308.]]

Digital Library

[27]

Draper, D. 1995. Localized partial evaluation of belief networks. Tech. rep. Ph.D. dissertation. University of Washington.]]

Digital Library

[28]

El Fattah, Y., and Dechter, R. 1995. Diagnosing tree-decomposable circuits. In Proceedings of the International Joint Conference of Artificial Intelligence (IJCAI-95) (Montreal, Ont., Canada, Aug.). pp. 1742--1748.]]

[29]

Jensen, F., and Andersen, S. K. 1990. Approximations in Bayesian belief universes for knowledge-based systems. In Proceedings of the 6th Conference on Uncertainty in Artificial Intelligence.]]

[30]

Freuder, E. C. 1978. Synthesizing constraint expressions. Commun. ACM 21, 11, 958--965.]]

Digital Library

[31]

Freuder, E. C. 1982. A sufficient condition for backtrack-free search. J. ACM 21, 11, 958--965.]]

Digital Library

[32]

Frey, B. J. 1998. Graphical Models for Machine Learning and Digital Communication. MIT Press, Cambridge, Mass.]]

Digital Library

[33]

Frey, B. J. 1998. Graphical Models for Machine Learning and Digital Communication. MIT Press, Cambridge, Mass.]]

Digital Library

[34]

Frey, B. J., and MacKay, D. J. C. 1998. A revolution: belief propagation in graphs with cycles. Adv. Neural Inf. Proc. Syst. 10.]]

Digital Library

[35]

Gallager, R. G. 1965. A simple derivation of the coding theorem and some applications. IEEE Trans. Inf. Theory IT-11, 3--18.]]

Digital Library

[36]

Guo, H., and Hsu, W. 2002. A survey on algorithms for real-time Bayesian network inference. In Proceedings of the Joint AAAI-02/KDD-02/UAI-02 Workshop on Real-Time Decision Support and Diagnosis Systems (Edmonton, Alberta, Canada).]]

[37]

Heckerman, D. and Breese, J. 1995. Causal independence for probability assessment and inference using Bayesian networks. Tech. Rep. MSR-TR-94-08, Microsoft Research.]]

[38]

Horvitz, E. 1987. Reasoning about beliefs and actions under computational resource constraints. In Proceedings of the 3rd Conference on Uncertainty in Artificial Intelligence (UAI-87) (Seattle, Wash.). pp. 301--324.]]

[39]

Horvitz, E. 1988. Reasoning under varying and uncertain resource constraints. In Proceedings of the 4th Conference on Uncertainty in Artificial Intelligence (UAI-88). pp. 111--116.]]

[40]

Horvitz, E. 1990. Computation and action under bounded resources. Ph.D. dissertation. Stanford Univ., Stanford, Calif.]]

Digital Library

[41]

Horvitz, E., Suermondt, H. J., and Cooper, G. F. 1989. Bounded conditioning: Flexible inference for decisions under scarce resources. In Proceedings of the 5th Conference on Uncertainty in Artificial Intelligence (UAI-89). pp. 182--193.]]

[42]

Kask, K., Rish, I., and Dechter, R. 1998. Approximation algorithms for probabilistic decoding. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI-98).]]

[43]

Jaakkola, T. S., and Jordan, M. I. 1996. Recursive algorithms for approximating probabilities in graphical models. Adv. Neural Inf. Proc. Syst. 9.]]

[44]

Jordan, M. I., Ghahramani, Z., Jaakkola, T. S., and Saul, L. K. 1998. An Introduction to Variational Methods for Graphical Models. Kluwer Academic Publishers.]]

[45]

Kask, K. 2000. New search heuristics for max-csp. In Proceedings of the Principles and Practice of Constraint Programming (CP2000). pp. 255--269.]]

Digital Library

[46]

Kask, K., and Dechter, R. 1999a. Mini-bucket heuristics for improved search. In Proceedings of 15th Conference on Uncertainty in Artificial Intelligence (UAI-99).]]

[47]

Kask, K., and Dechter, R. 1999b. Stochastic local search for bayesian networks. In Proceedings of Workshop on AI and Statistics (AISTAT'99). pp. 113--122.]]

[48]

Kask, K., and Dechter, R. 2001. A general scheme for automatic search heuristics from specification dependencies. Artif. Intel.]]

Digital Library

[49]

Kask, K., Dechter, R., Larrosa, J., and Fabio, G. 2001. Bucket-tree elimination for automated reasoning. Artif. Intel. 125, 91--131.]]

Digital Library

[50]

Kjaerulff, U. 1990. Triangulation of graph-based algorithms giving small total state space. Tech. Rep. 90-09, Department of Mathematics and Computer Science, Univ. Aalborg, Aalborg, Denmark.]]

[51]

Kjaerulff, U. 1992. Optimal decomposition of probabilistic networks by simulated annealing. Stat. Comput. 2, 7--17.]]

[52]

Kjaerulff, U. 1994. Reduction of computational complexity in Bayesian networks through removal of week dependencies. In Proceedings of the 10th Conference on Uncertainty in Artificial Intelligence (UAI-94).]]

[53]

Larrosa, J. 2000. On the time complexity of bucket elimination algorithms. ICS Tech. rep.]]

[54]

Lassez, J.-L., and Mahler, M. 1992. On Fourier's algorithm for linear constraints. J. Automat. Reas. 9.]]

Digital Library

[55]

Lauritzen, S. L., and Spiegelhalter, D. J. 1988. Local computation with probabilities on graphical structures and their application to expert systems. J. Roy. Stat. Soc., Seri. B 50, 2, 157--224.]]

[56]

MacKay, D. J. C. 1998. Introduction to Monte Carlo methods. In Learning in Graphical Models, M. I. Jordan, ed. Kluwer Academic Press.]]

Digital Library

[57]

MacKay, D. J. C., and Neal, R. M. 1996. Near Shannon limit performance of low density parity check codes. Electron. Lett. 33, 457--458.]]

[58]

Mackworth, A. K. 1977. Consistency in networks of relations. Artif. Intel. 8, 1, 99--118.]]

Digital Library

[59]

Mateescu, R., Dechter, R., and Kask, K. 2002. Tree approximation for belief updating. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI-2002) (Edmonton, Alberta, Canada). pp. 553--559.]]

Digital Library

[60]

McEliece, R. J., MacKay, D. J. C., and Cheng, J. F. 1997. Turbo decoding as an instance of Pearl's belief propagation algorithm. IEEE J. Select. Areas Commun.]]

[61]

Miller, R. A., Masarie, F. E., and Myers, J. 1986. Quick medical reference (QMR) for diagnostic assistance. Medi. Comput. 3, 5, 34--38.]]

[62]

Miller, R. A., Pople, H. E., and Myers, J. D. 1982. Internist-1: An experimental computer-based diagnostic consultant for general internal medicine. New Eng. J. Med. 307, 468--476.]]

[63]

Montanari, U. 1972. On the optimal approximation of discrete functions with low-dimensional tables. Inf. Proc. 71, 1363--1368.]]

[64]

Park, J. 2002. MAP complexity results and approximation methods. In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI) (San Francisco, Calif.) Morgan-Kaufmann, San Mateo, Calif., pp. 388--396.]]

Digital Library

[65]

Parker, R., and Miller, R. 1987. Using causal knowledge to create simulated patient cases: the CPCS project as an extension of INTERNIST-1. In Proceedings of the 11th Symposium Computer Applications in Medical Care, pp. 473--480.]]

[66]

Pearl, J. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan-Kaufmann, San Mateo, Calif.]]

Digital Library

[67]

Peng, Y., and Reggia, J. A. 1989. A connectionist model for diagnostic problem solving. IEEE Trans. Syst., Man and Cybernet.]]

[68]

Poole, D. 1996. Probabilistic conflicts in a search algorithm for estimating posterior probabilities in Bayesian networks. Artif. Intel. 88, 69--100.]]

Digital Library

[69]

Pradhan, M., Provan, G., Middleton, B., and Henrion, M. 1994. Knowledge engineering for large belief networks. In Proceedings of the 10th Conference on Uncertainty in Artificial Intelligence.]]

[70]

Rish, I., Brodie, M., and Ma, S. 2002. Accuracy vs. efficiency trade-offs in probabilistic diagnosis. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI2002) (Edmonton, Alb., Canada).]]

Digital Library

[71]

Rish, I., and Dechter, R. 1998. On the impact of causal independence. Tech. rep., Information and Computer Science, Univ. California, Irvine, Irvine, Calif.]]

[72]

Rish, I., and Dechter, R. 2000. Resolution vs. search; Two strategies for SAT. J. Automat. Reas. 24, 1/2, 225--275.]]

Digital Library

[73]

Robertson, N., and Seymour, P. 1995. Graph minor. XIII. The disjoint paths problem. Combinat. Theory, Ser. B 63, 65--110.]]

Digital Library

[74]

Roth, D. 1996. On the hardness of approximate reasoning. AI J. 82, 1-2 (Apr.), 273--302.]]

Digital Library

[75]

Santos, E. 1991. On the generation of alternative explanations with implications for belief revision. In Proceedings of the 7th Annual Conference on Uncertainty in Artificial Intelligence (UAI-91). pp. 339--347.]]

Digital Library

[76]

Santos, E. J., and Shimony, S. E. 1998. Deterministic approximation of marginal probabilities in Bayes nets. IEEE Trans. Syst. Man, Cybernet. 28, 4, 377--393.]]

Digital Library

[77]

Shachter, R. D. 1986. Evaluating influence diagrams. Oper. Res. 34.]]

[78]

Shannon, C. E. 1948. A mathematical theory of communication. Bell Syst. Tech. J. 27, 379--423, 623--656.]]

[79]

Shimony, S. E., and Charniack, E. 1991. A new algorithm for finding MAP assignments to belief networks. In Uncertainty in Artificial Intelligence, P. Bonissone, M. Henrion, L. Kanal, and J. Lemmer, Eds. pp. 185--193.]]

Digital Library

[80]

Shwe, M., Middleton, B. F., Heckerman, D. E., Henrion, M., Horvitz, E. J., Lehmann, H., and Cooper, G. F. 1991. Probabilistic diagnosis using a reformulation of the Internist-1/QMR knowledge base: I. The probabilistic model and inference algorithms. Meth. Inf. Med. 30, 241--255.]]

[81]

Tatman, J. A., and Shachter, R. D. 1990. Dynamic programming and influence diagrams. IEEE Trans. Syst. Man, Cyberneti.]]

[82]

van Engelen, R. A. 1997. Approximating Bayesian belief networks by arc removal. IEEE Trans. Patt. Anal. Mach. Intel. 19, 8, 916--920.]]

Digital Library

[83]

Weiss, Y. 1997. Belief propagation and revision in networks with loops. In Proceedings of the NIPS-97 Workshop on Graphical Models.]]

[84]

Wellman, M. P., and Liu, C. 1994. State-space abstraction for anytime evaluation of probabilistic networks. In Proceedings of the 10th Annual Conference on Uncertainty in Artificial Intelligence (UAI-94). pp. 567--574.]]

[85]

Yedidia, J., Freeman, W. T., and Weiss, Y. 2001. Generalized belief propagation. In NIPS 13. MIT Press, Cambridge, Mass, pp. 689--695.]]

[86]

Zhang, N. L., and Poole, D. 1996. Exploiting causal independence in Bayesian network inference. J. Artif. Intel. Res. 5, 301--328.]]

Digital Library

Cited By

Pezeshki BKask KIhler ADechter RKiyavash NMooij J(2024)Value-based abstraction functions for abstraction samplingProceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence10.5555/3702676.3702811(2861-2901)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.5555/3702676.3702811
Boizumault Pde Givry SLoudni SOuali A(2024)Variable Neighborhood Search for Cost Function NetworksHandbook of Formal Optimization10.1007/978-981-97-3820-5_10(847-875)Online publication date: 17-Jul-2024
https://doi.org/10.1007/978-981-97-3820-5_10
Marinescu RBhattacharjya DLee JGray ACozman FOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Credal marginal MAPProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668194(47804-47815)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668194
Show More Cited By

Index Terms

Mini-buckets: A general scheme for bounded inference

Recommendations

Mini-buckets: a general scheme for generating approximations in automated reasoning
IJCAI'97: Proceedings of the Fifteenth international joint conference on Artifical intelligence - Volume 2

The class of algorithms for approximating reasoning tasks presented in this paper is based on approximating the general bucket elimination framework. The algorithms have adjustable levels of accuracy and efficiency, and they can be applied uniformly ...
A modified VNS metaheuristic for max-bisection problems

Variable neighborhood search (VNS) metaheuristic as presented in Festa et al. [Randomized heuristics for the MAX-CUT problem, Optim. Methods Software 17 (2002) 1033-1058] can obtain high quality solution for max-cut problems. Therefore, it is worthwhile ...
Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference

A feedback vertex set of an undirected graph is a subset of vertices that intersects with the vertex set of each cycle in the graph. Given an undirected graph G with n vertices and weights on its vertices, polynomial-time algorithms are provided for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 50, Issue 2

March 2003

169 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/636865

Issue’s Table of Contents

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2003

Published in JACM Volume 50, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

142
Total Citations
View Citations
1,246
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)1

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pezeshki BKask KIhler ADechter RKiyavash NMooij J(2024)Value-based abstraction functions for abstraction samplingProceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence10.5555/3702676.3702811(2861-2901)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.5555/3702676.3702811
Boizumault Pde Givry SLoudni SOuali A(2024)Variable Neighborhood Search for Cost Function NetworksHandbook of Formal Optimization10.1007/978-981-97-3820-5_10(847-875)Online publication date: 17-Jul-2024
https://doi.org/10.1007/978-981-97-3820-5_10
Marinescu RBhattacharjya DLee JGray ACozman FOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Credal marginal MAPProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668194(47804-47815)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668194
Díaz-Macías EMoral S(2023)A Deletion Algorithm for the Marginal Problem in Propositional Logic Based on Boolean ArraysMathematics10.3390/math1112274811:12(2748)Online publication date: 17-Jun-2023
https://doi.org/10.3390/math11122748
Gao JChen ZZhang C(2023)Pretrained Parameter Configurator for Large Neighborhood Search to Solve Weighted Constraint Satisfaction Problems2023 International Joint Conference on Neural Networks (IJCNN)10.1109/IJCNN54540.2023.10191732(1-8)Online publication date: 18-Jun-2023
https://doi.org/10.1109/IJCNN54540.2023.10191732
Boizumault Pde Givry SLoudni SOuali A(2023)Variable Neighborhood Search for Cost Function NetworksHandbook of Formal Optimization10.1007/978-981-19-8851-6_10-1(1-29)Online publication date: 22-Jul-2023
https://doi.org/10.1007/978-981-19-8851-6_10-1
Montalbano PAllouche Dde Givry SKatsirelos GWerner T(2023)Virtual Pairwise Consistency in Cost Function NetworksIntegration of Constraint Programming, Artificial Intelligence, and Operations Research10.1007/978-3-031-33271-5_27(417-426)Online publication date: 29-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-33271-5_27
Deng YKong SLiu CAn BKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Deep attentive belief propagationProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602114(25436-25449)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602114
Chen DChen ZHe ZGao JSu Z(2022)Learning heuristics for weighted CSPs through deep reinforcement learningApplied Intelligence10.1007/s10489-022-03992-553:8(8844-8863)Online publication date: 3-Aug-2022
https://dl.acm.org/doi/10.1007/s10489-022-03992-5
Chen DChen ZDeng YHe ZWang L(2022)Inference-based complete algorithms for asymmetric distributed constraint optimization problemsArtificial Intelligence Review10.1007/s10462-022-10288-056:5(4491-4534)Online publication date: 3-Oct-2022
https://dl.acm.org/doi/10.1007/s10462-022-10288-0
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents