Simple Algorithm
Artificial Intelligence · Hidden Layer · 24 min

Markov Chains, HMMs & Filters

Reasoning about processes that unfold in time.

A phone fuses jittery satellite fixes with its accelerometer, a speech recognizer turns noisy audio into words, a robot works out where it is from a door sensor. Each tracks a hidden state through time with the same recursion: push the belief through a model of how the world moves, then reweight it by what the sensors report. This lesson derives that recursion for discrete states (hidden Markov models), for linear-Gaussian states (the Kalman filter) and for everything else (particle filters).

What you’ll learn

  • Compute multi-step transition probabilities and stationary distributions of Markov chains, and state when a chain converges to its stationary distribution.
  • Derive the forward (filtering) recursion and the forward–backward smoothing algorithm for hidden Markov models, with their O(TS2)\order{TS^2} cost.
  • Derive the Viterbi algorithm for the most likely state sequence, and explain how its answer differs from smoothing.
  • Derive the Kalman filter's predict and update steps in one dimension, state them in general, and explain why particle filters resample.

Markov chains and their long run

A Markov chain is a sequence of random states X0,X1,…X_0,X_1,\dots with the Markov property: the future depends on the past only through the present, P(Xt+1∣X0,…,Xt)=P(Xt+1∣Xt)P(X_{t+1}\mid X_0,\dots,X_t)=P(X_{t+1}\mid X_t). For a finite, time-homogeneous chain, collect the transition probabilities in a row-stochastic matrix Tij=P(Xt+1=j∣Xt=i)T_{ij}=P(X_{t+1}=j\mid X_t=i). A distribution over states is a row vector, and one step multiplies it by TT:

πt+1=πtT,πt=π0Tt,Ts+t=TsTt  (Chapman–Kolmogorov).\pi_{t+1}=\pi_tT,\qquad \pi_t=\pi_0T^t,\qquad T^{s+t}=T^sT^t\ \ \text{(Chapman–Kolmogorov)}.

The weather of the umbrella world is such a chain: rain follows rain with probability 0.7, and a dry day is followed by rain with probability 0.3.

Predict before you look

It rains today. In the umbrella world's weather chain, what is the probability that it rains the day after tomorrow?

Show the answer

58 %

Sum over tomorrow's weather: 0.7×0.7+0.3×0.3=0.49+0.09=0.580.7\times0.7+0.3\times0.3=0.49+0.09=0.58. That is the (rain, rain) entry of T2T^2. A day later it is 0.5320.532, then 0.5130.513: the chain forgets today's weather.

A stationary distribution satisfies π=πT\pi=\pi T: a left eigenvector of TT with eigenvalue 1. A finite chain that is irreducible (every state can reach every other) and aperiodic (returns to a state are not restricted to multiples of some period greater than 1) has exactly one, and πt→π\pi_t\to\pi from every starting distribution. The time averages along one long run also converge to π\pi, which is what lets MCMC replace integrals by averages.

DerivationTwo states: how fast the chain forgets
  1. pt+1=pt(1−a)+(1−pt) b=b+(1−a−b) ptp_{t+1}=p_t(1-a)+(1-p_t)\,b=b+(1-a-b)\,p_t

    Let a=P(rain→dry)a=P(\text{rain}\to\text{dry}) and b=P(dry→rain)b=P(\text{dry}\to\text{rain}), and write ptp_t for the probability of rain on day tt:

  2. p∗=ba+bp^*=\frac{b}{a+b}

    The fixed point is the stationary probability of rain:

  3. pt−p∗=(1−a−b)t (p0−p∗)p_t-p^*=(1-a-b)^t\,(p_0-p^*)

    Subtracting the fixed-point equation, the distance to it shrinks by the factor λ2=1−a−b\lambda_2=1-a-b every day. That number is the second eigenvalue of TT (the first is 1):

  4. pt=12+12(0.4)tp_t=\tfrac12+\tfrac12(0.4)^t

    For the umbrella world a=b=0.3a=b=0.3, so p∗=12p^*=\tfrac12 and the gap shrinks by 0.40.4 a day: starting from rain, 1, 0.7, 0.58, 0.532, 0.513,…1,\ 0.7,\ 0.58,\ 0.532,\ 0.513,\dots In general the gap between ∣λ2∣|\lambda_2| and 1, the spectral gap, sets the speed of forgetting.

