PAC learning of Probabilistic Automaton based on the Method of Moments - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

PAC learning of Probabilistic Automaton based on the Method of Moments

Résumé

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.
Fichier principal
Vignette du fichier
glaude16.pdf (501.61 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01406889 , version 1 (01-12-2016)

Identifiants

  • HAL Id : hal-01406889 , version 1

Citer

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⟩
153 Consultations
224 Téléchargements

Partager

Gmail Facebook X LinkedIn More