M6-T3 — Representing Belief: Parametric and Nonparametric

Learning objectives

After this lesson, you should be able to:

• Describe grid, Gaussian and particle representations of a belief, and what each can and cannot represent.
• Derive that the best single Gaussian approximation matches the mean and covariance of the belief, and compute it for a mixture.
• Compute the probability that a particle set misses a hypothesis, and the number of particles that prevents it.
• Choose a representation for a given problem from its dimension, the number of peaks and the noise.

The intuition

Rover is in a corridor and knows it is at one of two doors: one 2 m along, the other 5 m, with equal belief and about 20 cm of uncertainty about each. Three ways to write that belief down:

• A grid (the histogram filter): divide the corridor into cells and store a probability for each. Any shape is possible, but the cell width limits how sharply a peak can be written. With 50 cm cells the two narrow peaks become blocky humps.
• A Gaussian (the Kalman filter): store a mean and a variance, two numbers. It is compact and fast. But a Gaussian has one peak. The best one can do is to put it at the average, 3.5 m, with a huge spread, 1.5 m. That is the middle of the corridor, where the robot is certainly not.
• Particles (the Monte Carlo filter): store a cloud of sample positions, each a possible truth. Forty samples already cluster around the two peaks. The cloud has no fixed shape and costs more with every sample.

The Gaussian's failure is the one to remember. The mean of a two-peaked belief is not a likely position, and a planner or a controller that takes “the estimate” to be 3.5 m will plan for a robot that is in neither place. In the figure, the Gaussian assigns 26% of the probability to the stretch between 3 and 4 m, where the true belief assigns essentially zero, and at the true position of 2 m its density is 0.16 against the correct 1.0: six times too low.

None of this makes the Gaussian bad. For a robot that has already localized, the belief is a single narrow peak, and then a Gaussian is a perfect and extremely cheap description; the Kalman filter will outperform the other two in speed and accuracy. The two-peaked situation arises in global localization, in symmetric environments, and after failures. So the choice is a question about the problem.

A representation is a bet about what the belief looks like. A Gaussian bets on one peak; a grid bets on a small number of cells; particles bet on enough samples. Choose the bet that the problem can win.

Definitions

Parametric representation

A belief of a fixed form described by a few numbers: a Gaussian (mean and covariance), or a mixture of Gaussians (several means, covariances and weights).

Nonparametric representation

A belief with no fixed form: a grid of cell probabilities, or a set of weighted samples (particles).

Moment matching

Choosing the Gaussian that has the same mean and covariance as the belief it replaces.

Mode

A peak of the belief: a hypothesis about where the robot is.

Mixture $p(x) = \sum_k w_k\,\mathcal{N}(x; \mu_k, \sigma_k^2)$

A belief made from several Gaussians with weights $w_k$ that sum to 1.

Derivation: the best Gaussian, and how many particles

The best Gaussian matches mean and variance

Take a one-dimensional belief $p$ and approximate it by $q = \mathcal{N}(\mu, \sigma^2)$, choosing $\mu$ and $\sigma$ to minimize the Kullback-Leibler divergence $\mathrm{KL}(p\,\|\,q) = \int p \ln(p/q)\,dx$.

1. $$\mathrm{KL}(p\,\|\,q) = \int p\ln p\,dx \;-\; \mathbb{E}_p\bigl[\ln q(x)\bigr]$$

   Expand the logarithm of the ratio. The first term does not depend on $q$.

2. $$\mathbb{E}_p[\ln q(x)] = -\tfrac{1}{2}\ln(2\pi\sigma^2) - \dfrac{\mathbb{E}_p[(x - \mu)^2]}{2\sigma^2}$$

   Insert the Gaussian density. Minimizing the divergence means maximizing this expression.

3. $$\dfrac{\partial}{\partial \mu}: \;\; \dfrac{\mathbb{E}_p[x - \mu]}{\sigma^2} = 0 \;\Rightarrow\; \mu = \mathbb{E}_p[x]$$

   The best centre is the mean of $p$, wherever that is.