Two facts about stationarity come up again and again:

  • Detailed balance. If πiTij=πjTji\pi_iT_{ij}=\pi_jT_{ji} for all i,ji,j, then π\pi is stationary: sum over ii to get ∑iπiTij=πj∑iTji=πj\sum_i\pi_iT_{ij}=\pi_j\sum_iT_{ji}=\pi_j. Metropolis–Hastings and Gibbs samplers are built this way (Bayesian Reasoning).
  • PageRank. A random surfer follows a random link with probability α=0.85\alpha=0.85 and jumps to a uniformly random page otherwise. The ranking is the stationary distribution of this chain; the random jumps make it irreducible and aperiodic, so repeatedly multiplying by the transition matrix converges.

Periodicity is the trap: a chain that alternates deterministically between two states has stationary distribution (12,12)(\tfrac12,\tfrac12), but πt\pi_t flips back and forth forever.

Hidden Markov models and filtering

In a hidden Markov model the chain XtX_t is hidden, and at each step it emits an observation EtE_t through a sensor model P(Et∣Xt)P(E_t\mid X_t). The joint distribution is a Bayesian network shaped like a comb, with one evidence leaf per time step:

P(x0:t,e1:t)=P(x0)∏k=1tP(xk∣xk−1) P(ek∣xk).P(x_{0:t},e_{1:t})=P(x_0)\prod_{k=1}^tP(x_k\mid x_{k-1})\,P(e_k\mid x_k).

Four questions come up: filtering P(Xt∣e1:t)P(X_t\mid e_{1:t}), the belief now; prediction P(Xt+h∣e1:t)P(X_{t+h}\mid e_{1:t}); smoothing P(Xk∣e1:t)P(X_k\mid e_{1:t}) for a past step k<tk<t; and the most likely explanation arg max⁡x1:tP(x1:t∣e1:t)\argmax_{x_{1:t}}P(x_{1:t}\mid e_{1:t}).

DerivationThe forward recursion
  1. P(Xt+1∣e1:t+1)=α P(et+1∣Xt+1) P(Xt+1∣e1:t)P(X_{t+1}\mid e_{1:t+1})=\alpha\,P(e_{t+1}\mid X_{t+1})\,P(X_{t+1}\mid e_{1:t})

    Split off the newest observation and apply Bayes' rule. Given Xt+1X_{t+1}, the new observation is independent of the older ones:

  2. P(Xt+1∣e1:t)=∑xtP(Xt+1∣xt) P(xt∣e1:t)P(X_{t+1}\mid e_{1:t})=\sum_{x_t}P(X_{t+1}\mid x_t)\,P(x_t\mid e_{1:t})

    Predict by conditioning on the current state, which by the Markov property screens off the older evidence:

  3. f1:t+1=α Ot+1 T⊤f1:tf_{1:t+1}=\alpha\,O_{t+1}\,T^{\top}f_{1:t}

    Together, with f1:t=P(Xt∣e1:t)f_{1:t}=P(X_t\mid e_{1:t}) as a column vector and Ot+1O_{t+1} the diagonal matrix of P(et+1∣Xt+1=i)P(e_{t+1}\mid X_{t+1}=i), one step costs O(S2)\order{S^2} for SS states, and memory does not grow with tt:

  4. f1:1=0.818,f1:2=0.9×0.6270.9×0.627+0.2×0.373=0.883f_{1:1}=0.818,\qquad f_{1:2}=\frac{0.9\times0.627}{0.9\times0.627+0.2\times0.373}=0.883

    Umbrella world, umbrellas on days 1 and 2, with P(u∣rain)=0.9P(u\mid\text{rain})=0.9 and P(u∣dry)=0.2P(u\mid\text{dry})=0.2. Day 1 predicts 0.50.5 and updates to 0.45/(0.45+0.10)0.45/(0.45+0.10); day 2 predicts 0.7×0.818+0.3×0.182=0.6270.7\times0.818+0.3\times0.182=0.627 and updates:

The normalizers are worth keeping: 1/α1/\alpha at step tt is P(et∣e1:t−1)P(e_t\mid e_{1:t-1}), so their product is the likelihood of the whole observation sequence, P(e1:t)P(e_{1:t}), the quantity used to compare models and to learn parameters. Products of many small numbers underflow, so implementations normalize at every step and add up the logarithms of the normalizers.

Smoothing: forward–backward

Filtering uses only the past. Whether it rained yesterday is better judged once you know that the director carried an umbrella today as well, because rain tends to persist. Smoothing computes P(Xk∣e1:t)P(X_k\mid e_{1:t}) for k<tk<t by combining a forward message with a backward message bk+1:t(xk)=P(ek+1:t∣xk)b_{k+1:t}(x_k)=P(e_{k+1:t}\mid x_k), the probability of the future evidence given the state at kk.

