Bayesian network induction via local neighborhoods.

D. Margaritis and S. Thrun.

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 Bayes networks from data. Our approach constructs Bayesian networks by first identifying each node's Markov blankets, then connecting nodes in a maximally consistent way. In contrast to the majority of work, which typically uses hill-climbingapproaches that may produce dense and causally incorrect nets, our approach yields much more compact causal networks by heeding independencies inthe data. Compact causal networksfacilitatefast 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 randomized variant, also presented here, yields comparable results at much higher speeds.

The full paper is available in PDF and gzipped Postscript

@INPROCEEDINGS{Margaritis99a,
  AUTHOR	= {Margaritis, D. and Thrun, S.},
  TITLE		= {{B}ayesian Network Induction via Local Neighborhoods},
  YEAR		= {1999},
  MONTH		= {},
  BOOKTITLE	= {Proceedings of Conference on Neural Information Processing Systems (NIPS-12)},
  EDITOR	= {S.A. Solla and T.K. Leen and K.-R. M\"{u}ller},
  PUBLISHER	= {MIT Press}
}