Model averaging for prediction with discrete Bayesian networks
Dash D, Cooper GF. Model averaging for prediction with discrete Bayesian networks. Journal of Machine Learning Research (2004) 1177-1203.
In this paper1 we consider the problem of performing Bayesian model-averaging over a class of discrete Bayesian network structures consistent with a partial ordering and with bounded in-degree k. We show that for N nodes this class contains in the worst-case at least Ω(N/2 k N/2 ) distinct network structures, and yet model averaging over these structures can be performed using O(N k·N) operations. Furthermore we show that there exists a single Bayesian network that deﬁnes a joint distribution over the variables that is equivalent to model averaging over these structures. Although constructing this network is computationally prohibitive, we show that it can be approximated by a tractable network, allowing approximate model-averaged probability calculations to be performed in O(N) time. Our result also leads to an exact and linear-time solution to the problem of averaging over the 2N possible feature sets in a naïve Bayes model, providing an exact Bayesian solution to the troublesome feature-selection problem for naïve Bayes classiﬁers. We demonstrate the utility of these techniques in the context of supervised classiﬁcation, showing empirically that model averaging consistently beats other generative Bayesian-network-based models, even when the generating model is not guaranteed to be a member of the class being averaged over. We characterize the performance over several parameters on simulated and real-world data. Keywords: Bayesian networks, Bayesian model averaging, classiﬁcation, naïve Bayes classiﬁers, feature selection