Kalman Filter for Bayesians

post by SatvikBeri · 2018-10-22T17:06:02.783Z · LW · GW · 6 comments

Summary: the Kalman Filter is Bayesian updating applied to systems that are changing over time, assuming all our distributions are Gaussians and all our transformations are linear.

Preamble - the general Bayesian approach to estimation: the Kalman filter is an approach to estimating moving quantities. When I think about a Bayesian approach to estimation, I think about passing around probability distributions: we have some distribution as our prior, we gather some evidence, and we have a new distribution as our posterior. In general, the mean of our distribution measures our best guess of the underlying value, and the variance represents our uncertainty.

In the Kalman filter, the only distribution we use is the normal/Gaussian distribution. One important property of this is that it can be parameterized completely by the mean and variance (or covariance in the multi-variate case.) If you know those two values, you know everything about the distribution.

As a result, people often talk about the Kalman filter as though it's estimating means and variances at different points, but I find it easier to think of it as outputting a distribution representing our current knowledge at any point.

The simplest case: taking multiple measurements of a fixed quantity with an accurate but imprecise sensor. For example, say we're trying to measure the temperature with a thermometer that we believe is accurate but has a variance of 5 degrees${}^2$.

We're very bad at estimating temperatures by hand, so let's say our prior distribution is that the temperature is somewhere around 70 degrees with a variance of 20, or $N(70,20)$ . We take one readout from the thermometer, which (by assumption) yields a normal distribution centered around the true temperature with variance 5: N(t, 5). The thermometer reads 78. What's our new estimate?

Well, it turns out there's a simple rule for combining Normal distributions with known variance: if our prior is $N({\mu }_0,{\sigma }_0^2)$ and our observation is $N({\mu }_1,{\sigma }_1^2)$ then the posterior has mean

(1) ${\mu }^{\prime }={\mu }_0+k({\mu }_1-{\mu }_0)$

(2) ${\sigma }^{{}^{\prime }2}={\sigma }_0^2-k{\sigma }_0^2$ , where

(3) $k=\frac{{\sigma }_0^2}{{\sigma }_0^2+{\sigma }_1^2}$ is called the Kalman gain.

So if our first reading is 72, then $k$ is $\frac{20}{25}=.8$, ${\sigma }^{\prime 2}=20-.8\ast 20=4$, and ${\mu }^{\prime }=70+.8\ast (78-70)=76.4$ . If we take another reading, we'd apply the same set of calculations, except our prior would be $N(76.4,4)$.

Some intuition: let's look at the Kalman gain. First, note that its value is always between 0 or 1. Second, note that the gain is close to 0 if ${\sigma }_1^2$ is large compared to ${\sigma }_0^2$ , and close to 1 in the opposite case. Intuitively, we can think of the Kalman gain as a ratio of how much we trust our new observation relative to our prior, where the variances are a measure of uncertainty.

What happens to the mean? It moves along the line from our prior mean to the observation. If we trust the observation a lot, $k$ is nearly 1, and we move almost all the way. If we trust the prior much more than the observation, we adjust our estimate very little. And if we trust them equally, we take the average of the two.

Also note that the variance always goes down. Once again, if we trust the new information a lot, the variance goes down a bunch. If we trust the new information and our prior equally, then the variance is halved.

Finally, as a last tidbit, it doesn't matter whether which distribution is the prior and which is the observation in this case - we'll get exactly the same posterior if we switch them around.

Adding a sensor: none of the math above assumes we're always using the same sensor. As long as we assume all our sensors draw from distributions centered around the true mean and with a known (or estimated) variance, we can update on observations from any number of sensors, using the same update rule.

Measuring multiple quantities: what if we want to measure two or more quantities, such as temperature and humidity? Then we now have multivariate normal distributions. While a single-variable Gaussian is parameterized by its mean and variance, an $n$-variable Gaussian is parameterized by a vector of $n$ means and an $n\times n$ covariance matrix: $N(\overrightarrow{\mu },\Sigma )$.

Our update equations are the multivariate versions of the equations above: given a prior distribution $N(\overrightarrow{{\mu }_0},{\Sigma }_0)$ and a measurement $\overrightarrow{{\mu }_1}$ from a sensor with covariance matrix ${\Sigma }_1$, our posterior distribution is $N(\overrightarrow{{\mu }^{\prime }},{\Sigma }^{\prime })$ with:

(4) $\overrightarrow{{\mu }^{\prime }}=\overrightarrow{{\mu }_0}+K\overrightarrow{{\mu }_1}$

(5) ${\Sigma }^{\prime }={\Sigma }_0-K{\Sigma }_0$

(6) $K={\Sigma }_0({\Sigma }_0+{\Sigma }_1{)}^{-1}$

These are basically just the matrix versions of equations (1), (2), and (3).

---

Adding predictable change over time: so far, we've covered Bayesian updates when you're making multiple measurements of some static set of quantities. But what about when things are changing? A classic example is a moving car. For this case, let's assume we're measuring two quantities – position and velocity.

For a bit more detail, say at time $0$ our vector $\overrightarrow{{\mu }_0}=\left(\begin{array}{c}{x}_0\\ v_0\end{array}\right)$ where $x_0$ is the position and $v_0$ is velocity. Then at time $\tau$ , we might expect the position to be $x_0+\tau \cdot v_0$, and the velocity to be the same on average. We can represent this with a matrix: $\overrightarrow{{\mu }^{\prime }}=F\overrightarrow{{\mu }_0}$ , where $F$ is the matrix $\left(\begin{array}{c}1\tau \\ 01\end{array}\right)$ .

More generally, say our belief at time $t$ is $N(\overrightarrow{{\mu }_0},{\Sigma }_0)$. Then our belief at time $t+\tau$, before we make any new observations, should be $FN(\overrightarrow{{\mu }_0},{\Sigma }_0)$. Fortunately there's a simple formula for this: $FN(\overrightarrow{{\mu }_0},{\Sigma }_0)=N(F{\mu }_0,F{\Sigma }_0{F}^T)$.

Putting it all together, say our belief at time $t$ is $N(\overrightarrow{{\mu }_0},{\Sigma }_0)$ , and at time $t+\tau$ we measure a value $\overrightarrow{{\mu }_1}$ from a sensor with covariance matrix ${\Sigma }_1$, then we perform the Bayesian update with $FN(\overrightarrow{{\mu }_0},{\Sigma }_0)=N(F{\mu }_0,F{\Sigma }_0{F}^T)$ as the prior and $N(\overrightarrow{{\mu }_1},{\Sigma }_1)$ as the posterior:

(7) $\overrightarrow{{\mu }^{\prime }}=\overrightarrow{F{\mu }_0}+K\overrightarrow{{\mu }_1}$

(8) ${\Sigma }^{\prime }=F{\Sigma }_0{F}^T-K{\Sigma }_0$

(9) $K=F{\Sigma }_0{F}^T(F{\Sigma }_0{F}^T+{\Sigma }_1{)}^{-1}$

And that's the main idea! We just adjust our prior by applying a transition function/matrix to it first In practice, the Kalman filter tends to quickly converge to true values, and is widely used in applications such as GPS tracking.

6 comments

Comments sorted by top scores.