2.3 Aléa sur les arbres digitaux
59
En français, la lettre ‘Q’ sera souvent suivie de la lettre ‘U’. Les chaînes de Markov
du premier ordre (car il est évidemment possible d’examiner les dépendances
plus lointaines, non réduites à deux lettres consécutives) permettent de prendre en
compte ce type de modèle (voir C.5 pour une présentation des chaînes de Markov).
Définition 2.24 (source markovienne d’ordre 1) Une source à dépendance
markovienne d’ordre 1 est donnée par une loi de probabilité (π a ) a∈A sur les
lettres de l’alphabet et une matrice stochastique de transition P = (p b|a ) (a,b)∈A×A .
La suite de variables aléatoires (X n ) n≥1 à valeur dans A est la suite des lettres du
mot émis par la source. C’est la chaîne de Markov de loi initiale (π a ) a∈A et de
matrice de transition P , autrement dit : la variable X 1 est de loi (π a ) a∈A
P(X 1 = a) = π a pour tout a ∈ A,
et pour i ≥ 2, les lois des variables X i sont définies conditionnellement par
P(X i = b | X i−1 = a) = p b|a pour a, b ∈ A.
La quantité π a est la probabilité que le premier symbole émis soit a. La quantité
p b|a est la probabilité d’émettre le symbole b juste après symbole a. La probabilité
fondamentale p w pour un préfixe fini w = w 1 w 2 . . . w n (avec w i ∈ A et n > 0)
s’écrit
p w = π w 1
n
i=2
p w i |w i−1 ,
ce qui définit la mesure P et ainsi la source.
Comment engendrer un texte markovien ? Pour générer un texte (issu d’un
corpus) qui obéisse à ce modèle, nous pouvons utiliser une méthode de type
Monte Carlo due à Shannon et décrite par exemple dans [248]. Cette méthode
permet d’éviter le calcul des probabilités de transition à partir du corpus. Dans le
texte de référence nous choisissons aléatoirement et uniformément une position p.
Supposons que cette position pointe sur le symbole ‘B’. Nous pointons ensuite au
hasard une position p dans le texte et nous parcourons ce texte jusqu’à rencontrer
à nouveau un symbole ‘B’ à une certaine position q. Le symbole à émettre est alors
celui situé à la position q +1. Ce symbole devient le symbole courant, et nous itérons
le processus. Les éventuels problèmes de cette méthode est qu’elle ne permet pas de
calculer un vecteur de probabilités initiales (ce qui n’est pas possible de toute façon
avec un seul texte de référence) et que nous pouvons échouer dans la recherche d’un
symbole s’il n’apparaît pas entre la position courante et la fin du texte (nous pouvons
résoudre en pratique ce problème en rendant le texte cyclique par exemple).
59
En français, la lettre ‘Q’ sera souvent suivie de la lettre ‘U’. Les chaînes de Markov
du premier ordre (car il est évidemment possible d’examiner les dépendances
plus lointaines, non réduites à deux lettres consécutives) permettent de prendre en
compte ce type de modèle (voir C.5 pour une présentation des chaînes de Markov).
Définition 2.24 (source markovienne d’ordre 1) Une source à dépendance
markovienne d’ordre 1 est donnée par une loi de probabilité (π a ) a∈A sur les
lettres de l’alphabet et une matrice stochastique de transition P = (p b|a ) (a,b)∈A×A .
La suite de variables aléatoires (X n ) n≥1 à valeur dans A est la suite des lettres du
mot émis par la source. C’est la chaîne de Markov de loi initiale (π a ) a∈A et de
matrice de transition P , autrement dit : la variable X 1 est de loi (π a ) a∈A
P(X 1 = a) = π a pour tout a ∈ A,
et pour i ≥ 2, les lois des variables X i sont définies conditionnellement par
P(X i = b | X i−1 = a) = p b|a pour a, b ∈ A.
La quantité π a est la probabilité que le premier symbole émis soit a. La quantité
p b|a est la probabilité d’émettre le symbole b juste après symbole a. La probabilité
fondamentale p w pour un préfixe fini w = w 1 w 2 . . . w n (avec w i ∈ A et n > 0)
s’écrit
p w = π w 1
n
i=2
p w i |w i−1 ,
ce qui définit la mesure P et ainsi la source.
Comment engendrer un texte markovien ? Pour générer un texte (issu d’un
corpus) qui obéisse à ce modèle, nous pouvons utiliser une méthode de type
Monte Carlo due à Shannon et décrite par exemple dans [248]. Cette méthode
permet d’éviter le calcul des probabilités de transition à partir du corpus. Dans le
texte de référence nous choisissons aléatoirement et uniformément une position p.
Supposons que cette position pointe sur le symbole ‘B’. Nous pointons ensuite au
hasard une position p dans le texte et nous parcourons ce texte jusqu’à rencontrer
à nouveau un symbole ‘B’ à une certaine position q. Le symbole à émettre est alors
celui situé à la position q +1. Ce symbole devient le symbole courant, et nous itérons
le processus. Les éventuels problèmes de cette méthode est qu’elle ne permet pas de
calculer un vecteur de probabilités initiales (ce qui n’est pas possible de toute façon
avec un seul texte de référence) et que nous pouvons échouer dans la recherche d’un
symbole s’il n’apparaît pas entre la position courante et la fin du texte (nous pouvons
résoudre en pratique ce problème en rendant le texte cyclique par exemple).