Discrete Bayes dog - MSML610 -- Tutorials

Imports¶

%load_ext autoreload
%autoreload 2

import logging

import numpy as np

import helpers.htutorial as ut

ut.config_notebook()

# Initialize logger.
logging.basicConfig(level=logging.INFO)
_LOG = logging.getLogger(__name__)

WARNING (pytensor.tensor.blas): Using NumPy C-API based implementation for BLAS functions.
vim support installed: restart the notebook, if needed

Python 3.12.3
Linux 7d77d2247121 6.12.67-linuxkit #1 SMP Sun Jan 25 02:26:28 UTC 2026 aarch64 aarch64 aarch64 GNU/Linux

import L09_05_01_discrete_bayes_dog_utils as ut

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[2], line 1
----> 1 import L09_05_01_discrete_bayes_dog_utils as ut

File /app/msml610/tutorials/L09_05_01_discrete_bayes_dog_utils.py:14
     11 from typing import Dict, List, Optional, Tuple, Union
     13 from ipywidgets import Dropdown, VBox, interactive_output
---> 14 from filterpy.discrete_bayes import predict, update
     15 from IPython.display import display
     16 import matplotlib.pyplot as plt

ModuleNotFoundError: No module named 'filterpy'

# `filterpy` is an extra for this notebook, pinned to the version already
# in requirements.txt.
!sudo /bin/bash -c "(source /venv/bin/activate; pip install --quiet filterpy==1.4.5)"

Part 1: Tracking a Dog¶

Cell 1.1: Problem definition¶

There is a dog with a sensor, that wanders around the offices and halls
There are 10 positions in the hallway, numbered 0 to 9
- The hallway is circular: there is position 0 after position 9
The sensor reports if the dog is in front of a door and its movement
- The sensor can have noise
Can we find out where the dog is from consecutive measurements?

Cell 1.2: Dog with a door sensor¶

A simple example with perfect sensors¶

# At the beginning, we don't know where the dog is.
# The prior is: "all the positions are equiprobable."
belief = np.array([1 / 10] * 10)
print("belief=", belief)

hallway = ut.get_hallway1()
ut.plot_belief(belief, hallway=hallway)

# The map of the office is the following.
hallway = ut.get_hallway1()
ut.plot_belief(hallway, hallway=hallway, title="Hallway")

Let’s assume that the sensor always returns the correct answer
The first reading from the sensor is “door”
The dog is in front of a door, but we don’t know which one
We can update our belief state

belief = np.array([1 / 3, 1 / 3, 0, 0, 0, 0, 0, 0, 1 / 3, 0])
ut.plot_belief(belief, hallway=hallway)

The next readings are “door”, “move right”, “door”
The only location possible is position #1
So the belief is the following

belief = np.array([0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0])
ut.plot_belief(belief, hallway=hallway)

Noisy door sensor¶

If the sensor is not reliable, it seems impossible to determine where the dog is
- “How can you conclude anything, if you are always unsure?”
Let’s assume that testing the sensor shows that the sensor is 3 times more likely to be right than wrong

def update_belief(
    hall: np.ndarray, belief: ut.Pdf, z: int, correct_scale: float
) -> None:
    """
    Update belief in-place based on a measurement.

    Scales belief values by correct_scale for positions that match the
    measurement z.

    :param hall: Array representing the hallway map (0=wall, 1=door)
    :param belief: Array representing current belief distribution
    :param z: Measurement value (0 or 1)
    :param correct_scale: Scale factor for matching positions
    """
    for i, val in enumerate(hall):
        if val == z:
            belief[i] *= correct_scale


belief = np.array([0.1] * 10)
reading = 1  # 1 is 'door'
update_belief(hallway, belief, z=reading, correct_scale=3.0)
print("belief:", belief)
print("sum =", sum(belief))
belief /= sum(belief)
ut.plot_belief(belief, hallway=hallway)

Now this is not a probability since the sum is 1.6 and not 1.0

from filterpy.discrete_bayes import normalize


