Décodage de Viterbi

Position dans le parcoursModule 2 sur 3 · Sujet 2 sur 4

2.2 Décodage de Viterbi

—Score du lab— / 100XP total—Série—

L'histoire unique la plus probable

L'algorithme forward additionne tous les chemins cachés pour dire quelle est la probabilité des données. On veut souvent autre chose : la meilleure histoire unique, la suite d'états qui explique les données avec la plus forte probabilité. Le décodage de Viterbi la trouve. L'idée est celle de l'algorithme forward avec un seul changement : au lieu de sommer sur les états précédents, prendre le meilleur. On garde un score $\delta_t(j)$ , la probabilité du meilleur chemin qui finit dans l'état $j$ le jour $t$ , et on retient quel état précédent l'a donné, le pointeur arrière.

\delta_1(j)=\pi_jB_j(o_1),\qquad \delta_t(j)=\Big[\max_i\delta_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad \psi_t(j)=\arg\max_i\delta_{t-1}(i)A_{ij}

(1)

Après le dernier jour, choisissez l'état de plus grand $\delta_T$ et remontez les pointeurs $\psi$ pour lire tout le chemin. Deux points pratiques. D'abord, travaillez avec des logs : les produits de nombreuses probabilités tendent vers zéro, mais les logs en font des sommes, et comme le log est croissant, le meilleur chemin est le même. Ensuite, le meilleur chemin n'est pas le même que choisir l'état le plus probable chaque jour séparément. Le chemin peut être imposé par ce qui vient après, comme le montre l'exemple.

Petit, Grand, Grand encoreJour 1 :

\delta_1=(0{,}54,\ 0{,}12)

. Jour 2 (grand) : Calme vient au mieux de Calme,

0{,}54\cdot0{,}9\cdot0{,}1=0{,}0486

. Orageux vient au mieux d'Orageux,

0{,}12\cdot0{,}8\cdot0{,}7=0{,}0672

, et non de Calme (

0{,}54\cdot0{,}1\cdot0{,}7=0{,}0378

). Jour 3 : Orageux vient d'Orageux,

0{,}0672\cdot0{,}8\cdot0{,}7=0{,}0376

, et Calme seulement

0{,}0044

. Le meilleur chemin est Orageux, Orageux, Orageux avec la probabilité

0{,}0376

. Pourtant le premier jour seul semblait calme avec la probabilité

0{,}82

. Les grands mouvements suivants tirent toute l'histoire vers Orageux. Ce chemin est

1{,}78

fois plus probable que Calme, Orageux, Orageux (

0{,}0212

Viterbi remplace la somme de l'algorithme forward par un maximum et garde des pointeurs arrière.
Le meilleur chemin peut différer de l'état le plus probable de chaque jour pris séparément.
Utilisez des logs : les sommes de logs évitent le soupassement et gardent le même meilleur chemin.

Lab : ce qui est noté

Un score de Viterbi au jour deux15 pts
La probabilité du meilleur chemin15 pts
Le log du meilleur chemin10 pts
Face à un autre chemin10 pts
Le premier état du meilleur chemin15 pts
Les étapes de Viterbi10 pts
Associer le vocabulaire10 pts
Pourquoi utiliser des logs15 pts

0/ 8 traités

1Réponse numérique15 ptsSans réponse

Avec $\delta_1=(0{,}54,\ 0{,}12)$ et un grand mouvement au jour 2, que vaut $\delta_2(O)=\max(0{,}54\cdot0{,}1,\ 0{,}12\cdot0{,}8)\cdot0{,}7$ ? Donnez quatre décimales.

d =

accepté : ± 0.0003

2Réponse numérique15 ptsSans réponse

Avec $\delta_2=(0{,}0486,\ 0{,}0672)$ et un grand mouvement au jour 3, que vaut $\delta_3(O)=\max(0{,}0486\cdot0{,}1,\ 0{,}0672\cdot0{,}8)\cdot0{,}7$ , la probabilité du meilleur chemin ? Donnez quatre décimales.

d =

accepté : ± 0.0003

3Réponse numérique10 ptsSans réponse

Quel est le logarithme népérien de la probabilité $0{,}0376$ du meilleur chemin ? Donnez deux décimales.

l =

accepté : ± 0.02

4Réponse numérique10 ptsSans réponse

Combien de fois le meilleur chemin (probabilité $0{,}0376$ ) est-il plus probable que le chemin Calme, Orageux, Orageux (probabilité $0{,}0212$ ) ? Donnez deux décimales.

r =

accepté : ± 0.02

5Choix15 ptsSans réponse

Le premier jour montre un petit mouvement, ce qui rend Calme probable à 82 % à lui seul. Quel est le premier état du meilleur chemin pour Petit, Grand, Grand ?

6Remettre les étapes dans l'ordre10 ptsSans réponse

Mettez dans l'ordre les étapes du décodage de Viterbi.

Faites glisser pour réordonner, ou placez le focus sur un élément, Espace pour le soulever, les flèches pour le déplacer et Espace pour le déposer.

1Après le dernier jour, choisir l'état de plus grand score
2Commencer avec delta égal à la probabilité initiale fois la première émission
3Remonter les pointeurs pour lire le chemin
4Pour chaque jour et état, garder le meilleur prédécesseur et s'en souvenir

7Associer10 ptsSans réponse

Associez chaque terme à son sens.

Choisissez le partenaire de chaque élément de gauche.

\delta_t(j)

\psi_t(j)

Algorithme forward

Algorithme de Viterbi

8Expliquer avec des mots15 ptsSans réponse

En une ou deux phrases, expliquez pourquoi le décodage de Viterbi s'écrit en général avec les logs des probabilités et pourquoi cela ne change pas le meilleur chemin.

Noté sur :Les produits de nombreuses probabilités tendent vers zéroLes logs transforment les produits en sommes et le log est croissant, donc le meilleur chemin est le même0 / 400 caractères

Mode mathsSaisie au clavier ou en LaTeXExercice 1 sur 8 · Ctrl ⏎ pour vérifier

Décodage de Viterbi

Position dans le parcoursModule 2 sur 3 · Sujet 2 sur 4

2.2 Décodage de Viterbi

—Score du lab— / 100XP total—Série—

L'histoire unique la plus probable

\delta_1(j)=\pi_jB_j(o_1),\qquad \delta_t(j)=\Big[\max_i\delta_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad \psi_t(j)=\arg\max_i\delta_{t-1}(i)A_{ij}

(1)

Petit, Grand, Grand encoreJour 1 :

\delta_1=(0{,}54,\ 0{,}12)

. Jour 2 (grand) : Calme vient au mieux de Calme,

0{,}54\cdot0{,}9\cdot0{,}1=0{,}0486

. Orageux vient au mieux d'Orageux,

0{,}12\cdot0{,}8\cdot0{,}7=0{,}0672

, et non de Calme (

0{,}54\cdot0{,}1\cdot0{,}7=0{,}0378

). Jour 3 : Orageux vient d'Orageux,

0{,}0672\cdot0{,}8\cdot0{,}7=0{,}0376

, et Calme seulement

0{,}0044

. Le meilleur chemin est Orageux, Orageux, Orageux avec la probabilité

0{,}0376

. Pourtant le premier jour seul semblait calme avec la probabilité

0{,}82

. Les grands mouvements suivants tirent toute l'histoire vers Orageux. Ce chemin est

1{,}78

fois plus probable que Calme, Orageux, Orageux (

0{,}0212

Viterbi remplace la somme de l'algorithme forward par un maximum et garde des pointeurs arrière.
Le meilleur chemin peut différer de l'état le plus probable de chaque jour pris séparément.
Utilisez des logs : les sommes de logs évitent le soupassement et gardent le même meilleur chemin.

Lab : ce qui est noté

Un score de Viterbi au jour deux15 pts
La probabilité du meilleur chemin15 pts
Le log du meilleur chemin10 pts
Face à un autre chemin10 pts
Le premier état du meilleur chemin15 pts
Les étapes de Viterbi10 pts
Associer le vocabulaire10 pts
Pourquoi utiliser des logs15 pts

0/ 8 traités

1Réponse numérique15 ptsSans réponse

Avec $\delta_1=(0{,}54,\ 0{,}12)$ et un grand mouvement au jour 2, que vaut $\delta_2(O)=\max(0{,}54\cdot0{,}1,\ 0{,}12\cdot0{,}8)\cdot0{,}7$ ? Donnez quatre décimales.

d =

accepté : ± 0.0003

2Réponse numérique15 ptsSans réponse

d =

accepté : ± 0.0003

3Réponse numérique10 ptsSans réponse

Quel est le logarithme népérien de la probabilité $0{,}0376$ du meilleur chemin ? Donnez deux décimales.

l =

accepté : ± 0.02

4Réponse numérique10 ptsSans réponse

Combien de fois le meilleur chemin (probabilité $0{,}0376$ ) est-il plus probable que le chemin Calme, Orageux, Orageux (probabilité $0{,}0212$ ) ? Donnez deux décimales.

r =

accepté : ± 0.02

5Choix15 ptsSans réponse

Le premier jour montre un petit mouvement, ce qui rend Calme probable à 82 % à lui seul. Quel est le premier état du meilleur chemin pour Petit, Grand, Grand ?

6Remettre les étapes dans l'ordre10 ptsSans réponse

Mettez dans l'ordre les étapes du décodage de Viterbi.

Faites glisser pour réordonner, ou placez le focus sur un élément, Espace pour le soulever, les flèches pour le déplacer et Espace pour le déposer.

1Après le dernier jour, choisir l'état de plus grand score
2Commencer avec delta égal à la probabilité initiale fois la première émission
3Remonter les pointeurs pour lire le chemin
4Pour chaque jour et état, garder le meilleur prédécesseur et s'en souvenir

7Associer10 ptsSans réponse

Associez chaque terme à son sens.

Choisissez le partenaire de chaque élément de gauche.

\delta_t(j)

\psi_t(j)

Algorithme forward

Algorithme de Viterbi

8Expliquer avec des mots15 ptsSans réponse

En une ou deux phrases, expliquez pourquoi le décodage de Viterbi s'écrit en général avec les logs des probabilités et pourquoi cela ne change pas le meilleur chemin.

Noté sur :Les produits de nombreuses probabilités tendent vers zéroLes logs transforment les produits en sommes et le log est croissant, donc le meilleur chemin est le même0 / 400 caractères

Mode mathsSaisie au clavier ou en LaTeXExercice 1 sur 8 · Ctrl ⏎ pour vérifier

Décodage de Viterbi

L'histoire unique la plus probable

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.

Décodage de Viterbi

L'histoire unique la plus probable

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.