title: Compositional generative mapping for tree-structured data--part I: bottom-up probabilistic modeling of trees.
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.
authors.forename: Davide
authors.initials: D
authors.lastname: Bacciu
authors.forename: Alessio
authors.initials: A
authors.lastname: Micheli
authors.forename: Alessandro
authors.initials: A
authors.lastname: Sperduti
mesh_terms: D003663:Decision Trees; D006801:Humans; D008390:Markov Chains; D015233:Models, Statistical; D010363:Pattern Recognition, Automated / Q000706:statistics & numerical data