Article

Free access

Large-sample learning of bayesian networks is NP-hard

Authors:

David Maxwell Chickering,

Christopher Meek,

David HeckermanAuthors Info & Claims

UAI'03: Proceedings of the Nineteenth conference on Uncertainty in Artificial Intelligence

Pages 124 - 133

Published: 07 August 2002 Publication History

PDF eReader Publisher Site

Abstract

In this paper, we provide new complexity results for algorithms that learn discretevariable Bayesian networks from data. Our results apply whenever the learning algorithm uses a scoring criterion that favors the simplest model able to represent the generative distribution exactly. Our results therefore hold whenever the learning algorithm uses a consistent scoring criterion and is applied to a sufficiently large dataset. We show that identifying high-scoring structures is NP-hard, even when we are given an independence oracle, an inference oracle, and/or an information oracle. Our negative results also apply when learning discrete-variable Bayesian networks in which each node has at most k parents, for all k ≥ 3.

References

[1]

Bouckaert, R. R. (1994). Properties of Bayesian belief network learning algorithms. In Proceedings of Tenth Conference on Uncertainty in Artificial Intelligence, Seattle, WA, pages 102-109. Morgan Kaufmann.

Digital Library

Google Scholar

[2]

Chickering, D. M. (1995). A transformational characterization of Bayesian network structures. In Hanks, S. and Besnard, P., editors, Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, Montreal, QU, pages 87-98. Morgan Kaufmann.

Digital Library

Google Scholar

[3]

Chickering, D. M. (1996). Learning Bayesian networks is NP-Compiete. In Fisher, D. and Lenz, H., editors, Learning from Data: Artificial Intelligence and Statistics V, pages 121-130. Springer-Verlag.

Google Scholar

[4]

Chickering, D. M. (2002). Optimal structure identification with greedy search. Journal of Machine Learning Research, 3:507-554.

Digital Library

Google Scholar

[5]

Chickering, D. M., Meek, C., and Heckerman, D. (2003). Large-sample learning of Bayesian networks is NP-hard. Technical Report MSR-TR-2003.17, Microsoft Research.

Google Scholar

[6]

Dasgupta, S. (1999). Learning polytrees. In Laskey, K. and Prade, H., editors, Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, Stockholm, Sweden, pages 131-141. Morgan Kaufmann.

Digital Library

Google Scholar

[7]

Garey, M. and Johnson, D. (1979). Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman.

Digital Library

Google Scholar

[8]

Garvil, F. (1977). Some NP-complete problems on graphs. In Proc. 11th Conf. on Information Sciences and Systems, Johns Hopkins University, pages 91-95. Baltimore, MD.

Google Scholar

[9]

Meek, C. (1997). Graphical Models: Selecting causal and statistical models. PhD thesis, Carnegie Mellon University.

Google Scholar

[10]

Meek, C. (2001). Finding a path is harder than finding a tree. Journal of Artificial Intelligence Research, 15:383-389.

Crossref

Google Scholar

[11]

Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo, CA.

Digital Library

Google Scholar

[12]

Spirtes, P., Glymour, C., and Scheines, R. (2000). Causation, Prediction, and Search (second edition). The MIT Press, Cambridge, Massachussets.

Google Scholar

Cited By

View all

Liu WYue KLi W(2011)Constructing the Bayesian network structure from dependencies implied in multiple relational schemasExpert Systems with Applications: An International Journal10.1016/j.eswa.2010.12.05338:6(7123-7134)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1016/j.eswa.2010.12.053
Etminani KNaghibzadeh MRazavi A(2010)Globally optimal structure learning of Bayesian networks from dataProceedings of the 20th international conference on Artificial neural networks: Part I10.5555/1886351.1886367(101-106)Online publication date: 15-Sep-2010
https://dl.acm.org/doi/10.5555/1886351.1886367
de Campos CZeng ZJi QDanyluk ABottou LLittman M(2009)Structure learning of Bayesian networks using constraintsProceedings of the 26th Annual International Conference on Machine Learning10.1145/1553374.1553389(113-120)Online publication date: 14-Jun-2009
https://dl.acm.org/doi/10.1145/1553374.1553389
Show More Cited By

