Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête

Le modèle de Markov caché, les trois problèmes de Rabiner, l’algorithme forward, l’algorithme de Viterbi, le décodage a posteriori et l’algorithme de Baum–Welch — sur un casino qui remplace parfois en secret le dé honnête par un dé truqué.

14 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 39 sur 52

Programme complet de la série 52 sur 83 sujets publiés

Ce que vous retiendrez

Ce qu’est un modèle de Markov caché et comment calculer la probabilité des observations sans parcourir tous les chemins.
Comment l’algorithme de Viterbi trouve les états cachés les plus probables, et où il se trompe.
Comment le modèle apprend ses paramètres à partir des seules observations, et combien de données il lui faut.

Utile à connaître avant : Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank

Dans la partie précédente, nous voyions l’état de la chaîne : aujourd’hui du soleil, demain de la pluie. Souvent, pourtant, nous ne voyons que ses manifestations. Un microphone capte une onde sonore, pas le mot qui l’a produite. Un séquenceur lit les lettres de l’ADN, pas l’endroit où commence un gène. Et au casino, nous voyons ce qui est sorti, pas le dé avec lequel le croupier lance. Les modèles de Markov cachés sont des chaînes dont nous ne voyons pas les états — et des algorithmes qui permettent malgré tout de découvrir ce qui se passe à l’intérieur. Pendant des décennies, la reconnaissance de la parole a reposé sur eux.

Cette partie fait suite à la partie Chaînes de Markov.

1. Le casino malhonnête

Un exemple classique des manuels (Durbin et al., 1998) : le croupier lance soit un dé honnête, soit un dé truqué, sur lequel le six sort avec une probabilité de 1/2 et chacun des autres nombres avec 1/10. Après chaque lancer, il remplace le dé honnête par le dé truqué avec une probabilité de 0,05, et le dé truqué par le dé honnête avec une probabilité de 0,1. L’échange, nous ne le voyons pas. Nous ne voyons qu’une suite de nombres — dans notre expérience, 300 lancers qui commencent ainsi :

163665521623524236522511663566613666222461626262162666626516…

Notre question : le jeu est-il honnête ? Et sinon, quand exactement le dé truqué était-il en jeu ?

2. Le modèle de Markov caché

Définition — modèle de Markov caché

Un modèle de Markov caché (HMM, de l’anglais hidden Markov model) λ = (π, A, B) a des états cachés 1, …, N et des symboles observables 1, …, M :

les états cachés X₁, X₂, … forment une chaîne de Markov de distribution initiale π et de matrice de transition A, a_ij = P(X_t+1 = j | X_t = i) ;
à chaque instant, l’état X_t = i génère une observation O_t selon les probabilités d’émission b_i(o) = P(O_t = o | X_t = i), indépendamment de tout le reste.

En termes simples

Derrière le rideau tourne une chaîne de Markov ordinaire — le dé change selon la matrice A. Nous ne voyons que ce qui « tombe » de chaque état : un lancer tiré selon les probabilités B. Sur le dé truqué, le six est cinq fois plus probable que n’importe quel autre nombre, mais il peut aussi sortir sur le dé honnête. Un lancer isolé ne trahit donc rien — seul le motif de toute la suite le trahit.

Le modèle du casino : états cachés en haut, probabilités des lancers en bas

La définition donne la probabilité d’une « histoire » particulière : une suite de dés x = (x₁, …, x_T) accompagnée des lancers O = (O₁, …, O_T).

P(x, O | λ) = π_x₁ b_x₁(O₁) · ∏_t=2^T a_{x_t−1 x_t} b_{x_t}(O_t)

π_x₁: le premier dé n’a pas de prédécesseur depuis lequel on y serait passé — sa probabilité est donnée par la distribution initiale
a_{x_t−1 x_t}: chaque dé suivant ne dépend que du précédent (propriété de Markov), si bien qu’à chaque pas un seul nombre de la matrice A suffit
b_{x_t}(O_t): le lancer ne dépend que du dé avec lequel on lance à ce moment — on prend la probabilité du nombre réellement sorti
∏_t=2^T: en général, on multiplierait des probabilités conditionnées par tout le passé (règle de la chaîne) ; les deux hypothèses d’indépendance de la définition les réduisent à ces nombres locaux, et c’est pourquoi le tout est un simple produit

