By author > Denis François

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.