Addressing Viterbi Algorithm challenges

3 min readMar 10, 2021

Part2: Viterbi decoding algorithm for POS tagging

In the last blog I discussed about how you can implement The Viterbi algorithm from scratch that can be used for decoding, finding the most likely tag sequence. Today we will identify some of the challenges and try to address them. Let’s go through the algorithm as well:

1. Underflow and Overflow

Except for rather short sequences in which n is relatively small, say, a couple hundred or so, the algorithm above will fail due to the fact that we are trying to represent numbers that are too small (or too large) for the computer to handle. And what’s worse, you will usually receive no warning or error that something has gone wrong. Basically, the issue is that (in most programming languages), there is a limit on how small (or large) of a number can be represented. (For example, in a couple of languages that I use, the lower limit seems to be around 10−323, and the upper limit around 10308.) Anything smaller (or larger) than this will be considered to be exactly zero (or infinity). This is referred to as “arithmetic underflow” (or “arithmetic overflow”)

The standard solution to this problem is to work with logs. This is a trick that works in a lot of other problems as well.
•Denote l= log p, e.g., l(z1) = log p(z1), l(zt |zt−1) = log p(zt |zt−1), and l(xt |zt) = log p(xt |zt).

2. Dealing with unknown words:

If o is not in the training text then bi(ot) = 0. Despite of course being a very bad estimate of the true probability, zero-probabilities like this will also result in that all possible state-sequences for an observation sequence containing an unknown word will have probability 0.Here I used maximum-entropy classifier to predict the emission probabilities for the unknown words.

regex_pattern = [
(r’^[aA-zZ].*[0–9]+’), #word contains a number

(r’^[A-Z]+’), #word contains an upper-case letter

(r’[aA-zZ]+(ed|ing|es)$’), #word ending with ‘ing’ or ‘ed’

(r’^[A-Z]{2,}+’), #word is all upper-case

(r’.*s$’), # plural nouns

(r’.[aA-zZ]+(ment|tion|ness|ism|ance)$’), (r’.*\’s$’),# possessive nouns — words ending with ‘s

(r’.[aA-zZ]+(able|ible|est|ful)$’), #Adjective — ends with able, ible, est, ful

(r’.[aA-zZ]+(ly|er)$’) #Adverb — ends with er,ly ]