An Algorithm for Bayesian Network Construction from Data

Jie Cheng, David A. Bell, Weiru Liu
Proceedings of the Sixth International Workshop on Artificial Intelligence and Statistics, PMLR R1:83-90, 1997.

Abstract

This paper presents an efficient algorithm for constructing Bayesian belief networks from databases. The algorithm takes a database and an attributes ordering (i.e., the causal attributes of an attribute should appear earlier in the order) as input and constructs a belief network structure as output. The construction process is based on the computation of mutual information and cross entropy of attribute pairs. This algorithm guarantees that the \emph{minimal Independent map} [1] of the underlying dependency model is generated, and at the same time, enjoys the time complexity of $O(N^2)$ on conditional independence (Cl) tests. To evaluate this algorithm, we present the experimental results on three versions of the well-known ALARM network database, which has 37 attributes and 10,000 records. The correctness proof and the analysis of computational complexity are also presented. We also discuss the features ofour work and relate it to previous works.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR1-cheng97a, title = {An Algorithm for Bayesian Network Construction from Data}, author = {Cheng, Jie and Bell, David A. and Liu, Weiru}, booktitle = {Proceedings of the Sixth International Workshop on Artificial Intelligence and Statistics}, pages = {83--90}, year = {1997}, editor = {Madigan, David and Smyth, Padhraic}, volume = {R1}, series = {Proceedings of Machine Learning Research}, month = {04--07 Jan}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/r1/cheng97a/cheng97a.pdf}, url = {https://proceedings.mlr.press/r1/cheng97a.html}, abstract = {This paper presents an efficient algorithm for constructing Bayesian belief networks from databases. The algorithm takes a database and an attributes ordering (i.e., the causal attributes of an attribute should appear earlier in the order) as input and constructs a belief network structure as output. The construction process is based on the computation of mutual information and cross entropy of attribute pairs. This algorithm guarantees that the \emph{minimal Independent map} [1] of the underlying dependency model is generated, and at the same time, enjoys the time complexity of $O(N^2)$ on conditional independence (Cl) tests. To evaluate this algorithm, we present the experimental results on three versions of the well-known ALARM network database, which has 37 attributes and 10,000 records. The correctness proof and the analysis of computational complexity are also presented. We also discuss the features ofour work and relate it to previous works.}, note = {Reissued by PMLR on 30 March 2021.} }
Endnote
%0 Conference Paper %T An Algorithm for Bayesian Network Construction from Data %A Jie Cheng %A David A. Bell %A Weiru Liu %B Proceedings of the Sixth International Workshop on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 1997 %E David Madigan %E Padhraic Smyth %F pmlr-vR1-cheng97a %I PMLR %P 83--90 %U https://proceedings.mlr.press/r1/cheng97a.html %V R1 %X This paper presents an efficient algorithm for constructing Bayesian belief networks from databases. The algorithm takes a database and an attributes ordering (i.e., the causal attributes of an attribute should appear earlier in the order) as input and constructs a belief network structure as output. The construction process is based on the computation of mutual information and cross entropy of attribute pairs. This algorithm guarantees that the \emph{minimal Independent map} [1] of the underlying dependency model is generated, and at the same time, enjoys the time complexity of $O(N^2)$ on conditional independence (Cl) tests. To evaluate this algorithm, we present the experimental results on three versions of the well-known ALARM network database, which has 37 attributes and 10,000 records. The correctness proof and the analysis of computational complexity are also presented. We also discuss the features ofour work and relate it to previous works. %Z Reissued by PMLR on 30 March 2021.
APA
Cheng, J., Bell, D.A. & Liu, W.. (1997). An Algorithm for Bayesian Network Construction from Data. Proceedings of the Sixth International Workshop on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research R1:83-90 Available from https://proceedings.mlr.press/r1/cheng97a.html. Reissued by PMLR on 30 March 2021.

Related Material