文档介绍：1
Learning works from Data:
An Information-Theory Based Approach
Jie Cheng1 , Russell Greiner and Jonathan Kelly
Department puting Science, University of Alberta
David Bell and Weiru Liu
Faculty of Informatics, University of Ulster
November 1, 2001
Abstract
This paper provides algorithms that use an information-theoretic analysis to learn Bayesian
network structures from data. Based on our three-phase learning framework, we develop efficient
algorithms that can effectively learn works, requiring only polynomial numbers of
conditional independence (CI) tests in typical cases. We provide precise conditions that specify
when these algorithms are guaranteed to be correct as well as empirical evidence (from real world
applications and simulation tests) that demonstrates that these systems work efficiently and
reliably in practice.
Keywords
Bayesian s, learning, probabilistic model, knowledge discovery, data mining, conditional
independence test, monotone DAG faithful, information theory
1 Now at Global Analytics, Canadian Imperial Bank merce, Toronto, Canada.
2
1 Introduction
works (BNs; defined below) are a powerful formalism for representing and reasoning
under conditions of uncertainty. Their ess has led to a recent furry of algorithms for learning
works from data. Although many of these learners produce good results on some
benchmark data sets, there are still several problems:
• Node ordering requirement. Many BN-learning algorithms require additional information –
notably an ordering of the nodes to reduce the search space (see [Cooper and Herskovits,
1992; Heckerman et al., 1994]). Unfortunately, this information is not always available.
We therefore want a learner that can exploit such prior information if it is available, but
which can still learn effectively if it is not.
• plexity. Practically all BN learners are slow, both in theory [Chickering
et al., 1994] and in