EÆcient Approximations for the Marginal Likelihood of Bayesian Networks with Hidden Variables

Abstract. We discuss Bayesian methods for model averaging and model selection among Bayesian-network models with hidden variables. In particular, we examine large-sample approximations for the marginal like-lihood of naive-Bayes models in which the root node is hidden. Such models are useful for clustering or unsupervised learning. We consider a Laplace approximation and the less accurate but more computa-tionally eÆcient approximation known as the Bayesian Information Criterion (BIC), which is equivalent to Rissanen's (1987) MinimumDescription Length (MDL). Also, we consider approximations that ignore some o-diagonal elements of the observed information matrix and an approximation proposed by Cheeseman and Stutz (1995). We evaluate the accuracy of these approximations using a Monte-Carlo gold standard. In experiments with articial and real examples, we nd that (1) none of the approximations are accu-rate when used for model averaging, (2) all of the approximations, with the exception of BIC/MDL, are accurate for model selection, (3) among the accurate approximations, the Cheeseman{Stutz and Diagonal approximations are the most computationally eÆcient, (4) all of the approximations, with the exception of BIC/MDL, can be sensitive to the prior distribution over model parameters, and (5) the Cheeseman{Stutz approximation can be more accurate than the other approximations, including the Laplace approximation, in situations where the parameters in the maximum a posteriori conguration are near a boundary