Viterbi Algorithm (1967) › Applications: From Communication to Language Processing

The earliest application of the Viterbi algorithm was in decoding convolutional codes for error correction in digital communication. When transmitting data over noisy channels (radio links, phone lines, storage media), convolutional codes add redundant information that allows the receiver to detect and correct errors. The decoder must determine the most likely transmitted sequence given the noisy received sequence.exactly the problem the Viterbi algorithm solves. By the 1970s, Viterbi decoding had become standard in satellite communication, modems, and digital cellular systems.

Speech recognition became the algorithm's main language application. In the 1970s and 1980s, as Hidden Markov Models became the dominant framework for speech recognition, the Viterbi algorithm became the standard method for decoding acoustic observations into word sequences. Every major speech recognition system used it: IBM's Tangora system, Dragon Systems' NaturallySpeaking, and the research systems that preceded them all relied on Viterbi decoding.

The algorithm worked as follows: acoustic features extracted from speech audio were treated as observations. The HMM had states representing phonemes or sub-phonetic units, with transitions modeling how sounds follow each other in the language and emissions modeling the acoustic features associated with each sound. Given a sequence of acoustic features, the Viterbi algorithm found the most likely sequence of phonemes, which could then be mapped to words using a pronunciation dictionary and language model.

Part-of-speech tagging emerged as another major application. Given a sequence of words, a part-of-speech tagger assigns each word its grammatical category (noun, verb, adjective, etc.). HMM taggers modeled words as observations and grammatical categories as hidden states. Transition probabilities captured how grammatical categories follow each other in valid sentences (verbs often follow nouns, determiners precede nouns, etc.), while emission probabilities captured how likely each word is given each grammatical category. The Viterbi algorithm found the most likely sequence of tags, resolving ambiguous cases like whether "bank" is a noun or verb based on surrounding context.

Named entity recognition systems used similar approaches. Given a sentence, the task is to identify which words form named entities (people, organizations, locations) and classify them. Systems modeled this using sequence labeling, where each word is assigned a label like B-PERSON (beginning of person name), I-PERSON (inside person name), or O (outside any entity). HMMs with Viterbi decoding provided early solutions to this problem, though they were later largely replaced by more sophisticated sequence labeling methods.

Machine translation systems in the 1990s and early 2000s used the Viterbi algorithm in various ways. Some phrase-based translation systems used it to find the best sequence of phrase translations. Statistical alignment models used it to find the most likely word alignment between source and target sentences. Even when neural translation systems later replaced these approaches, the conceptual framework of finding optimal sequences persisted.