Understanding the Viterbi algorithm
What is it?
The Viterbi algorithm is used for calculating the most likely sequence of events in a Hidden Markov Model.
As a bit of a reminder, in this kind of model, what we do is that we have a Markov chain which we cannot observe, however, there are also events which we can observe which depend on the states of the HMM.
Having said that, what we theoretically could do would be to would be to take all the possible combinations of states which could lead to the observed events, get the likelihood of each of those combinations and see which combination reaches the highest value. However, this is incredibly inefficient, so, here is where the Viterbi algorithm comes in. It reaches the same result as comparing all the possible combinations, it just does it in a clever way.
How does it work?
Assume we have the following table of transition log probabilities in the Markov chain:
| Noun | Verb | ENDTOKEN | |
|---|---|---|---|
| STARTTOKEN | \(-1\) | \(-2\) | \(-\infty\) |
| Noun | \(-3\) | \(-1\) | \(-4\) |
| Verb | \(-1\) | \(-3\) | \(-1\) |
And the following table for the observable events that depend on the Markov chain states:
| They | can | fish | |
|---|---|---|---|
| Noun | -2 | -3 | -3 |
| Verb | -10 | -1 | -3 |
Now, we can take a look at a sentence:
They can fish.
What is the most likely sequence of states (Parts of speech) that could have lead to this sequence.
Using the Viterbi algorithm, we can do the following:
- First we examine the probability of the first word belonging to any of the classes. This is, the probability of the class following a STARTTOKEN, times the probability of the class.
| They | |
|---|---|
| Noun | \(-1-2=-3\) |
| Verb | \(-2 -10 = -12\) |
- Now, we have the probability of They being each of those classes. We need to incorporate this into the calculation of the next word.
- In particular, we now have to juggle 3 probabilities. The probability of the previous tag, the probability of the current tag given the previous tag and the probability of the current tag given the word. (In this order in the table below).
| They | can | |
|---|---|---|
| Noun | \(-3\) | \(-3-3-3=-9\) | \(-12-1-3=-14\) |
| Verb | \(-12\) | \(-3-1-1=-5\) | \(-12-3-1=-16\) |
Doing this gets us various probabilities per cell. We simply take the highest one, note down the assumption about previous tag that lead us to it and repeat until the table is full.
| They | can | fish | |
|---|---|---|---|
| Noun | \(-3\) | -9 (from noun) | \(-9 -3 -3 = -15\)|\(-5 -1 -3 = -9\) |
| Verb | \(-12\) | -5 (from noun) | \(-9 -1 -3 = -13\)|\(-5 -3 -3 =-11\) |
Now, for the end token, we take just the probability of it following a specific pos tag times the probability of that pos tag. We aren’t assigning it any tag, so there is no need for multiple cells in that last column, I just don’t know how to do that in Obsidian.
| They | can | fish | END TOKEN | |
|---|---|---|---|---|
| Noun | \(-3\) | -9 (from noun) | \(-9\) (from noun) | \(-9 -4 = -13\) | \(-11 - 1 = -12\) |
| Verb | \(-12\) | -5 (from noun) | \(-11\) (from verb) |
Once this is done, we once again take the highest probability and note down where it came from.
| They | can | fish | END TOKEN | |
|---|---|---|---|---|
| Noun | \(-3\) | -9 (from noun) | \(-9\) (from noun) | \(-12\) (from verb) |
| Verb | \(-12\) | -5 (from noun) | \(-11\) (from verb) |
Once this table is complete, what we do is that we start from the end and follow the arrows all the way to the beginning. That is, we got the best probability for the end token from a verb, so we assume that the last tag was a verb. Then, we look at the column corresponding to that token and the cell corresponding to the verb tag. Where did we get the best probability for that cell? From the verb tag. So we go to the previous and repeat until we have found the most probable sequence.
| They | can | fish | END TOKEN | |
|---|---|---|---|---|
| Noun | -3 | \(-9\) (from noun) | \(-9\) (from noun) | -12 (from verb) |
| Verb | \(-12\) | -5 (from noun) | -11 (from verb) |
Therefore, the most likely sequence of tags would be the following: \[[[\text{NOUN}]], [[\text{VERB}]], [[\text{VERB}]]\]