Large-Sample Learning of Bayesian Networks is NP-Hard

Abstract

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 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 hard, even when we are given an independence oracle, an inference oracle, and/or an information oracle. Our negative results also apply to the learning of discrete-variable Bayesian networks in which each node has at most k parents, for all k > 3.

Appears in Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence (UAI2003)

References in corpus (3)

• A Transformational Characterization of Equivalent Bayesian Network Structures
• On Local Optima in Learning Bayesian Networks
• Finding a Path is Harder than Finding a Tree

Cited by in corpus (7)

• A simple approach for finding the globally optimal Bayesian network structure
• A sparse conditional Gaussian graphical model for analysis of genetical genomics data
• Learning Bayesian Network Equivalence Classes with Ant Colony Optimization
• Structure Learning of Probabilistic Graphical Models: A Comprehensive Survey
• Computably Continuous Reinforcement-Learning Objectives are PAC-learnable
• Graphical modeling of stochastic processes driven by correlated errors
• Genetic Algorithms for Tractable Bayesian Network Fusion via Pre-Fusion Edge Pruning