Learning Structure from Data: A Survey

Abstract

This paper summarizes several investigations into the prospects of identifying meaningful structures in empirical data. Starting with an early work on identifying probabilistic trees, we extend the method to polytrees (directed trees with arbitrary edge orientation) and show that, under certain conditions, the skeleton of the polytree as well as the orientation of some of the arrows, are identifiable. We next address the problem of identifying probabilistic trees in which some of the nodes are unobservable. It is shown that such trees can be effectively identified in cases where all variables are either bi-valued or normal, and where all correlation coefficients are known precisely. Finally, it is shown that an effective procedure exists for determining whether a given categorical relation is decomposable into a tree of binary relations and, if the answer is positive, identifying the topology of such a tree. Guided by these results, we then propose a general framework whereby the notion of identifiability is given a precise formal definition, similar to that of learnability.