Chaque pas ajoute deux facteurs : si le dé a changé (ou non) et ce qui est sorti dessus.

Exemple — deux histoires des trois premiers lancers

Notre suite commence par les lancers 1, 6, 3. Notons H le dé honnête et T le dé truqué. L’histoire « trois fois truqué » :

P(TTT, 1, 6, 3) = 0,5 · 0,1 · 0,9 · 0,5 · 0,9 · 0,1 = 0,002025,

l’histoire « trois fois honnête » :

P(HHH, 1, 6, 3) = 0,5 · ¹/₆ · 0,95 · ¹/₆ · 0,95 · ¹/₆ = 0,002089.

L’histoire honnête l’emporte d’un cheveu : le six sur le dé truqué obtient certes 0,5 au lieu de ¹/₆, mais le un et le trois seulement 0,1 au lieu de ¹/₆. (Dans la simulation, les trois lancers ont pourtant tous été faits avec le dé truqué — trois lancers ne suffisent pas à le reconnaître.)

Dans son célèbre article de synthèse de 1989, Lawrence Rabiner a résumé ce que l’on peut faire avec un tel modèle en trois problèmes : l’évaluation (quelle est la probabilité de la suite observée ?), le décodage (quels états cachés se trouvaient le plus probablement derrière elle ?) et l’apprentissage (quels sont les paramètres du modèle quand on ne connaît que les observations ?). Chacun a son algorithme élégant.

3. Quelle est la probabilité de la suite : l’algorithme forward

La probabilité de la suite observée est une somme sur toutes les suites possibles d’états cachés. Pour 300 lancers et deux dés, il y en a 2³⁰⁰ ≈ 2 · 10⁹⁰ — plus qu’il n’y a d’atomes dans l’univers. Les additionner directement est impossible. La propriété de Markov permet cependant de calculer pas à pas.

Exemple — la probabilité de trois lancers comme somme sur toutes les histoires

La probabilité des observations est la somme de la probabilité jointe sur toutes les histoires possibles : P(O | λ) = ∑_x P(x, O | λ). Pour les lancers 1, 6, 3, il y en a 2³ = 8 :

Histoire	`P`(`x`, `O`)
HHH	0,002089
HHT	0,000066
HTH	0,000035
HTT	0,000188
THH	0,000132
THT	0,000004
TTH	0,000375
TTT	0,002025
somme	0,004913

Chaque histoire coûte 2T − 1 = 5 multiplications, soit 8 · 5 = 40 au total. Pour T lancers, c’est (2T − 1) · 2^T — pour 300 lancers, un nombre inimaginable.

Algorithme — algorithme forward

Notons α_t(j) = P(O₁, …, O_t, X_t = j). Alors

α₁(j) = π_j b_j(O₁), α_t+1(j) = [∑_i α_t(i) a_ij] b_j(O_t+1), P(O | λ) = ∑_j α_T(j).

Le calcul prend O(N² T) au lieu de O(N^T). Pour que les nombres ne sous-débordent pas, on normalise α_t à chaque pas et on additionne les logarithmes des constantes de normalisation.

En termes simples

Vous n’avez pas besoin de suivre chaque histoire possible séparément. Après chaque lancer, il suffit de retenir deux nombres : « quelle est la probabilité de tout ce que j’ai vu jusqu’ici, avec le dé honnête en jeu maintenant » — et la même chose pour le dé truqué. On en calcule les nombres pour le lancer suivant. Toutes les histoires qui finissent dans le même état se fondent en un seul nombre.

α_t+1(j) = ∑_i α_t(i) a_ij · b_j(O_t+1)

α_t(i): tout ce que nous savons du passé : la probabilité des lancers jusqu’ici et du fait que le dé i est en jeu maintenant ; ce seul nombre réunit toutes les histoires qui finissent en i
a_ij: un pas de la chaîne de i à j ; grâce à la propriété de Markov, peu importe comment nous sommes arrivés en i
∑_i: nous ne savons pas avec quel dé on a lancé la fois précédente, et on peut arriver en j depuis n’importe lequel — d’où la somme sur toutes les possibilités (les histoires sont des événements incompatibles)
b_j(O_t+1): le nouveau lancer doit réellement être généré par le dé j ; il ne dépend pas de i, et peut donc être mis en facteur devant la somme

