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.
Type de document :
Communication dans un congrès
International Conference on Machine Learning (ICML 2016), Jun 2016, New York, United States
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01406889
Contributeur : Olivier Pietquin <>
Soumis le : jeudi 1 décembre 2016 - 16:32:17
Dernière modification le : mardi 3 juillet 2018 - 11:29:37
Document(s) archivé(s) le : mardi 21 mars 2017 - 08:28:49

Fichier

glaude16.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01406889, version 1

Collections

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〉

Partager

Métriques

Consultations de la notice

302

Téléchargements de fichiers

58