Local Structure Discovery in Bayesian Networks
This work addresses scalability issues in Bayesian network structure learning for researchers and practitioners, but it is incremental as it builds on existing local learning approaches.
The paper tackles the NP-hard problem of learning Bayesian network structures from data by introducing SLL, a score-based local learning algorithm that focuses on target variables. Empirical results show SLL is competitive with the HITON algorithm, and they propose methods to construct full networks from local results.
Learning a Bayesian network structure from data is an NP-hard problem and thus exact algorithms are feasible only for small data sets. Therefore, network structures for larger networks are usually learned with various heuristics. Another approach to scaling up the structure learning is local learning. In local learning, the modeler has one or more target variables that are of special interest; he wants to learn the structure near the target variables and is not interested in the rest of the variables. In this paper, we present a score-based local learning algorithm called SLL. We conjecture that our algorithm is theoretically sound in the sense that it is optimal in the limit of large sample size. Empirical results suggest that SLL is competitive when compared to the constraint-based HITON algorithm. We also study the prospects of constructing the network structure for the whole node set based on local results by presenting two algorithms and comparing them to several heuristics.