Learning Bayesian Networks: Search Methods and Experimental Results

David Maxwell Chickering, Dan Geiger, David Heckerman
Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics, PMLR R0:112-128, 1995.

Abstract

We discuss Bayesian approaches for learning Bayesian networks from data. First, we review a metric for computing the relative posterior probability of a network structure given data developed by Heckerman et al. (1994 a, b, c). We see that the metric has a property useful for inferring causation from data. Next, we describe search methods for identifying network structures with high posterior probabilities. We describe polynomial algorithms for finding the highestscoring network structures in the special case where every node has at most $k=1$ parent. We show that the general case $(k>1)$ is NP-hard, and review heuristic search algorithms for this general case. Finally, we describe a methodology for evaluating learning algorithms, and use this methodology to evaluate various scoring metrics and search procedures.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR0-chickering95a, title = {Learning Bayesian Networks: Search Methods and Experimental Results}, author = {Chickering, David Maxwell and Geiger, Dan and Heckerman, David}, booktitle = {Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics}, pages = {112--128}, year = {1995}, editor = {Fisher, Doug and Lenz, Hans-Joachim}, volume = {R0}, series = {Proceedings of Machine Learning Research}, month = {04--07 Jan}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/r0/chickering95a/chickering95a.pdf}, url = {https://proceedings.mlr.press/r0/chickering95a.html}, abstract = {We discuss Bayesian approaches for learning Bayesian networks from data. First, we review a metric for computing the relative posterior probability of a network structure given data developed by Heckerman et al. (1994 a, b, c). We see that the metric has a property useful for inferring causation from data. Next, we describe search methods for identifying network structures with high posterior probabilities. We describe polynomial algorithms for finding the highestscoring network structures in the special case where every node has at most $k=1$ parent. We show that the general case $(k>1)$ is NP-hard, and review heuristic search algorithms for this general case. Finally, we describe a methodology for evaluating learning algorithms, and use this methodology to evaluate various scoring metrics and search procedures.}, note = {Reissued by PMLR on 01 May 2022.} }
Endnote
%0 Conference Paper %T Learning Bayesian Networks: Search Methods and Experimental Results %A David Maxwell Chickering %A Dan Geiger %A David Heckerman %B Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 1995 %E Doug Fisher %E Hans-Joachim Lenz %F pmlr-vR0-chickering95a %I PMLR %P 112--128 %U https://proceedings.mlr.press/r0/chickering95a.html %V R0 %X We discuss Bayesian approaches for learning Bayesian networks from data. First, we review a metric for computing the relative posterior probability of a network structure given data developed by Heckerman et al. (1994 a, b, c). We see that the metric has a property useful for inferring causation from data. Next, we describe search methods for identifying network structures with high posterior probabilities. We describe polynomial algorithms for finding the highestscoring network structures in the special case where every node has at most $k=1$ parent. We show that the general case $(k>1)$ is NP-hard, and review heuristic search algorithms for this general case. Finally, we describe a methodology for evaluating learning algorithms, and use this methodology to evaluate various scoring metrics and search procedures. %Z Reissued by PMLR on 01 May 2022.
APA
Chickering, D.M., Geiger, D. & Heckerman, D.. (1995). Learning Bayesian Networks: Search Methods and Experimental Results. Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research R0:112-128 Available from https://proceedings.mlr.press/r0/chickering95a.html. Reissued by PMLR on 01 May 2022.

Related Material