On this page
In 1967, the engineer Andrew Viterbi published a way to decode digital messages sent over noisy radio channels. His method, now known as the Viterbi algorithm, became a cornerstone of modern communications, used in everything from satellite links to mobile networks.
But the mathematics of decoding a noisy transmission turned out to be universal. The same algorithm that cleans up a digital signal is now used in education to solve a very human problem: working out exactly when you understand a new concept.
What is the history of the Viterbi algorithm?
Andrew Viterbi introduced his method in an April 1967 paper in the *IEEE Transactions on Information Theory*. He originally designed it as an optimal decoding algorithm for convolutional codes—a way to package data so that errors caused by static or interference can be corrected at the receiving end, building on earlier discoveries like those of Richard Hamming and the codes that fix their own errors.
The challenge in 1967 was that decoding these signals took too much computing power; the number of possible messages grew exponentially with the length of the transmission. Viterbi's breakthrough was using dynamic programming. Instead of checking every possible message, his algorithm only keeps the most probable path to each state at every step. This cut the complexity down to a linear scale, making real-time decoding possible.
How does the Viterbi algorithm work?
The algorithm is the standard way to decode a Hidden Markov Model (HMM), a statistical tool built on the rules of Andrey Markov and the chains that link random events.
In an HMM, a system moves through a series of "hidden states" that you cannot see directly. Instead, you only see "observations" that leak out of the system. Because the system is noisy, a single observation does not tell you the exact state. The Viterbi algorithm looks at the entire sequence of observations and computes the single most likely path of hidden states that could have produced them. It reconstructs the hidden truth from the noisy evidence.
A worked example of the Viterbi path
In the 1990s, researchers realised that a student learning a new skill behaves exactly like a Hidden Markov Model.
When you sit down to solve a problem, your understanding is a hidden state. A teacher cannot look inside your head to see if a concept is "Unlearned" or "Mastered". The only things they observe are your answers. But answers are a noisy signal. A student who has mastered a skill might make a careless slip and get the answer wrong. A student who has not learned it might guess correctly. In 1995, Albert Corbett and John Anderson published the framework for Bayesian Knowledge Tracing, which models this exact process.
Imagine you are solving four physics problems. The system tracks your answers and wants to know when you learned the concept. It uses four probabilities:
Initial knowledge: The chance you already knew it before starting.
Learning rate: The chance you learn it after a practice attempt.
Guess rate: The chance of getting it right without knowing it.
Slip rate: The chance of making a careless mistake despite knowing it.
Suppose your answers are: Incorrect, Incorrect, Correct, Correct.
To find the hidden sequence of your mind, the Viterbi algorithm calculates the probability of every possible path through the "Unlearned" and "Mastered" states.
Path 1 (Never learned): Unlearned → Unlearned → Unlearned → Unlearned. For this to be true, the two correct answers at the end would both have to be lucky guesses.
Path 2 (Learned instantly): Mastered → Mastered → Mastered → Mastered. For this to be true, the two incorrect answers at the start would both have to be careless slips.
Path 3 (Learned halfway): Unlearned → Unlearned → Mastered → Mastered. Here, you didn't know it, got two wrong, then learned the rule, and got the next two right without slipping.
The algorithm multiplies the probabilities along each branch. Because two slips or two guesses in a row are statistically unlikely, Path 3 emerges as the "Viterbi path"—the single most mathematically probable sequence. The system records that mastery occurred exactly at question three.
How do AI tutors use Hidden Markov Models?
By applying the Viterbi algorithm to a history of correct and incorrect answers, an educational system can trace this path continuously. It pinpoints the exact moment the hidden state flipped from "Unlearned" to "Mastered".
This is the engine behind modern adaptive learning. When Fermi's AI tutor watches you work, it does not just count your right and wrong answers. It works out what you already know and builds a plan for the session.
A mathematical trick designed to hear whispers from deep space is now the tool that listens to how we learn.
