Mind change optimal learning of Bayes net structure

Schulte, Oliver, Luo, Wei and Greiner, Russell 2007, Mind change optimal learning of Bayes net structure, in COLT 2007 : Proceedings of the 20th Annual Conference on Learning Theory 2007, Springer, Berlin, Germany, pp. 187-202.

Attached Files
Name Description MIMEType Size Downloads

Title Mind change optimal learning of Bayes net structure
Author(s) Schulte, Oliver
Luo, WeiORCID iD for Luo, Wei orcid.org/0000-0002-4711-7543
Greiner, Russell
Conference name Learning Theory. Conference (20th : 2007 : San Diego, California)
Conference location San Diego, California
Conference dates 13-15 Jun. 2007
Title of proceedings COLT 2007 : Proceedings of the 20th Annual Conference on Learning Theory 2007
Editor(s) Nader, H. Bshouty
Gentile, Claudio
Publication date 2007
Conference series Learning Theory Conference
Start page 187
End page 202
Total pages 16
Publisher Springer
Place of publication Berlin, Germany
Summary 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| 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.
ISBN 9783540729259
Language eng
Field of Research 170203 Knowledge Representation and Machine Learning
Socio Economic Objective 970108 Expanding Knowledge in the Information and Computing Sciences
HERDC Research category E1.1 Full written paper - refereed
Copyright notice ©2007, Springer
Persistent URL http://hdl.handle.net/10536/DRO/DU:30052500

Connect to link resolver
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 2 times in TR Web of Science
Scopus Citation Count Cited 2 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 490 Abstract Views, 0 File Downloads  -  Detailed Statistics
Created: Tue, 14 May 2013, 13:51:29 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.