La somme sur 2^T histoires se décompose en T petites sommes de N termes.

Exemple — l’algorithme forward sur les lancers 1, 6, 3

Départ : α₁(H) = 0,5 · ¹/₆ = 0,0833, α₁(T) = 0,5 · 0,1 = 0,0500. Le deuxième lancer est un six :

α₂(H) = (0,0833 · 0,95 + 0,0500 · 0,1) · ¹/₆ = 0,0140,
α₂(T) = (0,0833 · 0,05 + 0,0500 · 0,9) · 0,5 = 0,0246.

`t`	lancer	`α`_t(H)	`α`_t(T)	somme = `P`(`O`₁, …, `O`_t)	`c`_t
1	1	0,0833	0,0500	0,133333	0,1333
2	6	0,0140	0,0246	0,038611	0,2896
3	3	0,0026	0,0023	0,004913	0,1273

La somme de la dernière ligne est exactement la somme des huit histoires de l’exemple précédent, sauf qu’au lieu de 40 multiplications, 2 + 2 · 6 = 14 ont suffi. La dernière colonne c_t = P(O_t | O₁, …, O_t−1) est la constante de normalisation issue de la mise à l’échelle : la probabilité du lancer t compte tenu des précédents. Leur produit vaut P(O | λ), donc log P(O | λ) = ∑_t log c_t.

Pourquoi des logarithmes ? Pour 3 000 lancers, P(O | λ) vaut environ 10^−2 278, alors que le plus petit nombre positif qu’un ordinateur peut stocker en double précision ordinaire (IEEE 754) est d’environ 4,9 · 10⁻³²⁴. Sans mise à l’échelle, α sous-déborderait vers zéro.

def dopredu(hody, pi, A, B):
    alfa = pi * B[:, hody[0]]
    logP = 0.0
    for t in range(len(hody)):
        if t > 0:
            alfa = (alfa @ A) * B[:, hody[t]]       # somme sur i, puis émission
        c = alfa.sum()                              # c_t = P(O_t | O_1, …, O_t−1)
        alfa = alfa / c                             # mise à l’échelle : la somme de α_t vaut maintenant 1
        logP += np.log(c)
    return logP                                     # log P(O | λ)

Pour nos 300 lancers, on obtient P(lancers | modèle du casino) ≈ 10^−230,03. Si l’on avait joué honnêtement tout du long, la probabilité serait (1/6)³⁰⁰ ≈ 10^−233,45. Le modèle avec un dé truqué occasionnel explique les lancers observés environ 2 600 fois mieux — une preuve solide qu’il y a tricherie, même si aucun lancer isolé ne trahit la fraude.

Définition — rapport de vraisemblances (facteur de Bayes)

Pour deux modèles M₁, M₂ et des données O, le facteur de Bayes vaut K = P(O | M₁) / P(O | M₂). Du théorème de Bayes (écrit pour les deux modèles, puis divisé) découle :

P(M₁ | O) / P(M₂ | O) = P(O | M₁) / P(O | M₂) · P(M₁) / P(M₂)

P(M₁ | O) / P(M₂ | O): la cote a posteriori — ce qui nous intéresse : combien nous croyons davantage à la tricherie qu’au jeu honnête une fois les lancers vus
P(O | M₁) / P(O | M₂): le facteur de Bayes — le seul endroit par lequel les données entrent dans la formule ; les deux vraisemblances sont calculées par l’algorithme forward. Le dénominateur P(O) du théorème de Bayes se simplifie dans la division, et c’est pourquoi il n’est pas nécessaire de le connaître
P(M₁) / P(M₂): la cote a priori — qui fait confiance au casino au départ a besoin d’une preuve plus forte ; les données ne font que la multiplier

Calcul. log₁₀ K = −230,03 − (−233,45) = 3,42 (3,413 à partir des valeurs non arrondies), donc K ≈ 10^3,413 ≈ 2 590, soit environ 2 600. Si vous jugiez au départ la tricherie et le jeu honnête également probables, après 300 lancers la cote est d’environ 2 600 : 1 en faveur de la tricherie. Selon l’échelle couramment utilisée de Kass et Raftery (1995), un facteur de Bayes supérieur à 150 constitue une preuve « très forte ».