def scaled_update(
    hall: np.ndarray, belief: ut.Pdf, z: int, z_prob: float
) -> None:
    """
    Update belief using scaled likelihood based on measurement probability.

    Computes a scale factor from the measurement probability and applies it
    to positions matching the measurement, then normalizes.

    :param hall: Array representing the hallway map (0=wall, 1=door)
    :param belief: Array representing current belief distribution
    :param z: Measurement value (0 or 1)
    :param z_prob: Probability that the measurement is correct
    """
    scale = z_prob / (1.0 - z_prob)
    belief[hall == z] *= scale
    normalize(belief)


belief = np.array([0.1] * 10)
scaled_update(hallway, belief, z=1, z_prob=0.75)

print("sum =", sum(belief))
print("probability of door =", belief[0])
print("probability of wall =", belief[2])
ut.plot_belief(belief, hallway=hallway)

Generalizing the update is always in the form of
posterior = likelihood * prior / normalization

from filterpy.discrete_bayes import update


def lh_hallway(hall: np.ndarray, z: int, z_prob: float) -> ut.Pdf:
    """
    Compute likelihood that a measurement matches positions in the hallway.

    Creates a likelihood array where positions matching the measurement z
    are scaled according to the measurement probability.

    :param hall: Array representing the hallway map (0=wall, 1=door)
    :param z: Measurement value (0 or 1)
    :param z_prob: Probability that the measurement is correct
    :return: Likelihood array for all positions
    """
    try:
        scale = z_prob / (1.0 - z_prob)
    except ZeroDivisionError:
        scale = 1e8
    likelihood = np.ones(len(hall))
    likelihood[hall == z] *= scale
    return likelihood


belief = np.array([0.1] * 10)
likelihood = lh_hallway(hallway, z=1, z_prob=0.75)
# The 2 steps above are equivalent to:
#   update(likelihood, prior) = normalize(likelihood * prior)
update(likelihood, belief)

Cell 1.3: Dog with a movement sensor¶

Incorporating movement¶

Assume that the movement sensor is perfect
- If the dog has moved to the right, we need to shift the belief to the right

def perfect_predict(belief: ut.Pdf, move: int) -> ut.Pdf:
    """
    Move the position by `move` spaces with perfect prediction.

    Shifts the belief distribution where positive is to the right, and
    negative is to the left. Uses circular indexing for wrap-around.

    :param belief: Array representing current belief distribution
    :param move: Number of positions to move (positive=right, negative=left)
    :return: Updated belief distribution after movement
    """
    n = len(belief)
    result = np.zeros(n)
    for i in range(n):
        result[i] = belief[(i - move) % n]
    return result


belief = np.array([0.35, 0.1, 0.2, 0.3, 0, 0, 0, 0, 0, 0.05])
ut.plot_belief(belief, hallway=hallway)

move = 1
new_belief = perfect_predict(belief, move)
ut.plot_belief(new_belief, hallway=hallway)

Incorporating the movement of the dog means updating our belief of the PDF

Terminology¶

system: what we are trying to model
- E.g., the dog
state: configuration of the system
- E.g., the position of the dog
The filter produces an estimated state of the system
process model: the dog moves one or more positions at each time step

Noisy movement sensor¶

Assume that the sensor’s movement measurement $z$ is:
- 80% to be correct
- 10% to overshoot by 1
- 10% to undershoot by 1
If movement measurement is 4, then the dog is:
- 80% likely to have moved to the right for positions
- 10% likely to have moved 3 or 5 spaces to the right

def predict_move(
    belief: ut.Pdf,
    move: int,
    p_under: float,
    p_correct: float,
    p_over: float,
) -> ut.Pdf:
    """
    Predict movement with uncertainty in the motion model.

    Models imperfect movement where the actual displacement can differ
    from the measured movement by +-1 position with specified
    probabilities.

    :param belief: Array representing current belief distribution
    :param move: Measured movement (number of positions)
    :param p_under: Probability of undershooting by 1 position
    :param p_correct: Probability of correct movement
    :param p_over: Probability of overshooting by 1 position
    :return: Prior belief distribution after movement prediction
    """
    n = len(belief)
    prior = np.zeros(n)
    for i in range(n):
        prior[i] = (
            belief[(i - move) % n] * p_correct
            + belief[(i - move - 1) % n] * p_over
            + belief[(i - move + 1) % n] * p_under
        )
    return prior


