How to uncover hidden truths from a sequence of noisy, observable data points
In short: We often see the effects of events without witnessing the events themselves. The Viterbi algorithm is a mathematical powerhouse that reconstructs the most likely sequence of hidden causes behind observed symptoms. From decoding deep-space signals to diagnosing patients, it turns messy, incomplete data into a clear, probable narrative.
Proposed by Andrew Viterbi in 1967, this dynamic programming method was originally designed to decode convolutional codes in noisy digital communications. While it bears his name, the concept is a classic example of multiple discovery, having been independently developed by at least seven different researchers, including teams like Needleman and Wunsch, and Wagner and Fischer. Today, it is a standard tool for solving maximization problems where we must infer a hidden state sequence from a series of observations.
The algorithm operates by breaking a complex problem into manageable subproblems. At each time step, it calculates the maximum probability of arriving at a specific state, keeping track of the most likely path taken to reach that point. By the time it processes the final observation, it has effectively mapped out the most probable history of the system. This efficiency makes it indispensable in fields as diverse as speech recognition, where it maps acoustic signals to text, and bioinformatics, where it identifies patterns in biological sequences.
In practice, the algorithm is most frequently applied to hidden Markov models. Consider a doctor trying to determine if a patient has a fever based only on reported symptoms like feeling dizzy or cold. Because the health state is hidden, the doctor uses the Viterbi algorithm to calculate the most likely sequence of health conditions over several days. The computational complexity of this process is generally proportional to the length of the observation sequence multiplied by the square of the number of possible states, though it can be optimized further if many state transitions are impossible.
Beyond simple diagnostics, the algorithm underpins modern infrastructure. It is essential for decoding signals in CDMA and GSM cellular networks, satellite communications, and wireless LANs. Whether it is parsing natural language or tracking a target, the Viterbi algorithm provides a rigorous framework for finding the most likely explanation for what we observe, proving that even when the truth is hidden, it is often mathematically reachable.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Viterbi algorithm
To cite this card, link to https://intellectplus.co.uk/app/science-viterbi-algorithm.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Statistics and probability · More in Science · Latest · A–Z · All topics