4. Quand a-t-on triché : l’algorithme de Viterbi

Algorithme — algorithme de Viterbi (1967)

Nous cherchons la suite d’états la plus probable argmax_x P(x, O | λ). Notons δ_t(j) la probabilité du meilleur chemin qui se termine dans l’état j à l’instant t :

δ₁(j) = π_j b_j(O₁), δ_t+1(j) = max_i [δ_t(i) a_ij] · b_j(O_t+1),

et pour chaque δ_t+1(j), retiens de quel i il provient. À la fin, choisis le meilleur état et remonte en suivant les pointeurs mémorisés. Le calcul se fait en logarithmes ; le temps est de nouveau O(N² T).

En termes simples

La même idée que l’algorithme forward, sauf qu’au lieu de la somme sur tous les chemins, on prend le meilleur. Vers chaque état à chaque instant mène un seul chemin « gagnant » — si le meilleur chemin global passait par là, il serait de toute façon arrivé à ce point par lui. C’est de la programmation dynamique, apparentée à la recherche du plus court chemin de la partie sur la recherche dans l’espace d’états.

δ_t+1(j) = max_i δ_t(i) a_ij · b_j(O_t+1), ψ_t+1(j) = argmax_i δ_t(i) a_ij

δ_t(i): la probabilité de la meilleure histoire qui se termine avec le dé i à l’instant t ; les histoires moins bonnes vers i ne nous servent plus — si le meilleur chemin complet passait par i, il continuerait à partir de la meilleure
a_ij: le coût du passage de i à j ; le petit a_HT = 0,05 est la raison pour laquelle Viterbi rechigne à basculer à cause d’un seul six
max_i, ψ_t+1(j): contrairement à l’algorithme forward, on ne fait pas la somme, on choisit le meilleur prédécesseur — nous voulons un seul chemin, pas la probabilité de tous ; ψ retient qui a gagné (les flèches ambrées dans le treillis), afin que le chemin puisse être reconstitué à rebours à la fin
b_j(O_t+1): dans quelle mesure le dé j explique le nouveau lancer — exactement comme pour α

La même formule que pour α, sauf que la somme ∑ est remplacée par un maximum.

Treillis de Viterbi pour les lancers 19–30 : les nombres sont le log₁₀ de la probabilité du meilleur chemin

Douze lancers suffisent pour voir comment Viterbi décide. Les six premiers lancers (5, 2, 2, 5, 1, 1) semblent honnêtes. Puis viennent deux six d’affilée, et deux autres un peu plus loin — et le meilleur chemin bascule sur le dé truqué. En réalité, le croupier n’a changé de dé que quatre lancers plus tard ; deux six d’affilée sortent aussi sur un dé honnête.

Exemple — Viterbi pas à pas sur les lancers 1, 6, 3

Le départ est le même que pour α : δ₁(H) = 0,0833, δ₁(T) = 0,0500. Pour le six du deuxième lancer :

δ₂(H) = max(0,0833 · 0,95 ; 0,0500 · 0,1) · ¹/₆ = 0,0792 · ¹/₆ = 0,0132 (H gagne),
δ₂(T) = max(0,0833 · 0,05 ; 0,0500 · 0,9) · 0,5 = 0,0450 · 0,5 = 0,0225 (T gagne).

`t`	lancer	`δ`_t(H)	`ψ`_t(H)	`δ`_t(T)	`ψ`_t(T)
1	1	0,083333	—	0,050000	—
2	6	0,013194	H	0,022500	T
3	3	0,002089	H	0,002025	T

À la fin, H gagne (0,002089 > 0,002025) et, en remontant les pointeurs ψ, on obtient le chemin HHH — exactement l’histoire du premier exemple qui était la plus probable des huit. L’algorithme forward donne pourtant pour le troisième lancer P(T | O₁, O₂, O₃) = 0,002283 / 0,004913 = 0,465. Le meilleur chemin et l’état le plus probable coïncident ici (H), mais la « victoire » est serrée et trois lancers ne suffisent pas à être sûr. En général, ils ne coïncident pas forcément — nous y reviendrons avec le décodage a posteriori.

