2
$\begingroup$

I am deeply struggling with understanding how to apply the Viterbi algorithm. From my course notes, I have the following simple(I'm told) example:

enter image description here

If the sequence HH was observed, what is the most likely sequence in which Fair and Biased coins were used ?

Following table was generated as part of solution:

enter image description here

and the answer was given as $O-Biased-Fair$ with probability 0.2025. The $O$ stands for original state before any observations.

Can someone explain this answer in much detail and simplest way possible ? Thanks.

$\endgroup$
2
$\begingroup$

Viterbi algorithm is a dynamic programming algorithm for finding the most probable sequence of hidden states given a sequence of observations in an HMM.

The table in your solution has one row per hidden state (O, F, B) and one column per observation ($\emptyset$, head, head) where $\emptyset$ denotes the beginning of the observation sequence. So, the first column tells you with what probabilities we start from each state. Since we always start from O and never from the other states, the first columns is 1, 0, 0.

The second column says, given the probabilities in the previous (i.e. the first) column, what is the probability that we end up at each state after observing the first observation. It seems that the probability of going form state O to F and B is the same and equal to $0.5$. So, your first graph should be like this:

enter image description here

1. After the first observation

Keep in mind that we know that in the beginning we were in state O with probability 1.

Probability of staying at O is 0.

Probability of going to F (from O) is $0.5$ and probability of observing a head (the first observation) there is $0.5$, so, probability of ending up at F after the first observation is $1 \times 0.5 \times 0.5 = 0.25$.

Probability of going to B (from O) is $0.5$ and probability of observing a head (the first observation) there is $0.9$, so, probability of ending up at B after the first observation is $1 \times 0.5 \times 0.9 = 0.45$.

2. After the second observation

The probability of ending up at O, F, or B after the second observation (head) is as follows:

2.1. Probability of ending up at O:

... is zero since there is no way we can enter O (see the diagram).

2.2. Probability of ending up at F:

... there are 3 possibilities:

  1. assuming we came from O: has probability 0 (see 2nd column of your table)
  2. assuming we came from F: has probability $0.25 \times 0.9 \times 0.5 = 0.1125$
  3. assuming we came from B: has probability $0.45 \times 0.9 \times 0.5 = 0.2025$

The most probable hypothesis is that we have come form state B.

2.3. Probability of ending up at B:

... there are 3 possibilities:

  1. assuming we came from O: has probability 0 (see 2nd column of your table)
  2. assuming we came from F: has probability $0.25 \times 0.1 \times 0.9 = 0.0225$
  3. assuming we came from B: has probability $0.45 \times 0.1 \times 0.9 = 0.0405$

The most probable hypothesis is that we have come form state B.

3. The Viterbi solution

According to the 3rd column of your table, the most probably hypothesis is that after observing two heads with this HMM we end up in state F (it has probability $0.2025$ versus $0.0405$ for state B and $0$ for state O). According to section 2.2, most likely, we have come from $B$ and we know that we started form O (these are indicated by arrows in your table). So, the Viterbi state sequence is O, B, S.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.