Large-Sample Learning of Bayesian Networks is NP-Hard

By David Maxwell Chickering, David E. Heckerman, Christopher Meek. 2002

851 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Generalization in anti-causal learning (2018, neutral): “…probabilistic inference and ﬁnding maximum a posteriori probabilities in Bayesian belief networks or learning large-scale discrete Bayesian networks are all NP-hard (Dagum and Luby, 1993; Shimony, 1994; Chickering et al., 2004), consistent with our interpretation (see “NP problems” in section 3).”
DAGs with NO TEARS: Continuous Optimization for Structure Learning (2018, background): “Unfortunately, (4) is NP-hard to solve Chickering (1996); Chickering et al. (2004) owing mainly to the nonconvex, combinatorial nature of the optimization problem.”
Causal Discovery with Reinforcement Learning (2019, background): “…score functions such as the BIC/MDL score [20, 5] and the BGe score [9] for linear-Gaussian models, problem (1) is generally NP-hard to solve [4, 6], largely due to its nonconvex and combinatorial nature; the acyclicity constraint is a combinatorial constraint with the number of DAGs increasing…”
DAG-GNN: DAG Structure Learning with Graph Neural Networks (2019, background): “Its structure learning problem is however NP-hard (Chickering et al., 2004) and stimulates a proliferation of literature.”
Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression (2015, background): “This is largely due to the complexity of the problem: In addition to the nonidentiﬁability, optimization over the space of DAGs is well-known to be nonconvex and NP-hard in general.”
A million variables and more: the Fast Greedy Equivalence Search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance images (2016, background): “There is no guarantee that on finite samples the model or models returned are those with the highest posterior probability, which is known to be an NP-hard problem [6].”
Machine Learning of Bayesian Networks Using Constraint Programming (2015, background): “Unfortunately, learning a BN from data is NP-hard, even if the number of parents per vertex in the DAG is limited to two [2].”
Learning Bayesian Network Structure using LP Relaxations (2010, background): “When the available data may be drawn from an arbitrary distribution, the resulting combinatorial search problem is known to be NP-hard [Chickering, 1996; Chickering et al., 2004].”
A network intrusion detection system based on a Hidden Naïve Bayes multiclass classifier (2012, methodology): “Because learning the optimal structure of the Bayesian network model is an NP-hard problem (Chickering, Heckerman, & Meek, 2004), some restrictions or heuristics must be applied to make the approach practical, such as those applied in the tree-augmented Naïve Bayes (TAN) (Friedman, Geiger, &…”
Data Based Identification and Prediction of Nonlinear and Complex Dynamical Systems (2016, background): “However, inferring regulatory interactions based on Bayesian networks is an intractable problem [147, 148].”
Conditional Likelihood Maximisation: A Unifying Framework for Information Theoretic Feature Selection (2012, background): “The problem of DAG learning from observed data is known to be NP-hard (Chickering et al., 2004), and as such there exist two main families of approximate algorithms.”
A Simple Approach for Finding the Globally Optimal Bayesian Network Structure (2006, methodology): “Finding the best Bayesian network structure is NP-hard (Chickering, Meek, & Heckerman, 2003), so the techniques presented will be feasible only for small networks.”
Efficient Structure Learning of Bayesian Networks using Constraints (2011, background): “The problem is known to be NP-hard (Chickering et al., 2003), and best exact known methods take exponential time on the number of variables and are applicable to small settings (around 30 variables).”
The max-min hill-climbing Bayesian network structure learning algorithm (2006, background): “Learning (the most probable a posteriori under certain conditions) Bayesian network from data is an NP-Hard problem (Chickering, 1996; Chickering et al., 2004).”
Single-cell RNA sequencing technologies and bioinformatics pipelines (2018, background): “Additionally, probabilistic graphical models require searching for all possible paths for many genes, which is an NP-hard problem 79 .”
Ordering-Based Search: A Simple and Effective Algorithm for Learning Bayesian Networks (2005, background): “Unfortunately, the task of (cid:12)nding a network structure that optimizes the score is a combinatorial optimization problem, and is known to be NP-hard [Chickering, 1996a; Chickering et al. , 2003], even if we restrict each node to having at most two parents.”
Learning Causal Bayesian Network Structures From Experimental Data (2008, background): “the number of vertices of the graph ( Chickering, Heckerman and Meek 2004 ).”