On the use of independence relationships for learning simplified belief networks

Belief networks are graphic structures capable of representing dependence and independence relationships among variables in a given domain of knowledge. We focus on the problem of automatic learning of these structures from data, and restrict our study to a specific type of belief network: simple graphs, i.e., directed acyclic graphs where every pair of nodes with a common direct child has no common ancestor nor is one an ancestor of the other. Our study is based on an analysis of the independence relationships that may be represented by means of simple graphs. This theoretical study, which includes new characterizations of simple graphs in terms of independence relationships, is the basis of an efficient algorithm that recovers simple graphs using only zero and first-order conditional independence tests, thereby overcoming some of the practical difficulties of existing algorithms. ©1997 John Wiley & Sons, Inc.