import numpy as np

def viterbi(hody, pi, A, B):
    T, N = len(hody), len(pi)
    delta = np.log(pi) + np.log(B[:, hody[0]])
    odkud = np.zeros((T, N), dtype=int)
    for t in range(1, T):
        kandidati = delta[:, None] + np.log(A)       # de chaque i vers chaque j
        odkud[t] = kandidati.argmax(axis=0)
        delta = kandidati.max(axis=0) + np.log(B[:, hody[t]])
    cesta = [int(delta.argmax())]
    for t in range(T - 1, 0, -1):                     # à rebours le long des pointeurs gagnants
        cesta.append(odkud[t][cesta[-1]])
    return cesta[::-1]

5. Les 300 lancers

Réalité, lancers, chemin de Viterbi et probabilité du dé truqué

Le dé truqué a été en jeu 88 fois, en neuf séquences. Viterbi a marqué 62 lancers comme truqués, dont 56 à juste titre, et a identifié correctement le dé pour 87,3 % des lancers au total. Il a trouvé les longues séquences de triche, mais a manqué les courtes ou les a fusionnées — au lieu de neuf séquences, il en voit deux. Sur une séquence courte, il ne sort tout simplement pas assez de six pour justifier un « coûteux » changement de dé (la probabilité d’un changement n’est que de 0,05).

Définition — probabilité a posteriori d’un état

L’algorithme forward-backward calcule en plus β_t(i) = P(O_t+1, …, O_T | X_t = i) en partant de la fin, et à partir des deux obtient γ_t(i) = P(X_t = i | O) ∝ α_t(i) β_t(i).

En termes simples

Viterbi donne une seule réponse : « c’était ce dé-là ». La probabilité a posteriori vous dit à quel point nous en sommes sûrs — pour chaque lancer séparément, en tenant compte de tout ce qui est sorti avant et après. C’est la courbe du bas dans la figure : là où elle dépasse la moitié, la triche est plus probable que le jeu honnête.

γ_t(i) = α_t(i) · β_t(i) / P(O | λ), β_t(i) = ∑_j a_ij b_j(O_t+1) β_t+1(j), β_T(i) = 1

γ_t(i): la probabilité que le dé i ait été en jeu à l’instant t, sachant tous les lancers — pour le dé truqué, c’est la courbe rouge de la figure
α_t(i): les indices venus du passé : les lancers 1 à t et l’état i à l’instant t
β_t(i): les indices venus du futur : dans quelle mesure l’état i explique les lancers t + 1 à T. Il se calcule en partant de la fin avec la même astuce que α — un pas de la chaîne, l’émission, le reste du futur. Nous avons le droit de multiplier α et β, car, l’état X_t étant connu, les lancers passés et futurs sont indépendants
P(O | λ): le produit α·β est la probabilité jointe P(X_t = i, O) ; en la divisant par la probabilité de tous les lancers, nous en faisons une probabilité conditionnelle. C’est le même nombre que celui donné par l’algorithme forward, et ∑_i α_t(i) β_t(i) = P(O | λ) est vrai pour tout t

Exemple — le deuxième lancer : ce qu’apporte le futur

Restons-en aux lancers 1, 6, 3 et interrogeons-nous sur le deuxième lancer (le six). Le pas arrière depuis β₃ = 1 avec le troisième lancer (le trois) :

β₂(H) = 0,95 · ¹/₆ + 0,05 · 0,1 = 0,1633, β₂(T) = 0,1 · ¹/₆ + 0,9 · 0,1 = 0,1067.

γ₂(T) = 0,024583 · 0,106667 / 0,004913 = 0,534.

Si nous ne connaissions que les deux premiers lancers, nous aurions P(T | O₁, O₂) = α₂(T) / (α₂(H) + α₂(T)) = 0,637. Le trois sorti ensuite est moins probable sur le dé truqué, et il abaisse donc rétroactivement le soupçon sur le deuxième lancer à 0,534.

Définition — décodage a posteriori et exactitude

