AI · Uncertain knowledge and reasoning

14 · Probabilistic Reasoning over Time

Temporal models combine state transitions with noisy observations. Add observations one at a time and see a hidden-state belief update by forward filtering.

Track hidden states through time

14.1 Time and Uncertainty

Temporal reasoning represents evolving state variables, transitions, and observations. A filtering system estimates the current state from evidence available so far.

14.2 Inference in Temporal Models

Filtering updates beliefs as each new observation arrives; prediction projects beliefs forward, and smoothing revises past-state estimates using later evidence.

14.3 Hidden Markov Models

An HMM has a Markov hidden state and observations conditionally independent given that state. The forward algorithm alternates transition prediction and emission reweighting.

14.4 Kalman Filters

For linear systems with Gaussian noise, Kalman filtering efficiently updates a continuous state estimate and its uncertainty.

14.5 Dynamic Bayesian Networks

Dynamic Bayesian networks describe dependencies within a time slice and across successive slices; compact repeated structure can model many variables over long sequences.

Key terms and one filter update

A hidden Markov model (HMM) has hidden state Xₜ, observation Eₜ, transition model P(Xₜ₊₁|Xₜ), and emission model P(Eₜ|Xₜ). The Markov assumption says the next state depends on the current state, not the full past; observations are conditionally independent given their states. Filtering estimates the current state from evidence so far; smoothing uses later evidence to revisit a past state.

With the initial Sunny/Rainy belief (0.5, 0.5), first predict Sunny = 0.5×0.8 + 0.5×0.3 = 0.55 and Rainy = 0.45. After observing an umbrella, weight these by likelihoods 0.1 and 0.8: (0.055, 0.36). Normalize by 0.415 to get Sunny ≈ 13.3%, Rainy ≈ 86.7%. Each update is valid because transition rows and observation likelihoods are probabilities.

Kalman filters are the continuous-state Gaussian counterpart for linear dynamics; DBNs generalize repeated temporal structure to multiple dependent variables. Neither is what this two-state discrete demo computes.

HMM forward filtering

Umbrella observations

Hidden weather is Sunny or Rainy. Transitions: P(Sunny′|Sunny)=.8 and P(Sunny′|Rainy)=.3. Umbrella likelihoods are .1 in sun and .8 in rain.

Sunny

Rainy

Each update first predicts with the transition model, then multiplies by the observation likelihood and normalizes. These are filtering beliefs, not smoothed past estimates.

Filtering complexity

Let K be the number of hidden states and T the number of observations. A dense HMM prediction sums over previous states for each next state, O(K²) per observation; likelihood weighting and normalization add O(K). Thus standard filtering takes O(T·K²) time and O(K) auxiliary memory when only the current belief vector is retained (O(T·K) if all belief vectors are saved).

This demo fixes K = 2, so the filtering arithmetic is O(1) per observation and O(T) across T observations, with O(1) belief-state workspace. The implementation also stores all observations (O(T)) and rebuilds their history list each time: UI rendering is O(T) per addition and O(T²) cumulatively, while its retained history/DOM uses O(T) memory. This distinction keeps visualization cost separate from the two-state filter itself. The model assumes a first-order Markov transition and the stated fixed transition/emission probabilities.