5 ms·

Kalman Filter Tutorial

358 points by ColinWright 2y ago

jtrueb 2y ago
Every time that one comes up, this one comes up https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt... (and vice versa)
- elcritch 2y ago
  That one is one of my favorite resources on Kalman filters. Deriving it from Bayesian principles make it much more intuitive. It also makes adapting or modifying the filters easier to understand. Using Jupyter notebooks is really great too.
magic_hamster 2y ago
Not sure why, but I get this vague notion that the author might have written a book.
- esafak 2y ago
  If it takes you a whole book to explain Kalman filtering you're doing it wrong.
  - elcritch 2y ago
    Perhaps to get the basics sure, but to go through all the edge cases and parameter tuning and failure modes will easily fill a small book. That's not even going into modifying Kalman filters for non-linear systems.
    - esafak 2y ago
      Here's a survey that covers all of Bayesian filtering in 60 pages, plus references. https://www.researchgate.net/publication/238689222 https://www.researchgate.net/publication/238689222
      - elcritch 2y ago
        That's a nice survey. However for kalman filters it doesn't give practical examples or the different techniques to estimate the parameters. It doesn't cover adaptive modifications to kalmans like you often want in robotics or other applications to handle non-process external events which kalmans don't handle well. Et cetera, there's lots of reasons book forms on a topic can be useful.
blharr 2y ago
The first example of tracking, is this the same thing as dead reckoning? I've always been confused on the term "tracking" since it is used a lot in common speech, but seems to mean some specific type of 'tracking'
- defrost 2y ago
  Dead reckoning is a form of prediction, based on past evidence that indicates location then, you are reckoning (best guessing) a current position and detrmining a direction to move forward to reach some target. "Past evidence that indicates" is deliberate phrasing, in the majority of these examples we are looking at acquired data with noise; errors, instrument noise, missing returns, etc. "Tracking" is multi-stage, there's a desired target to be found (or to be declared absent) in noisy data .. that's pattern search and locking, the trajectory (the track) of that target must be best guessed, and the best guess forward prediction can be used to assist the search for the target in a new position. This is not all that can be done with a Kalman filter but it's typical of a class of common applications.
- hansvm 2y ago
  Kind of. "Tracking", here, means providing some kind of `f(time) -> space` API. Dead reckoning is a mechanism for incorporating velocity and whatnot into a previously estimated position to estimate a new position (and is also one possible way to implement tracking, usually with compounding errors). The Kalman filter example is better than just dead reckoning. For a simple example, imagine you're standing still but don't know exactly where. You have an API (like GPS) that can estimate your current position within some tolerance. If you're able to query that API repeatedly and the errors aren't correlated, you can pinpoint your location much more precisely. Back to tracking with non-zero velocity, every new position estimate (e.g., from GPS) can be incorporated with all the information you've seen so far, adjusting your estimates of velocity, acceleration, and position and giving you a much more accurate current estimate but also better data for dead-reckoning estimates while you wait for your next external signal. The technique (Kalman Filter) is pretty general. It's just merging all your noisy sources of information according to some ruleset (real-world physics being a common ruleset). You can tack on all sorts of other interesting information, like nearby wifi signals or whatever, and even very noisy signals can aggregate to give precise results. Another application I threw it at once was estimating my true weight, glycogen reserves, ..., from a variety of noisy measurements. The sky's the limit. You just need multiple measurements and a rule for how they interact.
rsp1984 2y ago
Always telling this whenever the topic of Kalman Filters come up: If you're learning the Kalman Filter in isolation, you're kind of learning it backwards and missing out on huge "aha" moments that the surrounding theory can unlock. To truly understand the Kalman Filter, you need to study Least Squares (aka linear regression), then recursive Least Squares, then the Information Filter (which is a different formulation of the KF). Then you'll realize the KF is just recursive Least Squares reformulated in a way to prioritize efficiency in the update step. This PDF gives a concise overview: [1] http://ais.informatik.uni-freiburg.de/teaching/ws13/mapping/pdf/slam07-eif.pdf http://ais.informatik.uni-freiburg.de/teaching/ws13/mapping/...
- raincom 2y ago
  That’s the one should learn any subject—-be it physics, chemistry, math, etc. However, textbooks don’t follow that technique.
  - ryan-duve 2y ago
    I strongly recommend Elements of Physics by Millikan and Gale for anyone who wants to learn pre-quantum physics this way.
