Abstract FR:

Les langages stochastiques -- des disbributions de probabilité sur des séquences -- jouent un rôle central dans de nombreux domaines. Notamment en bio-informatique, en reconnaissance vocale et plus généralement dans la plupart des domaines qui traitent un grand nombre de données représentées comme des chaînes de caractères. Nous utilisons des automates probabilistes (PA) -- un modèle équivalent aux chaînes de Markov cachées -- pour modéliser de tels langages stochastiques. Inférer des automates probabilistes à partir de données est un vaste domaine de recherche ouvert. Nous montrons qu'à partir d'une séquence de mots indépendamment et identiquement distribués selon un langage stochastique modélisé par un PA, on peut identifier celui-ci à la limite avec probabilité 1. Pour cela nous utilisons un algorithme d'inférence de PA qui n'a pas un comportement énumératif. Malheureusement, la complexité de cet algorithme est trop importante pour pouvoir en envisager une utilisation réelle. Il semble alors naturel d'essayer de trouver une sous-classe, la plus grande possible, pour laquelle nous pouvons concevoir un algorithme utilisable. Aussi, introduisons-nous une nouvelle classe d'automates probabilistes : les automates probabilistes à résiduels (PRA). La définition des PRA est basée sur une notion intrinsèque des langages stochastiques : les résiduels. Nous montrons que les PRA sont plus concis et plus expressifs que les automates probabilistes déterministes (PDA) -- une sous-classe des PA pour laquelle des algorithmes d'inférence existe. Comme les PDA, les PRA possèdent une forme canonique. De l'algorithme d'inférence de PA, nous en déduisons un algorithme d'inférence de PRA utilisable. On peut aussi modéliser les langages stochastiques avec des automates à multiplicité. Il s'agit d'un modèle qui généralise la notion de PA. Nous montrons que la classe des langages stochastiques modélisables par des MA est strictement plus grande que celle modélisée par des PA. Nous montrons de plus que l'on ne peut pas décider si un MA modélise un langage stochastique. Ce résultat négatif associé au manque de robustesse de la représentation des langages stochastiques par des MA nous permet de conclure qu'il n'existe probablement pas d'algorithme d'inférence de MA utilisable. Les MA ne semblent donc pas être une bonne représentation pour l'inférence de langages stochastiques.