• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

How to apply the Viterbi algorithm

Contents

  • How to apply the Viterbi algorithm
    • See also

The goal of the Viterbi algorithm is find the most likely sequence of hidden states given some observed events.

Lets say this is your HMM:

A hidden Markov model (HMM) example
A hidden Markov model (HMM) example

We always start in \(x\) and always end in \(z\).

Now you observed the sequence \(O_1 = BAB\). What is the most likely sequence that would generate this path?

Candidates are:

  • xxyz
  • xyyz
  • xyzz

If you're learing this because you will write the exam at KIT, you might have such an diagram:

Scheme of the Viterbi algorithm
Scheme of the Viterbi algorithm

In this case, the bold path is the Viterbi path. You can see this when you get backwards from the last state:

\(\frac{1}{125} \cdot 1 \cdot 0.2 > \frac{9}{2500} \cdot 0.8 \cdot 0.2\). After this step, you only have one choice. So the Viterbi path is xyzz.

Please note that there might be multiple paths with the highest possibility.

As every state depends only on the state before, you can get the most likely path step by step. In every step, you calculate how likely it is that you end up in state x, state y, state z. After that, it doesn't matter how you got there. So you always have to expand those three nodes. You will get 9 following states, but only three of them matter (for each resulting state, the paths that had the highest probability leading there).

See also

  • Wikipedia

Published

Sep 11, 2013
by Martin Thoma

Category

My bits and bytes

Tags

  • HMM 1
  • KogSys 5
  • Machine Learning 81

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor