Email this article 
Open Access
Subscription or Fee Access
A Deterministic Annealing Approach to Learning Bayesian Networks
Abstract
Graphical models have been very promising tools that
can effectively model uncertainty, causal relation-ships, and
conditional distributions among random variables. This paper
proposes a new method for the induction of Bayesian Network
structures from the data. The proposed method uses the concept of deterministic annealing; a global optimization approach originally developed for clustering and classification problems. In the proposed method the existence of an edge in the network is no longer considered as a hard 0/1 issue, but rather we assign a certain probability for the existence of an edge. The deterministic annealing procedure then proceeds by optimizing with respect to these edge
probabilities. The experimental results show that the proposed approach achieves very promising results compared to other structure learning approaches.
Keywords
References
S. Acid and L. D. Campos. An algorithm for learning probabilistic belief networks. In The Sixth Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU),1996.
D. Chickering. Learning bayesian networks is np-complete. Springer, 1995.
G. Cooper and E. Herskovits. A bayesian method for the induction of probabilistic networks from data. Machine Learning, 9:309–347, 1992.
Cowel. Probabilistic networks and expert systems. Springer Verlag, 1999.
A. P. D. Geiger and J. Pearl. Learning simple causal structures. International Journal of Intelligent Systems, 8:231247, 1993.
D. G. D. Heckerman and D. Chickering. Learning bayesian networks: The combination of knowledge and statistical data. Machine Learning, 20:197–243, 1995.
K. R. D. Miller, A. Rao and A. Gersho. A global optimization technique for statistical classifier design. IEEE Transactions on Signal Processing, 44:31083122, 1996.
L. De Campos. Independency relationships and learning algorithms for singly connected net- works. J. Exp. Theoret. Artificial Intelligence,10:511549,1998.
L. De Campos and J. Huete. On the use of independence relationships for learning simplified belief networks. International Journal of Intelligent Systems, 12:495522, 1997.
L. De Campos and J. Huete. A new approach for learning belief networks using independence criteria. International Journal of Approximate Reasoning, 24:1137, 200.
E. T. F. Glover and D. D. Werr. Tabu search. ORSA Journal on Computing, 2:432, 1990.
N. Friedman. The bayesian structural em algorithm. In Proceedings of the 14th Conference In Uncertainty in Artificial Intelligence, 1998.
R. Fung and S. Crawford. A system for the induction of probabilistic models. In Proceedings of the Eighth National conference on Artificial Intelligence, 1990.
F. Glover. A user guide to tabu search. Annals of Operations Research, 41:328, 1993.
E. Herskovits and G. Cooper. An entropy-driven system for the construction of probabilistic expert systems from databases. In Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, 1996.
R. C. I. Beinlich, H. Suermondt and G. Cooper. The case study with two probabilistic inference techniques for bayesian networks. In Proceedings of the Second European Conference on Artificial Intelligence in Medicine, 1989.
S. R. J. Binder, D. Koller and K. Kanazawa. Adaptive probabilistic networks with hidden variables. Machine Learning, 29:213–244, 1997.
D. B. J. Cheng and W. Liu. An algorithm for bayesian belief network construction from data. In Proceedings of the Fourth International Workshop on Artificial Intelligence and Statistics, 1997.
M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul. An introduction to variational methods for graphical models. Mach. Learn., 37(2):183–233, 1999.
E. G. K. Rose and G. Fox. A deterministic annealing approach to clustering. Pattern Recognition Letters, 11:589594, 1990.
E. G. K. Rose and G. Fox. Constrained clustering as an optimization method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15:785794, 1993.
E. G. K. Rose and G. Fox. Vector quantization by deterministic annealing. IEEE Transactions on Information Theory, 38:12491257, 1993.
S. Kullback. Information theory and statistics. Dover, New York, 1968.
J. G. L. De Campos, J. Fernandez-Luna and J. Puerta. Ant colony optimization for learning bayesian networks. International Journal of Approximate Reasoning, 31:291311, 2002.
W. Lam and F. Bacchus. Using causal information and local measures to learn bayesian belief networks. In Proceedings of the Ninth Conference on Uncertainty in Artificial Intelligence, 1993.
W. Lam and F. Bacchus. Learning bayesian belief networks: An approach based on the mdl principle. Computational Intelligence, 10:269293, 1994.
I. N. N. Friedman and D. Peer. Learning bayesian network structure from massive datasets. In Proceedings of the 15th Conference In Uncertainty in Artificial Intelligence, 1999.
Y. Y. R. M. P. Larrafiag, M. Poza and C. Kuijpers. Structure learning of bayesian networks by genetic algorithms: performance analysis of control parameters. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18:912926, 1996.
M. P. P. Nang, R. Murga and C. Kuijpers. Structure learning of bayesian networks by hybrid genetic algorithms. In Preliminary Papers of the Fifth International Workshop on Artificial Intelligence and Statistics, 1995.
T.R. P. Spirtes and C. Meek. Learning bayesian networks with discrete variables from data. In Proceedings of the First International Conference on Knowledge Discovery and Data Mining, 1995.
J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, September 1988.
J. Pearl and T. Verma. A theory of inferred causation. In Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning, 1991.
C. Robert and G. Casella. Monte carlo statistical methods. Springer, 1999.
K. Rose. Deterministic annealing for clustering, compression, classification, regression, and related optimization problems. Proceedings of the IEEE, 86:2210 2239, 1998.
S. R. S. Srinivas and A. Agogino. Automated construction of sparse bayesian networks from unstructured probabilistic models and domain information. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 1990.
M. Singh and M. Valtorta. Construction of bayesian networks structures from data: a survey and an efficient algorithm. International Journal of Approximate Reasoning, 12:111123, 1995.
J. Suzuki. A construction of bayesian networks from databases based on an mdl principle. In Proceedings of the 9th Annual Conference on Uncertainty in Artificial Intelligence, 1993.
J. T. T. Wang and G. Xue. Applying two-level simulated annealing on bayesian structure learning to infer genetic networks. In Proceedings of the IEEE Computational Systems Bioinformatics Conference, 2004.
S. Y. X. Li and X. He. Learning Bayesian networks structure based on extending evolutionary programming. In Proceedings of the 3rd International Conference on Machine Learning and Cybernetics, 2004.
Refbacks
- There are currently no refbacks.