DerivationThe forward–backward algorithm
  1. P(Xk∣e1:t)=α P(Xk∣e1:k) P(ek+1:t∣Xk)=α f1:k×bk+1:tP(X_k\mid e_{1:t})=\alpha\,P(X_k\mid e_{1:k})\,P(e_{k+1:t}\mid X_k)=\alpha\,f_{1:k}\times b_{k+1:t}

    Split the evidence at kk. Given XkX_k, the future evidence is independent of the past evidence (d-separation in the chain); ×\times multiplies vectors elementwise:

  2. bk+1:t(xk)=∑xk+1P(ek+1∣xk+1) bk+2:t(xk+1) P(xk+1∣xk),bk+1:t=T Ok+1 bk+2:tb_{k+1:t}(x_k)=\sum_{x_{k+1}}P(e_{k+1}\mid x_{k+1})\,b_{k+2:t}(x_{k+1})\,P(x_{k+1}\mid x_k),\qquad b_{k+1:t}=T\,O_{k+1}\,b_{k+2:t}

    The backward message satisfies a recursion that runs from tt down to kk, starting from bt+1:t=1b_{t+1:t}=\mathbf 1:

  3. P(R1∣u1,u2)=α (0.818×0.69, 0.182×0.41)=α (0.564, 0.075)≈(0.883, 0.117)P(R_1\mid u_1,u_2)=\alpha\,(0.818\times0.69,\ 0.182\times0.41)=\alpha\,(0.564,\ 0.075)\approx(0.883,\ 0.117)

    Umbrella world, day 1 given both days: b2:2=(0.7×0.9+0.3×0.2, 0.3×0.9+0.7×0.2)=(0.69, 0.41)b_{2:2}=(0.7\times0.9+0.3\times0.2,\ 0.3\times0.9+0.7\times0.2)=(0.69,\ 0.41). Day 2's umbrella raises the belief in rain on day 1 from 0.818 to 0.883:

  4. cost: O(tS2) time,O(tS) memory\text{cost: }\order{tS^2}\ \text{time},\qquad\order{tS}\ \text{memory}

    Run the forward pass and store every f1:kf_{1:k}, then sweep backward, multiplying as you go: all tt smoothed estimates for O(tS2)\order{tS^2} time and O(tS)\order{tS} memory, instead of O(t2S2)\order{t^2S^2} for tt separate computations.

The most likely sequence: Viterbi

For speech recognition, the right output is the single most likely sequence of words, not the most likely word at each instant considered separately. The most likely explanation maximizes the joint probability of the whole hidden path, and the Viterbi algorithm finds it by replacing the sum in the forward recursion with a maximum.

DerivationMax-product dynamic programming
  1. m1:t+1(xt+1)=P(et+1∣xt+1) max⁡xt[P(xt+1∣xt) m1:t(xt)]m_{1:t+1}(x_{t+1})=P(e_{t+1}\mid x_{t+1})\,\max_{x_t}\big[P(x_{t+1}\mid x_t)\,m_{1:t}(x_t)\big]

    Let m1:t(xt)m_{1:t}(x_t) be the probability of the best path that ends in xtx_t, jointly with the evidence. The best path ending in xt+1x_{t+1} must extend the best path ending in some xtx_t (optimal substructure):

  2. ψt+1(xt+1)=arg max⁡xtP(xt+1∣xt) m1:t(xt),xt∗=arg max⁡xm1:t(x),xk∗=ψk+1(xk+1∗)\psi_{t+1}(x_{t+1})=\argmax_{x_t}P(x_{t+1}\mid x_t)\,m_{1:t}(x_t),\qquad x_t^*=\argmax_xm_{1:t}(x),\quad x_k^*=\psi_{k+1}(x_{k+1}^*)

    Record which xtx_t achieved each maximum (a backpointer). At the end, start from the best final state and follow the backpointers to recover the path:

  3. log⁡m1:t+1(xt+1)=log⁡P(et+1∣xt+1)+max⁡xt[log⁡P(xt+1∣xt)+log⁡m1:t(xt)]\log m_{1:t+1}(x_{t+1})=\log P(e_{t+1}\mid x_{t+1})+\max_{x_t}\big[\log P(x_{t+1}\mid x_t)+\log m_{1:t}(x_t)\big]

    The cost is the same as filtering, O(tS2)\order{tS^2}, plus O(tS)\order{tS} backpointers. Implementations add log-probabilities instead of multiplying probabilities, which avoids underflow and turns the recursion into a shortest-path computation on a trellis.

