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.