Hacker News Reader

Comment by TekMol | Hacker News Reader

Do I understand it correctly that Kalman filters are supposed to give a better estimate of a value from noisy observations than just averaging the observations?

Say I measured something 3 times and observed 7,8 and 9. My guess would be that the actual value is 8. Would a Kalman filter come up with a different estimate?

View on HN

> Do I understand it correctly that Kalman filters are supposed to give a better estimate of a value from noisy observations than just averaging the observations?

Yes, but with a big caveat. Your observations are related by something like the transition mechanism. You can't just apply a Kalman filter to every problem and expect to get better results.

A Kalman filter is traditionally used in estimating something that moves over time (but can be used for more than just this). Think a person moving in a video, or some other sort of random walk. By assuming some sort of relationship between two successive timepoints/measurements, like speed and current heading, we can blend the information from a model for motion with the model from noisy measurements to get a better estimate of the position/value or of the entire motion history.

If that motion model is meaningfully incorrect, then you don't get improved estimates.

A lot of the ways that people have extended them have to do with incorporating more sophisticated motion models, like dealing with wheel slippage in robotics, so your heading direction might have error now, etc.

Yes, because unlike an simple average you have a model for both what you are trying to measure and the measurement.

For example, one basic model for your example could be if you are trying to measure a constant with some initial uncertainty, say it's Gaussian with a standard deviation, and noisy measurements with say also an uncertainty with Gaussian distribution and some standard deviation. You can tune the initial uncertainty (a number) around the constant you are trying to estimate , and the uncertainty in the measurements (another number than may or may not change).

In this example a Kalman filter won't behave as an average. If the measurements are good (low uncertainty) they will converge quickly, if they are bad the estimate will jump around and take longer to converge.

Anyway, I made a mess, I'm not good at explaining...

And by the way, it's not true what people are suggesting here that Kalman filters are for moving things. They are used to estimate constants _all the time_ but yes, they're more popular for moving things.

In addition to what others (and I) said elsewhere, where the Kalman filter beats the simple average is when your samples are not identically and independently distributed. If they were, then yes, you can just take an average as justified by the law of large numbers.

