A Spectral Approach for Probabilistic Grammatical Inference on Trees
Abstract
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.
Cite
Text
Bailly et al. "A Spectral Approach for Probabilistic Grammatical Inference on Trees." International Conference on Algorithmic Learning Theory, 2010. doi:10.1007/978-3-642-16108-7_10Markdown
[Bailly et al. "A Spectral Approach for Probabilistic Grammatical Inference on Trees." International Conference on Algorithmic Learning Theory, 2010.](https://mlanthology.org/alt/2010/bailly2010alt-spectral/) doi:10.1007/978-3-642-16108-7_10BibTeX
@inproceedings{bailly2010alt-spectral,
title = {{A Spectral Approach for Probabilistic Grammatical Inference on Trees}},
author = {Bailly, Raphaël and Habrard, Amaury and Denis, François},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2010},
pages = {74-88},
doi = {10.1007/978-3-642-16108-7_10},
url = {https://mlanthology.org/alt/2010/bailly2010alt-spectral/}
}