MRE: Exact and approximation algorithms for solving Most Relevant Explanations in Bayesian Networks

Xiaoyuan Zhu, Heejin Lim, Changhe Yuan

Abstract

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. We have developed both exact and approximation algorithms for solving MRE. These algorithms are developed on top of the SMILE library developed at University of Pittsburgh and commercialized by BayesFusion, LLC. Due to IP issues, we can only make our parts of the code available. Users of our software can any of the following papers when you see fit. Disclaimer: The software is provided as is without any guarantee, and can be reused and redistributed except for commercial use.

Download approximation methods (size: 166k; updated: 8/25/2015)

Download exact methods (size: 7,072k; updated: 12/12/2016)

Bibtex

@article{Zhu16exact, title={Exact Algorithms for MRE Inference},
author={Zhu, Xiaoyuan and Yuan, Changhe},
journal={Journal of Artificial Intelligence Research},
volume={55},
pages={653--683},
year={2016} }

@INPROCEEDINGS{Zhu15exact,
author = {Xiaoyuan Zhu, Changhe Yuan},
title = {An Exact Algorithm for Solving Most Relevant Explanation in Bayesian Networks},
booktitle = {In Proceedings of the 29th AAAI Conference (AAAI-15)},
address = {Austin, Texas},
year = {2015}
}

@INPROCEEDINGS{Zhu15hierarchical,
author = {Xiaoyuan Zhu and Changhe Yuan},
title = {Hierarchical Beam Search for Solving Most Relevant Explanation in Bayesian Networks},
booktitle = {In Proceedings of The 28th International FLAIRS Conference (FLAIRS-15)},
address = {Hollywood, Florida},
year = {2015}
}

@ARTICLE{Yuan11mostJAIR,
author = {Changhe Yuan and Heejin Lim and Tsai-Ching Lu},
title = {Most Relevant Explanation in Bayesian Networks},
journal = {Journal of Artificial Intelligence Research (JAIR)},
year = {2011},
volume = {42},
pages = {309--352}
}

@ARTICLE{Yuan11most,
author = {Changhe Yuan and Heejin Lim and Michael L. Littman},
title = {Most Relevant Explanation: Computational Complexity and Approximation Methods},
journal = {Annals of Mathematics and Artificial Intelligence},
volume = {61},
issue = {3},
pages = {159--183},
year = {2011}
}

@CONFERENCE{Yuan07finding,
author = {Changhe Yuan and Tsai-Ching Lu},
title = {Finding Explanations in {B}ayesian Networks},
booktitle = {Proceedings of the 18th International Workshop on Principles of Diagnosis (DX-07)},
year = {2007},
pages = {414--419}
}