Quelle est la différence entre les algorithmes avant-arrière et Viterbi?

Un peu de contexte dabord peut-être que ça clarifie les choses un peu.

Quand on parle de HMM (Hidden Markov Models), il y a généralement 3 problèmes à considérer:

1. Problème dévaluation

   • Le problème dévaluation répond à la question: quelle est la probabilité quune séquence particulière de symboles soit produite par un modèle particulier?
   • Pour lévaluation, nous utilisons deux algorithmes: l algorithme avant ou l algorithme arrière (NE les confondez PAS avec lalgorithme avant-arrière).

2. Problème de décodage

   • Le problème de décodage répond à la question: étant donné une séquence de symboles (vos observations) et un modèle, quelle est la séquence détats la plus probable qui a produit la séquence.
   • Pour le décodage, nous utilisons l algorithme de Viterbi .

3. Problème de formation

   • Le problème de formation répond à la question: étant donné une structure de modèle et un ensemble de séquences, trouvez le modèle qui correspond le mieux aux données .
   • Pour ce problème, nous pouvons utiliser les 3 algorithmes suivants:
     1. MLE (estimation du maximum de vraisemblance)
     2. Viterbi training (NE PAS confondre avec le décodage de Viterbi)
     3. Baum Welch = algorithme avant-arrière

Pour résumer, vous utilisez lalgorithme de Viterbi pour le problème de décodage et Baum Welch / Avant-arrière lorsque vous entraînez votre modèle sur un ensemble de séquences.

Baum Welch fonctionne de la manière suivante.

Pour chaque séquence de lensemble de séquences dapprentissage.

1. Calculer les probabilités avant avec lalgorithme avant
2. Calculer les probabilités arrière avec lalgorithme arrière
3. Calculer les contributions de la séquence actuelle aux transitions du modèle, calculer les contributions de la séquence actuelle aux probabilités démission du modèle.
4. Calculer les nouveaux paramètres du modèle (probabilités de départ, probabilités de transition, probabilités démission )
5. Calculez le nouvelle probabilité de journalisation du modèle
6. Arrêter lorsque la modification de la probabilité de journal est inférieure à un seuil donné ou lorsquun nombre maximum ditérations est dépassé.

Si vous avez besoin une description complète des équations pour le décodage de Viterbi et lalgorithme de formation faites le moi savoir et je peux vous orienter dans la bonne direction.

Commentaires

• Salut . Si nous sauvegardons le chemin, lors de lévaluation à laide de lalgorithme de transfert, lutilisation de lalgorithme de Viterbi pour le décodage est-elle redondante?

Forward-Backward donne une probabilité marginale pour chaque état individuel , Viterbi donne la probabilité de la séquence détats la plus probable. Par exemple, si votre tâche HMM consiste à prédire le temps ensoleillé ou pluvieux pour chaque jour, Forward Backward vous indiquera la probabilité quil soit « ensoleillé » pour chaque jour, Viterbi donnera la séquence la plus probable de jours ensoleillés / pluvieux, et le probabilité de cette séquence.

Je trouve que ces deux diapositives suivantes de {2} sont vraiment bonnes pour situer lavant -algorithmes de retour et de Viterbi parmi tous les autres algorithmes typiques utilisés avec HMM:

Remarques :

• $ x $ est la ou les émissions observées, $ \ pi $ sont les paramètres du HMM.
• path = une séquence démissions
• decoding = inference
• learning = training = estimation des paramètres
• Certains articles (par exemple, {1}) affirment que Baum – Welch est identique à lalgorithme avant-arrière, mais Je suis agr ee avec Masterfool et Wikipedia: Baum – Welch est un algorithme de maximisation des attentes qui utilise lalgorithme avant-arrière. Les deux illustrations distinguent également Baum – Welch de lalgorithme avant-arrière.

Références:

• {1} Lember, Jüri et Alexey Koloydenko. « La formation Viterbi ajustée pour les modèles de Markov cachés. » Bernoulli 14, no. 1 (2008): 180-206.
• {2} 6.047 / 6.878 Computational Biology: Genomes, Networks, Evolution (Fall 2012) Conférence 07 – HMMs II (2012-09-29) http://stellar.mit.edu/S/course/6/fa12/6.047/courseMaterial/topics/topic2/lectureNotes/Lecture07_HMMsIIb_6up/Lecture07_HMMsIIb_6up.pdf (Manolis Kellis):

La réponse de Morat est fausse sur un point: Baum -Welch est un algorithme de maximisation des attentes, utilisé pour entraîner les paramètres dun HMM. Il utilise lalgorithme avant-arrière à chaque itération. Lalgorithme avant-arrière nest en réalité quune combinaison des algorithmes avant et arrière: une passe avant, une passe arrière. Seul, lalgorithme avant-arrière nest pas utilisé pour lapprentissage des paramètres dun HMM, mais uniquement pour le lissage: calcul des probabilités marginales dune séquence détats.

https://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm

https://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm

@Yaroslav Bulatov avait une réponse précise. Jen ajouterais un exemple pour indiquer au les différences entre les algorithmes avant-arrière et de Viterbi.

Supposons que nous ayons un this HMM (de la page Wikipedia HMM). Remarque, le modèle est déjà donné, donc il ny a pas de tâche dapprentissage à partir des données ici.

Supposons que nos données soient une séquence de longueur 4. (Walk, Shop, Walk, Clean). Deux algorithmes donneront des choses différentes.

• Lalgorithme avant en arrière donnera le probabi lité de chaque état caché . Voici un exemple. Notez que chaque colonne du tableau sélève à 1 $.

• Lalgorithme de Viterbi donnera la séquence détats cachés la plus probable . Voici un exemple. Notez quil existe également une probabilité associée à cette séquence détats cachés. Cette séquence a un maximum de prob. sur toutes les autres séquences (par exemple, $ 2 ^ 4 = 16 $ séquences de tous les Sunny à tous les Rainy).

Voici quelques R code de la démo

library(HMM) # in education setting, # hidden state: Rainy and Sunny # observation: Walk, Shop, Clean # state transition P <- as.matrix(rbind(c(0.7,0.3), c(0.4,0.6))) # emission prob R <- as.matrix(rbind(c(0.1, 0.4, 0.5), c(0.6,0.3, 0.1))) hmm = initHMM(States=c("Rainy","Sunny"), Symbols=c("Walk","Shop", "Clean"), startProbs=c(0.6,0.4), transProbs=P, emissionProbs=R) hmm obs=c("Walk","Shop","Walk", "Clean") print(posterior(hmm,obs)) print(viterbi(hmm, obs))