Day12345
Umbrellayesyesnoyesyes
Filtered P(rain)0.8180.8830.1910.7310.867
Smoothed P(rain)0.8670.8200.3070.8200.867
Viterbi m(rain)m(\text{rain})0.8180.5150.0360.0330.021
Viterbi m(dry)m(\text{dry})0.1820.0490.1240.0170.002
Most likely pathrainraindryrainrain
Russell & Norvig's example. The Viterbi messages are not normalized after day 1; they shrink because they are joint probabilities of a path and the evidence. Here the most likely path agrees with the day-by-day smoothed guesses, but that is not guaranteed.
Check your understanding

Which statement about the Viterbi path and the smoothed estimates is true in general?

  1. The Viterbi path always consists of the individually most likely (smoothed) states
  2. Viterbi is a fast approximation to forward–backward smoothing
  3. The two can disagree, and the sequence of individually most likely states can even have probability zero
  4. They agree whenever the hidden chain is irreducible and aperiodic
Show the answer

C. The two can disagree, and the sequence of individually most likely states can even have probability zero

Smoothing maximizes each step's marginal separately; Viterbi maximizes the probability of the whole sequence. If the paths (A, B), (C, A) and (C, C) have probabilities 0.4, 0.3 and 0.3, the individually most likely states are C and then B, a sequence of probability zero, while Viterbi returns (A, B).

So far the model was given. Baum–Welch learns TT, the sensor model and the prior from observation sequences alone. It is the EM algorithm: forward–backward computes the expected number of times each transition and each emission occurred, and the parameters are re-estimated as normalized expected counts. Each iteration never decreases the likelihood P(e1:t)P(e_{1:t}), but it can stop at a local optimum, so restarts matter.

Continuous states: the Kalman filter

Position and velocity are continuous. In a linear-Gaussian state-space model, the state evolves linearly with Gaussian noise and the sensor measures a linear function of it with Gaussian noise:

xt=Fxt−1+wt,wt∼N(0,Q);zt=Hxt+vt,vt∼N(0,R).\mathbf x_t=F\mathbf x_{t-1}+\mathbf w_t,\quad\mathbf w_t\sim\mathcal N(\mathbf 0,Q);\qquad\mathbf z_t=H\mathbf x_t+\mathbf v_t,\quad\mathbf v_t\sim\mathcal N(\mathbf 0,R).

A Gaussian belief stays Gaussian under both steps, so the Kalman filter only has to track a mean and a covariance.

