Comprendre Algorithme de Viterbi
Le filtrage et le lissage répondent à des questions portant sur un pas de temps à la fois. Demander au contraire l’historique entier qui explique le mieux les observations est une autre question, et y répondre en prenant l’état le plus probable à chaque pas séparément est faux : les gagnants pas à pas ne forment pas nécessairement une séquence possible, encore moins une séquence probable.
L’algorithme de Viterbi corrige cela par un seul changement de la récurrence avant. Là où le filtrage somme sur les façons d’atteindre un état, Viterbi prend le maximum, portant la probabilité du meilleur chemin vers chaque état plutôt que la probabilité totale de tous les chemins. Noter quel prédécesseur a réalisé ce maximum donne un pointeur arrière, et remonter les pointeurs depuis le meilleur état final reconstitue la séquence.
L’économie est celle que la programmation dynamique procure toujours. Il y a 2^t historiques sur t états binaires, et la récurrence touche chaque état une fois par pas : le coût est donc linéaire en t et quadratique en le nombre d’états. Rien n’est approché : la réponse est le maximiseur exact.
Le choix de la question est une décision de modélisation, non un détail technique. Les marginales pas à pas conviennent quand chaque pas sera traité séparément ; Viterbi convient quand les états doivent tenir ensemble, comme pour décoder un message, aligner une séquence ou reconstituer un trajet, où une transition physiquement impossible au milieu de la réponse est pire qu’une réponse un peu moins probable.
Comment calculer
m_{1:t+1} = P(\mathbf{e}_{t+1} \mid \mathbf{X}_{t+1}) \max_{\mathbf{x}_t} \big( P(\mathbf{X}_{t+1} \mid \mathbf{x}_t)\, m_{1:t} \big)
où
- m_{1:t}
- la probabilité du meilleur chemin aboutissant à chaque état à l’instant t
- P(\mathbf{X}_{t+1} \mid \mathbf{x}_t)
- le modèle de transition
- P(\mathbf{e}_{t+1} \mid \mathbf{X}_{t+1})
- le modèle d’observation
Exemple : Algorithme de Viterbi
Dans le monde du parapluie - la pluie persiste avec une probabilité de 0,7, un parapluie apparaît 90 pour cent des jours pluvieux et 20 pour cent des jours secs - prenez les trois observations pas de parapluie, parapluie, pas de parapluie.
Le lissage du deuxième jour pris isolément donne une probabilité de pluie de 0,554 : la réponse pas à pas dit qu’il a plu. L’historique de trois jours le plus probable, trouvé par Viterbi et confirmé en énumérant les huit, est sec les trois jours, avec une probabilité de 0,402.
Il n’y a pas de contradiction. La pluie au deuxième jour est la valeur la plus probable pour ce jour-là quand on moyenne sur les autres ; l’historique tout sec est la combinaison la plus probable quand on ne moyenne pas. Les deux questions ont des réponses différentes parce que les jours ne sont pas indépendants.
Questions fréquentes
Le chemin de Viterbi est-il la suite des maxima lissés ?
Pas en général, et l’exemple du parapluie ci-dessus est un contre-exemple trouvé par énumération et non affirmé. Les maxima lissés peuvent même former une séquence de probabilité nulle si une transition est impossible.
Fonctionne-t-il en espace logarithmique ?
On l’y exécute d’ordinaire. La récurrence multiplie des probabilités, ce qui sous-dépasse sur une longue séquence ; prendre les logarithmes transforme les produits en sommes, et le maximum n’est pas affecté puisque le logarithme est croissant.
En résumé
Remplacez la somme de la récurrence avant par un maximum, gardez un pointeur arrière, et vous obtenez l’historique le plus probable en temps linéaire. Sachez seulement qu’il répond à une autre question que le lissage, et que les deux peuvent authentiquement diverger.