Sequential Probabilistic Models

A Markov chain is a sequence of random states X1, X2, X3, ... satisfying the Markov property: the distribution over the next state depends only on the current state, not on the full history that produced it. Formally, P(Xt+1 | Xt, Xt-1, ..., X1) = P(Xt+1 | Xt). This single assumption is what makes reasoning about long sequences tractable at all - it means the current state is a sufficient statistic for everything relevant about the past, and the chain's dynamics can be fully specified by an initial distribution over states plus a transition matrix giving P(Xt+1 = j | Xt = i) for every pair of states i and j. Repeatedly applying that transition matrix describes how a distribution over states evolves many steps into the future, and under mild conditions the chain settles toward a stationary distribution that no longer changes from one step to the next, regardless of where it started. A Markov chain by itself assumes the states are directly observed, which is often unrealistic: a system's true underlying condition is frequently hidden, and what is actually available are indirect, noisy measurements generated by that condition rather than the condition itself.

A hidden Markov model (HMM) adds exactly that layer of indirection. There is a Markov chain of hidden states, exactly as before, but at each time step the current hidden state stochastically generates an observation through an emission distribution, rather than the state itself being seen directly. Rabiner's widely used tutorial calls this a "doubly embedded stochastic process" and formalizes the HMM with three components: the state transition probabilities (matrix A, giving P(next state | current state)), the observation probability distributions per state (matrix or distribution set B, giving P(observation | current state)), and the initial state distribution (π, giving the probability of starting in each state). Together, A, B, and π fully specify the model, denoted λ, and Rabiner organizes everything a practitioner is asked to do with such a model around three canonical problems: evaluation (computing the probability P(observations | λ) of an observed sequence given the model), decoding (finding the single most likely hidden state sequence that produced the observations), and learning (estimating the model's parameters λ from observed data alone, without ever seeing the hidden states directly).

Each of these three problems has a specific algorithm built to solve it efficiently rather than by brute-force enumeration, which would require summing or maximizing over an exponential number of possible state sequences. The evaluation problem is solved by the forward algorithm (or the related forward-backward algorithm), a dynamic-programming recursion that tracks, for each state and time step, the total probability of all state-sequence paths ending there - reducing the computation from exponential to a cost proportional to the square of the number of states times the sequence length. The decoding problem is solved by the Viterbi algorithm, a closely related dynamic program that tracks the single best path rather than summing over all paths. The learning problem is solved by Baum-Welch re-estimation, an expectation-maximization procedure that alternates between inferring expected state occupancies given the current parameters and updating the parameters to better fit those expectations, provably increasing the data's likelihood at every iteration.

A hidden Markov model compresses everything about a system's hidden condition into a single state variable at each time step, which is often too coarse a representation for realistic domains where many distinct, partially independent aspects of the world change over time - a robot's position, orientation, and battery level, say, each evolving somewhat separately yet also interacting with one another. Dean and Kanazawa's early work on reasoning about persistence and causation over time laid groundwork for representing exactly this kind of structured temporal domain within a probabilistic framework, treating the question of which facts persist unchanged from one moment to the next, and which are caused to change by some other event, as itself a modeling problem to be represented probabilistically, rather than something to be hand-coded as a separate logical layer sitting outside the probability model entirely. Prior approaches to temporal reasoning in AI had often relied on non-probabilistic, logic-based formalisms for handling persistence (commonly discussed under the heading of the "frame problem" - how to represent, economically, that most facts stay the same from one time step to the next); framing persistence itself as a probabilistic quantity meant it could be learned from data and combined coherently with genuine uncertainty elsewhere in the model, rather than assumed by default.

A dynamic Bayesian network (DBN) generalizes this idea directly: it is a Bayesian network structure that repeats across discrete time slices, with two kinds of edges - intra-slice edges connecting variables within the same time step, exactly as in an ordinary Bayesian network, and inter-slice edges connecting a variable at time t to a variable at time t+1, encoding how the world's structured state evolves and what persists versus what changes from one slice to the next. Because this template is typically identical from one time slice to the next, a DBN can be specified compactly using just two time slices (commonly called a "two-time-slice Bayesian network," or 2TBN) together with a specification of the initial time slice, even though the compact template implicitly defines a network of unbounded length once unrolled over however many time steps the application actually requires. Any query about the modeled process - the probability of some future event, the most likely explanation for a sequence of past observations, or the current filtered belief given evidence so far - can then be answered by unrolling the template to the necessary length and applying the same general Bayesian-network inference machinery already established in this domain, rather than requiring an entirely new algorithm purpose-built for temporal reasoning.