4. $$\dfrac{\partial}{\partial \sigma^2}: \;\; -\dfrac{1}{2\sigma^2} + \dfrac{\mathbb{E}_p[(x - \mu)^2]}{2\sigma^4} = 0 \;\Rightarrow\; \sigma^2 = \mathrm{Var}_p(x)$$

   The best variance is the variance of $p$. (The same argument in several dimensions gives the covariance matrix.)

5. $$\mu = 0.5\cdot 2 + 0.5\cdot 5 = 3.5, \qquad \sigma^2 = 0.5(0.04 + 4) + 0.5(0.04 + 25) - 3.5^2 = 2.29$$

   For the two-door belief. The mean falls in the gap and the variance is dominated by the distance between the modes (2.25), not by the 0.04 of each door.

This is what a Kalman filter does implicitly to any belief it cannot represent: it keeps the mean and the covariance and throws the rest away. For one peak that loses nothing; for two peaks it loses everything that mattered.

How many particles keep a hypothesis alive?

1. $$P(\text{a given particle lands in the mode}) = w$$

   A particle is a sample of the belief, so it falls in a mode of mass $w$ with probability $w$.

2. $$P(\text{no particle in the mode}) = (1 - w)^N \approx e^{-Nw}$$

   The $N$ particles are independent (the independence of the Monte Carlo lesson). For small $w$, $\ln(1-w) \approx -w$.

3. $$(1 - w)^N \le \delta \;\Longleftrightarrow\; N \ge \dfrac{\ln(1/\delta)}{-\ln(1 - w)} \approx \dfrac{\ln(1/\delta)}{w}$$

   Solve for $N$. For $\delta = 0.05$ this is $N \approx 3/w$: a hypothesis of mass 5% needs about 60 particles, one of mass 1% needs 300.

A mode that a filter loses cannot be recovered by correction: there is no particle there to be reweighted. This is particle deprivation, treated in module 9.

Moment matching puts a Gaussian at the mean of the belief with the belief’s variance, even if that is where nothing is. A particle filter loses a hypothesis of mass w with probability e^(−Nw), so it needs N of the order of 3/w particles to keep it.

A worked example

The two-door belief, 0.5 N(2 m, 0.2 m) + 0.5 N(5 m, 0.2 m), represented three ways. All numbers are printed by the program below.

1. Gaussian. Moment matching gives mean 3.5 m and standard deviation 1.513 m. It puts 0.259 of its probability between 3 m and 4 m, where the true belief puts less than $10^{-6}$. At the true position 2.0 m its density is 0.161 against the true belief's 0.997.
2. Grid. The total variation distance between a grid belief and the true one (half the integral of the absolute difference: 0 for a perfect copy, 1 for no overlap) is 0.571 for 1 m cells, 0.303 for 0.5 m cells, 0.103 for 0.2 m cells and 0.050 for 0.1 m cells. The cell must be a fraction of the 0.2 m width of the peaks to represent them well; at 10 cm the 70 cells hold the belief with a 5% error.
3. Particles. A hypothesis of mass 0.05 is missed by 20 particles with probability $0.95^{20} = 0.358$, by 60 with 0.046 (simulation with 10 000 particle sets: 0.048), by 100 with 0.006, by 300 with $2\times 10^{-7}$. For the two equal doors a few tens of particles suffice; for a 5% alternative, a hundred.
4. Cost. A 1D corridor: 200 cells, 2 Gaussian numbers, about 100 particles. A 3D pose (x, y, heading): 7.2 million cells, 9 numbers, perhaps 1 500 numbers of particles. A 6D pose: 7 trillion cells, 27 numbers, tens of thousands of particle numbers.

import math
from robotprob import Rng, gaussian_pdf, gaussian_cdf

