M3-T4 — Recursive Bayesian Updating

Learning objectives

After this lesson, you should be able to:

• Update a belief recursively, using each posterior as the prior for the next reading, and show that this equals a batch update.
• Convert between probability, odds and log odds, and compute the evidence of a reading as a likelihood ratio.
• Derive the odds and log-odds forms of the update and use them to track a belief over a sequence of readings.
• Explain why the belief must be clamped, and recognise the bugs of re-applying the prior and of treating a changing state as static.

The intuition

Recall the marker detector of the last lesson: it fires with probability 0.8 when the marker is in view and 0.1 when it is not, and the marker is in view on 5% of the corridor frames. One detection raised the belief from 0.05 to 0.30. What should happen on the next frame?

The robot does not start from scratch. After the first frame its belief is 0.30, and that is now its prior for the second frame: what it believed before seeing the new reading. It applies Bayes' rule again, with 0.30 as the prior. If the second frame also fires, the belief becomes 0.77. A miss then lowers it to 0.43; two more detections raise it to 0.86 and 0.98. This is recursive Bayesian updating: the posterior of one step is the prior of the next, so the robot only has to remember its current belief, not the whole history of readings.

The two panels show the same belief, and the right-hand one is simpler. A detection always adds the same amount of evidence, whatever the robot already believes, and a miss always subtracts a smaller fixed amount. The left-hand curve moves by 0.25 on the first detection and by only 0.12 on the last, because probabilities get crowded near 1; in log odds the steps are all equal. A practical consequence follows: to update a belief, a robot can just add a number to a stored value, with no division or normalization.

Odds and log odds

Betting people use odds: 1 to 19 against means a probability of 0.05. The odds of a probability $p$ are $p/(1-p)$, and the log odds (also called the logit) are their natural logarithm. The mapping is one to one, and it stretches the unit interval onto the whole number line: probability 0.5 is log odds 0, probabilities near 1 are large positive numbers, and probabilities near 0 are large negative numbers.

Why does the update become an addition? Bayes' rule says posterior ∝ prior × likelihood. Taking odds divides out the common normalizer, and taking logarithms turns the multiplication into a sum. The evidence a reading carries is its likelihood ratio, the probability of the reading if the hypothesis is true divided by its probability if it is false: 0.8 / 0.1 = 8 for a detection, 0.2 / 0.9 = 0.22 for a miss. In log units, +2.08 and −1.50.

In log odds a belief is a running total. Every independent reading adds its own weight of evidence, positive for evidence in favour, negative against, and the order in which they arrive does not matter.

Definitions

Belief $\mathrm{bel}_t(x)$

The robot’s probability for each state $x$ after the readings $z_1, \dots, z_t$: $P(x \mid z_{1:t})$.

Odds $O(H)$

$P(H)/(1 - P(H))$: how many times more likely the hypothesis is than its opposite.

Log odds $\ell$

$\ln O$ (also logit). Probability is recovered by $p = 1/(1 + e^{-\ell})$ (the logistic function).

Likelihood ratio $\mathrm{LR}(z)$

$P(z \mid H)/P(z \mid \neg H)$: the factor by which a reading multiplies the odds.

Weight of evidence

$\ln \mathrm{LR}(z)$: the amount a reading adds to the log odds.

Static state

A state that does not change while the readings arrive. The updates of this lesson assume it; module 6 adds the prediction step for a state that moves.

Derivation: the recursion, the odds form and the log-odds sum

The recursion

1. $$P(x \mid z_{1:t}) = \dfrac{P(z_t \mid x, z_{1:t-1})\; P(x \mid z_{1:t-1})}{P(z_t \mid z_{1:t-1})}$$

   Bayes’ rule with all the earlier readings $z_{1:t-1}$ carried along as background knowledge: the “prior” is now what we believed after those readings.

2. $$P(z_t \mid x, z_{1:t-1}) = P(z_t \mid x)$$

   The assumption. Given the state, the new reading does not depend on the old ones: conditional independence of the readings (the last lesson). For a static state this is the sensor model.

3. $$\mathrm{bel}_t(x) = \eta\; P(z_t \mid x)\; \mathrm{bel}_{t-1}(x), \qquad \eta = \dfrac{1}{P(z_t \mid z_{1:t-1})}$$

   Name the old posterior $\mathrm{bel}_{t-1}$. The denominator does not depend on $x$ and is found by normalizing.

4. $$\mathrm{bel}_t(x) \;\propto\; \mathrm{bel}_0(x)\, \prod_{i=1}^{t} P(z_i \mid x)$$

   Unroll the recursion. It gives the batch formula of the last lesson, so processing readings one at a time loses nothing.

5. $$\text{the product is commutative} \;\Rightarrow\; \text{any order of the readings gives the same } \mathrm{bel}_t$$

   For a static state, the order of independent readings is irrelevant.

Odds and log odds

