Credal marginal MAP
AUTHORs: 
Radu Marinescu, Debarun Bhattacharjya, Junkyu Lee, Alexander Gray, Fabio CozmanAuthors Info & Claims
Article No.: 2072, Pages 47804 - 47815
Abstract
Credal networks extend Bayesian networks to allow for imprecision in probability values. Marginal MAP is a widely applicable mixed inference task that identifies the most likely assignment for a subset of variables (called MAP variables). However, the task is extremely difficult to solve in credal networks particularly because the evaluation of each complete MAP assignment involves exact likelihood computations (combinatorial sums) over the vertices of a complex joint credal set representing the space of all possible marginal distributions of the MAP variables. In this paper, we explore Credal Marginal MAP inference and develop new exact methods based on variable elimination and depth-first search as well as several approximation schemes based on the mini-bucket partitioning and stochastic local search. An extensive empirical evaluation demonstrates the effectiveness of our new methods on random as well as real-world benchmark problems.
References
[1]
Judea Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988.
[2]
Rina Dechter. Bucket elimination: A unifying framework for reasoning. Artificial Intelligence, 113:41-85, 1999.
[3]
James Park. MAP complexity results and approximation methods. In Uncertainty in Artificial Intelligence (UAI), pages 388-396, 2002.
[4]
Radu Marinescu, Rina Dechter, and Alexander Ihler. AND/OR search for marginal MAP. In Uncertainty in Artificial Intelligence (UAI), pages 563-572, 2014.
[5]
Junkyu Lee, Radu Marinescu, and Rina Dechter. Applying search based probabilistic inference algorithms to probabilistic conformant planning: Preliminary results. In Proceedings of the International Symposium on Artificial Intelligence and Mathematics (ISAIM), 2016.
[6]
Jose M. Bioucas-Dias and Mario A. T. Figueiredo. Bayesian image segmentation using hidden fields: Supervised, unsupervised, and semi-supervised formulations. In Proceedings of the European Signal Processing Conference (EUSIPCO), pages 523-527, 2016.
[7]
Evangelia Kyrimi, Scott McLachlan, Kudakwashe Dube, Mariana R. Neves, Ali Fahmi, and Norman Fenton. A comprehensive scoping review of bayesian networks in healthcare: Past, present and future. Artificial Intelligence in Medicine, 117, 2021.
[8]
Fabio Cozman. Generalizing variable-elimination in Bayesian networks. In Workshop on Probabilistic Reasoning in Bayesian Networks at SBIA/Iberamia 2000, pages 21-26, 2000.
[9]
Denis Maua and Fabio Cozman. Thirty years of credal networks: Specifications, algorithms and complexity. International Journal of Approximate Reasoning, 1(126):133-137, 2020.
[10]
Gregory Cooper. Nestor: A computer-based medical diagnosis aid that integrates causal and probabilistic knowledge. Technical report, Computer Science department, Stanford University, Palo-Alto, California, 1984.
[11]
Johan Kwisthout. Most probable explanations in Bayesian networks: Complexity and tractability. International Journal of Approximate Reasoning, 52(1):1452-1469, 2011.
[12]
Marco Zaffalon, Alessandro Antonucci, and Rafael Cabanas. Structural causal models are (solvable by) credal networks. In European Workshop on Probabilistic Graphical Models, 2020.
[13]
Isaac Levi. The Enterprise of Knowledge. MIT Press, 1980.
[14]
Peter Walley. Statistical Reasoning with Imprecise Probabilities. Chapman and Hall, London, UK, 1991.
[15]
Cassio Campos and Fabio Cozman. The inferential complexity of Bayesian and credal networks. In International Joint Conference on Artificial Intelligence (IJCAI), pages 1313-1318, 2005.
[16]
Eyke Hüllermeier, Sébastien Destercke, and Mohammad Hossein Shaker. Quantification of credal uncertainty in machine learning: A critical analysis and empirical comparison. In James Cussens and Kun Zhang, editors, Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, volume 180 of Proceedings of Machine Learning Research, pages 548-557. PMLR, 01-05 Aug 2022.
[17]
James Park and Adnan Darwiche. Solving MAP exactly using systematic search. In Uncertainty in Artificial Intelligence (UAI), pages 459-468, 2003.
[18]
Changhe Yuan and Eric Hansen. Efficient computation of jointree bounds for systematic MAP search. In InternationalJoint Conference on Artificiallntelligence (IJCAI), pages 1982-1989, 2009.
[19]
Junkyu Lee, Radu Marinescu, Rina Dechter, and Alexander Ihler. From exact to anytime solutions for marginal MAP. In 30th AAAI Conference on Artificial Intelligence, pages 1749-1755, 2016.
[20]
Radu Marinescu, Junkyu Lee, Rina Dechter, and Alexander Ihler. Anytime best+depth-first search for bounding marginal MAP. In 31st AAAI Conference on Artificial Intelligence, pages 1749-1755, 2017.
[21]
Radu Marinescu, Junkyu Lee, Rina Dechter, and Alexander Ihler. AND/OR search for marginal MAP. Journal of Artificial Intelligence Research, 63:875-921, 2018.
[22]
Rina Dechter and Irina Rish. Mini-buckets: A general scheme of approximating inference. Journal of ACM, 50(2):107-153, 2003.
[23]
Jiarong Jiang, Piyush Rai, and Hal Daume. Message-passing for approximate MAP inference with latent variables. In Advances in Neural Information Processing Systems (NIPS), pages 1197-1205. 2011.
[24]
Qiang Cheng, Feng Chen, Jianwu Dong, Wenli Xu, and Alexander Ihler. Approximating the sum operation for marginal-MAP inference. In 26th AAAI Conference on Artificial Intelligence, AAAI, pages 1882-1887, 2012.
[25]
Qiang Liu and Alexander Ihler. Variational algorithms for marginal MAP. Journal of Machine Learning Research, 14:3165-3200, 2013.
[26]
Wei Ping, Qiang Liu, and Alexander Ihler. Decomposition bounds for marginal MAP. In Advances in Neural Information Processing Systems 28, pages 3267-3275, 2015.
[27]
Denis Maua and Cassio Campos. Anytime marginal MAP inference. In International Conference on Machine Learning (ICML), pages 1471-1478, 2012.
[28]
Rina Dechter. Mini-buckets: A general scheme of generating approximations in automated reasoning. In International Joint Conference on Artificial Intelligence (IJCAI), pages 1297-1302, 1997.
[29]
Jaime Shinsuke Ide and Fabio Gagliardi Cozman. Approximate algorithms for credal networks with binary variables. International Journal of Approximate Reasoning, 48(1):275-296, 2008.
[30]
Alessandro Antonucci, Yi Sun, Cassio P De Campos, and Marco Zaffalon. Generalized loopy 2u: A new algorithm for approximate inference in credal networks. International Journal of Approximate Reasoning, 51(5):474-484, 2010.
[31]
Alessandro Antonucci, Cassio Campos, David Huber, and Marco Zaffalon. Approximate credal network updating by linear programming with applications to decision making. International Journal of Approximate Reasoning, 58(3):25-38, 2015.
[32]
R. Marinescu and R. Dechter. AND/OR branch-and-bound search for combinatorial optimization in graphical models. Artificial Intelligence, 173(16-17):1457-1491, 2009.
Recommendations
Credal model averaging: an extension of Bayesian model averaging to imprecise probabilities
ECMLPKDD'08: Proceedings of the 2008th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part IWe deal with the arbitrariness in the choice of the prior over the models in Bayesian model averaging (BMA), by modelling prior knowledge by a set of priors (i.e., a prior credal set). We consider Dash and Cooper's BMA applied to naive Bayesian networks,...
Decomposition bounds for marginal MAP
NIPS'15: Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 2Marginal MAP inference involves making MAP predictions in systems defined with latent variables or missing information. It is significantly more difficult than pure marginalization and MAP tasks, for which a large class of efficient and convergent ...
Credal ensembles of classifiers
It is studied how to aggregate the probabilistic predictions generated by different SPODE (Super-Parent-One-Dependence Estimators) classifiers. It is shown that aggregating such predictions via compression-based weights achieves a slight but consistent ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2023 Neural Information Processing Systems Foundation, Inc.
Publisher
Curran Associates Inc.
Red Hook, NY, United States
Publication History
Published: 10 December 2023
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 29 Jan 2025