def truth_pdf(x):                                # the belief: the robot is at one of two doors, 2 m or 5 m along
    return 0.5 * gaussian_pdf(x, 2.0, 0.2) + 0.5 * gaussian_pdf(x, 5.0, 0.2)
def truth_cdf(x):
    return 0.5 * gaussian_cdf(x, 2.0, 0.2) + 0.5 * gaussian_cdf(x, 5.0, 0.2)

mu = 0.5 * 2.0 + 0.5 * 5.0                       # the moment-matched Gaussian: mean and variance of the mixture
var = 0.5 * (0.2 ** 2 + 2.0 ** 2) + 0.5 * (0.2 ** 2 + 5.0 ** 2) - mu ** 2
sd = math.sqrt(var)
print('moment-matched Gaussian: mean', mu, ' std', round(sd, 3))
gap_fit = gaussian_cdf(4.0, mu, sd) - gaussian_cdf(3.0, mu, sd)
gap_true = truth_cdf(4.0) - truth_cdf(3.0)
print('probability between 3 and 4 m, where the robot cannot be: Gaussian', round(gap_fit, 3), ' true belief', round(gap_true, 6))
print('density at the true position 2.0 m: true belief', round(truth_pdf(2.0), 3), ' Gaussian', round(gaussian_pdf(2.0, mu, sd), 3))

def tv_grid(cell):                               # total variation distance between a grid belief and the true one
    n = int(round(7.0 / cell))
    masses = [truth_cdf((i + 1) * cell) - truth_cdf(i * cell) for i in range(n)]
    step, total, x = 0.005, 0.0, 0.0
    while x < 7.0:
        i = min(n - 1, int((x + step / 2) / cell))
        total += abs(masses[i] / cell - truth_pdf(x + step / 2)) * step
        x += step
    return 0.5 * total
for cell in (1.0, 0.5, 0.2, 0.1):
    print('grid with', cell, 'm cells: total variation distance from the true belief', round(tv_grid(cell), 3))

for n in (20, 60, 100, 300):                     # the chance that n particles contain none from a mode of mass 0.05
    print(n, 'particles: chance of missing a mode of mass 0.05 =', round(0.95 ** n, 4))
rng = Rng(6)
missed = 0
for _ in range(10000):
    if not any(rng.random() < 0.05 for _ in range(60)):
        missed += 1
print('simulated, 60 particles:', missed / 10000)

for name, cells, gauss, particles in (('1D (x)', 200, 2, 100), ('2D (x, y)', 200 * 200, 5, 500), ('3D (x, y, heading)', 200 * 200 * 180, 9, 1500), ('6D pose', 200 * 200 * 30 * 180 ** 3, 27, 30000)):
    print(name.ljust(20), 'grid cells', str(cells).rjust(15), ' gaussian numbers', str(gauss).rjust(3), ' particle numbers (typical)', particles)

moment-matched Gaussian: mean 3.5  std 1.513
probability between 3 and 4 m, where the robot cannot be: Gaussian 0.259  true belief 0.0
density at the true position 2.0 m: true belief 0.997  Gaussian 0.161
grid with 1.0 m cells: total variation distance from the true belief 0.571
grid with 0.5 m cells: total variation distance from the true belief 0.303
grid with 0.2 m cells: total variation distance from the true belief 0.103
grid with 0.1 m cells: total variation distance from the true belief 0.05
20 particles: chance of missing a mode of mass 0.05 = 0.3585
60 particles: chance of missing a mode of mass 0.05 = 0.0461
100 particles: chance of missing a mode of mass 0.05 = 0.0059
300 particles: chance of missing a mode of mass 0.05 = 0.0
simulated, 60 particles: 0.0481
1D (x)               grid cells             200  gaussian numbers   2  particle numbers (typical) 100
2D (x, y)            grid cells           40000  gaussian numbers   5  particle numbers (typical) 500
3D (x, y, heading)   grid cells         7200000  gaussian numbers   9  particle numbers (typical) 1500
6D pose              grid cells   6998400000000  gaussian numbers  27  particle numbers (typical) 30000