1. $$\dfrac{P(H \mid z_{1:t})}{P(\neg H \mid z_{1:t})} = \dfrac{\eta\, P(z_t \mid H)\, P(H \mid z_{1:t-1})}{\eta\, P(z_t \mid \neg H)\, P(\neg H \mid z_{1:t-1})}$$

   Write the recursion for $H$ and for its complement and divide one by the other.

2. $$= \dfrac{P(z_t \mid H)}{P(z_t \mid \neg H)} \cdot \dfrac{P(H \mid z_{1:t-1})}{P(\neg H \mid z_{1:t-1})}$$

   The normalizer $\eta$ is the same in both and cancels. No normalization is needed in this form.

3. $$\ln O_t = \ln O_{t-1} + \ln \mathrm{LR}(z_t)$$

   The logarithm turns the product into a sum: the log-odds update.

4. $$\ell_t = \ell_0 + \sum_{i=1}^{t} \ln \mathrm{LR}(z_i)$$

   Unroll: the final log odds are the prior log odds plus the total weight of evidence, with no dependence on the order of the readings.

5. $$p = \dfrac{O}{1 + O} = \dfrac{e^{\ell}}{1 + e^{\ell}} = \dfrac{1}{1 + e^{-\ell}}$$

   Converting back: the logistic function.

Why a stored log odds must be bounded

The log-odds sum has no ceiling: ten detections give $\ell \approx 17.9$, a probability within $2 \times 10^{-8}$ of 1. Evidence is only worth as much as the assumptions under it. If the marker then leaves the view, each miss subtracts only 1.50, and the belief needs twelve misses to fall below ½. A cap $\ell_{\max}$ limits how far the belief can run ahead of the assumptions, and bounds the number of contrary readings needed to change its mind to $\lceil \ell_{\max} / 1.5 \rceil$.

Evidence adds in log odds. The belief is the prior plus the sum of the weights of evidence of all the readings, in any order. A cap on the sum is what keeps a belief able to change.

A worked example

Rover drives down the corridor looking for the dock marker. The prior probability that the marker is in view is 0.05 (log odds −2.944), the detector has $d = 0.8$ and $f = 0.1$, and the five frames give: detect, detect, miss, detect, detect.

1. Weights of evidence. A detection: $\ln(0.8/0.1) = \ln 8 = +2.079$. A miss: $\ln(0.2/0.9) = -1.504$.
2. Frame by frame. Log odds: −2.944 → −0.865 → 1.214 → −0.290 → 1.790 → 3.869. Probabilities: 0.05 → 0.296 → 0.771 → 0.428 → 0.857 → 0.980. Entropy of the belief, a measure of how undecided it is, rises while the belief is near ½ (0.985 bits after the miss) and falls to 0.144 bits at the end.
3. Check the first step against the last lesson: 0.05 → 0.296 is the same posterior computed there with Bayes’ rule directly.
4. Batch equals recursive. The batch posterior odds are prior odds times the product of all five likelihood ratios: $(0.05/0.95) \times 8^4 \times (0.2/0.9) = 47.9$, so $p = 47.9/48.9 = 0.9796$. Processing the five frames in the reverse order also gives 0.9796.
5. Clamping. After ten detections in a row, an uncapped belief needs 12 consecutive misses to drop below ½ if the marker disappears. A belief capped at log odds ±3 (probability 0.953) needs only 2.

import math
from robotprob import logit, inv_logit, entropy

d, f = 0.8, 0.1
lr_detect = math.log(d / f)                  # weight of evidence of a detection, in nats
lr_miss = math.log((1 - d) / (1 - f))        # weight of evidence of a non-detection
print('evidence per detection =', round(lr_detect, 4), ' per miss =', round(lr_miss, 4))

seq = ['detect', 'detect', 'miss', 'detect', 'detect']
l = logit(0.05)                              # prior log odds
print('start: log odds', round(l, 3), ' p =', round(inv_logit(l), 4), ' entropy =', round(entropy([0.05, 0.95]), 3), 'bits')
for i, s in enumerate(seq, 1):
    l += lr_detect if s == 'detect' else lr_miss          # the whole update is an addition
    p = inv_logit(l)
    print(i, s.ljust(6), 'log odds', round(l, 3), ' p =', round(p, 4), ' entropy =', round(entropy([p, 1 - p]), 3), 'bits')

l2 = logit(0.05)
for s in reversed(seq):                      # the same readings in the opposite order
    l2 += lr_detect if s == 'detect' else lr_miss
print('same final belief in any order:', abs(l - l2) < 1e-12)
batch = 0.05 / 0.95 * (d / f) ** 4 * ((1 - d) / (1 - f))   # batch posterior odds
print('batch posterior          =', round(batch / (1 + batch), 4))

def misses_to_forget(l_max):                 # ten detections, then the marker disappears
    l = logit(0.05)
    for _ in range(10):
        l = min(l + lr_detect, l_max)
    k = 0
    while inv_logit(l) >= 0.5:
        l = max(l + lr_miss, -l_max)
        k += 1
    return k