The Kalman filter handles the case where your samples are correlated due to some (linear) dynamics (also your measurements don’t need to be directly of the quantity of interest, they can be a (linear) function of that quantity (plus Gaussian noise). Thus, the probability of you observing 8 for your second measurement changes given the knowledge that you observed a 7 as the first measurement. If you just take the sample average like you did above, that will not in general converge to the actual mean value.

KF gives you the optimal estimate (in the sense of maximum likelihood) for a (multivariate) Gaussian model.

What KF would give you in your example depends on what exactly the model is. But even in the simplest scenario imaginable you'd have to specify what expected value you start with, in the same way that you would in Bayes.

It would if you had some past history to work with. Let’s say that you measured the same object awhile ago and you want to incorporate that prior information in a principled way, while also letting the new measurements dominate if they give a very different result.

If you encode that language into a linear Gaussian model, you get KF.

The way I understand it, in a linear system with discrete measurements where you move and measure your position, averaging last 3 measurements, you are effectively lagging 1 step behind your actual position.

What Kalman filter does is that it estimates your position and then averages measurement with that, in essence bringing the value closer to where you are at the moment.

Having a delay in a feedback loop may cause oscillations. If you react way slower than you measure, you might not need Kalman filter. Proposed GPS example is relevant here, because position updates come in slowly.

Kalman filters are used for changing entities. Say you have a moving object. You could measure (with some errors) its position every second and use that as an estimate of where it is. Or use your position measurements in combination with an estimation of the object's speed that you can get from previous measurements and estimate where the object is. The second method is the Kalman filter.

To clarify, you mean completely independent speed measurements, right? As in speeds not derived from the position measurements? Otherwise, that feels like getting something from nothing.

I meant speeds derived from previous position measurements. Using those speeds is not getting something from nothing. It means using previous measurements to estimate where the object might be now then combine that estimate with current measurement to have the "best" estimate for its current position, for some definition of best.

I believe part of the cleverness of the Kalman Filter is that it works out the degree to which your measurements are correlated for you. I haven’t looked at it in a while, though.

Not your measurements. That correlation must be specified. It works out the correlations of your state (the thing you are estimating).

In the above example, their measurements are noisy mechanical states (position and momentum). However your measurements can be any (linear plus noise) function of the state, but you need the covariance of your sensor noise.

No. It's used differently.

Here's another way to understand Kalman filters that doesn't require statistics, but does require some knowledge of feedback controllers. Consider a model of a system of the form

  x'=Ax+Bu
  y=Cx

Here, we have a linear system with a state variable `x`, system dynamics `A`, control `u`, control dynamics, `B`, and observation `y`. This states that we have linear dynamics, but we can only observe some of the state variables. For example, perhaps we can observe position, but not velocity or acceleration. At the same time, we want those other variables because we need them for a feedback control or some kind of observation. In order to do this, we use machinery similar to a feedback controller. Define an observer system:

  xx' = Axx + Bu + L(y-Cxx)
  xx(0) = xx0

Here, we have a new observer variable `xx` that we want to converge to the true state variable `x`. To do this, we have introduced a new matrix of gains called `L`, which we call the observer gain for a Luenberger observer. The reason that this system is useful is that if we consider the error `e=x-xx`, and subsitute this into the above equations, we get:

  e' = x' - xx'
     = ...
     = (A-LC) e

From ODE theory, we know that `e` will converge to 0 if the real part of the eigenvalues of `A-LC` is negative. Hence, to facilitate this, we focus on trying to find an appropriate `L` that forces this condition. In order to do this, we note that the eigenvalues of `A-LC` are the same as it's transpose, `At-CtLt`. This leads to an optimization formulation:

  min 0.5 <Qee,ee> + 0.5 <Ruu,uu> st ee' = Atee + Ctuu, ee(0) = ee(0)

The notation `<x,y>` means inner product and is simply `xt y`. Here, we're essentially looking at the adjoint equation with a new kind of control `uu` and a new adjoint state variable `ee`. This is a linear quadratic control on the adjoint of the error generated by the Luenberger observer. There is a mostly open choice for `Q` and `R` that we discuss below. Through a long sequence of derivations that is nearly identical to that of linear quadratic control, we find that we eventually solve for a matrix P in the system:

  PAt + AP - PCt inv(R) C P = -Q

And then set the observer gain to `L=-PCt inv(R)`

Given this observer gain, we go back to our system above with `xx`, plug it in, and then solve. That system is constantly updated with observations of the original system in `y` and it produces an `xx` that converges very rapidly to the original state variable `x`. This gives us a way to view all of the state variables in the original equation even though we can't observe them all directly.

Now, to get to a full Kalman filter, there's a question of how to choose the matrices Q and R above. They could be almost anything. If you have an estimate of the what you believe the covariance of the errors are in the state and observations in the original equations, you get to a Kalman filter. Really, the derivation above is continuous, so it would be a Kalman-Bucy filter. Honestly, you don't need any statistics, though. Normally, just normalize the weights, so that all of the state variables are around the same size and then maybe adjust it on what you think is more important. It generally works just fine.

In short, a Kalman filter is a little machine that uses the same machinery as a feedback controller that rapidly converges to the state of a system of interest. This is useful because it's unlikely that all of those states can be observed directly. Due to how feedback controllers work, it is robust to errors and can handle variation or error in the observations.

So my very easy mental model of Kalman filter is: you feed model with some data (measurements, that are noisy, unstable) and some noise (usually Gaussian). Kalman filter actually kinda reduces precision by adding this noise, but you gain stability and less fluctuations and that's what makes it beautiful.

The Kalman filter does not require adding noise. The noise is a product of whatever phenomenon you are estimating. Normally we use noise in a model to cover up some behavior that is far to complicated to include in a more rigorous way. A classic example is the origin of Brownian motion. This probabilistic model came about to describe the motion of a large particle in a fluid of a smaller particles (e.g. a spec of dust in water). You could do physics and model every particle in the fluid and its collisions but that’s not tractable. Thus, the insight was to just model the large particle and turn the effects of collisions with the smaller ones into random disturbances.

Reply on news.ycombinator.com