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 : mercredi 21 février 2018 - 12:06:26
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

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

245

Téléchargements de fichiers

35