print('misses needed to doubt the marker after 10 detections: no clamp', misses_to_forget(1e9), ' clamp at 3:', misses_to_forget(3.0))

evidence per detection = 2.0794  per miss = -1.5041
start: log odds -2.944  p = 0.05  entropy = 0.286 bits
1 detect log odds -0.865  p = 0.2963  entropy = 0.877 bits
2 detect log odds 1.214  p = 0.7711  entropy = 0.776 bits
3 miss   log odds -0.29  p = 0.4281  entropy = 0.985 bits
4 detect log odds 1.79  p = 0.8569  entropy = 0.592 bits
5 detect log odds 3.869  p = 0.9796  entropy = 0.144 bits
same final belief in any order: True
batch posterior          = 0.9796
misses needed to doubt the marker after 10 detections: no clamp 12  clamp at 3: 2

In robotics

The occupancy grid is this lesson, once per cell

Each cell of an occupancy grid map holds a log odds value, initially 0 (probability ½). A range beam that ends in a cell adds a positive weight of evidence; a beam that passes through adds a negative one; the values are capped. Mapping a whole room is millions of additions of the kind above, and the map can be stored as small integers. M10-T1: Occupancy Grids and the Binary Bayes Filter derives the update from this lesson; the SLAM course shows the practical version in Occupancy Grid Mapping.

Sequential tests for faults and detections

Instead of a fixed k-of-n vote (M2-T1: Discrete Random Variables and Probability Mass Functions), a detector can keep a running log odds and declare “marker found” when it crosses an upper threshold, and “not there” when it falls below a lower one. This is the sequential probability ratio test: it reaches the same error rates with fewer readings on average, and it is how many fault monitors work (Sensor fault detection and isolation).

Fusion of several detectors

Two independent detectors can be fused by adding their weights of evidence. A camera that says “person” with a likelihood ratio of 20 and a thermal sensor with a ratio of 5 give a total ratio of 100, which turns a prior of 1 in 1000 into about 9%. Writing evidence in log units makes it easy to audit which sensor drove a decision.

When the state changes, add a prediction step

Everything above assumes the marker's presence is fixed while the readings arrive. If a door can open or close between frames, the old belief is partly out of date and must be softened before each update, otherwise it becomes more and more stubborn. That softening is the prediction step of the Bayes filter (M6-T1: The Bayes Filter). A cap on the log odds is a crude, always-available version of it.

Common implementation bugs

• The prior applied at every step: bel = prior * likelihood inside the loop instead of bel = bel * likelihood. The prior is counted once per reading.
• Probabilities multiplied without normalizing, until they underflow to zero. Work in log odds or log probabilities, or normalize every step.
• No cap, so the belief can never change its mind after a long run of the same reading.

Common misconceptions

Key takeaways

1. Update one reading at a time: the posterior of one step is the prior of the next, bel_t ∝ P(z_t | x) bel_{t−1}. For independent readings of a static state this equals the batch update, in any order.
2. In odds form, posterior odds = likelihood ratio × prior odds; in log odds the update is an addition of the weight of evidence ln LR.
3. A detection with d = 0.8, f = 0.1 is worth +2.08 and a miss −1.50. The probability moves by different amounts each time; the log odds move by the same.
4. Cap the log odds so that a long run of one reading cannot make the belief impossible to change; this is how occupancy grids are stored.
5. The prior enters once. A moving state needs a prediction step (module 6) that softens the belief between readings.

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.

• C. Stachniss, “Bayes Filter” (video lecture) , the recursive update with a prediction step. Free to watch.
• J. Tsitsiklis and P. Jaillet, MIT RES.6-012 Introduction to Probability , lectures 14 to 17 (Bayesian inference). Free videos and notes, licence CC BY-NC-SA 4.0.
• S. Thrun, W. Burgard and D. Fox, Probabilistic Robotics, MIT Press, 2005, section 4.2 (the binary Bayes filter, with its log-odds form). Paid book.
• A. Wald, “Sequential Tests of Statistical Hypotheses”, Annals of Mathematical Statistics 16 (2), 1945 , the sequential probability ratio test. Paid journal article.
• C. Piech, Probability for Computer Scientists (Stanford CS109 course reader) , part 1 (updating beliefs). Free to read online.

Knowledge check

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

What’s next

Module 3 gave you the rules for updating a belief from evidence. Module 4 looks at the quantities that summarise a distribution: the mean, the variance, and the covariance that describes uncertainty in two or more dimensions at once.

Related content

Nothing below is required to finish this lesson.

• Before
  M3-T3: Independence and Conditional Independence

  Test whether two variables are independent, explain conditional independence, and identify when evidence is being counted twice.

• Lab
  M3-L1: Bayesian Landmark Detection

  A marker detector fires near the charging dock, but it also fires by mistake. Compute how much each detection should change the belief that the robot is at the dock.

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

• SLAM M2-T5: Bayesian Estimation
• UAV M3-T3: Bayesian estimation
• Physical AI: Belief under uncertainty