Compositional generative mapping for tree-structured data--part I: bottom-up probabilistic modeling of trees

IEEE Trans Neural Netw Learn Syst. 2012 Dec;23(12):1987-2002. doi: 10.1109/TNNLS.2012.2222044.

Abstract

We introduce a novel compositional (recursive) probabilistic model for trees that defines an approximated bottom-up generative process from the leaves to the root of a tree. The proposed model defines contextual state transitions from the joint configuration of the children to the parent nodes. We argue that the bottom-up context postulates different probabilistic assumptions with respect to a top-down approach, leading to different representational capabilities. We discuss classes of applications that are best suited to a bottom-up approach. In particular, the bottom-up context is shown to better correlate and model the co-occurrence of substructures among the child subtrees of internal nodes. A mixed memory approximation is introduced to factorize the joint children-to-parent state transition matrix as a mixture of pairwise transitions. The proposed approach is the first practical bottom-up generative model for tree-structured data that maintains the same computational class of its top-down counterpart. Comparative experimental analyses exploiting synthetic and real-world datasets show that the proposed model can deal with deep structures better than a top-down generative model. The model is also shown to better capture structural information from real-world data comprising trees with a large out-degree. The proposed bottom-up model can be used as a fundamental building block for the development of other new powerful models.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Decision Trees*
  • Humans
  • Markov Chains
  • Models, Statistical*
  • Pattern Recognition, Automated* / statistics & numerical data