Reasoning About a Changing World

A Bayesian network describes a world that holds still. Most worlds do not. You watch a patient, a market, or a road through sensors that are noisy and intermittent, and the thing you care about keeps moving while you look at it. This article is about the machinery for that, and about one place where the obvious approach quietly gives the wrong answer.

A. Two assumptions

Split the variables into state $\mathbf{X}_t$, which is true but hidden, and evidence $\mathbf{E}_t$, which you observe. The difficulty is that $P(\mathbf{X}_t \mid \mathbf{X}_{0:t-1})$ has a parent set that grows forever. Two assumptions bound it.

The Markov assumption says the current state depends on the history only through the previous state, $\mathbf{P}(\mathbf{X}_t \mid \mathbf{X}_{0:t-1}) = \mathbf{P}(\mathbf{X}_t \mid \mathbf{X}_{t-1})$. The sensor Markov assumption says the current reading depends only on the current state. Both are claims about whether the state variable is well chosen, not about hardware: if yesterday's reading still informs today's once today's state is known, the state is missing something, and the repair is to enrich it.

Russell and Norvig's example is a security guard underground who wants to know whether it is raining, and whose only clue is whether the director arrives with an umbrella:

$$\begin{array}{ll} P(R_0) = \langle 0.5,\ 0.5 \rangle & \\[4pt] P(r_t \mid r_{t-1}) = 0.7 & P(r_t \mid \lnot r_{t-1}) = 0.3 \\[4pt] P(u_t \mid r_t) = 0.9 & P(u_t \mid \lnot r_t) = 0.2 \end{array}$$

Rain persists, and the umbrella is a decent but imperfect proxy. With the two assumptions in place the joint over a whole history factorises into a prior, a transition model and a sensor model:

$$P(\mathbf{X}_{0:t}, \mathbf{E}_{1:t}) = P(\mathbf{X}_0) \prod_{i=1}^{t} P(\mathbf{X}_i \mid \mathbf{X}_{i-1})\, P(\mathbf{E}_i \mid \mathbf{X}_i).$$

Three small factors now describe a history of any length. Every question has an answer - sum the histories that agree with it - and that answer costs $2^t$, which is why the rest of this article exists.

B. Filtering, prediction, smoothing

Filtering maintains a belief about now. It is one recursion, run as predict then update: push the belief through the transition model, then multiply by the likelihood of the new observation and normalise. The belief is a fixed-size vector, so an agent can run this forever.

On day 1 the umbrella appears. The symmetric transition model leaves the uniform prior at $\langle 0.5, 0.5 \rangle$, and the update gives

$$\mathbf{P}(R_1 \mid u_1) = \alpha \langle 0.9, 0.2 \rangle \langle 0.5, 0.5 \rangle = \alpha \langle 0.45, 0.10 \rangle = \langle 0.818,\ 0.182 \rangle .$$

On day 2 the prediction drops to $\langle 0.627, 0.373 \rangle$ - a step into the future costs certainty on this chain - and a second umbrella lifts it to $\langle 0.883, 0.117 \rangle$.

Prediction is the same recursion without the update. Keep going with no further umbrellas and the belief decays $0.818 \to 0.627 \to 0.551 \to 0.520 \to \cdots \to 0.5$, relaxing to the chain's stationary distribution. That is not numerical decay; it is the model being honest. Evidence is the only thing holding a belief away from that fixed point, so every predictor has a horizon past which it says nothing.

Smoothing improves an earlier estimate with later evidence, by splitting the evidence at the time of interest and running a second recursion backward. For day 1 the backward message is

$$\mathbf{P}(u_2 \mid R_1) = (0.9 \times \langle 0.7, 0.3 \rangle) + (0.2 \times \langle 0.3, 0.7 \rangle) = \langle 0.69,\ 0.41 \rangle,$$

and combining it with the forward message raises day 1 from $0.818$ to $\langle 0.883, 0.117 \rangle$. Hindsight genuinely helps: the day-2 umbrella makes rain on day 2 likelier, and because rain persists that reflects backward. Note that $\langle 0.69, 0.41 \rangle$ does not sum to one, and should not - it is a likelihood, not a distribution. Caching the forward pass and sweeping back smooths an entire sequence in $O(t)$, which is the forward-backward algorithm.

