Mind Change Optimal Learning of Bayes Net Structure from Dependency and Independency Data
This paper analyzes the problem of learning the structure of a Bayes net in the theoretical framework of
Gold's learning paradigm. Bayes nets are one of the most prominent formalisms for knowledge representation and
probabilistic and causal reasoning. We follow constraint-based approaches to learning Bayes net structure, where
learning is based on observed conditional dependencies and independencies between variables of interest (e.g., the
data are of the form "X is dependent on Y given any assignment to variables S" or of the form "X is independent of
Y given any assignment to variables S"). Applying learning criteria in this model leads to the following results. (1)
The mind change complexity of identifying a Bayes net graph over variables V from either dependency data or from
independency data is (|V| choose 2), the maximum number of edges. (2) There is a unique fastest mind-change optimal Bayes
net learner for either data type; convergence speed is evaluated using Gold's dominance notion of "uniformly faster
convergence". For dependency data, the optimal learner conjectures a graph if it is the unique Bayes net pattern
that satisfies the observed dependencies with a minimum number of edges, and outputs "no guess" otherwise. For
independency data, the optimal learner conjectures a graph if it is the unique Bayes net pattern that satisfies the
observed dependencies with a maximum number of edges, and outputs "no guess" otherwise. We investigate the
complexity of computing the output of the fastest mind-change optimal learner for either data type, and show that
each of these two problems is NP-hard (assuming P = RP). To our knowledge these are the first NP-hardness
results concerning the existence of a uniquely optimal Bayes net structure.
Citation
O. Schulte,
W. Luo,
R. Greiner.
"Mind Change Optimal Learning of Bayes Net Structure from Dependency and Independency Data".
Information and Computation, 208(1), pp 63--82, March 2010.
| Keywords: |
Bayesian net, structure learning, machine learning |
| Category: |
In Journal |
| Web Links: |
DOI |
BibTeX
@article{Schulte+al:I&C10,
author = {Oliver Schulte and Wei Luo and Russ Greiner},
title = {Mind Change Optimal Learning of Bayes Net Structure from Dependency
and Independency Data},
Volume = "208",
Number = "1",
Pages = {63--82},
journal = {Information and Computation},
year = 2010,
}Last Updated: September 25, 2016
Submitted by Russ Greiner 
