---
title: "Reasoning over Time: Tracking and Data Association"
module: Uncertainty
moduleNumber: 4
lessonNumber: 6
order: 406
summary: >
  Dynamic Bayesian networks generalize HMMs and Kalman filters to arbitrarily many
  state variables per slice, and when exact inference blows up, particle filtering
  approximates the belief state with a population of weighted samples that propagate,
  reweight, and resample. Tracking several objects at once adds the data-association
  problem — which observation came from which object — whose combinatorics defeat any
  exact filter, so particle filters and MCMC keep many hypotheses alive. We close with
  SLAM and learned state-space models.
topics: [Uncertainty]
sources:
  - book: AIMA
    ref: "Ch. 15 — Probabilistic Reasoning over Time; §15.5 Dynamic Bayesian Networks"
  - book: AIMA
    ref: "§15.6 Keeping Track of Many Objects"
---

This builds on [Probabilistic Reasoning over Time](/artificial-intelligence/uncertainty/reasoning-over-time),
which set up temporal models, the four inference tasks, hidden Markov models, and the
Kalman filter for continuous linear-Gaussian state. That last one broke down when the
true belief was genuinely non-Gaussian — several distinct possibilities a single
Gaussian bump cannot hold. The general fix is a richer temporal network and a sampling
filter that can represent any belief at all.

## Dynamic Bayesian networks and particle filtering

A **dynamic Bayesian network** (DBN) is a Bayesian network that represents a
temporal model with _arbitrarily many_ state variables per slice, the links
replicated from slice to slice. HMMs and Kalman filters are both special cases: any
HMM is a DBN with one discrete state variable, and any Kalman filter is a DBN with
continuous linear-Gaussian variables. The reason to prefer a DBN over the
equivalent HMM is **sparseness**. A DBN with 20 boolean state variables, each with
three parents in the previous slice, has a transition model of $20 \times 2^3 = 160$
probabilities; the equivalent HMM has one megavariable with $2^{20}$ states and a
transition matrix of $2^{40}$ — a trillion — entries. Factoring the state helps the
same way it does in a static network.[^dbn]

> **Definition (Dynamic Bayesian network).** A Bayesian network representing a
> stationary first-order temporal model: state variables $X_t$ and evidence
> variables $E_t$ per slice, with each variable's parents drawn from its own slice
> or the immediately preceding one, and the topology repeated across all slices.

Exact inference in a DBN can proceed by **unrolling** — replicating slices until
the network spans the observations, then running any Bayes-net inference algorithm.
But naive unrolling costs $O(t)$ space, growing without bound. Running variable
elimination in temporal order recovers the constant-space recursive update, keeping
only two slices in memory at a time. The catch: as elimination proceeds the factors
grow to include every state variable with a parent in the previous slice, so the
per-step cost is exponential in the number of state variables. Even a DBN we can
_write down_ compactly we generally cannot reason about exactly — the forward
message over many variables does not factor. We fall back on approximation.

The method of choice is **particle filtering**. Represent the belief state not by a
formula but by a population of $N$ samples — **particles** — scattered across the
state space in proportion to the posterior. Each update cycle is three steps that
mirror the filter's predict / update / resample:

1. **Propagate.** Move each particle forward by sampling the next state from the
   transition model $P(X_{t+1} \mid x_t)$.
2. **Weight.** Weight each particle by the likelihood it assigns the new evidence,
   $P(e_{t+1} \mid x_{t+1})$.
3. **Resample.** Draw $N$ new particles from the current population with
   probability proportional to weight, then discard the weights.

```algorithm
caption: $\textsc{Particle-Filtering}$ — approximate filtering by a sample population
input: new evidence $e$, sample count $N$, DBN (prior, transition, sensor)
persistent: $S$, a population of $N$ samples, initially drawn from $P(X_0)$
for $i = 1$ to $N$ do
  $S[i] \gets$ sample from $P(X_1 \mid X_0 = S[i])$ // propagate
  $W[i] \gets P(e \mid X_1 = S[i])$ // weight by the observation
$S \gets \textsc{Weighted-Sample-With-Replacement}(N, S, W)$ // resample
return $S$
```

The propagate step alone would drift: the particles wander by the transition model
with no pull from the evidence, and the fraction landing near reality decays
exponentially with the sequence length. Resampling is the fix — it culls
low-weight particles and clones high-weight ones, concentrating the population on
the high-probability regions of the state space that the observations single out.

