Reasoning over Time: Tracking and Data Association

This builds on Probabilistic 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.¹

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.

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.

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.²

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_t^1$ and $e_t^2$, but the labels $1$ and $2$ are assigned arbitrarily and carry no information — that arbitrariness is the problem.

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

We would like to split the observation term $P(e_i^1,e_i^2\mid x_i^A,x_i^B)$ 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,

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.

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_t^A\mid e_{1:t}^1,e_{1:t}^2)$ 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.

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.

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.

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.

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.