DerivationOne dimension: predict, then combine precisions
  1. μ−=μ,σ−2=σ2+q\mu^-=\mu,\qquad\sigma_-^2=\sigma^2+q

    Take a random walk xt=xt−1+wtx_t=x_{t-1}+w_t with Var⁡(wt)=q\Var(w_t)=q, measured as zt=xt+vtz_t=x_t+v_t with Var⁡(vt)=r\Var(v_t)=r. Predict: independent variances add.

  2. 1σ′2=1σ−2+1r,μ′=r μ−+σ−2 zσ−2+r\frac1{\sigma'^2}=\frac1{\sigma_-^2}+\frac1r,\qquad\mu'=\frac{r\,\mu^-+\sigma_-^2\,z}{\sigma_-^2+r}

    Update: the posterior is proportional to N(x;μ−,σ−2) N(z;x,r)\mathcal N(x;\mu^-,\sigma_-^2)\,\mathcal N(z;x,r). Completing the square in xx, precisions add and the mean is a precision-weighted average:

  3. K=σ−2σ−2+r,μ′=μ−+K (z−μ−),σ′2=(1−K) σ−2K=\frac{\sigma_-^2}{\sigma_-^2+r},\qquad\mu'=\mu^-+K\,(z-\mu^-),\qquad\sigma'^2=(1-K)\,\sigma_-^2

    Rewrite with the Kalman gain KK, the fraction of the surprise z−μ−z-\mu^- (the innovation) that the estimate absorbs:

  4. μ′=0+23×2=43,σ′2=13×2=23\mu'=0+\tfrac23\times2=\tfrac43,\qquad\sigma'^2=\tfrac13\times2=\tfrac23

    Example: μ=0\mu=0, σ2=1\sigma^2=1, q=r=1q=r=1 and a measurement z=2z=2. The prediction has variance 2, so K=2/3K=2/3:

predict:μ−=Fμ,Σ−=FΣF⊤+Qupdate:K=Σ−H⊤(HΣ−H⊤+R)−1,μ′=μ−+K(z−Hμ−),Σ′=(I−KH) Σ−\begin{aligned}\text{predict:}\quad&\boldsymbol\mu^-=F\boldsymbol\mu,\qquad\Sigma^-=F\Sigma F^\top+Q\\ \text{update:}\quad&K=\Sigma^-H^\top\big(H\Sigma^-H^\top+R\big)^{-1},\qquad\boldsymbol\mu'=\boldsymbol\mu^-+K\big(\mathbf z-H\boldsymbol\mu^-\big),\qquad\Sigma'=(I-KH)\,\Sigma^-\end{aligned}
The general filter. Each step costs a few matrix products and one inversion of a matrix the size of the measurement. For linear-Gaussian models it computes the exact posterior; without the Gaussian assumption it is still the best linear estimator in mean squared error.
Check your understanding

A Kalman filter's predicted variance is σ−2=4\sigma_-^2=4 and the sensor noise variance is r=1r=1. A measurement arrives 5 units above the predicted mean. What happens?

  1. The mean moves up 4 units and the variance drops to 0.8
  2. The mean moves up 5 units and the variance drops to 1
  3. The mean moves up 2.5 units and the variance drops to 2.5
  4. The mean moves up 1 unit and the variance drops to 3.2
Show the answer

A. The mean moves up 4 units and the variance drops to 0.8

K=4/(4+1)=0.8K=4/(4+1)=0.8, so the mean moves 0.8×5=40.8\times5=4 units and the variance becomes (1−0.8)×4=0.8(1-0.8)\times4=0.8, below both the prediction's 4 and the sensor's 1. A precise sensor (r≪σ−2r\ll\sigma_-^2) pulls the estimate most of the way to the measurement; a noisy one (r→∞r\to\infty) gives K→0K\to0, and the measurement is ignored.

Nonlinear models are handled by linearizing FF and HH around the current estimate (the extended Kalman filter) or by pushing a few deterministically chosen sigma points through the nonlinearity (the unscented Kalman filter). Both keep a single Gaussian, so neither can represent a belief with two separate peaks, such as a robot that might be in either of two identical corridors.

Particle filters, dynamic Bayes nets, and where to go deeper

When the belief is multimodal or the model is far from linear-Gaussian, represent the belief by NN samples, called particles. A particle filter runs the same predict–update loop on them, and adds a third step, resampling:

text
function PARTICLE-FILTER(particles x[1..N], action a, observation z):
    for i = 1 to N:
        x[i] ← a sample from P(X_t | X_{t−1} = x[i], a)    # predict: move each particle
        w[i] ← P(z | X_t = x[i])                            # update: weight by the sensor
    normalize w so that it sums to 1
    x ← N draws, with replacement, from x[1..N] with probabilities w   # resample
    return x                                                # the new belief, as N samples

Sequential importance resampling with the motion model as proposal, the "bootstrap" filter of Gordon, Salmond & Smith (1993). The empirical distribution of the particles approximates the filtering distribution, with error of order 1/N1/\sqrt N at each fixed time.

All of these models are dynamic Bayesian networks (DBNs): a Bayesian network slice repeated over time. An HMM is a DBN with one discrete state variable per slice, and the Kalman filter's model is a DBN with linear-Gaussian conditionals. Factoring the state into dd variables keeps the transition model small (dd small CPTs instead of a 2d×2d2^d\times2^d matrix), but exact filtering still needs all 2d2^d joint values of the belief: after a few steps, every state variable becomes correlated with every other, even when their dynamics interact only locally. Approximate filters, such as projecting the belief onto a factored form after each step (Boyen & Koller, 1998) and particle filters, are the practical answer.

Key takeaways

  • A Markov chain evolves as πt+1=πtT\pi_{t+1}=\pi_tT. Irreducible, aperiodic finite chains converge to a unique stationary distribution π=πT\pi=\pi T, at a rate set by the second eigenvalue (for two states, 1−a−b1-a-b).
  • Filtering in an HMM is predict-then-update: f1:t+1=α Ot+1T⊤f1:tf_{1:t+1}=\alpha\,O_{t+1}T^{\top}f_{1:t}, at O(S2)\order{S^2} per step; the normalizers multiply to the likelihood P(e1:t)P(e_{1:t}).
  • Smoothing multiplies forward and backward messages, P(Xk∣e1:t)∝f1:k×bk+1:tP(X_k\mid e_{1:t})\propto f_{1:k}\times b_{k+1:t}; forward–backward gives every smoothed estimate in O(tS2)\order{tS^2} time.
  • Viterbi replaces the sum by a max and follows backpointers to the single most likely sequence, which can differ from the sequence of individually most likely states. Baum–Welch learns the model by EM from forward–backward's expected counts.
  • The Kalman filter predicts by adding process noise and updates by adding precisions, with gain K=Σ−H⊤(HΣ−H⊤+R)−1K=\Sigma^-H^\top(H\Sigma^-H^\top+R)^{-1}; it is exact for linear-Gaussian models. Particle filters handle anything else with weighted samples, and resample to fight weight degeneracy.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A two-state chain moves from AA to BB with probability 0.1 and from BB to AA with probability 0.3. What fraction of the time does it spend in AA in the long run?

  1. 0.25
  2. 0.5
  3. 0.75
  4. 0.9
Show the answer

C. 0.75

p∗=b/(a+b)=0.3/(0.1+0.3)=0.75p^*=b/(a+b)=0.3/(0.1+0.3)=0.75, where a=0.1a=0.1 is the rate of leaving AA and b=0.3b=0.3 the rate of entering it. Check balance: the flow A→BA\to B is 0.75×0.1=0.0750.75\times0.1=0.075, and B→AB\to A is 0.25×0.3=0.0750.25\times0.3=0.075.

Question 2

An HMM has S=100S=100 hidden states and you observe a sequence of length T=1000T=1000. About how many multiply–add operations does the forward algorithm need to compute P(e1:T)P(e_{1:T})?

  1. About 10510^5
  2. About 10710^7
  3. About 10910^9
  4. About 1001000100^{1000}
Show the answer

B. About 10710^7

Each step multiplies a 100-vector by a 100×100100\times100 matrix, S2=104S^2=10^4 operations, and there are T=1000T=1000 steps: TS2=107TS^2=10^7. Summing over all STS^T hidden sequences directly would be hopeless.

Question 3

A speech recognizer must output one transcript for a recorded utterance, using an HMM over phones. Which computation should it run?

  1. Filtering, P(Xt∣e1:t)P(X_t\mid e_{1:t}) at every step
  2. Smoothing, then the most likely phone at each step
  3. The Viterbi algorithm
  4. Prediction, P(Xt+1∣e1:t)P(X_{t+1}\mid e_{1:t})
Show the answer

C. The Viterbi algorithm

A transcript is one sequence, so the right objective is the most likely sequence, arg max⁡x1:tP(x1:t∣e1:t)\argmax_{x_{1:t}}P(x_{1:t}\mid e_{1:t}). Stringing together per-step maxima can produce a sequence that the model considers unlikely or even impossible.

Question 4

Two independent sensors measure the same quantity: one reads 10 with noise variance 4, the other reads 14 with noise variance 4. With a flat prior, what is the Gaussian posterior?

  1. Mean 12, variance 2
  2. Mean 12, variance 4
  3. Mean 12, variance 8
  4. Mean 14, variance 2
Show the answer

A. Mean 12, variance 2

Precisions add, 1/4+1/4=1/21/4+1/4=1/2, so the variance is 2, and the mean is the precision-weighted average, here the plain average 12. This is exactly the Kalman update, with one sensor playing the role of the prediction.

Question 5

What problem does the resampling step of a particle filter address?

  1. It removes the bias of the motion model
  2. It makes the particles independent of each other
  3. It reduces the cost of each step from O(N2)\order{N^2} to O(N)\order{N}
  4. Weight degeneracy: without it, a few particles soon carry almost all the weight
Show the answer

D. Weight degeneracy: without it, a few particles soon carry almost all the weight

Weights are running products of likelihoods, so their spread grows over time. Resampling replaces the weighted set by an unweighted one concentrated where the posterior mass is, at the price of some duplicated particles.

Go deeper

Further reading

  • S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapter 14.
  • L. R. Rabiner, "A tutorial on hidden Markov models and selected applications in speech recognition," Proceedings of the IEEE 77(2), 257–286 (1989).
  • R. E. Kalman, "A new approach to linear filtering and prediction problems," Journal of Basic Engineering 82(1), 35–45 (1960).
  • S. Thrun, W. Burgard & D. Fox, Probabilistic Robotics (MIT Press, 2005).