Hidden Markov Model

A hidden Markov model applies the Bayesian-network idea to a world that changes. Variables are split into a state, which is true but unobservable, and evidence, which is observed and unreliable. Time is cut into fixed slices, and the model is assumed stationary, meaning the same two conditional distributions apply at every step. Russell and Norvig introduce it with a security guard who cannot see the weather and must infer whether it is raining from whether his director arrives carrying an umbrella.

The two assumptions are what make the model finite. The Markov assumption states that the current state depends on the entire history only through the immediately preceding state; the sensor Markov assumption states that the current observation depends only on the current state. Both are claims about whether the state variable has been chosen well rather than about the physical sensor. When the first fails, the usual repairs are to raise the order of the model or, better, to enlarge the state so that the missing dependence runs through a variable instead of through time.

Under those assumptions the joint distribution over a complete history factorises into a prior, one transition factor per step and one sensor factor per step. Every query is then answered by one of four tasks. Filtering computes the belief about the current state given all evidence so far, and is what a running agent maintains. Prediction extends that belief into the future, where in the absence of new evidence it relaxes toward the stationary distribution of the chain and eventually carries no information. Smoothing estimates an earlier state using evidence that arrived afterwards, by multiplying the forward message by a backward message that summarises the later observations. Running the forward pass once and then sweeping backward smooths an entire sequence in time linear in its length, the forward-backward algorithm.

The fourth task is different in kind. Asking for the single most likely sequence of states is not the same as asking for the most likely state at each step, because marginals sum over all paths through a state while a sequence is one path. Assembling per-step winners can therefore produce a history less probable than another, and the Viterbi algorithm exists to optimise over whole paths: it is the forward recursion with the sum over the previous state replaced by a maximum, plus a back-pointer at each step so that the winning path can be recovered and not merely its probability. When the state is continuous rather than discrete, the same predict-and-update cycle survives only for special families; the linear-Gaussian case gives the Kalman filter.

In the umbrella world the state is whether it rains, with P(rain today | rain yesterday) = 0.7 and P(rain today | dry yesterday) = 0.3, and the sensor is whether an umbrella appears, with P(umbrella | rain) = 0.9 and P(umbrella | dry) = 0.2. Starting from a uniform prior, one umbrella gives a filtered belief of ⟨0.818, 0.182⟩, and a second on the following day gives ⟨0.883, 0.117⟩.

Smoothing day 1 once day 2 has been seen raises it from 0.818 to 0.883, because the second umbrella makes rain on day 2 likelier and rain persists. The backward message that carries this is ⟨0.69, 0.41⟩, which does not sum to one because it is a likelihood rather than a distribution.

On the observations no umbrella, umbrella, no umbrella, the smoothed probability of rain on day 2 is 0.554, yet the most likely sequence is dry on all three days at 0.402 against 0.332 for the runner-up. The marginal collects its mass from four separate histories; the winning sequence concentrates its own into one.