A Spectral Approach for Probabilistic Grammatical Inference on Trees

摘要

We focus on the estimation of a probability distribution over a set of trees. We consider here the class of distributions computed by weighted automata -a strict generalization of probabilistic tree automata. This class of distributions (called rational distributions, or rational stochastic tree languages - RSTL) has an algebraic characterization: All the residuals (conditional) of such distributions lie in a finite-dimensional vector subspace. We propose a methodology based on Principal Components Analysis to identify this vector subspace. We provide an algorithm that computes an estimate of the target residuals vector subspace and builds a model which computes an estimate of the target distribution.