Hierarchical beam search for solving most relevant explanation in Bayesian networks. (English) Zbl 1436.68368
Summary: Most Relevant Explanation (MRE) is an inference problem in Bayesian networks that finds the most relevant partial instantiation of target variables as an explanation for given evidence. It has been shown in recent literature that it addresses the overspecification problem of existing methods, such as MPE and MAP. In this paper, we propose a novel hierarchical beam search algorithm for solving MRE. The main idea is to use a second-level beam to limit the number of successors generated by the same parent so as to limit the similarity between the solutions in the first-level beam and result in a more diversified population. Three pruning criteria are also introduced to achieve further diversity. Empirical results show that the new algorithm outperforms local search and regular beam search.
MSC:
| 68T37 | Reasoning under uncertainty in the context of artificial intelligence |
References:
| [1] | Beinlich, I.; Suermondt, G.; Chavez, R.; Cooper, G., The alarm monitoring system: a case study with two probabilistic inference techniques for belief networks, (Proceedings of the 2nd European Conference on AI and Medicine (1989)), 247-256 |
| [2] | Binder, J.; Koller, D.; Russell, S.; Kanazawa, K., Adaptive probabilistic networks with hidden variables, Mach. Learn., 29, 213-244 (1997) · Zbl 0892.68079 |
| [3] | Dietterich, T. G., Ensemble methods in machine learning, Lecture Notes in Computer Science, 1857, 1-15 (2000) · Zbl 0963.68085 |
| [4] | Fitelson, B., Likelihoodism, bayesianism, and relational confirmation, Synthese, 156, 473-489 (2007) · Zbl 1125.03302 |
| [5] | Glover, F., Tabu search: a tutorial, Interfaces, 20, 74-94 (1990) |
| [6] | Good, I. J., Weight of evidence: a brief survey, Bayesian Stat., 2, 249-270 (1985) |
| [7] | Koller, D.; Friedman, N., Probabilistic Graphical Models - Principles and Techniques (2009), MIT Press · Zbl 1183.68483 |
| [8] | Lacave, C.; Díez, F. J., A review of explanation methods for Bayesian networks, Knowl. Eng. Rev., 17, 107-127 (2002) |
| [9] | Nielsen, U. H.; Pellet, J.-P.; Elisseeff, A., Explanation trees for causal Bayesian networks, (Proceedings of the 24th Annual Conference on Uncertainty in Artificial Intelligence. Proceedings of the 24th Annual Conference on Uncertainty in Artificial Intelligence, UAI-08 (2008)), 427-434 |
| [10] | Onisko, A., Probabilistic causal models in medicine: application to diagnosis of liver disorders (2003), Institute of Biocybernetics and Biomedical Engineering, Polish Academy of Science, Ph.D. thesis |
| [11] | Pacer, M.; Lombrozo, T.; Griffiths, T.; Williams, J.; Chen, X., Evaluating computational models of explanation using human judgments, (Proceedings of the 29th Annual Conference on Uncertainty in Artificial Intelligence. Proceedings of the 29th Annual Conference on Uncertainty in Artificial Intelligence, UAI-13 (2013)), 498-507 |
| [12] | Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufmann |
| [13] | Rubin, S. M.; Reddy, R., The locus model of search and its use in image interpretation, (IJCAI (1977)), 590-595 |
| [14] | Yuan, C.; Lu, T.-C., Finding explanations in Bayesian networks, (Proceedings of the 18th International Workshop on Principles of Diagnosis. Proceedings of the 18th International Workshop on Principles of Diagnosis, DX-07 (2007)), 414-419 |
| [15] | Yuan, C.; Liu, X.; Lu, T.-C.; Lim, H., Most relevant explanation: properties, algorithms, and evaluations, (Proceedings of 25th Annual Conference on Uncertainty in Artificial Intelligence. Proceedings of 25th Annual Conference on Uncertainty in Artificial Intelligence, UAI-09 (2009)), 631-638 |
| [16] | Yuan, C.; Lim, H.; Littman, M. L., Most relevant explanation: computational complexity and approximation methods, Ann. Math. Artif. Intell., 61, 159-183 (2011) · Zbl 1234.68378 |
| [17] | Yuan, C.; Lim, H.; Lu, T.-C., Most relevant explanation in Bayesian networks, J. Artif. Intell. Res., 42, 309-352 (2011) · Zbl 1263.68161 |
| [18] | Zhu, X.; Yuan, C., An exact algorithm for solving most relevant explanation in Bayesian networks, (Proceedings of the 29th National Conference on Artificial Intelligence (2015)) |
| [19] | Zhu, X.; Yuan, C., Hierarchical beam search for solving most relevant explanation in bayesian networks, (Proceedings of the Twenty-Eighth International Flairs Conference (2015)) |
| [20] | Zhu, X.; Yuan, C., Exact algorithms for MRE inference, J. Artif. Intell. Res., 55, 653-683 (2016) · Zbl 1352.68255 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