In robotics

A rule for choosing

The SLAM course discusses the hybrid in Particle Filters and FastSLAM.

Reporting “the estimate” from a multimodal belief

Downstream software wants one pose. For a belief with one dominant peak the mean is fine. For a multimodal belief, the mean can be a place the robot is not: report the mode (the most likely cell or particle cluster) and, importantly, report that the belief is multimodal, so that a planner can stay still, move to disambiguate, or act safely under all hypotheses. Localization stacks expose a covariance or a particle spread for exactly this purpose, and a large one is a reason to slow down.

Switching representations

A common design starts with particles for global localization and, once the cloud has converged to one cluster, hands over to a Kalman filter for efficient tracking, switching back to particles if the covariance grows or the residuals become inconsistent. This uses each representation where it is strongest.

Dimension is the deciding factor

The number of cells grows exponentially with the dimension, the number of particles needed grows with the volume of belief that must be covered, and the Gaussian grows only quadratically. High-dimensional states, such as the full state of a flying robot or of a humanoid, almost always use Gaussian filters (often with careful treatment of rotations, module 12) or optimization over a window of recent states (module 11).

Narrow beliefs and a single Gaussian

If the belief is a narrow single peak, the Gaussian loses nothing. The practical test is the Mahalanobis residuals and consistency checks of module 7: if they stay within their expected range, the Gaussian assumption is doing no harm.

Common misconceptions

Key takeaways

1. A belief can be a grid (any shape, exponential cost), a Gaussian (one peak, two numbers per dimension plus a covariance), or a particle set (any shape, cost grows with the complexity of the belief).
2. The best single Gaussian for any belief has its mean and covariance. For a two-peaked belief that is a wide bell centred between the peaks, where the robot is not.
3. A particle set loses a mode of mass w with probability (1 − w)^N ≈ e^(−Nw); keeping it with 95% confidence needs about 3/w particles.
4. A grid needs cells smaller than the features of the belief and costs ∏ Lᵢ/Δᵢ. It is suited to low-dimensional or discrete states.
5. Choose by problem: Gaussian when the belief is one peak and the state is large, particles for several hypotheses, grids for small discrete states, and report the mode or the whole belief when the belief is multimodal.

References and further reading

Each source is marked free or paid. Free to read does not mean free to reuse: the course resources page lists every source with its licence.

• S. Thrun, W. Burgard and D. Fox, Probabilistic Robotics, MIT Press, 2005, chapters 3 and 4 (Gaussian and nonparametric filters) and the comparison in chapter 8. Paid book.
• T. D. Barfoot, State Estimation for Robotics, 2nd edition, Cambridge University Press, 2024 , chapter “Nonlinear Non-Gaussian Estimation” (representing the posterior). Free to read as the author’s PDF; the book is copyrighted.
• S. Särkkä and L. Svensson, Bayesian Filtering and Smoothing, 2nd edition, Cambridge University Press, 2023 , chapters 7 to 11 (Gaussian and particle approximations). Free to read for personal use; no redistribution or derivative works.
• C. Stachniss, “Particle Filter and Monte Carlo Localization” (video lecture) . Free to watch.
• K. P. Murphy, Probabilistic Machine Learning: An Introduction, MIT Press, 2022 , chapter 6 (information theory, including KL divergence). Free to read as the draft PDF, licence CC BY-NC-ND.

Knowledge check

Three questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Module 6 is complete: you have the filter and the three ways of storing its belief. Module 7 takes the Gaussian one and derives the Kalman filter, the exact solution when everything is linear and Gaussian.

Related content

Nothing below is required to finish this lesson.

• Before
  M6-T2: Histogram Filters and Grid Localization

  Implement the Bayes filter on a discrete grid as a convolution followed by a product, and choose the grid resolution.

Other courses on this site treat neighbouring topics from their own angle:

• SLAM M2-T5: Bayesian Estimation
• Robot Foundations 05: Where Am I?