Tester un générateur markovien

Le programme écrit fonctionnait en trois phases:

1. On lit le texte et on compte chaque enchaînement de deux mots. Par exemple, dans la phrase
   "Le président est petit, il l'est par manque de grandeur."
   Le mot "est" est suivi une fois par le mot "petit", une fois par le mot "par". Le mot "Le" est lui suivi par le mot "président", une seule fois.
2. A partir de ce comptage, on calcule ce que l'on appelle un noyau de transition markovien, c'est-à-dire une matrice dont chaque ligne correspond à un mot. Sur chaque ligne, on trouve les probabilités d'avoir chaque mot suivant; la somme des coefficients d'une ligne est donc 1 (matrice stochastique).
3. Ensuite, on se sert de ce noyau pour générer du texte qui "a l'air" d'un vrai texte: On commence par choisir un mot de départ, puis on choisit le mot suivant au hasard en respectant la probabilité associée à ce mot sur la ligne du mot de départ, et on itère autant de fois qu'on veut de mots, le mot généré devenant le mot de départ pour le mot suivant.

Pour les exercices en coding dojo, une pratique courante est d'écrire les tests avant le code. Il fallait donc pouvoir écrire un test sur la correction du générateur.

Voici une méthode possible pour tester un tel générateur, c'est-à-dire pour s'assurer que les mots générés correspondent bien au noyau de transition calculé. En statistique, cela correspond à un test d'adéquation à une loi, en l'occurence la loi de la chaîne de Markov associée à notre noyau, en régime stationnaire.

La méthode consiste à calculer une distance entre la loi observée sur la séquence générée et la loi "théorique" utilisée pour générer la séquence. Plus la distance est grande, moins est crédible l'hypothèse selon laquelle la loi observée correspond à la loi théorique. Le test nous donnera la valeur seuil à partir de laquelle la distance est trop grande pour que cette hypothèse soit vraie.

Remarque: On suppose que notre chaîne de Markov théorique est

• à espace d'états fini, c'est-à-dire que le nombre de mots possibles est fini, ce qui est bien notre cas,
• récurrente, c'est-à-dire qu'il n'y a pas de "puits": on peut, depuis n'importe quel mot, atteindre en un temps fini n'importe quel autre mot. Cela devrait être vrai dans notre cas. Pour les mots qui n'ont pas de successeur, nous considérerons que n'importe quel autre mot peut lui succéder, avec tous la même probabilité.

Nous noterons:

• le nombre d'occurences du mot dans la séquence générée,
• le nombre de fois où le mot est suivi du mot dans la séquence générée,
• la probabilité de transition pour passer du mot au mot , d'après notre matrice de transitions, c'est-àdire la probabilité (conditionnelle) d'avoir un le mot sachant que le mot précédent est ,
• l'alphabet, c'est-à-dire pour nous l'ensemble des mots générables,
• le cardinal de , c'est-à-dire le nombre de mots générables distincts dans notre cas,
• le nombre de transitions dont la probabilité n'est pas nulle, dans notre matrice de transitions.

La distance est alors calculée selon la formule:

Si la séquence est suffisamment longue, suit une loi de à degrés de liberté.

Les tests statistiques ne sont pas symétriques: ils ne permettent pas de dire si une hypothèse est vérifiée ou non, mais seulement de pouvoir rejeter une hypothèse avec un certain niveau de confiance fixé par celui qui utilise le test.

Par exemple, si nous fixons le niveau de confiance à 95%, il faut lire dans la table de la loi du à degrés de liberté le quantile correspond à ce niveau de confiance.

Il est possible d'utiliser un logiciel comme R pour l'obtenir, grâce à la fonction qchisq. Ainsi, si :

> qchisq(0.95, df=380);
[1] 426.4537

Si notre distance est supérieure à ce quantile, alors l'hypothèse est rejetée: la séquence générée ne vérifie pas la loi théorique, c'est-à-dire notre loi de chaîne de Markov. Sinon, nous acceptons l'hypothèse avec un niveau de confiance de 95%. Ce niveau signifie que sur 100 séquences testées, il y en a en moyenne 5 qui seront rejetées alors qu'elles vérifient la loi théorique.

On préfère en gros laisser un coupable en liberté (rejet de l'hypothèse pourtant vraie) plutôt que mettre un innocent en prison (ne pas rejeter une hypothèse pourtant fausse).

Merci à ma statisticienne préférée, qui m'a laissé passer sous silence quelques détails pour rendre l'article accessible aux non-spécialistes comme moi.