Below, each day is two bars rather than one: the belief after the predict step, then the belief after the update step. The claim that, in this model, one half costs certainty and the other buys it back is a shape in that picture, not a sentence to take on trust. Push the horizon slider to watch an evidence-free week relax to the stationary distribution, and run the backward pass to see day 1 rise from 0.818 to 0.883 because of an umbrella it had not yet seen.

C. The most likely sequence is a different question

Smoothing answers "was it raining on day 2?". Asking "what happened?" is not the same question at finer grain, and the natural shortcut - smooth every step, take the winner at each - is wrong.

Take the three-day observation sequence no umbrella, umbrella, no umbrella. Only eight histories exist, so list them:

$$\begin{array}{lll} \text{dry, dry, dry} & 0.0314 & 40.2\% \\ \text{dry, rain, dry} & 0.0259 & 33.2\% \\ \text{rain, rain, dry} & 0.0076 & 9.7\% \\ \text{dry, rain, rain} & 0.0076 & 9.7\% \\ \text{rain, rain, rain} & 0.0022 & 2.8\% \\ \text{others} & & 4.4\% \end{array}$$

Smoothing day 2 sums every history in which it rained: $0.332 + 0.097 + 0.097 + 0.028 = 0.554$, so day 2 on its own is more likely wet than dry. But the most likely sequence is dry, dry, dry. Both are correct. Rain on day 2 collects its $0.554$ from four separate histories, none of them individually strong, while the all-dry explanation concentrates $40.2\%$ into one. Marginals sum over paths; the best path does not.

The fix is the Viterbi recursion, which is filtering with one change - the sum over the previous state becomes a maximum:

$$\mathbf{m}_{1:t+1} = \mathbf{P}(\mathbf{e}_{t+1} \mid \mathbf{X}_{t+1}) \max_{x_t} \Big( \mathbf{P}(\mathbf{X}_{t+1} \mid x_t)\, m_{1:t}(x_t) \Big),$$

plus a back-pointer at each step recording which predecessor won, since the message gives the probability of the best path and not the path itself. On the five-day sequence umbrella, umbrella, no umbrella, umbrella, umbrella it returns rain, rain, dry, rain, rain: one missing umbrella breaks a run of rain, but not for longer than a day, because the transition model makes an isolated dry day cheaper than a lasting change of regime.

D. When the state is a real number

Track a position rather than a coin flip and the belief is a density, prediction becomes an integral with no closed form, and the shape of the belief can change at every step. One family escapes: assume linear models with Gaussian noise and both steps stay Gaussian, because pushing a Gaussian through a linear map and adding noise gives a Gaussian, and a product of Gaussians is Gaussian. The belief is then always described by a mean and a variance, however long the filter runs.

For a random walk the update is

$$\mu_{t+1} = \frac{(\sigma_t^2 + \sigma_x^2) z_{t+1} + \sigma_z^2 \mu_t}{\sigma_t^2 + \sigma_x^2 + \sigma_z^2}, \qquad \sigma_{t+1}^2 = \frac{(\sigma_t^2 + \sigma_x^2)\sigma_z^2}{\sigma_t^2 + \sigma_x^2 + \sigma_z^2},$$

a weighted average in which the less uncertain of prediction and observation gets more say. With $\mu_0 = 0$, $\sigma_0 = 1$, $\sigma_x = 2$, $\sigma_z = 1$ and $z_1 = 2.5$, the posterior is $\mu_1 = 2.083$ with $\sigma_1^2 = 0.833$. The mean falls short of the observation because the prediction still holds weight, and the variance ends up below both inputs, which is the point of filtering at all.

The variance update never mentions the observation. So the whole sequence of variances, and with it the Kalman gain, can be computed before any data arrives; here it converges to $\sigma^2 \approx 0.828$ and a constant gain of about $0.828$. A settled variance means the filter has learned what the noise allows, not that it has stopped: the mean keeps moving.

Where this leaves you

Two assumptions turn an unbounded history into two small tables. One forward recursion answers what is true now, the same recursion without evidence predicts until it dissolves into the stationary distribution, and a backward pass buys hindsight. The most likely history needs its own algorithm, and the reason is worth remembering whenever you are tempted to assemble an answer out of per-item winners. The training path Probabilistic Reasoning over Time works every one of these by hand and in code.