Comment by jvanderbot | Hacker News Reader

Comment by jvanderbot | Hacker News Reader

Parent Full thread

It's simpler than that. The linear algebra is actually easier.

The kalman filter tries to guess the hidden input that produced the measurements. It does so forming the minimization problem:

'minimize over x, the function [ actual_measurement - expected_measurement(x) ]^2/s^2', here 's' is sigma of noise.

This follows from the state estimation problem:

'maximize over x, the likelihood of seeing the actual_measurement', because the only term that matters in the likelihood function is -([x-expected(x)]/s )^2. (look at the exponent in the Normal distribution, or any exponential distribution really).

'actual_measurement' is a constant, so if it happens that the function 'expected_measurement' is linear, this is trivially solved directly as a convex optimization, and if you take derivative, equate to zero, and solve, you'll get the kalman filter update step.

If it so happens that the function is non-linear, well we just make a single netwton-rhapson step by linearizing the equation, minimizing, and returning the solution to the "pretend linearization".

This is basic calc + linear algebra at an undergrad level, but nobody bothered to tell you that.

---

It's also completely wrong. It's a hack from the 60s to maximize the likelihood function using a recursive, single-step linearization like this. A misreading of the Cramer Rao Lower Bound has "proven" to generations of engineers that this is optimal. It's not, not really.[^1]

Nowadays we have 10,000x more compute, and any one of the following _will_ produce better performance:

* Forming and solving the non-linear equation using many newton-rhapson steps

* Keeping a long history of measurements, and solving using many newton-rhapson steps over this batch

* Using sum-of-guassian representation to accomodate multi-modal measurement functions, esp when including the prior bullets

All of these were well covered by state estimation research from 80s to now, but again, the textbooks seem to be written in stone in 1972.

[^1]: (the cramer rao lower bound is only defined when all measurement likelihood functions are linearized at the true state - which is only possible asymptotically in a batch which preserves all the measurements - and not possible before time infinity and not possible with recursive filter)

> All of these were well covered by state estimation research from 80s to now, but again, the textbooks seem to be written in stone in 1972.

Do you have any good resources (online or textbook) you could recommend, as an introduction to these concepts, that is more modern / up-to-date?

I don't, sadly. The only coverage of this that was first-principles accessible was the course taught by Prof Stergios Romelioutis where I went to grad school.

You could do fine by reading some old books by Bar-Shalom. Any practical textbook like his would include all the "other stuff" about the EKF that helps you understand how nonperforming it often is.

But the actual derivation of the EKF is probably only one or two pages in such a textbook, which is a damn shame nobody includes it.

The background required is simply:

* Know the form of exponential family of PDFs (like Normal Gaussian)

* Bayes rule

* Recognize that to maximize f~= exp(-a), you have to minimize 'a'

* Know how to take derivative of matrix equation ('a', above)

* Solve it

* Use 'matrix inversion lemma' to transform solution to what KF/EKF provides.

Ah hell, I'll just write it up.

Probabilistic Robotics covers Kalman Filter from a first principles probabilistic viewpoint, and its extension the EKF. It's quite readable for someone with basic understanding of linear algebra, probability, and calculus. I believe it also has a refresher on these basics in the introduction.

http://www.probabilistic-robotics.org/

It all depends on your background. If you come from a Bayesian background, looking at a Kalman filter as a posterior update mechanism is very intuitive. A distribution over state that gets updated as more information arrives...

Yeah one needs to distinguish between the optimal state sequence and the optimal state at a particular time. In other words, a joint posterior (state trajectory up to now given all measurements up to now) vs a marginal posterior (state right now given all measurements up to now). the KF only gives you a marginal posterior. they are not the same

Both the Bayesian perspective and the optimization perspectice are legitimate ways of understanding the Kalman filter. I like the Bayesian perspective better.

Forgive me, I'm thoroughly confused by that dichotomy. How are they different? Approaching from bayes rule or a "maximum likelihood" approach produces the same results.

The problems of the filter are present in both.

Well, the derivations are different, and your comment seemed to imply that the maximum likelihood perspective was easier to understand.

The result is identical, the understanding is different. I would suggest that the Bayesian perspective leads to insights like the UKF [1] which IME is all round much better than the apparently better known EKF for approximating non linear systems.

[1] That is, it is generally easier to approximate a distribution than a non linear function.

Can we just use Neural Networks?

Reply on news.ycombinator.com