HW 3 -- Kalman Filters & Approximate Inference

The questions below are due on Monday March 02, 2026; 11:59:00 PM.
 

This week's Colab notebook can be found here: Colab Notebook (Click Me!)

1) Gaussians§

1.1) §

Let A \sim \mathcal{N}(\mu_A, \sigma_{A}^{2}) and let B | A \sim \mathcal{N} (A, \sigma^{2}_{B|A}). We can show the distribution A | B = b is a univariate Gaussian.

For parsing purposes, enter \mu_A as mu_A, \sigma_{A} as sigma_A, \sigma_{B \mid A} as sigma_BA, b as b, and the ^ character for exponentation.

1.2) §

1.3) §

1.4) §

1.5) §

2) Continuous PGMs §

Consider a Bayesian network with three one-dimensional continuous variables: A, B, and C. Let A \sim \mathcal{N}(1, 1), B \sim \mathcal{N}(2, 4), and C \sim \mathcal{N}(A + B, 1).

2.1) §

2.2) §

2.3) §

2.4) §

2.5) §

2.6) §

2.7) §

2.8) §

2.9) §

2.10) §

3) HMMs: Are my leftovers (still) edible? §

I use an HMM to model the state of my leftover food over time. The state space is \{\textit{tasty}, \textit{smelly}, \textit{furry} \}. Initially, I'm sure they're tasty: P(S_0 = \textit{tasty}) = 1. The state transition model is:

3.1) Sampling Formulas §

You decide to estimate P(S_2) by forward (prior) sampling. You generate 100 sample trajectories of length 3 for your leftovers. Given those trajectories what are the three terms to construct an estimate of P(S_2)?

4) Properties of Viterbi§

Maximillian thinks the Viterbi algorithm is too complicated and we could get away without the backward “decoding” pass, and instead just return the maximum of the marginal distribution at each time step.

You know better than Max! In the HMM below, provide a sequence of three observations for which Max will get the wrong answer, but Viterbi decoding will be correct Your answer should be a Python list of three True/False values. Assume that the initial distribution is uniform.

5) HMMs and Kalman Filters§

6) Kalman Filtering§

Consider the following one-dimensional continuous-state system:

where w_t \sim N(0, \sigma_w^2) and v_t \sim N(0, \sigma^2_v). This is the same linear-Gaussian model that we discussed in lecture, but we now have a control input u_t.

Let us say that a = 2, h = 10, \sigma^2_w = 1 and \sigma^2_v = .25. Let us also say that the initial estimate of the state is

1. Given a single action u_0 = 1, what is the mean of x_1?

   Enter a number that is accurate to within 1.0e-5. You can also enter a python expression that will evaluate to a number (e.g., 3*2 + 4 - 7/11.0).

   

2. Given a single action u_0 = 1, what is the variance of x_1?

   Enter a number that is accurate to within 1.0e-5. You can also enter a python expression that will evaluate to a number (e.g., 3*2 + 4 - 7/11.0).

   

3. After the action u_0 = 1, what is the expected measurement y_1?

   Enter a number that is accurate to within 1.0e-5. You can also enter a python expression that will evaluate to a number (e.g., 3*2 + 4 - 7/11.0).

   

4. Given a subsequent measurement y_1 = 0, what is the variance of the posterior on x_1?

   Enter a number that is accurate to within 1.0e-5. You can also enter a python expression that will evaluate to a number (e.g., 3*2 + 4 - 7/11.0).

   

5. Given a subsequent measurement y_1 = 0, what is the mean of the posterior on x_1?

   Enter a number that is accurate to within 1.0e-5. You can also enter a python expression that will evaluate to a number (e.g., 3*2 + 4 - 7/11.0).

   

6. The covariance of the posterior will ...

   	always get smaller over time
   	always get bigger over time
   	get bigger or smaller over time depending on the relative magnitudes of a to h
   	get bigger or smaller over time depending on the relative magnitudes of \sigma_w to \sigma_v

   

7) Coding: Kalman Filter§

Let's implement the Kalman Filter for the one-dimensional continuous-state system from the previous section.

7.1) Kalman Filter Warmup§

Return an Gaussian object with mean=0, std=2. Please see the provided code for the definition of Gaussian.

For reference, our solution is 1 line(s) of code.

7.2) Kalman filter process model§

Implement the process step of a 1D Kalman filter, given a Gaussian prior distribution, a process model a, \sigma^2_w, and a control u.

For reference, our solution is 4 line(s) of code.

7.3) Kalman filter measurement model§

Implement the measurement step of a 1D Kalman filter, given a prior mean and variance, a measurement model h, \sigma^2_v, and a received measurement y.

For reference, our solution is 18 line(s) of code.

7.4) Kalman filter§

Combine the process and measurement steps into a single estimator that takes a prior, a process model, a measurement model, a list of controls, measurements, and returns a posterior.

For reference, our solution is 9 line(s) of code.

In addition to all the utilities defined at the top of the Colab notebook, the following functions are available in this question environment: kf_measurement, kf_process. You may not need to use all of them.

7.5) Kalman Filter Visualization§

We have created a visualization tool in Colab for the filtering process. You can run the code blocks and an animation of the filtered Gaussian in each step will be shown. There is also a plot showing the line chart of ground-truth locations, measurements, and posteriors.

