An Exact Algorithm for Solving Most Relevant Explanation in Bayesian Networks
Abstract
Most Relevant Explanation (MRE) is a new inference task in Bayesian networks that finds the most relevant partial instantiation of target variables as an explanation for given evidence by maximizing the Generalized Bayes Factor (GBF). No exact algorithm has been developed for solving MRE previously. This paper fills the void and introduces a breadth-first branch-and-bound MRE algorithm based on a novel upper bound on GBF. The bound is calculated by decomposing the computation of the score to a set of Markov blankets of subsets of evidence variables. Our empirical evaluations show that the proposed algorithm scales up exact MRE inference significantly.
Cite
Text
Zhu and Yuan. "An Exact Algorithm for Solving Most Relevant Explanation in Bayesian Networks." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9686Markdown
[Zhu and Yuan. "An Exact Algorithm for Solving Most Relevant Explanation in Bayesian Networks." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/zhu2015aaai-exact/) doi:10.1609/AAAI.V29I1.9686BibTeX
@inproceedings{zhu2015aaai-exact,
title = {{An Exact Algorithm for Solving Most Relevant Explanation in Bayesian Networks}},
author = {Zhu, Xiaoyuan and Yuan, Changhe},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2015},
pages = {3649-3656},
doi = {10.1609/AAAI.V29I1.9686},
url = {https://mlanthology.org/aaai/2015/zhu2015aaai-exact/}
}