# Current belief.
belief = [0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]

# Belief after update with imperfect movement sensor.
move = 2
prior = predict_move(belief, move, 0.1, 0.8, 0.1)

ut.plot_beliefs(
    belief,
    prior,
    hallway=hallway,
    same_plot=False,
    title1="Belief",
    title2="Prior",
)

# Assume the belief is not correct.
belief = [0, 0, 0.4, 0.6, 0, 0, 0, 0, 0, 0]

move = 2
prior = predict_move(belief, move, 0.1, 0.8, 0.1)

ut.plot_beliefs(
    belief,
    prior,
    hallway=hallway,
    same_plot=False,
    title1="Belief",
    title2="Prior",
)

After the update with the noisy sensor there is always some lost information
For instance
- We start with a strong belief on the dog being in position 0
- We just get a reading of the dog movement and update our belief based on the prediction model
- We don’t have any door sensor update
- The belief becomes flat (i.e., no information)

belief = np.array([1.0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
predict_beliefs = []
predict_beliefs.append(belief)
print("Initial belief:", belief)

for i in range(100):
    move = 1
    belief = predict_move(belief, move, 0.1, 0.8, 0.1)
    predict_beliefs.append(belief)
print("Final belief:", belief)

# Interactively step through the belief flattening over 100 predict-only
# steps.
ut.cell1_3_predict_only_widget(predict_beliefs, hallway)

Generalizing the model prediction uncertainty requires a convolution which is conceptually implemented as below

def predict_move_convolution(pdf: ut.Pdf, offset: int, kernel: ut.Pdf) -> ut.Pdf:
    N = len(pdf)
    kN = len(kernel)
    width = int((kN - 1) / 2)

    prior = np.zeros(N)
    for i in range(N):
        for k in range(kN):
            index = (i + (width - k) - offset) % N
            prior[i] += pdf[index] * kernel[k]
    return prior

This is a generalization of the previous formula so it returns the same result

belief = [0.05, 0.05, 0.05, 0.05, 0.55, 0.05, 0.05, 0.05, 0.05, 0.05]

prior = predict_move_convolution(belief, offset=1, kernel=[0.1, 0.8, 0.1])

ut.plot_beliefs(belief, prior, hallway=hallway, same_plot=False)

A more efficient implementation using numpy is here

# Using filterpy.

from filterpy.discrete_bayes import predict

belief = [0.05, 0.05, 0.05, 0.05, 0.55, 0.05, 0.05, 0.05, 0.05, 0.05]
prior = predict(belief, offset=1, kernel=[0.1, 0.8, 0.1])
ut.plot_beliefs(belief, prior, hallway=hallway, same_plot=False)

An example with a more complex and asymmetric model uncertainty is below
You can see how the belief becomes more uncertain

kernel = (0.05, 0.05, 0.6, 0.2, 0.1)
belief = [0.05, 0.05, 0.05, 0.05, 0.55, 0.05, 0.05, 0.05, 0.05, 0.05]
prior = predict(belief, offset=3, kernel=kernel)

ut.plot_beliefs(belief, prior, hallway=hallway, same_plot=False)

Integrating measurements and updates¶

Each model prediction loses information / knowledge (at best, there is no improvement)
With each sensor update, we incorporate the measurement into the estimate, which improves knowledge
The output of the update step is then fed into the next prediction

hallway = ut.get_hallway1()
# Sensor measurements are imperfect.
kernel = (0.1, 0.8, 0.1)

# We don't have any information. The dog could be anywhere.
prior1 = np.array([0.1] * 10)

# The sensor tells that the dog is in front of a door, but the sensor is
# imprecise.
sensor = 1
likelihood = ut.lh_hallway(hallway, z=sensor, z_prob=0.75)

posterior1 = update(likelihood, prior1)

y_lim = (0, 0.4)
ut.plot_beliefs(
    prior1,
    posterior1,
    title1="Prior 1",
    title2="Posterior 1",
    y_lim=y_lim,
    hallway=hallway,
    same_plot=False,
)

# The sensor says that the dog moved to the right.
move = 1
prior2 = predict(posterior1, move, kernel)
ut.plot_beliefs(
    posterior1,
    prior2,
    title1="Posterior1",
    title2="Prior2",
    y_lim=y_lim,
    hallway=hallway,
    same_plot=False,
)

# The probabilities move to the right and get smeared a bit.

# The sensor reports another door.
likelihood = ut.lh_hallway(hallway, z=1, z_prob=0.75)
posterior2 = update(likelihood, prior2)

ut.plot_beliefs(
    prior2,
    posterior2,
    title1="Prior2",
    title2="Posterior2",
    y_lim=y_lim,
    hallway=hallway,
    same_plot=False,
)
# The belief is that the dog is in front of position 1.

# Then the dog moves again.
move = 1
prior3 = predict(posterior2, move, kernel)
likelihood = ut.lh_hallway(hallway, z=0, z_prob=0.75)
posterior3 = update(likelihood, prior3)
ut.plot_beliefs(
    prior3,
    posterior3,
    title1="Prior3",
    title2="Posterior3",
    y_lim=y_lim,
    hallway=hallway,
    same_plot=False,
)

Part 2: A Bayes Dog Simulation¶

Cell 2.1: Interactive visualization¶

Goal:

Run the full filter (door sensor + movement sensor) on a dog moving around the hallway, and see the belief track it in real time

Implementation: ut.cell2_1_interactive()

The green line marks where the dog actually is at each step

ut.cell2_1_interactive()

Usage

Inputs
- Movement: the dog’s movement pattern (movement1: traverses all 10 positions sequentially; movement2: alternates between positions 0 and 1; movement3: a third pattern)
- Initial Prior: the starting belief (flat/uniform, all in position 3, or all in position 8)
- z_prob: door-sensor accuracy, from 1.0 (perfect) down to noisier values
Panels
- left: the dog’s movement trajectory, current position highlighted in green
- right: the belief distribution (prior or posterior), with red lines marking door positions

Guided usage

Select movement1 with z_prob=1
- Observe the prior tracks the dog well, and the estimate sharpens near doors and loosens on stretches with no doors
Set the initial prior to a wrong position (e.g., position 8) while the dog follows movement1
- Observe the prior starts wrong but is corrected by the data over time
Lower z_prob
- Observe the estimates get worse as the door sensor gets noisier
Switch to movement2 (alternating between 2 adjacent doors)
- Observe the sensor stays precise, since there is a steady stream of door information coming in

Cell 2.2: Bad sensor data¶

Goal:

Inject one bad (wrong) sensor reading into an otherwise-normal run, to see how the filter reacts to, and recovers from, an outlier measurement

Implementation: ut.cell2_2_interactive()

Consider a symmetric office geometry and a dog running in circles: [1, 1, 0, 1, 0, 1, 1, 0, 1, 0]. The correct answer is a filter aligned with the dog, but with uncertainty on which half of the hallway it is in
Then a completely wrong measurement is injected via a bad sensor: [1, 1, 0, 1, 0, 1, 1, 1, 0, 0]

ut.cell2_2_interactive()

Usage

Same inputs and panels as Cell 2.1, with the bad-sensor step baked into the simulated data

Guided usage

Step through the simulation
- Observe the first part of the run tracks normally
- Around step 14-16, observe the filter is “surprised” by the bad measurement: the belief spikes to a wrong position
- Observe it recovers over the following steps, as further correct measurements pull it back
Although this example is very simple, it incorporates all the concepts that a Kalman filter relies on