Viterbi algorithm: Difference between revisions

Revision as of 00:17, 17 October 2004

Revision as of 22:45, 19 October 2004

Line 34:

In this fragment, <code>start_probability</code> refers to your uncertainty about which state the HMM is in when your friend first calls you (all you know is that it tends to be rainy on average). The <code>transition_probability</code> refers to the change of the weather in the underlying Markov chain. In this example, there is only a 30% chance that tomorrow will be sunny if today is rainy. The <code>emission_probability</code> tells you how likely your friend is to perform a certain activity on each day. If it's rainy, there is a 50% chance that he is cleaning his apartment; if it's sunny, there is a 60% chance that he will go outside for a walk.

You talk to your friend three days in a row and discover that on the first day he went for a walk, on the second day he went shopping, and on the third day he cleaned his apartment. You have two questions: What is the overall probability of this sequence of observations? And what is the most likely sequence of rainy/sunny days that would explain these observations? The first question is answered by the '''forward algorithm'''; the second by the Viterbi algorithm. These two algorithm are structurally so similar (in fact, they are both instances of the same abstract algorithm) that they can be implemented in a single function:

def forward_viterbi(y, X, sp, tp, ep):