Utilisation de matrices de Hankel non bornées pour l'apprentissage spectral de langages stochastiques

Résumé : Un problème de base en inférence grammaticale consiste à inférer un modèle probabiliste, par exemple sous la forme d'un automate pondéré, à partir d'un échantillon $S$ de chaînes tirées indépendamment selon une distribution cible $p$. Des avancées récentes - les méthodes spectrales - reformulent cette tâche comme un problème d'algèbre linéaire : le modèle inféré se calcule aisément à partir d'une décomposition en valeurs singulières tronquée d'une matrice $H$, appelée matrice de Hankel, qui résume l'information contenue dans l'échantillon et dont les lignes $U$ et les colonnes $V$ sont indexées par des chaînes. Les performances du modèle dépendent à la fois de la distance entre la matrice de Hankel réelle et sa version empirique calculée à partir de $S$ ainsi que du choix des ensembles indexant la matrice. Les approches existantes se basent sur des ensembles $U$ et $V$ de taille finie, généralement petite, et les bornes de concentration qui sont invoquées sur la différence entre les matrices de Hankel empirique et réelle dépendent de ces tailles. Nous proposons dans cet article une borne de concentration indépendante des tailles de $U$ et de $V$ qui laisse penser qu'il n'y a pas d'inconvénient majeur à ne pas borner a priori ces tailles. Nous fournissons des comptes-rendus d'expériences dans lesquelles nous comparons les résultats obtenus à partir de différentes versions de la matrices de Hankel empirique montrant l'intérêt d'utiliser des ensembles $U$ et $V$ non bornés.
Document type :
Conference papers
Complete list of metadatas

https://hal-ujm.archives-ouvertes.fr/ujm-00870081
Contributor : Amaury Habrard <>
Submitted on : Friday, October 4, 2013 - 8:32:20 PM
Last modification on : Tuesday, April 2, 2019 - 1:42:38 AM

Identifiers

  • HAL Id : ujm-00870081, version 1

Citation

Mattias Gybels, François Denis, Amaury Habrard. Utilisation de matrices de Hankel non bornées pour l'apprentissage spectral de langages stochastiques. Conférence d'Apprentissage, 2013, France. ⟨ujm-00870081⟩

Share

Metrics

Record views

226