$$
% caption: One particle-filtering cycle for the umbrella DBN with $N=10$ samples.
% Propagate moves each particle through the transition model; weight scales it by
% the observation likelihood (shown by dot size); resample draws a fresh
% population favoring the heavy particles.
\begin{tikzpicture}[>=stealth, font=\small,
  bx/.style={draw, minimum width=15mm, minimum height=9mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  % row labels
  \node[font=\scriptsize, anchor=east] at (-0.2,0.9) {rain};
  \node[font=\scriptsize, anchor=east] at (-0.2,-0.5) {no rain};
  % stage 1: propagate
  \node[bx] (p1t) at (0.9,0.9) {};
  \node[bx] (p1f) at (0.9,-0.5) {};
  \foreach \x/\y in {0.55/1.1, 0.85/1.1, 1.15/1.1, 0.55/0.75, 0.85/0.75, 1.15/0.75, 0.7/0.95, 1.0/0.95}
    \fill[acc] (\x,\y) circle (1pt);
  \foreach \x/\y in {0.75/-0.35, 1.05/-0.6}
    \fill[acc] (\x,\y) circle (1pt);
  \node[font=\scriptsize, anchor=north] at (0.9,-1.1) {propagate};
  % stage 2: weight (dot size varies)
  \node[bx] (w1t) at (3.3,0.9) {};
  \node[bx] (w1f) at (3.3,-0.5) {};
  \foreach \x/\y/\r in {3.0/1.05/1.6, 3.3/1.05/1.6, 3.6/1.05/1.6, 3.0/0.75/1.6, 3.3/0.75/1.6, 3.6/0.75/1.6}
    \fill[acc] (\x,\y) circle (\r pt);
  \foreach \x/\y/\r in {3.2/-0.4/0.6, 3.45/-0.6/0.6}
    \fill[acc] (\x,\y) circle (\r pt);
  \node[font=\scriptsize, anchor=north] at (3.3,-1.1) {weight};
  % stage 3: resample
  \node[bx] (r1t) at (5.7,0.9) {};
  \node[bx] (r1f) at (5.7,-0.5) {};
  \foreach \x/\y in {5.5/1.1, 5.7/1.1, 5.9/1.1, 5.45/0.9, 5.7/0.9, 5.95/0.9, 5.5/0.72, 5.9/0.72}
    \fill[acc] (\x,\y) circle (1pt);
  \foreach \x/\y in {5.6/-0.5, 5.85/-0.5}
    \fill[acc] (\x,\y) circle (1pt);
  \node[font=\scriptsize, anchor=north] at (5.7,-1.1) {resample};
  \draw[->, acc, thick] (1.75,0.2) -- (2.45,0.2);
  \draw[->, acc, thick] (4.15,0.2) -- (4.85,0.2);
\end{tikzpicture}
$$

Particle filtering is **consistent** — as $N \to \infty$ the sample proportions
converge to the true posterior — and in practice seems to stay accurate with a
_fixed_ $N$. It has grown into the general-purpose approximate filter
for DBNs, from tracking motion in video to fault diagnosis on rovers.

The same machinery extends to the hardest case, tracking _several_ objects at
once, where uncertainty about which observation came from which object — the **data
association** problem — multiplies the hypotheses combinatorially. There, too,
particle filtering and Markov-chain Monte Carlo are the practical methods, maintaining a
population of association hypotheses rather than committing to one.

## Keeping track of many objects: data association

Every filter so far tracked a _single_ object: one weather, one robot, one aircraft.
The moment two or more objects generate the observations, a new difficulty appears
that has nothing to do with noise or dynamics. When the radar sweep returns two
blips, _which blip is which aircraft?_ The observations arrive unlabelled, and
assigning each observation to the object that produced it is the **data
association** problem — the temporal face of the identity uncertainty met in
first-order probability models.[^data]

The problem was first studied in radar tracking, where a rotating antenna reports
blips at fixed intervals with no record of which blip at time $t$ continues which
blip at $t-1$. Suppose exactly two aircraft $A$ and $B$, each moving independently
under a known linear-Gaussian transition model, produce two blips per sweep. The
blips at time $t$ are $e^1_t$ and $e^2_t$, but the labels $1$ and $2$ are assigned
arbitrarily and carry no information — that arbitrariness is the problem.

$$
% caption: Observations of two objects over several time steps, each labelled with
% its step but not its source. The dashed lines show two of the possible track
% hypotheses: the observations could continue as two roughly straight paths, or
% cross over, and nothing in the data alone decides between them.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % observation dots (two per time step); step index labelled once, along the top
  \fill[black] (0,0.6) circle (2pt);
  \fill[black] (0,2.4) circle (2pt);
  \fill[black] (1.8,0.9) circle (2pt);
  \fill[black] (1.8,2.1) circle (2pt);
  \fill[black] (3.6,1.2) circle (2pt);
  \fill[black] (3.6,1.8) circle (2pt);
  \fill[black] (5.4,1.5) circle (2pt);
  \fill[black] (5.4,2.4) circle (2pt);
  % step indices along the top axis, clear of the tracks
  \foreach \x/\s in {0/1, 1.8/2, 3.6/3, 5.4/4}
    \node[font=\scriptsize, text=black] at (\x,3.1) {\s};
  \node[font=\scriptsize, text=black, anchor=east] at (-0.4,3.1) {step:};
  % hypothesis 1 (blue): parallel tracks
  \draw[acc, thick] (0,2.4) -- (1.8,2.1) -- (3.6,1.8) -- (5.4,1.5);
  \draw[acc, thick] (0,0.6) -- (1.8,0.9) -- (3.6,1.2) -- (5.4,2.4);
  % hypothesis 2 (red dashed): crossing
  \draw[red, densely dashed, thick] (0,2.4) -- (1.8,2.1) -- (3.6,1.2) -- (5.4,1.5);
  \node[acc, anchor=west, font=\scriptsize] at (5.6,1.5) {track A?};
  \node[red, anchor=west, font=\scriptsize] at (5.6,2.4) {or track A?};
\end{tikzpicture}
$$

Write the joint over both trajectories and all observations. It factors, as usual,
into a product over time steps of transition and observation terms:

$$
P(x^A_{0:t}, x^B_{0:t}, e^1_{1:t}, e^2_{1:t}) = P(x^A_0)\,P(x^B_0) \prod_{i=1}^{t}
P(x^A_i \mid x^A_{i-1})\, P(x^B_i \mid x^B_{i-1})\, P(e^1_i, e^2_i \mid x^A_i, x^B_i).
$$

We would like to split the observation term $P(e^1_i, e^2_i \mid x^A_i, x^B_i)$ into
one factor per object, but that split requires knowing which observation each object
generated. Introduce the missing information explicitly: let $\omega_t$ be the
one-to-one mapping from objects to observations at time $t$, so $\omega_t(A)$ is the
observation (either $1$ or $2$) assigned to $A$. For $n$ objects $\omega_t$ has $n!$
values; its prior is uniform and independent of the states, since the labels are
arbitrary. Conditioning on $\omega_t$ and summing it out,

$$
P(e^1_i, e^2_i \mid x^A_i, x^B_i)
= \frac{1}{n!} \sum_{\omega_i}
P\!\left(e^{\omega_i(A)}_i \mid x^A_i\right) P\!\left(e^{\omega_i(B)}_i \mid x^B_i\right),
$$

which _is_ a product of single-object sensor terms — but wrapped inside a sum over
every association. That sum is the combinatorial explosion: for $n$ objects and $T$
time steps there are $(n!)^T$ ways to thread the observations into tracks.

$$
% caption: The association hypotheses branch at every time step. With $n$ objects
% each sweep admits $n!$ pairings, so after $T$ steps there are $(n!)^T$ complete
% association histories; the count for $n = 3$ objects grows as $6, 36, 216, \ldots$
% down the tree.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  h/.style={draw, circle, minimum size=4mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[h] (root) at (0,0) {};
  \node[font=\scriptsize, anchor=east] at (-0.3,0) {t=0};
  % level 1: 3 branches shown of n! 
  \node[h] (a1) at (2.4,1.5) {};
  \node[h] (a2) at (2.4,0) {};
  \node[h] (a3) at (2.4,-1.5) {};
  \node[font=\scriptsize, anchor=south] at (2.4,1.9) {t=1};
  \draw[->, acc] (root) -- (a1);
  \draw[->, acc] (root) -- (a2);
  \draw[->, acc] (root) -- (a3);
  \node[font=\scriptsize, text=black, anchor=north] at (1.2,-0.4) {each branch: one pairing};
  % level 2 fan from a1
  \foreach \y in {2.1,1.5,0.9} { \node[h] (b) at (4.8,\y) {}; \draw[->, acc] (a1) -- (b); }
  \foreach \y in {0.4,-0.4} { \node[h] (b) at (4.8,\y) {}; \draw[->, black] (a2) -- (b); }
  \foreach \y in {-0.9,-1.5,-2.1} { \node[h] (b) at (4.8,\y) {}; \draw[->, black] (a3) -- (b); }
  \node[font=\scriptsize, anchor=south] at (4.8,2.4) {t=2};
  \node[font=\scriptsize] at (6.0,0) {. . .};
  \node[font=\scriptsize, text=black, anchor=west, align=left] at (6.4,0)
    {(n!) to the T\\histories};
\end{tikzpicture}
$$

### Why no exact filter survives

Filtering summed out the hidden state variables cheaply for HMMs, DBNs, and Kalman
filters. Data association defeats that trick, for the same reason the switching
Kalman filter does: the filtering distribution $P(x^A_t \mid e^1_{1:t}, e^2_{1:t})$
for object $A$ becomes a **mixture of exponentially many** Gaussians, one for every
sequence of observations that could have been assigned to $A$. There is no known
efficient exact algorithm, so every practical method approximates.

The simplest approximation commits to a single **best assignment** each step, given
the objects' predicted positions, then updates each track and predicts forward as if
that assignment were certain. The **nearest-neighbour filter** builds the assignment
greedily: repeatedly pair the closest predicted-position/observation couple and fix
it. It works when objects are well separated and prediction and observation errors
are small — when confusion is impossible — but degrades sharply otherwise. A better
single-assignment rule maximizes the _joint_ probability of all current observations
given the predictions, which despite there being $n!$ assignments is solved exactly
in polynomial time by the **Hungarian algorithm**.

$$
% caption: Nearest-neighbour assignment. Predicted positions (open circles) are
% paired to new observations (filled dots) by choosing the closest pairing first.
% The greedy choice is wrong when tracks pass close: assigning obs y to the nearer
% prediction pA can steal the observation that truly belongs to B.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  pred/.style={draw, circle, minimum size=5mm, inner sep=0pt},
  obs/.style={fill=acc, circle, minimum size=0pt, inner sep=1.6pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % predicted positions
  \node[pred] (pa) at (0,1.6) {}; \node[font=\scriptsize, anchor=east] at (-0.15,1.6) {pA};
  \node[pred] (pb) at (0,0.4) {}; \node[font=\scriptsize, anchor=east] at (-0.15,0.4) {pB};
  % observations
  \node[obs] (ox) at (3.2,1.9) {}; \node[font=\scriptsize, anchor=west] at (3.35,1.9) {obs x};
  \node[obs] (oy) at (3.2,0.9) {}; \node[font=\scriptsize, anchor=west] at (3.35,0.9) {obs y};
  % candidate pairings
  \draw[acc, thick] (pa) -- (ox);
  \draw[red, densely dashed] (pa) -- (oy);
  \draw[acc, thick] (pb) -- (oy);
  \node[red, anchor=north, font=\scriptsize] at (1.9,0.6) {greedy conf\/lict};
\end{tikzpicture}
$$

Any single-assignment method fails badly in hard cases: one wrong commitment
corrupts the next prediction, which invites further wrong commitments, and the track
diverges. Two better approaches keep _many_ hypotheses alive. A **particle filter**
for data association maintains a large population of current assignments, letting the
evidence sort out which survive. An **MCMC** algorithm explores the space of whole
assignment _histories_ — each track hypothesis a state — and can revise a past
decision when later evidence contradicts it; current MCMC data-association methods
track hundreds of objects in real time while approximating the true posterior well.

$$
% caption: Instead of one committed assignment, an MCMC or particle method keeps a
% population of association histories, each a full set of tracks. Later evidence
% reweights them: histories consistent with the new observations gain weight, and
% MCMC moves can swap two objects' assignments in the past to escape a bad early
% commitment.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  hyp/.style={draw, minimum width=22mm, minimum height=14mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[hyp, draw=acc, text=acc] (h1) at (0,0) {history 1\\A straight\\B straight\\weight 0.6};
  \node[hyp] (h2) at (3.4,0) {history 2\\A, B cross\\weight 0.3};
  \node[hyp] (h3) at (6.8,0) {history 3\\B splits\\weight 0.1};
  \node[font=\scriptsize, text=black, anchor=north] at (3.4,-1.1)
    {new evidence reweights; MCMC can swap a past assignment};
\end{tikzpicture}
$$

### False alarms, missed detections, appearing objects

Real tracking is messier still. Observations may be **false alarms** (clutter) from
moving shadows, reflections, or articulated vehicles, caused by no real object at
all. **Detection failures** occur when a real object produces no observation, from
occlusion, fog, or darkness. And objects arrive and depart — **track initiation** and
**track termination** — so the number of objects is not even fixed. Each phenomenon
multiplies the possible worlds further.

$$
% caption: The four complications beyond clean n-to-n association. A false alarm is
% an observation with no source; a detection failure is an object with no
% observation; track initiation adds a new object; track termination removes one.
% Each expands the space of association hypotheses the filter must consider.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  ob/.style={fill=acc, circle, inner sep=1.6pt},
  ghost/.style={draw, circle, minimum size=4mm, inner sep=0pt, densely dashed}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % false alarm
  \node[ob] (fa) at (0,1.4) {};
  \node[font=\scriptsize, text=red, anchor=south] at (0,1.6) {false alarm};
  \node[font=\scriptsize, text=black, anchor=north] at (0,1.2) {no object};
  % detection failure
  \node[ghost] (df) at (2.6,1.4) {};
  \node[font=\scriptsize, text=red, anchor=south] at (2.6,1.7) {detection fail};
  \node[font=\scriptsize, text=black, anchor=north] at (2.6,1.1) {no obs};
  % track initiation
  \node[ob] (ti) at (5.2,1.4) {};
  \draw[->, acc] (5.2,0.6) -- (ti);
  \node[font=\scriptsize, text=acc, anchor=south] at (5.2,1.6) {track init};
  % track termination
  \node[ghost] (tt) at (7.6,1.4) {};
  \draw[->, black] (7.6,0.6) -- (tt);
  \node[font=\scriptsize, anchor=south] at (7.6,1.7) {track end};
\end{tikzpicture}
$$

These are not academic. To estimate freeway travel times and traffic demand,
surveillance cameras miles apart must decide when a vehicle seen upstream is the same
vehicle seen downstream — data association over tens of thousands of vehicles per
hour, with false alarms from shadows and reflections, detection failures from
occlusion and fog, and vehicles constantly entering and leaving. A vehicle's very
appearance changes between cameras with lighting and pose, and the transition model
shifts as jams form and clear. Modern data-association algorithms nonetheless
recover traffic parameters in these conditions. Data association is the foundation
for tracking a complex world at all: without it there is no way to combine multiple
observations of the same object, and when objects interact in structured activities,
tracking them requires joining data association with the relational and open-universe
probability models of the previous lesson.

## SLAM, and learning the state-space model

AIMA stops at particle filtering for a fixed, hand-specified DBN. Two public lines
of work push the temporal model past that — one by scaling the classical filters to
a landmark problem in robotics, the other by learning the transition and sensor
models with neural networks rather than writing them down.

**Filters at scale: SLAM.** A robot that must build a map _and_ localize within it
at the same time faces **simultaneous localization and mapping** (SLAM), and the
state — robot pose plus every landmark position — is high-dimensional and
continuous. The **extended Kalman filter** was the first workable solution, keeping
a joint Gaussian over pose and landmarks, but its covariance is dense and updating it
costs $O(n^2)$ in the number of landmarks. **FastSLAM** (Montemerlo, Thrun, Koller,
and Wegbreit, _AAAI_ 2002) restructured the problem using a fact this lesson makes
visible: _conditioned on the robot's path_, the landmark estimates are independent
of one another, since each landmark is observed only through the pose. FastSLAM
therefore runs a particle filter over the robot's trajectory and attaches a small
independent Kalman filter to each landmark inside each particle — a
**Rao-Blackwellized particle filter**, sampling the variables that make the rest
conditionally Gaussian and integrating the Gaussians exactly. Thrun, Burgard, and
Fox's _Probabilistic Robotics_ (2005) is the standard treatment of these filters,
and **Monte Carlo localization** — a particle filter over robot pose against a known
map — is the algorithm running on most deployed indoor robots. The lesson's umbrella
filter and the robot on a grid are the same recursion these systems scale to
millions of particles and thousands of landmarks.

**Learning the model: deep state-space models.** An HMM, a Kalman filter, and a DBN
all assume the transition and sensor distributions are given. When they are not — a
patient's physiology, a video's dynamics — one can parameterize them with neural
networks and learn them from sequences. The **deep Kalman filter** (Krishnan,
Shalit, and Sontag, 2015) keeps the linear-Gaussian _structure_ of the state-space
model but replaces the fixed transition and emission matrices with neural networks,
learning the whole thing by variational inference; **structured inference networks**
(Krishnan et al., _AAAI_ 2017) added an inference network shaped like the backward
message so that learning respects the forward-backward structure of smoothing.
Rangapuram et al.'s **deep state-space models** (_NeurIPS_ 2018) let a recurrent
network output the parameters of a classical linear state-space model at each step,
so the exact Kalman recursions still run for inference while a network supplies the
time-varying dynamics — the interpretability and calibrated uncertainty of the
Kalman filter with the flexibility of deep learning. These systems keep the
predict/update skeleton of this lesson intact and learn only the two conditional
distributions that fill it in.

**Differentiable filtering.** A further step makes the filter _itself_ a layer in a
network. **Particle filter networks** and differentiable particle filters (Jonschkowski
et al., 2018; Karkus et al., 2018) implement the propagate/weight/resample cycle with
differentiable operations, so the transition and sensor models can be trained
end-to-end by backpropagating a tracking loss through the filter. The stubborn part
is resampling, which is discontinuous; soft or reparameterized resampling schemes
restore a usable gradient. The common thread across all three lines is that the
recursive belief-state update — predict, then weight by evidence — is not only an
inference algorithm but a differentiable computational structure that a learned
model can be wrapped around.

$$
% caption: Two ways past a fixed, hand-built temporal model. Left: keep the classical
% filter and scale it (FastSLAM factors the posterior into a particle filter over the
% path times per-landmark Kalman filters). Right: keep the predict/update recursion but
% learn its transition and sensor models with neural networks (deep / differentiable
% state-space models).
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bx/.style={draw, minimum width=34mm, minimum height=13mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[bx, draw=acc, text=acc] (core) at (0,1.6) {predict / update\\recursion};
  \node[bx] (scale) at (-3.3,-0.6) {scale it:\\FastSLAM,\\MC localization};
  \node[bx] (learn) at (3.3,-0.6) {learn it:\\deep / di\/f\/f.\\state-space models};
  \draw[->, acc, thick] (core) -- (scale);
  \draw[->, acc, thick] (core) -- (learn);
  \node[font=\scriptsize, text=black, anchor=north, align=center] at (-3.3,-1.35)
    {Rao-Blackwellized\\particles};
  \node[font=\scriptsize, text=black, anchor=north, align=center] at (3.3,-1.35)
    {networks f\/ill the\\two conditionals};
\end{tikzpicture}
$$

## Where this sits

Temporal models are Bayesian networks with a clock. The Markov assumption and a
stationary process reduce an unbounded history to a prior, a transition model, and
a sensor model; the four inference tasks — filtering, prediction, smoothing, most
likely explanation — are all recursive messages passed along the sequence, linear
in its length. HMMs give the discrete case a matrix algebra, Kalman filters give the
continuous-Gaussian case a mean-and-covariance update, and DBNs give the general
case, with particle filtering as the approximate method when exact inference blows
up. The next step is to let the agent _act_ rather than only observe: attach
utilities and choices to the state and the belief-state update becomes the basis
of [sequential decision making](/artificial-intelligence/uncertainty/making-decisions).

[^dbn]: **Russell & Norvig**, _AIMA_, §15.5 — Dynamic Bayesian Networks: DBNs as sparse temporal Bayes nets, unrolling and exact inference, and the particle-filtering algorithm (Fig. 15.17) as the general approximate method.
[^data]: **Russell & Norvig**, _AIMA_, §15.6 — Keeping Track of Many Objects: data association as temporal identity uncertainty, the radar example and Figure 15.19, the factored joint (Eq. 15.24) with the association variable $\omega_t$ summed over $n!$ pairings and $(n!)^T$ histories, the mixture-of-exponentially-many filtering distribution, the nearest-neighbour filter, the Hungarian algorithm for the best joint assignment, particle-filtering and MCMC over assignment histories, and false alarms/clutter, detection failures, and track initiation/termination (with the Highway 99 traffic-surveillance application, Figure 15.20).