Mind Change Optimal Learning of Bayes Net Structure
- Oliver Schulte, Department of Computer Science, Simon Fraser University
- Wei Luo
- Russ Greiner, Dept of Computing Science; PI of AICML
This paper analyzes the problem of learning the structure of a Bayes net (BN) 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 between variables of interest (e.g., "X is dependent on Y given any assignment to variable Z"). 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 dependency data is ( |V| choose 2), the maximum number of edges. (2) There is a unique fastest mind-change optimal Bayes net learner; convergence speed is evaluated using Gold's dominance notion of "uniformly faster convergence". This 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. Therefore we are using standard learning criteria to define a natural and novel Bayes net learning algorithm. We investigate the complexity of computing the output of the fastest mind-change optimal learner, and show that this problem is NP-hard (assuming P = RP). To our knowledge this is the first NP-hardness result 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". Conference on Learning Theory (COLT), San Diego, CA, June 2007.| Keywords: | bayesian network, belief nets, learning, complexity, NP-hardness, structure learning, machine learning |
| Category: | In Conference |
BibTeX
@incollection{Schulte+al:COLT07,
author = {Oliver Schulte and Wei Luo and Russ Greiner},
title = {Mind Change Optimal Learning of Bayes Net Structure},
booktitle = {Conference on Learning Theory (COLT)},
year = 2007,
}Last Updated: July 07, 2007Submitted by Russ Greiner