- dr_kiszonka 2y ago
  You are probably right, but many folks following your advice will give up halfway through and never get to KF.
- jampekka 2y ago
  I think the easiest way depends on your background knowledge. If you understand linearity of the Gaussian distribution and the Bayesian posterior of Gaussians, the Kalman filter is almost trivial. For (1D) we get the prior from the linear prediction X'1 = X0*a + b, for which mean(X'1) = mean(X0)*a + b and var(X'1) = var(X0)*a^2, where a and b give the assumed dynamics. The posterior for Gaussians is the precision weighted mean of the prior and the observation: X1 = (1 - K)*X'1 + Y*K, where the weighting K = (1/var(X'1))/(1/var(X'1) + 1/var(Y)), with Y being the Gaussian observation. Iterating this gives the Kalman filter. Generalizing this to multiple dimensions is straightforward given the linearity of multidimensional Gaussians. This is how (after I understood it) it makes it really simple to me, but things like linearity of (multidimensional) Gaussians and the posterior of Gaussians as such probably are not.
dang 2y ago
Related. Others? Kalman filter from the ground up - https://news.ycombinator.com/item?id=37879715 https://news.ycombinator.com/item?id=37879715 - Oct 2023 (150 comments) (also what's the best year to put in the title above?)
dpflan 2y ago
Anyone else watch Michael van Biezem (with the bow tie) lectures on Kalman Filters while learning this topic? - https://www.youtube.com/watch?v=CaCcOwJPytQ&list=PLX2gX-ftPVXU3oUFNATxGXY90AULiqnWT https://www.youtube.com/watch?v=CaCcOwJPytQ&list=PLX2gX-ftPV...
- FilosofumRex 2y ago
  I like how he teaches so many different topics and subjects using nothing more than arithmetics. All computable math is reducible to arithmetics...
david_draco 2y ago
As far as I am aware, there is no symbolic computing tool yet for probability distributions? For example, multiplying two multivariate Gaussian PDFs together and getting the covariance matrix out. Or defining all the ingredients for a Kalman filter (prediction model and observing process) and getting the necessary formulas out (as in sympy's lambdify).
- jampekka 2y ago
  Sympy can manipulate Gaussian distributions symbolically, but the Gaussian is more or less the only distribution that can be really symbolically manipulated. Though I'm not sure Sympy can handle the conditional (Bayesian posterior) distribution needed for the Kalman filter. In any case, you are better off working direcly with the mean and variance (or covariance matrix) if you want to play around with the Kalman filter with Sympy.
  - mitthrowaway2 2y ago
    The posterior is also a Gaussian, is it not?
    - jampekka 2y ago
      Yes.
- jiggawatts 2y ago
  I'm pretty sure Wolfram Mathematica can do what you're looking for. See: https://reference.wolfram.com/language/howto/WorkWithStatisticalDistributions.html https://reference.wolfram.com/language/howto/WorkWithStatist... and: https://reference.wolfram.com/language/ref/MultinormalDistribution.html https://reference.wolfram.com/language/ref/MultinormalDistri...
- nathansherburn 2y ago
  Not sure if relevant but I thought this looked very cool. https://www.squiggle-language.com/docs https://www.squiggle-language.com/docs
pmarreck 2y ago
Something occurred to me a while back: Can we treat events that only have eyewitness testimony with a Kalman filter somehow in order to strengthen the evidential value of the observations after encoding it into vectors of some sort? This would treat both lying and inaccuracy as "error" I'm thinking of things like: reports of Phoenix lights or UFOs in general, ghosts, NDEs, and more prosaically, claims of rape
- plasticchris 2y ago
  Only if you can make a linear model of those things…
  - bradly 2y ago
    Why does the model need to be linear?
    - pinkmuffinere 2y ago
      “Kalman filter” usually refers to “linear quadratic estimator”, which assumes a linear model in its derivation. This will impact the “predict“ step at the very least, and I think also the way the uncertainty propagates. There are nonlinear estimators as well, though they usually have less-nice guarantees (eg particle filter, extended kalman filter) Edit: in fact, I see part three of the book in tfa is devoted to nonlinear Kalman filters. I suspect some of the crowd (myself included) just assumed we were talking about linear Kalman filters
      - RossBencina 2y ago
        Indeed the Extended Kalman Filter (EKF) and Unscented Kalman Filter (UKF) are both standard methods to deal with non-linear systems. They each provide a method of propagating uncertainty through nonlinear state and measurement functions. FWIW I would assume that EKF and UKF are within scope whenever Kalman Filtering is mentioned but I may be misinformed.
        2y ago
einpoklum 2y ago
The one sentence you really need to know: "The filter is named after Rudolf E. Kálmán (May 19, 1930 – July 2, 2016). In 1960, Kálmán published his famous paper describing a recursive solution to the discrete-data linear filtering problem."
escapecharacter 2y ago
Please, if you’re looking to denoise a signal for human input, use the 1-Euro filter instead: https://gery.casiez.net/1euro/ https://gery.casiez.net/1euro/ Easier to code, easier to tune parameters without a noise model
- RossBencina 2y ago
  It's a one-pole lowpass IIR filter. But I agree, if a one-pole filter will solve your problem. Kalman filter is an optimal state estimator, useful when you have: - multiple input and/or multiple output system - non-trivial dynamics (i.e. the system of interest is in motion and you have a state space description of the dynamics) - noisy measurements - statistical estimates of process and measurement noise are available - ideally, iid gaussian noises Also good if you want to fuse data on different time scales or with different noise properties. What have I missed?
greesil 2y ago
You can do all of this with machine learning better now, if you have the data.
- RossBencina 2y ago
  Kalman Filtering is machine learning. It has been used as a neural network training method. I'm implementing real-time dual state/parameter estimators at the limits of computational tractability. Please tell me how "machine learning" can solve my problem better.
  - greesil 2y ago
    You've got nonlinear things happening?
    - RossBencina 2y ago
      The state dynamics are linear but they are time varying and unknown. I am tracking the dynamics with a second Kalman filter (dual UKF like structure but mostly linear). Main "problem area" is covariance propagation, since the dynamics are defined by GRVs estimated by the parameter estimator but this uncertainty is not propagated between state/parameter estimators. It's a known shortcoming with standard (UKF) dual parameter+state estimation. I've yet to conclude whether it's a real or imaginary problem for my use-case.
thundercarrot 2y ago
If Q and R are constant (as is usually the case), the gain quickly converges, such that the Kalman filter is just an exponential filter with a prediction step. For many people this is a lot easier to understand, and even matches how it is typically used, where Q and R are manually tuned until it “looks good” and never changed again. Moreover, there is just one gain to manually tune instead of multiple quantities Q and R.
- blharr 2y ago
  This is really what I have never understood about Kalman Filters. As to how you pick Q and R. Do you just adjust them until the result looks right? How does that end up working for anything not completely over-fit? For example, if I'm tracking birds from video footage, I might choose a certain Q, but depending on the time of day the noise statistics might change. What do you do then?
graycat 2y ago
The Kalman Filter is a topic in the more general David G.\ Luenberger, {\it Optimization by Vector Space Methods,\/} John Wiley and Sons, Inc., New York, 1969.\ \
752963e64 2y ago
[dead]
f1shy 2y ago
Another resource: https://news.ycombinator.com/item?id=42755133 https://news.ycombinator.com/item?id=42755133
zipy124 2y ago
The best resource is almost always this: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt... Even if you aren't a python person, it's fantastic and really goes through everything.
deleted 2y ago
[deleted]

358 points by ColinWright 2y ago

Every time that one comes up, this one comes up https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt... (and vice versa)

elcritch 2y ago
That one is one of my favorite resources on Kalman filters. Deriving it from Bayesian principles make it much more intuitive. It also makes adapting or modifying the filters easier to understand. Using Jupyter notebooks is really great too.

magic_hamster 2y ago

Not sure why, but I get this vague notion that the author might have written a book.

esafak 2y ago
If it takes you a whole book to explain Kalman filtering you're doing it wrong.
- elcritch 2y ago
  Perhaps to get the basics sure, but to go through all the edge cases and parameter tuning and failure modes will easily fill a small book. That's not even going into modifying Kalman filters for non-linear systems.
  - esafak 2y ago
    Here's a survey that covers all of Bayesian filtering in 60 pages, plus references. https://www.researchgate.net/publication/238689222 https://www.researchgate.net/publication/238689222
    - elcritch 2y ago
      That's a nice survey. However for kalman filters it doesn't give practical examples or the different techniques to estimate the parameters. It doesn't cover adaptive modifications to kalmans like you often want in robotics or other applications to handle non-process external events which kalmans don't handle well. Et cetera, there's lots of reasons book forms on a topic can be useful.

blharr 2y ago

The first example of tracking, is this the same thing as dead reckoning? I've always been confused on the term "tracking" since it is used a lot in common speech, but seems to mean some specific type of 'tracking'

defrost 2y ago
Dead reckoning is a form of prediction, based on past evidence that indicates location then, you are reckoning (best guessing) a current position and detrmining a direction to move forward to reach some target. "Past evidence that indicates" is deliberate phrasing, in the majority of these examples we are looking at acquired data with noise; errors, instrument noise, missing returns, etc. "Tracking" is multi-stage, there's a desired target to be found (or to be declared absent) in noisy data .. that's pattern search and locking, the trajectory (the track) of that target must be best guessed, and the best guess forward prediction can be used to assist the search for the target in a new position. This is not all that can be done with a Kalman filter but it's typical of a class of common applications.
hansvm 2y ago
Kind of. "Tracking", here, means providing some kind of `f(time) -> space` API. Dead reckoning is a mechanism for incorporating velocity and whatnot into a previously estimated position to estimate a new position (and is also one possible way to implement tracking, usually with compounding errors). The Kalman filter example is better than just dead reckoning. For a simple example, imagine you're standing still but don't know exactly where. You have an API (like GPS) that can estimate your current position within some tolerance. If you're able to query that API repeatedly and the errors aren't correlated, you can pinpoint your location much more precisely. Back to tracking with non-zero velocity, every new position estimate (e.g., from GPS) can be incorporated with all the information you've seen so far, adjusting your estimates of velocity, acceleration, and position and giving you a much more accurate current estimate but also better data for dead-reckoning estimates while you wait for your next external signal. The technique (Kalman Filter) is pretty general. It's just merging all your noisy sources of information according to some ruleset (real-world physics being a common ruleset). You can tack on all sorts of other interesting information, like nearby wifi signals or whatever, and even very noisy signals can aggregate to give precise results. Another application I threw it at once was estimating my true weight, glycogen reserves, ..., from a variety of noisy measurements. The sky's the limit. You just need multiple measurements and a rule for how they interact.

rsp1984 2y ago

Always telling this whenever the topic of Kalman Filters come up: If you're learning the Kalman Filter in isolation, you're kind of learning it backwards and missing out on huge "aha" moments that the surrounding theory can unlock. To truly understand the Kalman Filter, you need to study Least Squares (aka linear regression), then recursive Least Squares, then the Information Filter (which is a different formulation of the KF). Then you'll realize the KF is just recursive Least Squares reformulated in a way to prioritize efficiency in the update step. This PDF gives a concise overview: [1] http://ais.informatik.uni-freiburg.de/teaching/ws13/mapping/pdf/slam07-eif.pdf http://ais.informatik.uni-freiburg.de/teaching/ws13/mapping/...

raincom 2y ago
That’s the one should learn any subject—-be it physics, chemistry, math, etc. However, textbooks don’t follow that technique.
- ryan-duve 2y ago
  I strongly recommend Elements of Physics by Millikan and Gale for anyone who wants to learn pre-quantum physics this way.
dr_kiszonka 2y ago
You are probably right, but many folks following your advice will give up halfway through and never get to KF.
jampekka 2y ago
I think the easiest way depends on your background knowledge. If you understand linearity of the Gaussian distribution and the Bayesian posterior of Gaussians, the Kalman filter is almost trivial. For (1D) we get the prior from the linear prediction X'1 = X0*a + b, for which mean(X'1) = mean(X0)*a + b and var(X'1) = var(X0)*a^2, where a and b give the assumed dynamics. The posterior for Gaussians is the precision weighted mean of the prior and the observation: X1 = (1 - K)*X'1 + Y*K, where the weighting K = (1/var(X'1))/(1/var(X'1) + 1/var(Y)), with Y being the Gaussian observation. Iterating this gives the Kalman filter. Generalizing this to multiple dimensions is straightforward given the linearity of multidimensional Gaussians. This is how (after I understood it) it makes it really simple to me, but things like linearity of (multidimensional) Gaussians and the posterior of Gaussians as such probably are not.

dang 2y ago

Related. Others? Kalman filter from the ground up - https://news.ycombinator.com/item?id=37879715 https://news.ycombinator.com/item?id=37879715 - Oct 2023 (150 comments) (also what's the best year to put in the title above?)

dpflan 2y ago

Anyone else watch Michael van Biezem (with the bow tie) lectures on Kalman Filters while learning this topic? - https://www.youtube.com/watch?v=CaCcOwJPytQ&list=PLX2gX-ftPVXU3oUFNATxGXY90AULiqnWT https://www.youtube.com/watch?v=CaCcOwJPytQ&list=PLX2gX-ftPV...

FilosofumRex 2y ago
I like how he teaches so many different topics and subjects using nothing more than arithmetics. All computable math is reducible to arithmetics...

david_draco 2y ago

As far as I am aware, there is no symbolic computing tool yet for probability distributions? For example, multiplying two multivariate Gaussian PDFs together and getting the covariance matrix out. Or defining all the ingredients for a Kalman filter (prediction model and observing process) and getting the necessary formulas out (as in sympy's lambdify).

jampekka 2y ago
Sympy can manipulate Gaussian distributions symbolically, but the Gaussian is more or less the only distribution that can be really symbolically manipulated. Though I'm not sure Sympy can handle the conditional (Bayesian posterior) distribution needed for the Kalman filter. In any case, you are better off working direcly with the mean and variance (or covariance matrix) if you want to play around with the Kalman filter with Sympy.
- mitthrowaway2 2y ago
  The posterior is also a Gaussian, is it not?
  - jampekka 2y ago
    Yes.
jiggawatts 2y ago
I'm pretty sure Wolfram Mathematica can do what you're looking for. See: https://reference.wolfram.com/language/howto/WorkWithStatisticalDistributions.html https://reference.wolfram.com/language/howto/WorkWithStatist... and: https://reference.wolfram.com/language/ref/MultinormalDistribution.html https://reference.wolfram.com/language/ref/MultinormalDistri...
nathansherburn 2y ago
Not sure if relevant but I thought this looked very cool. https://www.squiggle-language.com/docs https://www.squiggle-language.com/docs

pmarreck 2y ago

Something occurred to me a while back: Can we treat events that only have eyewitness testimony with a Kalman filter somehow in order to strengthen the evidential value of the observations after encoding it into vectors of some sort? This would treat both lying and inaccuracy as "error" I'm thinking of things like: reports of Phoenix lights or UFOs in general, ghosts, NDEs, and more prosaically, claims of rape

plasticchris 2y ago
Only if you can make a linear model of those things…
- bradly 2y ago
  Why does the model need to be linear?
  - pinkmuffinere 2y ago
    “Kalman filter” usually refers to “linear quadratic estimator”, which assumes a linear model in its derivation. This will impact the “predict“ step at the very least, and I think also the way the uncertainty propagates. There are nonlinear estimators as well, though they usually have less-nice guarantees (eg particle filter, extended kalman filter) Edit: in fact, I see part three of the book in tfa is devoted to nonlinear Kalman filters. I suspect some of the crowd (myself included) just assumed we were talking about linear Kalman filters
    - RossBencina 2y ago
      Indeed the Extended Kalman Filter (EKF) and Unscented Kalman Filter (UKF) are both standard methods to deal with non-linear systems. They each provide a method of propagating uncertainty through nonlinear state and measurement functions. FWIW I would assume that EKF and UKF are within scope whenever Kalman Filtering is mentioned but I may be misinformed.
      - 2y ago

einpoklum 2y ago

The one sentence you really need to know: "The filter is named after Rudolf E. Kálmán (May 19, 1930 – July 2, 2016). In 1960, Kálmán published his famous paper describing a recursive solution to the discrete-data linear filtering problem."

escapecharacter 2y ago

Please, if you’re looking to denoise a signal for human input, use the 1-Euro filter instead: https://gery.casiez.net/1euro/ https://gery.casiez.net/1euro/ Easier to code, easier to tune parameters without a noise model

RossBencina 2y ago
It's a one-pole lowpass IIR filter. But I agree, if a one-pole filter will solve your problem. Kalman filter is an optimal state estimator, useful when you have: - multiple input and/or multiple output system - non-trivial dynamics (i.e. the system of interest is in motion and you have a state space description of the dynamics) - noisy measurements - statistical estimates of process and measurement noise are available - ideally, iid gaussian noises Also good if you want to fuse data on different time scales or with different noise properties. What have I missed?

greesil 2y ago

You can do all of this with machine learning better now, if you have the data.

RossBencina 2y ago
Kalman Filtering is machine learning. It has been used as a neural network training method. I'm implementing real-time dual state/parameter estimators at the limits of computational tractability. Please tell me how "machine learning" can solve my problem better.
- greesil 2y ago
  You've got nonlinear things happening?
  - RossBencina 2y ago
    The state dynamics are linear but they are time varying and unknown. I am tracking the dynamics with a second Kalman filter (dual UKF like structure but mostly linear). Main "problem area" is covariance propagation, since the dynamics are defined by GRVs estimated by the parameter estimator but this uncertainty is not propagated between state/parameter estimators. It's a known shortcoming with standard (UKF) dual parameter+state estimation. I've yet to conclude whether it's a real or imaginary problem for my use-case.

thundercarrot 2y ago

If Q and R are constant (as is usually the case), the gain quickly converges, such that the Kalman filter is just an exponential filter with a prediction step. For many people this is a lot easier to understand, and even matches how it is typically used, where Q and R are manually tuned until it “looks good” and never changed again. Moreover, there is just one gain to manually tune instead of multiple quantities Q and R.

blharr 2y ago
This is really what I have never understood about Kalman Filters. As to how you pick Q and R. Do you just adjust them until the result looks right? How does that end up working for anything not completely over-fit? For example, if I'm tracking birds from video footage, I might choose a certain Q, but depending on the time of day the noise statistics might change. What do you do then?

graycat 2y ago

The Kalman Filter is a topic in the more general David G.\ Luenberger, {\it Optimization by Vector Space Methods,\/} John Wiley and Sons, Inc., New York, 1969.\ \

752963e64 2y ago

[dead]

f1shy 2y ago

Another resource: https://news.ycombinator.com/item?id=42755133 https://news.ycombinator.com/item?id=42755133

zipy124 2y ago

The best resource is almost always this: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt... Even if you aren't a python person, it's fantastic and really goes through everything.

deleted 2y ago

[deleted]