CMStatistics 2015: Start Registration
View Submission - CMStatistics
B0609
Title: Finding optimal Bayesian network structures with constraints learned from data Authors:  Brandon Malone - Max Planck Institute for Biology of Ageing (Germany) [presenting]
Changhe Yuan - Queens College - City University of New York (United States)
Xiannian Fan - Queens College - City University of New York (United States)
Abstract: The Bayesian network structure learning problem (BNSL) is NP-hard. Nevertheless, several algorithms have been proposed which, in practice, can probably solve many instances quite effectively. All of these algorithms first calculate potentially optimal parent sets (POPS) for all variables, and they then use various optimization techniques to find a set of POPS, one for each variable, that constitutes an optimal network structure. We first briefly describe BNSL and give details on an admissible state space search algorithm for finding provable optimal networks. We then show how the POPS given as input to the problem constrain the parent candidates for each variable. Taken together, the parent candidates of all variables give rise to a directed cyclic graph which decomposes into a set of strongly connected components (SCCs). Each SCC corresponds to an independent subproblem. This decomposition is applicable to all current optimal BNSL algorithms. Empirical results show that solving the decomposed problem significantly improves the efficiency and scalability of admissible search-based BNSL algorithms. Further, we show that by considering only the top $p$ POPS of each variables, we quickly find very high quality networks for large datasets.