Efficiently Learning Bayesian Network Structures Based on the B&B Strategy: A Theoretical Analysis
Joe Suzuki · Lecture notes in computer science · 2015
This paper addresses the problem of efficiently finding an optimal Bayesian network structure w.r.t. maximizing the posterior probability and minimizing the description length. In particular, we focus on the branch and bound strategy to save computational effort. To obtain an efficient search, a larger lower bound of the score is required (when we seek its minimum). We generalize an existing lower bound (Campose and Ji, 2011) for the Bayesian Dirichlet BDeu (Bayesian Dirichlet equivalent uniform) to one for the BD (Bayesian Dirichlet) and mathematically prove that the number of variables in each parent set cannot be bounded for maximizing the posterior probability.