Hidden Markov Models: States, Observations and Viterbi

A chain of states you cannot see

An ordinary Markov chain moves between states you can watch directly, and the transition probabilities alone tell the whole story. A hidden Markov model adds a layer of indirection: the states still exist and still transition according to a matrix of probabilities, but you never observe them. At every time step the current hidden state emits a visible observation, drawn from a per-state emission distribution, and that observation is all you get to see. Weather is the classic toy example - you cannot directly see whether the underlying regime is sunny or rainy, only whether a person carried an umbrella that day, and umbrellas are only a noisy clue.

Three questions, three algorithms

A model is fully specified by three pieces: the transition matrix between hidden states, the emission distribution for each state, and the initial state distribution. Given that model, three canonical questions each have a dedicated dynamic-programming algorithm. Evaluation - how likely is this observation sequence under the model? - is answered by the forward algorithm. Decoding - what is the single most likely hidden state sequence that produced these observations? - is answered by the Viterbi algorithm. Learning - given only observations, what are the model's parameters? - is answered by Baum-Welch, an expectation-maximisation procedure.

The forward algorithm

Computing the total probability of an observation sequence by brute force means summing over every possible hidden state sequence, which grows exponentially with time. The forward algorithm avoids this by building a table alpha, where alpha at time t and state i is the probability of being in state i at time t having produced all observations up to t. Each column depends only on the previous column, so the whole table fills in O(states squared times time steps) instead of exponential time - the same trellis structure that makes the Viterbi algorithm below tractable too.

Viterbi: sum becomes max

Viterbi solves a different question over the identical trellis: instead of the total probability, it wants the single best path. Every sum in the forward recursion is replaced with a maximum, and at each cell the algorithm additionally records a backpointer to whichever previous state produced that maximum. Once the table is filled, tracing the backpointers from the highest-probability final state back to time zero reconstructs the most likely hidden state sequence in one pass.

delta[0][i] = initial[i] * emit[i][obs[0]];
for (let t = 1; t < T; t++)
  for (let i = 0; i < N; i++) {
    let best = -Infinity, arg = -1;
    for (let j = 0; j < N; j++) {
      const score = delta[t-1][j] * trans[j][i];
      if (score > best) { best = score; arg = j; }   // max, not sum
    }
    delta[t][i] = best * emit[i][obs[t]];
    backptr[t][i] = arg;
  }
// trace backptr from argmax(delta[T-1]) back to t=0 for the best state path

Where hidden Markov models show up

Speech recognition systems long used HMMs with phonemes as hidden states and acoustic features as observations. Bioinformatics uses them to find genes, aligning a sequence of DNA bases against hidden states such as exon and intron. Part-of-speech tagging treats grammatical categories as hidden states emitting the words of a sentence. In every case the shared structure is the same: a chain of states you cannot see, generating a chain of things you can, and Viterbi decoding is what turns the visible chain back into a best guess at the hidden one.

Frequently asked questions

Try it live

Everything above runs in your browser - open Hidden Markov Model and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.