Part-of-Speech Tagging Using the Viterbi Algorithm

Introduction to the Viterbi algorithm

The hidden Markov model (HMM) finds the likely part of speech for a given word. However, for a sentence, we need to generate the most likely sequence of part of speech tags instead of a single word. For this task, we can use the Viterbi algorithm, a dynamic programming algorithm developed for finding the most likely sequence of hidden states, or a Viterbi path. The Viterbi algorithm does this by systematically "crawling" over all of the possible states of our HMM for each step in our sequence of words and uses these calculations to find the maximal set of states.

The algorithm can be split into three steps:

• Initialization step

• Forward pass

• Backward pass