Skip to Main content Skip to Navigation
Conference papers

PAC learning of Probabilistic Automaton based on the Method of Moments

Abstract : Probabilitic Finite Automata (PFA) are gener-ative graphical models that define distributions with latent variables over finite sequences of symbols, a.k.a. stochastic languages. Traditionally , unsupervised learning of PFA is performed through algorithms that iteratively improves the likelihood like the Expectation-Maximization (EM) algorithm. Recently, learning algorithms based on the so-called Method of Moments (MoM) have been proposed as a much faster alternative that comes with PAC-style guarantees. However, these algorithms do not ensure the learnt automata to model a proper distribution , limiting their applicability and preventing them to serve as an initialization to iterative algorithms. In this paper, we propose a new MoM-based algorithm with PAC-style guarantees that learns automata defining proper distributions. We assess its performances on synthetic problems from the PAutomaC challenge and real datasets extracted from Wikipedia against previous MoM-based algorithms and EM algorithm.
Document type :
Conference papers
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Olivier Pietquin Connect in order to contact the contributor
Submitted on : Thursday, December 1, 2016 - 4:32:17 PM
Last modification on : Thursday, January 20, 2022 - 4:17:06 PM
Long-term archiving on: : Tuesday, March 21, 2017 - 8:28:49 AM


Files produced by the author(s)


  • HAL Id : hal-01406889, version 1


Hadrien Glaude, Olivier Pietquin. PAC learning of Probabilistic Automaton based on the Method of Moments. International Conference on Machine Learning (ICML 2016), Jun 2016, New York, United States. ⟨hal-01406889⟩



Les métriques sont temporairement indisponibles