Introduction

The Viterbi algorithm finds the most likely full tag sequence for a sentence. It uses the transition and emission probabilities of an HMM, and it does not need to score every possible path.

With 3 tags and words, there are possible tag paths, so scoring each path one by one becomes too slow. Viterbi solves this with 1 idea: many paths share the same start, so we calculate each shared part only once and reuse it.

Insanely useful video:

Structure

We draw every possible tag at every word as a grid. Each box is 1 tag at 1 word. At each box, we keep only the best score that reaches it.

Steps

  1. Start at <s> and calculate the score for each possible tag of the first word
  2. Move to the next word and look at each possible tag
  3. For each previous tag, multiply the previous score, the transition probability and the emission probability of the current word
  4. Keep only the highest score for each tag, and keep a backpointer to the previous tag that gave it
  5. Continue to the last word, add the transition to <e>, and choose the best final score
  6. Backtrace: follow the backpointers from the end back to the start
  7. Reverse the tags that you collect, so they are in sentence order

The score of 1 box is:

Backpointer and backtrace

A backpointer remembers which previous tag gave the best score for the current box. The forward pass calculates the scores. The backtrace follows the backpointers from the end to recover the tag sequence.

For Will can spot Mary, the backtrace gives:

<s> -> Noun -> Modal -> Verb -> Noun -> <e>
       Will    can      spot    Mary

Do not choose the best tag for each word on its own. At "Will", Modal has a higher score than Noun in the grid above. But Modal followed by Modal has a transition probability of 0, so the best full path goes through Noun. Keep the best score for each tag until the last word.

Remembering tip

Viterbi: keep the best way into each box, then walk back from the end.

Viterbi needs the transition and emission probabilities that a Hidden Markov Model (HMM) learns from the training data.