Abstract
We examine a novel addition to the known methods for learning Bayesian networks from data that improves the quality of the learned networks. Our approach explicitly represents and learns the local structure in the conditional probability distributions (CPDs) that quantify these networks. This increases the space of possible models, enabling the representation of CPDs with a variable number of parameters. The resulting learning procedure induces models that better emulate the interactions present in the data. We describe the theoretical foundations and practical aspects of learning local structures and provide an empirical evaluation of the proposed learning procedure. This evaluation indicates that learning curves characterizing this procedure converge faster, in the number of training instances, than those of the standard procedure, which ignores the local structure of the CPDs. Our results also show that networks learned with local structures tend to be more complex (in terms of arcs), yet require fewer parameters.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
I. Beinlich, G. Suermondt, R. Chavez, and G. Cooper. The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks. In Proc. 2’nd European Conf. on AI and Medicine. Springer-Verlag, Berlin, 1989.
R. R. Bouckaert. Properties of Bayesian network learning algorithms. In R. López de Mantarás and D. Poole, editors, Proc. Tenth Conference on Uncertainty in Artificial Intelligence (UAI ‘84), pages 102–109. Morgan Kaufmann, San Francisco, CA, 1994.
C. Boutilier, N. Friedman, M. Goldszmidt, and D. Koller. Context-specific independence in Bayesian networks. In E. Horvitz and F. Jensen, editors, Proc. Twelfth Conference on Uncertainty in Artificial Intelligence (UAI ‘86), pages 115–123. Morgan Kaufmann, San Francisco, CA, 1996.
W. Buntine. A theory of learning classification rules. PhD thesis, University of Technology, Sydney, Australia, 1991.
W. Buntine. Theory refinement on Bayesian networks. In B. D. D’Ambrosio, P. Sinets, and P. P. Bonissone, editors, Proc. Seventh Annual Conference on Uncertainty Artificial Intelligence (UAI ‘82), pages 52–60. Morgan Kaufmann, San Francisco, CA, 1991.
W. Buntine. Learning classification trees. In D. J. Hand, editor, Artificial Intelligence Frontiers in Statistics, number III in Al and Statistics. Chapman & Hall, London, 1993.
D. M. Chickering. Learning Bayesian networks is NP-complete. In D. Fisher and H.-J. Lenz, editors, Learning from Data: Artificial Intelligence and Statistics V. Springer Verlag, 1996.
G. F. Cooper and E. Herskovits. A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 9: 309–347, 1992.
T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, New York, 1991.
M. H. DeGroot. Optimal Statistical Decisions. McGraw-Hill, New York, 1970.
F. J. Diez. Parameter adjustment in Bayes networks: The generalized noisy or-gate. In D. Heckerman and A. Mamdani, editors, Proc. Ninth Conference on Uncertainty in Artificial Intelligence (UAI ‘83), pages 99–105. Morgan Kaufmann, San Francisco, CA, 1993.
N. Friedman and Z. Yakhini On the sample complexity of learning Bayesian networks. In E. Horvitz and F. Jensen, editors, Proc. Twelfth Conference on Uncertainty in Artificial Intelligence (UAI ‘86). Morgan Kaufmann, San Francisco, CA, 1996.
D. Beckerman and J. S. Breese. A new look at causal independence. In R. López de Mantarás and D. Poole, editors, Proc. Tenth Conference on Uncertainty in Artificial Intelligence (UAI ‘84), pages 286–292. Morgan Kaufmann, San Francisco, CA, 1994.
D. Beckerman, D. Geiger, and D. M. Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Machine Learning, 20: 197–243, 1995.
D. Beckerman. A tutorial on learning Bayesian networks. Technical Report MSR-TR95–06, Microsoft Research, 1995.
W. Lam and F. Bacchus. Learning Bayesian belief networks: An approach based on the MDL principle. Computational Intelligence, 10: 269–293, 1994.
R. Musick. Belief Network Induction. PhD thesis, University of California, Berkeley, CA, 1994.
R. M. Neal. Connectionist learning of belief networks. Artificial Intelligence, 56: 71–113, 1992.
J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Francisco, CA, 1988.
J. R. Quinlan and R. Rivest. Inferring decision trees using the minimum description length principle. Information and Computation, 80: 227–248, 1989.
J. R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, San Francisco, CA, 1993.
J. Rissanen. Stochastic Complexity in Statistical Inquiry. World Scientific, River Edge, NJ, 1989.
S. Russell, J. Binder, D. Koller, and K. Kanazawa. Local learning in probabilistic networks with hidden variables. In Proc. Fourteenth International Joint Conference on Artificial Intelligence (IJCAI ‘85), pages 1146–1152. Morgan Kaufmann, San Francisco, CA, 1995.
G. Schwarz. Estimating the dimension of a model. Annals of Statistics, 6: 461–464, 1978.
J. E. Shore and R. W. Johnson. Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy. IEEE Transactions on Information Theory, IT-26(1): 26–37, 1980.
D. J. Spiegelhalter and S. L. Lauitzen. Sequential updating of conditional probabilities on directed graphical structures. Networks, 20: 579–605, 1990.
S. Srinivas. A generalization of the noisy-or model. In D. Beckerman and A. Mamdani, editors, Proc. Ninth Conference on Uncertainty in Artificial Intelligence (UAI ‘83), pages 208–215. Morgan Kaufmann, San Francisco, CA, 1993.
C. Wallace and J. Patrick. Coding decision trees. Machine Learning, 11: 7–22, 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer Science+Business Media Dordrecht
About this chapter
Cite this chapter
Friedman, N., Goldszmidt, M. (1998). Learning Bayesian Networks with Local Structure. In: Jordan, M.I. (eds) Learning in Graphical Models. NATO ASI Series, vol 89. Springer, Dordrecht. https://doi.org/10.1007/978-94-011-5014-9_15
Download citation
DOI: https://doi.org/10.1007/978-94-011-5014-9_15
Publisher Name: Springer, Dordrecht
Print ISBN: 978-94-010-6104-9
Online ISBN: 978-94-011-5014-9
eBook Packages: Springer Book Archive