Learning Rational Stochastic Tree Languages
Abstract
We consider the problem of learning stochastic tree languages, i.e. probability distributions over a set of trees $T({\cal F})$ , from a sample of trees independently drawn according to an unknown target P . We consider the case where the target is a rational stochastic tree language, i.e. it can be computed by a rational tree series or, equivalently, by a multiplicity tree automaton. In this paper, we provide two contributions. First, we show that rational tree series admit a canonical representation with parameters that can be efficiently estimated from samples. Then, we give an inference algorithm that identifies the class of rational stochastic tree languages in the limit with probability one.
Cite
Text
Denis and Habrard. "Learning Rational Stochastic Tree Languages." International Conference on Algorithmic Learning Theory, 2007. doi:10.1007/978-3-540-75225-7_21Markdown
[Denis and Habrard. "Learning Rational Stochastic Tree Languages." International Conference on Algorithmic Learning Theory, 2007.](https://mlanthology.org/alt/2007/denis2007alt-learning/) doi:10.1007/978-3-540-75225-7_21BibTeX
@inproceedings{denis2007alt-learning,
title = {{Learning Rational Stochastic Tree Languages}},
author = {Denis, François and Habrard, Amaury},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2007},
pages = {242-256},
doi = {10.1007/978-3-540-75225-7_21},
url = {https://mlanthology.org/alt/2007/denis2007alt-learning/}
}