Le décodage a posteriori choisit à chaque instant séparément x̂_t = argmax_i γ_t(i). L’exactitude d’un décodage x̂ par rapport aux vrais états x est la proportion de concordances (1/T) ∑_t [x̂_t = x_t], où [·] vaut 1 si l’affirmation est vraie, 0 sinon.

Le décodage a posteriori maximise le nombre attendu de lancers correctement identifiés, Viterbi la probabilité que le chemin entier soit correct d’un coup. C’est pourquoi une suite a posteriori peut même contenir une transition de probabilité nulle dans le modèle — le casino n’en a pas, mais en général cela peut arriver.

Si, pour chaque lancer, nous choisissions le dé ayant la plus grande probabilité a posteriori, nous aurions juste dans 87,7 % des cas — un cheveu de plus que Viterbi (263 lancers sur 300 contre 262, une différence d’un seul lancer). (Viterbi cherche le meilleur chemin entier, le décodage a posteriori la meilleure estimation de chaque lancer séparément ; ce n’est pas la même chose.) Et méfiez-vous d’une simulation unique : sur douze essais différents, l’exactitude de l’algorithme de Viterbi a varié de 73,3 à 90,0 %, avec une moyenne de 83,4 %. Tout dépend de la longueur des séquences de triche que produit le hasard.

6. Apprentissage : l’algorithme de Baum–Welch

Jusqu’ici, nous connaissions les paramètres du casino. Et si nous savions seulement qu’il y a deux dés, et qu’il fallait lire tout le reste dans les lancers ?

Algorithme — algorithme de Baum–Welch

C’est un algorithme EM (Baum et al., vers 1970). Répète :

étape E : avec les paramètres actuels, calcule par l’algorithme forward-backward γ_t(i) et les nombres attendus de transitions ξ_t(i, j) = P(X_t = i, X_t+1 = j | O) ;
étape M : nouveau a_ij = ∑_t ξ_t(i, j) / ∑_t γ_t(i), nouveau b_i(o) = part de γ aux instants où o est sorti.

La vraisemblance P(O | λ) ne diminue à aucune itération ; l’algorithme converge vers un maximum local.

En termes simples

Si nous savions quand chaque dé était en jeu, nous obtiendrions les paramètres par simple comptage. Nous ne le savons pas — mais avec une estimation quelconque des paramètres, nous savons calculer avec quelle probabilité chaque dé était où. Nous calculons donc des comptes « souples », puis de meilleurs paramètres, puis de meilleurs comptes… Chaque tour améliore le modèle.

Le nombre attendu de transitions se calcule à partir des mêmes α et β que γ, on insère simplement un pas de la chaîne entre eux :

ξ_t(i, j) = α_t(i) a_ij b_j(O_t+1) β_t+1(j) / P(O | λ)

α_t(i): les lancers jusqu’à l’instant t et le dé i à l’instant t — l’extrémité gauche de la transition
a_ij: la transition i → j elle-même, dont nous estimons la fréquence
b_j(O_t+1): le lancer t + 1 doit être généré par le nouveau dé j
β_t+1(j): le reste des lancers à partir de t + 2, expliqué à partir du dé j — l’extrémité droite de la transition
P(O | λ): la division transforme la probabilité jointe « transition et tous les lancers » en probabilité conditionnelle « transition, sachant les lancers »

â_ij = ∑_t=1^T−1 ξ_t(i, j) / ∑_t=1^T−1 γ_t(i)

â_ij: la nouvelle estimation de la probabilité de transition — une fréquence relative, comme si l’on comptait des bâtons
∑ ξ_t(i, j): le nombre attendu de transitions i → j ; au lieu de « il y a eu transition ou non » (1 ou 0), nous additionnons des probabilités, car nous ne voyons pas les états
∑ γ_t(i): le nombre attendu de départs depuis l’état i ; la somme ne va que jusqu’à T − 1, car aucune transition ne part du dernier état. Grâce à cela, chaque ligne de la nouvelle matrice a pour somme 1

Si nous voyions les états, ξ et γ seraient des zéros et des uns, et la formule serait l’estimation ordinaire du maximum de vraisemblance à partir des comptes.

