Herself’s Artificial Intelligence

These have been used in speech recognition, handwriting recognition and in many biotechnology projects.

Markov Chain: is a statistical technique that uses a weighted automaton, a weighted directed graph, in which the input sequence uniquely determines the path through the automaton to the output observed.

Hidden Markov Model: is a weighted automaton in which only one path is allowed per specific input. The Viterbi is the most commonly used algorithm for processing these models. Viterbi Algorithm traces through state graph multiplying the probabilities.

If the probability from the previous level is higher it back traces Example, for words: need (n-iy), neat (n-iy-t), new (n-uw), knee (n-iy)

Begin
n/1.0
iy/.64 uw/.36
t/.24 d/.315
End

Possible paths are:
new/n – uw => 1.0 .36 => .36
neat/n – iy – t => 1.0 .64 .24 => .128
need/n – iy – d => 1.0 .64 .445 => .178
knee/n – iy => 1.0 .64 .315 => .2016

The first loop checks n – uw1.0 .36 = .36 and n – iy1.0 .64 = .64 64 is a higher probability so we pursue that

Next pass gives us iy – t.64 .24 = .128
iy.64 .315 = .2016
iy – d.64 .445 = .178

But these are smaller than the .36 we collected as a high probability in the previous pass so we back track to that. If there were more levels through our graph we would continue this loop until reaching the end.

The probabilities are calculated as so: weight = -log[actualprobability] so if the probability of n – uwis.44 the graph weight is -log(.44) => .36

See also:
Simple example, Java source parsing and printing text using Markov models
Graphical models of knowledge representation

Papers:
An Efficient Hidden Markov Mobel for Offline Handwritten Numerical Recognition
Network as a computer: ranking paths to find flows ( pdf )
A spectral algorithm for learning hidden markov models