Hidden Markov Models (1970s) › The Three Fundamental Problems

The practical power of HMMs comes from their ability to solve three fundamental computational problems, each essential for different aspects of building working systems. Understanding these problems and their solutions reveals why HMMs became so influential in the development of language technology.

The first problem is evaluation. Given a complete HMM with known parameters and a sequence of observations, how do we compute the probability that this particular model generated those observations? This calculation lets you compare different models or interpretations. Suppose you have multiple candidate models for speech recognition, each representing a different possible word or phrase. The evaluation problem lets you score how well each model explains the acoustic signal you observed, allowing you to rank the candidates and select the most likely interpretation.

The second problem is decoding, and it's arguably the most important for practical applications. Given a sequence of observations, what is the most likely sequence of hidden states that produced them? In speech recognition, this is the core challenge: given acoustic features extracted from audio, find the most probable sequence of phonemes or words that were spoken. The Viterbi algorithm, developed for exactly this purpose, uses dynamic programming to efficiently find the optimal state sequence without having to enumerate every possible path through the hidden states. This transforms what would be an intractable combinatorial search into a practical computation.

The third problem is learning. Given a collection of observation sequences, how do we estimate the best parameters for an HMM? This is what allows us to train models from real data rather than hand-specifying every probability. The Baum-Welch algorithm, an instance of the more general expectation-maximization algorithm, provides an iterative method for adjusting transition and emission probabilities to better explain the training data. Starting from initial guesses, the algorithm alternates between computing expected state sequences given current parameters and updating parameters to better fit those expectations. Over many iterations, the model converges to a local optimum that captures statistical patterns in the data.

The beauty of HMMs lies in their ability to handle uncertainty gracefully throughout this process. They don't force you to commit to a single "correct" interpretation. Instead, they maintain probability distributions over all possibilities, allowing downstream systems to make informed decisions based on the full range of options weighted by their likelihoods. This probabilistic perspective would prove essential not just for HMMs but for virtually all statistical approaches to language that followed.