répéter (ici 100 fois) :
    α, β, P(O) ← algorithme forward-backward avec les π, A, B actuels
    # étape E : comptes souples
    pour chaque t, i :         γ[t][i]    ← α[t][i] · β[t][i] / P(O)
    pour chaque t < T, i, j : ξ[t][i][j] ← α[t][i] · a[i][j] · b[j](O[t+1]) · β[t+1][j] / P(O)
    # étape M : fréquences relatives
    π[i]    ← γ[1][i]
    a[i][j] ← ∑_{t<T} ξ[t][i][j] / ∑_{t<T} γ[t][i]
    b[i](o) ← ∑_{t: O[t]=o} γ[t][i] / ∑_t γ[t][i]

Nous sommes partis d’une mauvaise estimation : les dés se distinguent à peine et sont échangés souvent. À partir de 300 lancers, Baum–Welch est arrivé à un modèle qui n’échange presque jamais les dés et ne donne au dé truqué le six qu’avec une probabilité de 0,39 — 300 lancers, c’est trop peu pour une estimation fiable. À partir de 3 000 lancers (une autre simulation du même casino), le résultat était déjà très proche de la vérité :

Paramètre	Réalité	Estimation sur 3 000 lancers
honnête → truqué	0,05	0,039
truqué → honnête	0,10	0,090
six sur le dé truqué	0,50	0,491
six sur le dé honnête	0,167	0,163

Pourquoi 300 lancers ne suffisent pas, la vraisemblance le montre. Au cours de 100 itérations sur nos 300 lancers, elle est passée de 10^−231,26 à 10^−227,14 — ce qui est plus que les 10^−230,03 du vrai modèle du casino. Le modèle appris explique donc ces lancers-là mieux que la vérité : il s’est adapté aussi aux fluctuations aléatoires de ces données précises. L’estimation du maximum de vraisemblance ne s’approche de la vérité qu’à mesure que les données s’accumulent.

7. Les modèles de Markov cachés en pratique

Reconnaissance de la parole. Des années 1980 jusqu’à l’arrivée des réseaux profonds vers 2010, presque tous les systèmes reposaient sur des HMM : les états cachés sont des parties de phonèmes, les observations de courts segments du spectre sonore, et Viterbi cherche la suite de mots la plus probable.
Langue. Étiquetage morphosyntaxique : l’état caché est la catégorie grammaticale, l’observation le mot. « Ferme » peut être un nom, un verbe ou un adjectif — c’est le contexte qui décide.
Bio-informatique. Recherche de gènes dans l’ADN (les régions codantes et non codantes sont les états cachés) ou HMM de profil pour les familles de protéines dans la base de données Pfam.
États continus. Quand l’état caché n’est pas « dé A ou B », mais une position et une vitesse, on utilise à la place d’un HMM le filtre de Kalman — il a sa propre partie dans le programme.

8. Résumé

Un modèle de Markov caché est une chaîne de Markov d’états cachés dont nous ne voyons que les émissions ; il est déterminé par π, A et B.
L’algorithme forward calcule la probabilité des observations en temps O(N²T) au lieu d’une somme sur 2³⁰⁰ chemins ; le casino avec tricherie explique nos lancers environ 2 600 fois mieux qu’un jeu honnête.
L’algorithme de Viterbi trouve le chemin d’états cachés le plus probable par programmation dynamique — dans notre simulation, il a identifié correctement le dé pour 87,3 % des lancers, mais a manqué les courtes séquences.
L’algorithme forward-backward donne la probabilité a posteriori de l’état à chaque instant.
L’algorithme de Baum–Welch apprend les paramètres à partir des seules observations — mais il lui faut assez de données : 300 lancers n’ont pas suffi, 3 000 oui.

Envie de mettre la main à la pâte ? Demandez à un agent IA d’entraîner un HMM à deux états sur les rendements journaliers d’un indice boursier — et regardez s’il trouve tout seul les périodes « calmes » et « agitées » du marché.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.

Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête

1. Le casino malhonnête

2. Le modèle de Markov caché

3. Quelle est la probabilité de la suite : l’algorithme forward

4. Quand a-t-on triché : l’algorithme de Viterbi

5. Les 300 lancers

6. Apprentissage : l’algorithme de Baum–Welch

7. Les modèles de Markov cachés en pratique

8. Résumé

Un Agent sur votre ordinateur, piloté depuis votre téléphone