Both the hidden Markov model and, as later material in this domain will show, the linear-Gaussian state-space model are special cases of this more general template: an HMM is a DBN with exactly one discrete hidden variable per time slice and no intra-slice structure, while a state-space model is a DBN whose hidden variables are continuous and whose transition and observation relationships are linear-Gaussian. The generality is genuinely useful for representing structured domains, but it is not free - inference in an unrolled DBN can be carried out by applying the same generic Bayesian-network inference machinery (variable elimination, junction trees) to the network sliced out to the required length, but the effective treewidth of that unrolled network, and therefore the cost of exact inference, typically grows with the number of variables tracked per time slice, motivating the approximate sequential methods introduced later in this domain. In practice, most DBN applications never perform exact inference over the entire unrolled history at once; instead they maintain only the current time slice's belief and discard earlier slices once they have been fully accounted for, an idea that reappears explicitly as filtering in the state-space and particle-filtering lessons that follow.

Many physical systems are more naturally described with continuous hidden state than with the discrete states of an HMM: a vehicle's true position and velocity, an aircraft's orientation, or a chemical process's concentration are all continuous quantities evolving over time and observed only through noisy sensors, never directly. A linear-Gaussian state-space model captures this with two equations: a transition equation xt = A·xt-1 + wt describing how the hidden state evolves under linear dynamics plus Gaussian process noise wt, and an observation equation zt = H·xt + vt describing how the (partially) observed measurement relates linearly to the hidden state plus Gaussian observation noise vt. This is the direct continuous analogue of a hidden Markov model's transition and emission structure: the matrix A plays the role the transition matrix plays in an HMM, and the matrix H plays the role the emission distribution plays, only now both the hidden state and the observation live in a continuous vector space rather than over a finite set of discrete symbols.

Kalman's 1960 paper gave a recursive, closed-form solution to exactly this filtering problem. Because Gaussian distributions are closed under the linear operations involved, the posterior over the hidden state at every time step remains exactly Gaussian, fully described by a mean vector and covariance matrix that the Kalman filter updates through a two-step predict/update cycle: a prediction step propagates the previous belief forward through the dynamics model, and an update step corrects that prediction using the new observation, weighted by the relative uncertainty of the prediction versus the measurement (the Kalman gain). This closed-form exactness plays the same structural role that the forward algorithm's alpha recursion plays for HMMs - both are predict/update recursions maintaining a filtered belief distribution over the current hidden state given all observations so far - but the Kalman filter's belief is a compact Gaussian rather than a table of state probabilities, which is what allows it to remain exact under linear-Gaussian assumptions rather than needing to enumerate discrete states.

That exactness is a genuine gift of the linear-Gaussian assumptions and does not survive when they are violated: once the dynamics or the observation model become meaningfully nonlinear, or the noise meaningfully non-Gaussian, the true posterior generally stops being Gaussian at all - it can become multimodal, skewed, or otherwise shaped in ways a single mean and covariance cannot capture - and the exact closed-form update breaks down along with it. Practical extensions - the extended Kalman filter, which linearizes a nonlinear model locally at each step before applying the ordinary Kalman update, and the unscented Kalman filter, which propagates a small deterministic set of representative points through the true nonlinear model and refits a Gaussian to the result - patch around this by approximation rather than by solving the nonlinear problem exactly, and both still assume the true posterior is reasonably well summarized by a single Gaussian shape. When those approximations are themselves inadequate, most often because the true posterior is genuinely multimodal, the field turns to fully sampling-based sequential methods, taken up as particle filtering in the next module, which represent the filtered belief with a weighted set of random samples rather than any fixed parametric family at all.