Deakin University
Browse

File(s) under permanent embargo

Mind change optimal learning of Bayes net structure

conference contribution
posted on 2007-01-01, 00:00 authored by O Schulte, Wei LuoWei Luo, R Greiner
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.

History

Event

Learning Theory. Conference (20th : 2007 : San Diego, California)

Pagination

187 - 202

Publisher

Springer

Location

San Diego, California

Place of publication

Berlin, Germany

Start date

2007-06-13

End date

2007-06-15

ISBN-13

9783540729259

ISBN-10

3540729259

Language

eng

Publication classification

E1.1 Full written paper - refereed

Copyright notice

2007, Springer

Editor/Contributor(s)

H Nader, C Gentile

Title of proceedings

COLT 2007 : Proceedings of the 20th Annual Conference on Learning Theory 2007

Usage metrics

    Research Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC