Viterbi Algorithm, Part 2: Decoding

This is my second post describing the Viterbi algorithm. As before, our presentation follows Jurafsky and Martin closely, merely filling in some details omitted in the text.

Viterbi Algorithm, Part 1: Likelihood

The Viterbi algorithm is used to find the most likely sequence of states given a sequence of observations emitted by those states and some details of transition and emission probabilities. It has applications in Natural Language Processing like part-of-speech tagging, in error correction codes, and more!

Minimum Edit Distance

Minimum Edit Distance is defined as the minimum number of edits (delete, insert, replace) needed to transform a source string to a target string. The algorithm uses dynamic programming both to calculate the minimum edit distance and to identify a corresponding sequence of edits.