Finding All Bayesian Network Structures within a Factor of Optimal

A Bayesian network is a widely used probabilistic graphicalmodel with applications in knowledge discovery and predic-tion. Learning a Bayesian network (BN) from data can be castas an optimization problem using the well-known score-and-search approach. However, selecting a single model (i.e., thebest scoring BN) can be misleading or may not achieve thebest possible accuracy. An alternative to committing to a sin-gle model is to perform some form of Bayesian or frequentistmodel averaging, where the space of possible BNs is sam-pled or enumerated in some fashion. Unfortunately, existingapproaches for model averaging either severely restrict thestructure of the Bayesian network or have only been shownto scale to networks with fewer than 30 random variables. Inthis paper, we propose a novel approach to model averaginginspired by performance guarantees in approximation algo-rithms. Our approach has two primary advantages. First, ourapproach only considers credible models in that they are op-timal or near-optimal in score. Second, our approach is moreefficient and scales to significantly larger Bayesian networksthan existing approaches