viterbi

The Viterbi algorithm is a dynamic programming algorithm to find optimal paths in the hidden space of an hidden Markov model. It has wide applications, including for Natural Language Processing tasks such as Part-of-Speech tagging. Problem and algorithm descriptions are given below.

Example

Compile and link example.cpp and viterbi.cpp, e.g.:

$ g++ example.cpp viterbi.cpp -o example
$ ./example

You will be prompted to insert the data defining the model, and the input path in observable space.

Problem

Let be an hidden Markov model, where:

• : hidden space of finite cardinality
• : observable space of finite cardinality
• : transition matrix
• : emission matrix
• : start probabilities

Given a path in observable space, find a corresponding path in hidden space maximizing the conditional probability or, equivalently, the joint probability

Algorithm

The Viterbi algorithm is a dynamic programming procedure to solve the problem above. It is based on the optimization subproblems:

which can be solved recursively. For more info and pseudocode, c.f. the Wikipedia article.