LEARNING BAYESIAN BELIEF NETWORKS: AN APPROACH BASED ON THE MDL PRINCIPLE

Computational Intelligence - Tập 10 Số 3 - Trang 269-293 - 1994
Wai Lam1, Fahiem Bacchus1
1Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L3G1

Tóm tắt

A new approach for learning Bayesian belief networks from raw data is presented. The approach is based on Rissanen's minimal description length (MDL) principle, which is particularly well suited for this task. Our approach does not require any prior assumptions about the distribution being learned. In particular, our method can learn unrestricted multiply‐connected belief networks. Furthermore, unlike other approaches our method allows us to trade off accuracy and complexity in the learned model. This is important since if the learned model is very complex (highly connected) it can be conceptually and computationally intractable. In such a case it would be preferable to use a simpler model even if it is less accurate. The MDL principle offers a reasoned method for making this trade‐off. We also show that our method generalizes previous approaches based on Kullback cross‐entropy. Experiments have been conducted to demonstrate the feasibility of the approach.

Từ khóa


Tài liệu tham khảo

Abramson B.1991.ARCOl: an application of belief networks to the oil market.InProceedings of the Conference on Uncertainty in Artificial Intelligence pp.1–8.

Beinlich I. A. H. J.Suermondt R. M.Chavez andG. F.Cooper.1989.The ALARM monitoring system: a case study with two probabilistic inference techniques for belief networks.InProceedings of the 2nd European Conference on Artificial Intelligence in Medicine pp.247–256.

Chavez R.1990.Architectures and approximation algorithms for probabilistic expert systems.Ph.D. thesis Medical Computer Science Group Stanford University Stanford CA.

10.1002/net.3230200510

10.1109/TIT.1968.1054142

Cooper G.1984.NESTOR: a computer‐based medical diagnosis aid that integrates causal and probabilistic knowledge.Ph.D. thesis Medical Computer Science Group Stanford University Stanford CA.

10.1016/0004-3702(90)90060-D

Cooper G. R. andE.Herskovits.1991.A Bayesian method for constructing Bayesian belief networks from databases.InProceedings of the Conference on Uncertainty in Artificial Intelligence 86–94.

Cormen T. H., 1989, Introduction to algorithms

Dagum P., 1991, Approximating probabilistic inference in Bayesian belief networks

10.1016/0004-3702(93)90036-B

10.1016/B978-0-444-88738-2.50023-3

Gao Q. andM.Li.1989.The minimum description length principle and its application to online learning of handprinted characters.InProceedings of the International Joint Conference on Artificial Intelligence (IJCAI) pp.843–848.

Geiger D. A.Paz andJ.Pearl.1990.Learning causal trees from dependence information.InProceedings of the AAAI National Conference pp.770–776.

10.1016/B978-0-444-88650-7.50006-8

Henrion M., 1987, Uncertainty in artifical intelligence 2, 149

Henrion M., 1990, Influence diagrams, belief nets, and decision analysis, 385

Henrion M.1991.Search‐based methods to bound diagnostic probabilities in very large belief nets.InProceedings of the Conference on Uncertainty in Artificial Intelligence pp.142–150.

Jensen F., 1990, Bayesian updating in causal probabilistic networks by local computations, Computational Statistics Quarterly, 4, 269

10.1214/aoms/1177729694

10.1145/45072.45074

10.1016/0004-3702(86)90072-X

10.1016/0004-3702(87)90012-9

Pearl J., 1988, Probabilistic reasoning in intelligent systems: networks of plausible inference

Pearl J. andT. S.Verma.1991.A theory of inferred causation.InProceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning pp.441–452.

10.1109/TSMC.1987.4309027

10.1109/TSMC.1987.4309056

Rebane G. andJ.Pearl.1987.The recovery of causal poly‐trees from statistical data.InProceedings of the Conference on Uncertainty in Artificial Intelligence pp.222–228.

10.1016/0005-1098(78)90005-5

Robinson R. W.1976.Counting unlabeled acyclic digraphs.InProceedings of the 5th Australian Conference on Combinatorial Mathematics pp.28–43.

10.1016/B978-0-444-88738-2.50024-5

Spirtes P. C.Glymour andR.Scheines.1990.Causality from probability.InEvolving knowledge in natural science and artificial ingelligence pp.181–199.

Verma T. andJ.Pearl.1990.Equivalence and synthesis of causal models.InProceedings of the Conference on Uncertainty in Artificial Intelligence pp.220–227.

Thông tin
Thông tin xuất bản

Computational Intelligence

Tập 10 Số 3

269-293

Thông tin tác giả