Index Terms

Large-sample learning of bayesian networks is NP-hard
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Probabilistic reasoning
      2. Vagueness and fuzzy logic
  2. Machine learning
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Large-Sample Learning of Bayesian Networks is NP-Hard

In this paper, we provide new complexity results for algorithms that learn discrete-variable Bayesian networks from data. Our results apply whenever the learning algorithm uses a scoring criterion that favors the simplest structure for which the model ...
Bayesian learning of Bayesian networks with informative priors

This paper presents and evaluates an approach to Bayesian model averaging where the models are Bayesian nets (BNs). A comprehensive study of the literature on structural priors for BNs is conducted. A number of prior distributions are defined using ...
Structural learning of mixed noisy-OR Bayesian networks
Abstract
In this paper we discuss learning Bayesian networks whose conditional probability tables are either Noisy-OR models or general conditional probability tables. We refer to these models as Mixed Noisy-OR Bayesian Networks. To learn their ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

UAI'03: Proceedings of the Nineteenth conference on Uncertainty in Artificial Intelligence

August 2002

639 pages

ISBN:0127056645

Editors:
Uffe Kjærulff
Aalborg University
,
Christopher Meek
Microsoft Research

Publisher

Morgan Kaufmann Publishers Inc.

San Francisco, CA, United States

Publication History

Published: 07 August 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
94
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)14

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liu WYue KLi W(2011)Constructing the Bayesian network structure from dependencies implied in multiple relational schemasExpert Systems with Applications: An International Journal10.1016/j.eswa.2010.12.05338:6(7123-7134)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1016/j.eswa.2010.12.053
Etminani KNaghibzadeh MRazavi A(2010)Globally optimal structure learning of Bayesian networks from dataProceedings of the 20th international conference on Artificial neural networks: Part I10.5555/1886351.1886367(101-106)Online publication date: 15-Sep-2010
https://dl.acm.org/doi/10.5555/1886351.1886367
de Campos CZeng ZJi QDanyluk ABottou LLittman M(2009)Structure learning of Bayesian networks using constraintsProceedings of the 26th Annual International Conference on Machine Learning10.1145/1553374.1553389(113-120)Online publication date: 14-Jun-2009
https://dl.acm.org/doi/10.1145/1553374.1553389
MartíNez-RodríGuez AMay JVargas L(2008)An optimization-based approach for the design of Bayesian networksMathematical and Computer Modelling: An International Journal10.1016/j.mcm.2008.01.00748:7-8(1265-1278)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.1016/j.mcm.2008.01.007
Shi ZHu HShi Z(2007)A Bayesian computational cognitive modelProceedings of the 3rd International Conference on Neural-Symbolic Learning and Reasoning - Volume 23010.5555/2907156.2907167(46-51)Online publication date: 8-Jan-2007
https://dl.acm.org/doi/10.5555/2907156.2907167
Silander TMyllymäki P(2006)A simple approach for finding the globally optimal Bayesian network structureProceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence10.5555/3020419.3020473(445-452)Online publication date: 13-Jul-2006
https://dl.acm.org/doi/10.5555/3020419.3020473
Guo YSchuurmans D(2006)Convex structure learning for Bayesian networksProceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence10.5555/3020419.3020445(208-216)Online publication date: 13-Jul-2006
https://dl.acm.org/doi/10.5555/3020419.3020445
Abbeel PKoller DNg A(2006)Learning Factor Graphs in Polynomial Time and Sample ComplexityThe Journal of Machine Learning Research10.5555/1248547.12486117(1743-1788)Online publication date: 1-Dec-2006
https://dl.acm.org/doi/10.5555/1248547.1248611
Brown LTsamardinos IAliferis C(2005)A comparison of novel and state-of-the-art polynomial Bayesian network learning algorithmsProceedings of the 20th national conference on Artificial intelligence - Volume 210.5555/1619410.1619451(739-745)Online publication date: 9-Jul-2005
https://dl.acm.org/doi/10.5555/1619410.1619451

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Large-Sample Learning of Bayesian Networks is NP-Hard

Bayesian learning of Bayesian networks with informative priors

Structural learning of mixed noisy-OR Bayesian networks