文档介绍：Learning works from Data: An Efficient Approach Based on
Information Theory
Jie Cheng David Bell, Weiru Liu
Dept. puting Science Faculty of Informatics,
University of Alberta University of Ulster,
Alberta, T6G 2H1 UK BT37 0QB
Email: ******@ Email: {, }***@
Abstract
This paper addresses the problem of learning work structures from data by using an information
theoretic dependency analysis approach. Based on our three-phase construction mechanism, two efficient
algorithms have been developed. One of our algorithms deals with a special case where the node ordering is given,
the algorithm only require O(N 2 ) CI tests and is correct given that the underlying model is DAG-Faithful [Spirtes
et. al., 1996]. The other algorithm deals with the general case and requires O(N 4 ) conditional independence (CI)
tests. It is correct given that the underlying model is monotone DAG-Faithful (see Section ). A system based on
these algorithms has been developed and distributed through the . The empirical results show that our
approach is efficient and reliable.
1 Introduction
The work is a powerful knowledge representation and reasoning tool under conditions of uncertainty. A
work is a directed acyclic graph (DAG) with a probability table for each node. The nodes in a Bayesian
network represent propositional variables in a domain, and the arcs between nodes represent the dependency
relationships among the variables. On constructing works from databases, we use nodes to represent
database attributes.
In recent years, many work structure learning algorithms have been developed. These algorithms
generally fall into two groups, search & scoring based algorithms and dependency analysis based algorithms. An
overview of these algorithms is presented in Section 6. Although some of these algorithms can give good results on
some benchmark data sets, there are still several problems:
• Node ordering requirement. A lot