Finding All Bayesian Network Structures within a Factor of Optimal

TY - GEN

T1 - Finding All Bayesian Network Structures within a Factor of Optimal

AU - Liao, Zhenyu

AU - Sharma, Charupriya

AU - Cussens, James

AU - van Beek, Peter

PY - 2019/7/17

Y1 - 2019/7/17

N2 - A Bayesian network is a widely used probabilistic graphical model with applications in knowledge discovery and prediction. Learning a Bayesian network (BN) from data can be cast as an optimization problem using the well-known score-andsearch approach. However, selecting a single model (i.e., the best scoring BN) can be misleading or may not achieve the best possible accuracy. An alternative to committing to a single model is to perform some form of Bayesian or frequentist model averaging, where the space of possible BNs is sampled or enumerated in some fashion. Unfortunately, existing approaches for model averaging either severely restrict the structure of the Bayesian network or have only been shown to scale to networks with fewer than 30 random variables. Inthis paper, we propose a novel approach to model averaging inspired by performance guarantees in approximation algorithms. Our approach has two primary advantages. First, our approach only considers credible models in that they are optimal or near-optimal in score. Second, our approach is moreefficient and scales to significantly larger Bayesian networks than existing approaches.

AB - A Bayesian network is a widely used probabilistic graphical model with applications in knowledge discovery and prediction. Learning a Bayesian network (BN) from data can be cast as an optimization problem using the well-known score-andsearch approach. However, selecting a single model (i.e., the best scoring BN) can be misleading or may not achieve the best possible accuracy. An alternative to committing to a single model is to perform some form of Bayesian or frequentist model averaging, where the space of possible BNs is sampled or enumerated in some fashion. Unfortunately, existing approaches for model averaging either severely restrict the structure of the Bayesian network or have only been shown to scale to networks with fewer than 30 random variables. Inthis paper, we propose a novel approach to model averaging inspired by performance guarantees in approximation algorithms. Our approach has two primary advantages. First, our approach only considers credible models in that they are optimal or near-optimal in score. Second, our approach is moreefficient and scales to significantly larger Bayesian networks than existing approaches.

U2 - 10.1609/aaai.v33i01.33017892

DO - 10.1609/aaai.v33i01.33017892

M3 - Conference contribution

SN - 978-1-57735-809-1

T3 - Proceedings of the AAAI Conference on Artificial Intelligence

SP - 7892

EP - 7899

BT - Proceedings of the AAAI Conference on Artificial Intelligence, 33(01)

PB - AAAI Press

ER -