Run the animation that visualizes the distribution of x_t after each process update and observation update. Use the "next frame" button (to the right of "play") to see what happens one step at a time.

Now look at the plot below the animation. The plot shows a green region that is the Kalman filter's mean +/- one stdev for each timestep after the observation update.

8) Sampling§

8.1) Sampling types§

8.2) Sampling efficiency§

Kullback-Leibler divergence is an estimate of how similar two distributions are, and for discrete distributions it is given by

Let us assume that P is the target distribution, and Q is the proposal distribution, and we are performing rejection sampling.

What does this mean for our sampling strategy?

9) More Sampling§

9.1) Gibbs Sampling§

Consider the following 3 node factor graph:

The table on the right gives three different potential tables for the factor. Gibbs sampling did a poor job on generating samples that reflected the joint of these three variables for one of these potential tables. Which was it?

9.2) Sampling in Bayes net§

Consider the following Bayes net.

We are interested in drawing samples from the distribution described by this network, conditioned on evidence, using ancestral sampling with rejection.

1. Is this a good way to sample from P(K \mid B = b)?

   	True
   	False

   

2. Is this a good way to sample from P(B \mid K = k)?

   	True
   	False

   

9.3) Markov Blanket§

Consider the Bayes net from the above question.

1. Enter the set of nodes in the Markov Blanket of node G, e.g. ['B','D'].

   

2. Enter the set of nodes in the Markov Blanket of node D, e.g. ['B','D'].

   

10) Gibbs Sampling§

We are going to study Gibbs sampling in a concrete case, to illustrate some of the principles. Assume that we choose variables to change uniformly in the Gibbs procedure. Consider the following Bayes net with three binary variables, A, B, and C.

1. What's the joint distribution? We've filled in most of the values for you.

2. In Gibbs sampling, say we start with assignment (0, 0, 0). Let's calculate some probabilities of a single step.

3. Now say we start with assignment (1, 0, 0).

4. Recall that Gibbs sampling implicitly constructs a Markov chain where the states are assignments of values to variables, and T(x, x') is the probability of moving from x to x'. One step in showing that the true joint distribution of this model (\pi) is the stationary distribution of this Markov chain, is to show that, for all x and x',
   \pi(x) \cdot T(x, x') = \pi(x') \cdot T(x', x).
   This is called detailed balance, which implies stationarity because it says the probability leaving is the same as the probability entering on every iteration. Let's verify the equation holds for a pair of states.

11) Particle Filter§

Consider a domain in which the forward transition dynamics are “hybrid” in the sense that

that is, with probability p, the state will hop forward one unit in expectation, and with probability 1-p, it will hop backward one unit in expectation, with variance 0.1 in each case.

Assume additionally that the observation model P(Y_t = y_t \mid X_t = x_t) = \mathtt{Uniform}(x_{t}-1, x_{t}+1)(y_t)

1. What is E[X_t \mid X_{t-1} = x]?

   	x-2
   	x + 2p - 1
   	p^2 * x
   	p * x

   

2. Assuming p=0.5, what is Var[X_t \mid X_{t-1} = x]?

   	0.1
   	0.2
   	1.1
   	0.05

   

3. You know the initial state of the system X_0 = 0. Your friend Norm thinks it’s fine to initialize a particle filter with a single particle at 0. What do you think?

   	This is fine and we can continue with a single particle.
   	We should initialize our pf with N copies of this particle.

   

4. Norm runs the filter for two steps with no observations several times and is trying to decide whether there could be bugs in the code. Assuming p=0.5, for each of the following sets of particles, indicate whether it is (a) fairly likely (b) quite unlikely (c) completely impossible:

   1. {-2.05, -1.95, -0.1, 0.1, 1.9, 2.1}

      	(a) fairly likely
      	(b) quite unlikely
      	(c) completely impossible

      

   2. {-2.01, -1.9, -1.0, 0.1, 0, 2.1}

      	(a) fairly likely
      	(b) quite unlikely
      	(c) completely impossible

      

   3. {-20, -2.01, -2.001, .01, .001, 1.99, 1.999}

      	(a) fairly likely
      	(b) quite unlikely
      	(c) completely impossible

      

5. Norm initializes the filter with particles {-2.05, -1.95, -0.1, 0.1, 1.9, 2.1} and then gets an observation of -1.0. Which of the following is a plausible posterior, assuming resampling without noise?

   	{-1.95, -0.1, -1.95, -1.95, -0.1, -0.1, -0.1}
   	{-1.95, -.01}
   	{0.1, 0.1, 0.1, -0.1, -0.1, -0.1}
   	{-1.96, -0.11, -1.94, -1.97, -0.11, -0.09, -0.12}

   

11.1) Particle Filter Code and Visualization§

We've created a visualization and code simulation in Colab for this problem, using the same hybrid dynamics model at the start of this problem. You can run the code block to run the particle filter on the problem, experiment with different parameters, and plot the results.

Experiment with the number of particles. The animation shows the location of the particles and ground truth after each timestep. The line plot shows the location over time, as well as a green shaded region indicating the particle filter's mean +/- one stdev of the particles.

12) Feedback§

1. How many hours did you spend on this homework?

   -- 2 3 4 5 6 7 8 more

   

2. Do you have any comments or suggestions (about the problems or the class)?