Bayesian Network Induction via Local Neighborhoods

This work presents an efficient algorithm for learning Bayes networks from data by first identifying each node's Markov blankets, then connecting nodes in a maximally consistent way, and proves that under mild assumptions, the approach requires time polynomial in the size of the data and the number of nodes.

Abstract

In recent years, Bayesian networks have become highly successful tool for diagnosis, analysis, and decision making in real-world domains. We present an efficient algorithm for learning Bayesian networks from data. Our approach constructs Bayesian networks by first identifying each node's Markov blankets, then connecting nodes in a consistent way. In contrast to the majority of work, which typically uses hill-climbing approaches that may produce dense nets and incorrect structure, our approach typically yields consistent structure and compact networks by heeding independencies in the data. Compact networks facilitate fast inference and are also easier to understand. We prove that under mild assumptions, our approach requires time polynomial in the size of the data and the number of nodes. A Monte Carlo variant, also presented here, is more robust and yields comparable results at much higher speeds. Keywords: Bayesian networks, Bayesian network induction, independence tests, Markov blan...