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 metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01406889
Contributor : Olivier Pietquin <>
Submitted on : Thursday, December 1, 2016 - 4:32:17 PM
Last modification on : Thursday, April 4, 2019 - 10:18:05 AM
Long-term archiving on : Tuesday, March 21, 2017 - 8:28:49 AM

File

glaude16.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01406889, version 1

Citation

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⟩

Share

Metrics

Record views

330

Files downloads

102