In this paper, we provide new complexity results for algorithms that learn discrete variable Bayesian networks from data. Our results apply whenever the learning algo rithm uses a scoring criterion that favors the simplest model able to represent the genera tive distribution exactly. Our results there fore hold when ever the learning algorithm uses a consistent scoring criterion and is ap plied to a sufficiently large dataset. We show that identifying high-scoring structures is NP-hard, even when we are given an inde pendence 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 2: 3. Researchers in the UAI community have generally ac cepted that without restrictive assumptions, learning Bayesian networks from data is NP-hard, and conse quently a large amount of work in this community has been dedicated to heuristic-search techniques to identify good models. A number of discouraging com plexity results have emerged over the last few years that indicate that this belief is well founded. Chick ering (1996) shows that for a general (and widely used) class of Bayesian scoring criteria, identifying the highest-scoring structure from small-sample data is hard, even when each node has at most two par ents. Dasgupta (1999) shows that it is hard to find the polytree with highest maximum-likelihood score. Al though we can identify the highest-scoring tree struc ture using a polynomial number of calls to the scoring criterion, Meek (2001) shows that identifying the best path structure--that is, a tree in which each node has degree at most two-is hard. Bouckaert (1994) shows that for independence-based learning algorithms, find ing the simplest model that is consistent with an in dependence oracle is hard. In this paper, we are interested in the large-sample version of the learning problem considered by Chick ering (1996). The approach used by Chickering (1996) to reduce a known NP-complete problem to the prob lem of learning is to construct a complicated prior net work that defines the Bayesian score, and then create a dataset consisting of a single record. Although the result is discouraging, the proof technique leaves open the hope that, in scenarios where the network scores are more "well behaved" , learning is much easier. As the number of records in the observed data grows large, most scoring criteria will agree on the same par tial ranking of models; in particular, any consistent scoring criterion will-in the limit of large data-favor a model that can represent the generative distribution over a model that cannot, and when comparing two models that can both represent the generative distri bution, will favor the model with fewer parameters. Almost all scoring criteria used in practice are consis tent, including (1) any Bayesian criterion that does not rule out models apriori, (2) the minimum-description length criterion, and (3) the Bayesian-information cri terion. In this paper, we consider the scenario when a learning algorithm is using a consistent scoring criterion with a large dataset. We assume that the learning algorithm has direct access to the generative distribution itself; the learning problem is thus to identify the simplest model that can represent that distribution exactly. There are scenarios in which we can accomplish large sample learning efficiently. If (1) there exists a DAG model solution in which all independence and depen dence relationships implied by that model hold in the generative distribution (that is, the generative distri bution is DA G perfect with respect to the observable
A Bayesian network, as one of the most common models to represent causal relationships between features, has been extensively studied. But learning a full Bayesian network from observational data is an NP-hard problem REF .
Large-Sample Learning of Bayesian Networks is NP-Hard
ArXiv
ArXiv
Mathematics Computer Science