Viterbi algorithm: Difference between revisions

Revision as of 05:11, 16 February 2022

Revision as of 10:18, 5 March 2022

Line 106:

== Example ==

Consider a village where all villagers are either healthy or have a fever, and only the village doctor can determine whether each has a fever. The doctor diagnoses fever by asking patients how they feel. The villagers may only answer that they feel normal, dizzy, or cold.

The doctor believes that the health condition of histhe patients operates as a discrete [[Markov chain]]. There are two states, "Healthy" and "Fever", but the doctor cannot observe them directly; they are ''hidden'' from himthe doctor. On each day, there is a certain chance that thea patient will tell the doctor he"I isfeel "normal", "I feel cold", or "I feel dizzy", depending on histhe patient's health condition.

The ''observations'' (normal, cold, dizzy) along with a ''hidden'' state (healthy, fever) form a hidden Markov model (HMM), and can be represented as follows in the [[Python (programming language)|Python programming language]]:

Line 124:

}

</syntaxhighlight>

In this piece of code, <code>start_p</code> represents the doctor's belief about which state the HMM is in when the patient first visits (all hethe doctor knows is that the patient tends to be healthy). The particular probability distribution used here is not the equilibrium one, which is (given the transition probabilities) approximately <code>{'Healthy': 0.57, 'Fever': 0.43}</code>. The <code>transition_p</code> represents the change of the health condition in the underlying Markov chain. In this example, therea patient who is healthy today has only a 30% chance that tomorrow the patient willof havehaving a fever if he is healthy todaytomorrow. The <code>emit_p</code> represents how likely each possible observation, (normal, cold, or dizzy) is, given theirthe underlying condition, (healthy or fever). If theA patient who is healthy, there ishas a 50% chance that heof feelsfeeling normal; ifone hewho has a fever, there ishas a 60% chance that heof feelsfeeling dizzy.

[[File:An example of HMM.png|thumb|center|300px|Graphical representation of the given HMM]]

TheA patient visits three days in a row, and the doctor discovers that the patient feels normal on the first day, he feels normal,cold on the second day, heand feels cold,dizzy on the third day he feels dizzy. The doctor has a question: what is the most likely sequence of health conditions of the patient that would explain these observations? This is answered by the Viterbi algorithm.

<syntaxhighlight lang="python" line="1">

Line 200:

</syntaxhighlight>

This reveals that the observations <code>['normal', 'cold', 'dizzy']</code> were most likely generated by states <code>['Healthy', 'Healthy', 'Fever']</code>. In other words, given the observed activities, the patient was most likely to have been healthy both on the first day whenand he felt normal as well asalso on the second day when(despite he feltfeeling cold that day), and thenonly heto have contracted a fever on the third day.

The operation of Viterbi's algorithm can be visualized by means of a