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

44

Je veux savoir quelles sont les différences entre l' algorithme avant-arrière et l' algorithme de Viterbi pour l'inférence dans les modèles de Markov cachés (HMM).

utilisateur34790
la source
2
Des descriptions des algorithmes ( ici et ici ) répondent-elles à votre question ou cherchez-vous autre chose? Vous vous demandez quand utiliser quel algorithme? Vous souhaitez discuter de leurs mérites respectifs?
mardi

Réponses:

65

Un peu d’arrière-plan d’abord peut-être éclaircit un peu les choses.

Quand on parle de HMM (modèles de Markov cachés), il y a généralement 3 problèmes à prendre en compte:

  1. Problème d'évaluation

    • Le problème d’évaluation répond à la question suivante: quelle est la probabilité qu’une séquence particulière de symboles soit produite par un modèle particulier?
    • Pour l'évaluation, nous utilisons deux algorithmes: l' algorithme forward ou l' algorithme backward (NE PAS les confondre avec l'algorithme forward-backward).
  2. Problème de décodage

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

    • Le problème de formation répond à la question: à partir d'une structure de modèle et d'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. Entraînement Viterbi (NE PAS confondre avec le décodage de Viterbi)
      3. Baum Welch = algorithme avant-arrière

Pour résumer, vous utilisez l'algorithme de Viterbi pour le problème de décodage et Baum Welch / Forward-backward 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 l'ensemble de séquences d'apprentissage.

  1. Calculer les probabilités forward avec l'algorithme forward
  2. Calculer les probabilités en arrière avec l'algorithme en arrière
  3. Calculez les contributions de la séquence en cours aux transitions du modèle, calculez les contributions de la séquence en cours 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. Calculer la nouvelle probabilité de log du modèle
  6. Arrêtez-vous lorsque le changement de probabilité de journal est inférieur à un seuil donné ou lorsqu'un nombre maximal d'itérations est passé.

Si vous avez besoin d'une description complète des équations pour le décodage de Viterbi et de l'algorithme d'apprentissage, faites-le moi savoir et je pourrai vous orienter dans la bonne direction.

Morat
la source
24

Forward-Backward donne une probabilité marginale pour chaque état , Viterbi donne une probabilité de la séquence d'états la plus probable . Par exemple, si votre tâche HMM consiste à prévoir le temps ensoleillé par rapport au temps pluvieux pour chaque jour, Avant en arrière vous indiquera la probabilité qu'il soit ensoleillé pour chaque jour, Viterbi donnera la séquence la plus probable de jours ensoleillés / pluvieux, et probabilité de cette séquence.

Yaroslav Bulatov
la source
15

Je trouve ces deux diapositives suivantes de {2} très utiles pour situer les algorithmes de transfert ascendant et précédent et de Viterbi parmi tous les autres algorithmes classiques utilisés avec HMM:

entrez la description de l'image ici

entrez la description de l'image ici

Remarques:

  • x est la ou les émissions observées, sont les paramètres du HMM.π
  • chemin = une séquence d'émissions
  • décodage = inférence
  • apprentissage = formation = estimation des paramètres
  • Certains articles ({1}, par exemple) prétendent que Baum – Welch est identique à l'algorithme avant-arrière, mais je suis d'accord avec Masterfool et Wikipedia: Baum – Welch est un algorithme d'optimisation des attentes qui utilise l'algorithme avant-arrière. Les deux illustrations distinguent également Baum – Welch de l'algorithme avant – arrière.

Les références:

Franck Dernoncourt
la source
12

La réponse de Morat est fausse sur un point: Baum-Welch est un algorithme d'espérance-maximisation, utilisé pour entraîner les paramètres d'un HMM. Il utilise l'algorithme avant-arrière lors de chaque itération. L'algorithme avant-arrière n'est en réalité qu'une combinaison des algorithmes avant et arrière: une passe avant, une passe arrière. À lui seul, l'algorithme avant-arrière n'est pas utilisé pour l'apprentissage des paramètres d'un HMM, mais uniquement pour le lissage: calcul des probabilités marginales d'une séquence d'états.

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

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

Masterfool
la source
2

@Yaroslav Bulatov avait une réponse précise. J'en ajouterais un exemple pour faire la différence entre les algorithmes avant-arrière et Viterbi.

Supposons que nous ayons ce HMM (extrait de la page Wikipedia HMM). Remarque, le modèle est déjà donné, il n'y a donc pas d'apprentissage à partir de la tâche de données ici.

entrez la description de l'image ici


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

  • L'algorithme Forward Backward donnera la probabilité de chaque état caché . Voici un exemple. Notez que chaque colonne du tableau totalise .1

entrez la description de l'image ici

  • L'algorithme de Viterbi donnera la séquence la plus probable d'états cachés . Voici un exemple. Notez qu'il existe également une probabilité associée à cette séquence d'états cachés. Cette séquence a max prob. sur toutes les autres séquences (par exemple, séquences de toutes à toutes ).24=16SunnyRainy

entrez la description de l'image ici


Voici du Rcode pour 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))
Haitao Du
la source