6 ms·

Kalman Filter Explained Simply

367 points by RafelMri 3y ago

pfdietz 3y ago
My late father used these all the time during his career, starting about the time they were invented. He worked on radar and missile guidance systems.
- lkdfjlkdfjlg 3y ago
  You mean, actual engineering.
  - willis936 3y ago
    Plenty of EEs understand and apply DSP techniques today without making weapons.
hprotagonist 3y ago
“if you do it right, the noise washes out.”
foobarbecue 3y ago
I've always thought math would be much easier to learn if they used descriptive variable names. Or, at least in an interactive medium like the web, add some tooltips at a bare minimum. Whenever I study math I spend 90% of the time looking up the symbols. Also when this person says the subscript "denotes the order of the measurement" I'm trying to figure out what kind of order he's talking about. I guess that's the index? It's been a while since I did kalman filters:-p
- Waterluvian 3y ago
  This was 90% of my problem with math. Same when something is named descriptively: shield volcano, star dunes, vs. some person’s name like Rayleigh scattering. It’s just an extra layer to memorize and parse.
  - bonoboTP 3y ago
    I agree but this is a surface level issue impacting the very beginner phase only. Once you get familiar with the vocabulary, the hard stuff will be the actual material, understanding the thing itself, not its description. This differentiates fields that have an actual subject matter from fields that are essentially terminology and categorizations all the way through, a self-referential map with no territory. In math/physics/engineering the terminology is unfamiliar at first but very precise and hence learnable. The vast majority of STEM textbooks (at least from good US university publishers) make their best effort in presenting the material understandably without any intentional obscurantism or additional fanciness. Academic joirnal/conference papers do sometimes intentionally confuse to game the publication metrics but intro materials are an earnest effort at educating. The subject matter has some inherent complexity, there's no need to prop it up artificially for prestige (that happens more in other fields that are insecure about their level of inherent complexity).
    - Waterluvian 3y ago
      Oh definitely! Eventually you've spent so much time that the thetas and lambdas and Lorentzes and whatever become your close intimate friends. I've most recently experienced this with learning piano and how an ocean of white and black keys all developed these individual "identities." Like, "ah yes, <looks at A4> I won't forget you. We've had so many dramatic moments before, and remember that time I kept showing up at your neighbour's house instead?" ...Okay maybe I'm just weird.
- shiandow 3y ago
  People always seem to forget that mathematical notation is designed to make algebraic manipulations easier to follow. It's not really intended as something that makes sense on its own, it's mostly physicists who think something like E=mc^2 should have any meaning. The more pure the mathematics the shorter the scope of most variables. Typically a variable is defined just before it's used, with a scope no longer than the proof or derivation it's in. Also some of the choices in this article are just plain silly. Such as using P as both variable and index, and then use it for the covariance matrix when the precision matrix is the exact inverse.
  - toxik 3y ago
    In computer science, we straddle this divide where the usual way to describe things in scientific literature is using algebraic notation, but the usual way to actually write up a program is to use meaningful variable names. It's not K_i, it's current_gains or something like that. It leads to a funny kind of style where especially computer science-related fields start writing K_{current} in scientific manuscripts, and are then chided because that is not how you use subscripts. The reverse is also true, theory-adjacent code tends to use a lot more terse naming conventions.
    - michaelrpeskin 3y ago
      I often work with a guy who's a pure computer scientist. He communicates in LaTeX and pseudocode only. I don't think he could find a compiler if he tried. What I've learned to do is keep his notation whenever I implement something. I start the function with a comment that says what paper I'm referencing when I implement it and then comment all of the one-letter variables. (In this case I would use K[i]). Usually the stuff I'm implementing is complicated enough that reading the code without reading the paper won't have much meaning. And if you're reading the paper, it's good to have as close to a 1-1 representation to help give confidence that I implemented it right. I've had non-zero times where I took his pseudocode, pasted it into my IDE and did a search and replace of begin/end to braces and "<-" to "=" and it "just worked" on the first try. I always found that amazing that he could write this stuff without ever trying it (outside of his head).
    - 3y ago
- pinkmuffinere 3y ago
  > Also when this person says the subscript "denotes the order of the measurement" I'm trying to figure out what kind of order he's talking about. I guess that's the index? It's been a while since I did kalman filters:-p The order referred to is the index-in-time that a value correspond to. Eg, x_3 would be the state at the third time step. I think their subscript “p” stands for prediction. x_p at time 3 is the state we expect at time 4. But then when time 4 comes around, we incorporate new measurements and calculate x_4 including that new information. Just to be explicit, this x_4 will be different from the x_p we calculated at time 3, as our prediction is always a bit incorrect
- gromneer 3y ago
  > Also when this person says the subscript "denotes the order of the measurement" I'm trying to figure out what kind of order he's talking about. I hate that the most when reading papers. Authors trying to sound abstract and academic, but only accomplishing being frustratingly vague. AUTHORS YOU STILL HAVE TO INSERT THE SUBJECT INTO YOUR SENTENCES FOR THEM TO MAKE SENSE. I'm so frustrated at this aspect in research papers more than anything else. You must disambiguate. Use absolute descriptors and do not use relative descriptors. Don't tell me to look right, because I'll look left. Use absolute descriptors! "then after spinning the prism the light cone blah blah blah" SPIN!? SPIN IN WHAT DIRECTION????? LEFT?RIGHT?! LATERAL? UP? DOWN???? How fast? How slow? You imagine all of these CRITICAL ASPECTS in your head when writing such ambiguous sentences, but the reader cannot read your mind.
  - saulrh 3y ago
    Having written papers like this before, a large part of the problem is that almost all CS research is published in conferences, rather than journals, and conferences frequently have extremely strict length limits, on the order of three or five pages. If you have an even slightly complicated procedure it can be nightmarishly difficult to get even the core information into your paper, and you can forget about details or tangents.
- foofie 3y ago
  > I've always thought math would be much easier to learn if they used descriptive variable names. I think the variable names are already picked to be descriptive. No one is picking them to be more obscure or harder to track. The problem is that those who are starting out still haven't picked up concepts or learned the standard notations for each problem domain, thus we are left with the pain of ramping up on a topic.
- max_ 3y ago
  I completely agree. And my insight similar to yours is that the greatest math book that no one has written is one where the meaning of notation, variables and a clear assortment of theorems across all topics are well curated.
  - bonoboTP 3y ago
    Many math books nowadays come with Python code eg jupyter notebooks.
    - max_ 3y ago
      Python code is abit of an over kill. I was for example reading a cryptography book and it has symbols like a hamadad product.
- deleted 3y ago
  [deleted]
- colechristensen 3y ago
  I've always thought that code would be much easier to understand with shorter, less descriptive variable names. Whenever I look at new code most of the confusion involves searching through layers of abstraction for the part that actually does the thing as opposed to the layer upon layer of connections between abstractions which would be much less necessary if the entire behavior could be encoded in a single line. You can only have a small number of descriptive variables in an expression before it becomes entirely unreadable. That is opposed to single character with sub/superscripts where you can easily see what's happening with tens of variables in a single line of math. https://wikimedia.org/api/rest_v1/media/math/render/svg/a7d22d3c91ab780f2cfdf7eab2aff60850476e37 https://wikimedia.org/api/rest_v1/media/math/render/svg/a7d2... Here's a formula for calculating the downstream Mach number in a certain kind of supersonic flow. I cannot imagine any way to write this in "descriptive variables" which makes the formula understandable at all, you just could not see the structure. (from https://en.wikipedia.org/wiki/Oblique_shock https://en.wikipedia.org/wiki/Oblique_shock )
- malkia 3y ago
  Check https://mitpress.ublish.com/ebook/structure-and-interpretation-classical-mechanics-0-preview/135/xiv https://mitpress.ublish.com/ebook/structure-and-interpretati...
- o11c 3y ago
  > trying to figure out what kind of order For reference, the Wikipedia page "Order (mathematics)" is a disambiguation page almost as long as the top-level disambiguation page "Order". https://en.wikipedia.org/wiki/Order_(mathematics) https://en.wikipedia.org/wiki/Order_(mathematics) I generally don't have a problem with variable names, but creating syntax and terminology that conflicts with other mathematical use is a real problem.
shiandow 3y ago
Kalman filters might be one of those weird cases in mathematics where the 'simple' version is simplified beyond all recognition. I mean what you're really doing is take a measurement then simulate the possible future states and combine this information with the next measurement and repeat. You can imagine e.g. taking multiple pictures of a tennis-ball, estimate its position and speed from the first picture, simulate where it's going to end up, and compare this with the next picture to see which estimate is closer to the truth. Or more old school, measure the inclination of the sun and compare the resulting line of possible locations on a map to the spot you thought you were. Of course the exact calculations are beyond impractical. So you use sampling to simplify. However that still makes it difficult so you assume the distribution is somewhat close to a Gaussian distribution. And then you simplify even more by assuming the evolution of the system is just a linear transformation. And that's how you end up with the Kalman filter discussed here. I'd be amazed if anyone could really understand what's going on just based on the linear algebra.
- jvanderbot 3y ago
  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)
visarga 3y ago
Simply put, it is an "online" model that which means that it learns on the fly. Specifically, it is the optimal online learning algorithm for linear systems with Gaussian noise. In a way it is like a primitive RNN, it has internal state, inputs and outputs.
nayuki 3y ago
I like this previous explanation: https://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/ https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture... , https://news.ycombinator.com/item?id=13449229 https://news.ycombinator.com/item?id=13449229
- swyx 3y ago
  this is way better, and should be at the top.
- Moduke 3y ago
  I enjoyed the simplicity of this explanation as well: https://praveshkoirala.com/2023/06/13/a-non-mathematical-introduction-to-kalman-filters-for-programmers/ https://praveshkoirala.com/2023/06/13/a-non-mathematical-int... https://news.ycombinator.com/item?id=36971975 https://news.ycombinator.com/item?id=36971975
- fho 3y ago
  That's the one with the cute little robot, is it? I always liked that one the most :-)
richrichie 3y ago
[dead]
syntaxing 3y ago
One thing that clicked for me is that two uncertain distribution of measurements (a high variance in the distribution) makes a “more certain” measurement (a narrower distribution). Use this more certain measurement and combine it with the next measurement, then rinse and repeat and boom, you have a Kalman filter.
Symmetry 3y ago
I've used them in robotics and for tracking satellites going overhead via radar. Apparently they're also used by economists for guessing the state of the economy, along with other filters in the standard robotics toolkit.
- mesofile 3y ago
  Purely idle curiosity – I've heard a lot about the Kalman filter over the years, it's a popular subject here, but what are the other filters in the standard robotics toolkit?
  - Symmetry 3y ago
    Particle filters would be the main other one I'd reach for. The ability to represent multiple hypotheses is a big advantage they have.
    - dplavery92 3y ago
      You can also construct multiple hypothesis trackers from multiple Kalman Filters, but there is a little more machinery. For example, Interacting Multiple Models (IMM) trackers may use Kalman Filters or Particle Filters, and a lot of the foundational work by Bar-Shalom and others focuses on Kalman Filters.
  - elbear 3y ago
    Someone in another comment mentioned a book called Probabilistic Robotics. I think that covers everything.
  - dplavery92 3y ago
    The Kalman filter has a family of generalizations in the Extended Kalman Filter (EKF) and Unscented Kalman Filter (UKF.) Also common in robotics applications is the Particle Filter, which uses a Monte Carlo approximation of the uncertainty in the state, rather than enforcing a (Gaussian) distribution, as in the traditional Kalman filter. This can be useful when the mechanics are highly nonlinear and/or your measurement uncertainties are, well, very non-Gaussian. Sebastian Thrun (a CMU robotics professor in the DARPA "Grand Challenge" days of self-driving cars) made an early Udacity course on Particle Filters.
01HNNWZ0MV43FF 3y ago
If I really needed a Kalman filter I'm sure I could read this, or the Wikipedia page, or an implementation's source code (https://github.com/LdDl/kalman-rs/blob/master/src/kalman/kalman_1d.rs https://github.com/LdDl/kalman-rs/blob/master/src/kalman/kal...) and figure it out. But IME everyone in the entire world is a "visual learner" who learns best by examples. So I'm surprised that the tutorial midway through the page doesn't put any example numbers into the formulas (maybe I glanced over it?) and the pictures only start after a page of "what is a Kalman filter" text, and the pictures are just of more formulas.
- the__alchemist 3y ago
  Another comment pointed out variable naming conventions as an obstacle to learning and understanding mathematical topics. I am sympathetic to that perspective, but even more so to this one you post. I am astounded by how common this is. A weaker form of this exists in software libraries that don't include code examples.
girzel 3y ago
No thread on Kalman Filters is complete without a link to this excellent learning resource, a book written as a set of Jupyter notebooks: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python/ https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt... That book mentions alpha-beta filters as sort of a younger sibling to full-blown Kalman filters. I recently had need of something like this at work, and started doing a bunch of reading. Eventually I realized that alpha-beta filters (and the whole Kalman family) is very focused on predicting the near future, whereas what I really needed was just a way to smooth historical data. So I started reading in that direction, came across "double exponential smoothing" which seemed perfect for my use-case, and as I went into it I realized... it's just the alpha-beta filter again, but now with different names for all the variables :( I can't help feeling like this entire neighborhood of math rests on a few common fundamental theories, but because different disciplines arrived at the same systems via different approaches, they end up sounding a little different and the commonality is obscured. Something about power series, Euler's number, gradient descent, filters, feedback systems, general system theory... it feels to me like there's a relatively small kernel of intuitive understanding at the heart of all that stuff, which could end up making glorious sense of a lot of mathematics if I could only grasp it. Somebody help me out, here!
- bonoboTP 3y ago
  Maybe check out Probabilistic Robotics by Dieter Fox, Sebastian Thrun, and Wolfram Burgard. It has a coherent Bayesian formulation with consistent notation on many Kalman-related topics. Also with the rise of AI/ML, classic control theory ideas are being merged with reinforcement learning.
  - girzel 3y ago
    Thanks for the recommendation! It would never have occurred to me to look at robotics, but I can understand why that's very relevant. I read Feedback Control for Computer Systems not too long ago, which felt like yet another restatement of the same ideas; I guess that counts as "classic control theory".
  - esafak 3y ago
ModernMech 3y ago
Close your eyes and walk around for a while. Imagine where you are. Now open your eyes. Is your actual location different from where you thought you were? That last bit, using an observation to update a belief on a state variable, that's what the Kalman filter does.
cocostation 3y ago
I really like this set of videos for explaining the KF. I 'got it' more than I did with the material on the original post. https://www.youtube.com/watch?v=CaCcOwJPytQ https://www.youtube.com/watch?v=CaCcOwJPytQ
lopatin 3y ago
Does anyone here use Kalman filter for pairs trading?
eclectic29 3y ago
Genuine question: why does kalman filter come up so frequently on HN? Is this something I'm missing? I'm a machine learning engineer, not a data scientist.
- xchip 3y ago
  It is considered a difficult topic and people want to show they understand it. A similar thing happens that had the word quantic or relativistic. I'm a physicist and we hardly talk about it, but here in HN we find people bringing in up every other day
- scarmig 3y ago
  ML and Kalman filtering try to solve similar problems. Some theories even suggest that Kalman filtering (or a similar algorithm) provides a basis for neurobiological learning. See predictive coding (e.g. https://arxiv.org/pdf/2102.10021.pdf https://arxiv.org/pdf/2102.10021.pdf) (Why I'm interested in it, at least.)
chubs 3y ago
Recently tasked with implementing a Kalman filter, I found it very very difficult to find good resources that explained it in language that made sense to a developer like me. So after spending a month learning it, I wrote a couple posts on it, perhaps someone might find it helpful? https://www.splinter.com.au/2023/12/14/the-kalman-filter-for-programmers/ https://www.splinter.com.au/2023/12/14/the-kalman-filter-for... https://www.splinter.com.au/2023/12/15/the-kalman-filter-with-velocity/ https://www.splinter.com.au/2023/12/15/the-kalman-filter-wit... As a developer I found the maths made sense only after implementing it, ironically. I guess we learn by building on top of what we already know? Is there a term for that?
- Subdivide8452 3y ago
  Off topic, but why are you one of those people who do a full screen “subscribe to my mailing list” overlay? I never understand why you’d wanna do that.
  - fransje26 3y ago
    Install ublock origin. No overlay to be seen.
  - chubs 3y ago
    Oh, many years ago I bought into the whole 'write a blog, collect subscribers, create a training product and sell it to them, retire on the beach' idea and gave it a go. I now think that's exceedingly unlikely, of course. Sorry you find it annoying, i'll have to get around to removing it sometime.
deleted 3y ago
[deleted]

367 points by RafelMri 3y ago

My late father used these all the time during his career, starting about the time they were invented. He worked on radar and missile guidance systems.

lkdfjlkdfjlg 3y ago
You mean, actual engineering.
- willis936 3y ago
  Plenty of EEs understand and apply DSP techniques today without making weapons.

hprotagonist 3y ago

“if you do it right, the noise washes out.”

foobarbecue 3y ago

I've always thought math would be much easier to learn if they used descriptive variable names. Or, at least in an interactive medium like the web, add some tooltips at a bare minimum. Whenever I study math I spend 90% of the time looking up the symbols. Also when this person says the subscript "denotes the order of the measurement" I'm trying to figure out what kind of order he's talking about. I guess that's the index? It's been a while since I did kalman filters:-p

Waterluvian 3y ago
This was 90% of my problem with math. Same when something is named descriptively: shield volcano, star dunes, vs. some person’s name like Rayleigh scattering. It’s just an extra layer to memorize and parse.
- bonoboTP 3y ago
  I agree but this is a surface level issue impacting the very beginner phase only. Once you get familiar with the vocabulary, the hard stuff will be the actual material, understanding the thing itself, not its description. This differentiates fields that have an actual subject matter from fields that are essentially terminology and categorizations all the way through, a self-referential map with no territory. In math/physics/engineering the terminology is unfamiliar at first but very precise and hence learnable. The vast majority of STEM textbooks (at least from good US university publishers) make their best effort in presenting the material understandably without any intentional obscurantism or additional fanciness. Academic joirnal/conference papers do sometimes intentionally confuse to game the publication metrics but intro materials are an earnest effort at educating. The subject matter has some inherent complexity, there's no need to prop it up artificially for prestige (that happens more in other fields that are insecure about their level of inherent complexity).
  - Waterluvian 3y ago
    Oh definitely! Eventually you've spent so much time that the thetas and lambdas and Lorentzes and whatever become your close intimate friends. I've most recently experienced this with learning piano and how an ocean of white and black keys all developed these individual "identities." Like, "ah yes, <looks at A4> I won't forget you. We've had so many dramatic moments before, and remember that time I kept showing up at your neighbour's house instead?" ...Okay maybe I'm just weird.
shiandow 3y ago
People always seem to forget that mathematical notation is designed to make algebraic manipulations easier to follow. It's not really intended as something that makes sense on its own, it's mostly physicists who think something like E=mc^2 should have any meaning. The more pure the mathematics the shorter the scope of most variables. Typically a variable is defined just before it's used, with a scope no longer than the proof or derivation it's in. Also some of the choices in this article are just plain silly. Such as using P as both variable and index, and then use it for the covariance matrix when the precision matrix is the exact inverse.
- toxik 3y ago
  In computer science, we straddle this divide where the usual way to describe things in scientific literature is using algebraic notation, but the usual way to actually write up a program is to use meaningful variable names. It's not K_i, it's current_gains or something like that. It leads to a funny kind of style where especially computer science-related fields start writing K_{current} in scientific manuscripts, and are then chided because that is not how you use subscripts. The reverse is also true, theory-adjacent code tends to use a lot more terse naming conventions.
  - michaelrpeskin 3y ago
    I often work with a guy who's a pure computer scientist. He communicates in LaTeX and pseudocode only. I don't think he could find a compiler if he tried. What I've learned to do is keep his notation whenever I implement something. I start the function with a comment that says what paper I'm referencing when I implement it and then comment all of the one-letter variables. (In this case I would use K[i]). Usually the stuff I'm implementing is complicated enough that reading the code without reading the paper won't have much meaning. And if you're reading the paper, it's good to have as close to a 1-1 representation to help give confidence that I implemented it right. I've had non-zero times where I took his pseudocode, pasted it into my IDE and did a search and replace of begin/end to braces and "<-" to "=" and it "just worked" on the first try. I always found that amazing that he could write this stuff without ever trying it (outside of his head).
  - 3y ago
pinkmuffinere 3y ago
> Also when this person says the subscript "denotes the order of the measurement" I'm trying to figure out what kind of order he's talking about. I guess that's the index? It's been a while since I did kalman filters:-p The order referred to is the index-in-time that a value correspond to. Eg, x_3 would be the state at the third time step. I think their subscript “p” stands for prediction. x_p at time 3 is the state we expect at time 4. But then when time 4 comes around, we incorporate new measurements and calculate x_4 including that new information. Just to be explicit, this x_4 will be different from the x_p we calculated at time 3, as our prediction is always a bit incorrect
gromneer 3y ago
> Also when this person says the subscript "denotes the order of the measurement" I'm trying to figure out what kind of order he's talking about. I hate that the most when reading papers. Authors trying to sound abstract and academic, but only accomplishing being frustratingly vague. AUTHORS YOU STILL HAVE TO INSERT THE SUBJECT INTO YOUR SENTENCES FOR THEM TO MAKE SENSE. I'm so frustrated at this aspect in research papers more than anything else. You must disambiguate. Use absolute descriptors and do not use relative descriptors. Don't tell me to look right, because I'll look left. Use absolute descriptors! "then after spinning the prism the light cone blah blah blah" SPIN!? SPIN IN WHAT DIRECTION????? LEFT?RIGHT?! LATERAL? UP? DOWN???? How fast? How slow? You imagine all of these CRITICAL ASPECTS in your head when writing such ambiguous sentences, but the reader cannot read your mind.
- saulrh 3y ago
  Having written papers like this before, a large part of the problem is that almost all CS research is published in conferences, rather than journals, and conferences frequently have extremely strict length limits, on the order of three or five pages. If you have an even slightly complicated procedure it can be nightmarishly difficult to get even the core information into your paper, and you can forget about details or tangents.
foofie 3y ago
> I've always thought math would be much easier to learn if they used descriptive variable names. I think the variable names are already picked to be descriptive. No one is picking them to be more obscure or harder to track. The problem is that those who are starting out still haven't picked up concepts or learned the standard notations for each problem domain, thus we are left with the pain of ramping up on a topic.
max_ 3y ago
I completely agree. And my insight similar to yours is that the greatest math book that no one has written is one where the meaning of notation, variables and a clear assortment of theorems across all topics are well curated.
- bonoboTP 3y ago
  Many math books nowadays come with Python code eg jupyter notebooks.
  - max_ 3y ago
    Python code is abit of an over kill. I was for example reading a cryptography book and it has symbols like a hamadad product.
deleted 3y ago
[deleted]
colechristensen 3y ago
I've always thought that code would be much easier to understand with shorter, less descriptive variable names. Whenever I look at new code most of the confusion involves searching through layers of abstraction for the part that actually does the thing as opposed to the layer upon layer of connections between abstractions which would be much less necessary if the entire behavior could be encoded in a single line. You can only have a small number of descriptive variables in an expression before it becomes entirely unreadable. That is opposed to single character with sub/superscripts where you can easily see what's happening with tens of variables in a single line of math. https://wikimedia.org/api/rest_v1/media/math/render/svg/a7d22d3c91ab780f2cfdf7eab2aff60850476e37 https://wikimedia.org/api/rest_v1/media/math/render/svg/a7d2... Here's a formula for calculating the downstream Mach number in a certain kind of supersonic flow. I cannot imagine any way to write this in "descriptive variables" which makes the formula understandable at all, you just could not see the structure. (from https://en.wikipedia.org/wiki/Oblique_shock https://en.wikipedia.org/wiki/Oblique_shock )
malkia 3y ago
Check https://mitpress.ublish.com/ebook/structure-and-interpretation-classical-mechanics-0-preview/135/xiv https://mitpress.ublish.com/ebook/structure-and-interpretati...
o11c 3y ago
> trying to figure out what kind of order For reference, the Wikipedia page "Order (mathematics)" is a disambiguation page almost as long as the top-level disambiguation page "Order". https://en.wikipedia.org/wiki/Order_(mathematics) https://en.wikipedia.org/wiki/Order_(mathematics) I generally don't have a problem with variable names, but creating syntax and terminology that conflicts with other mathematical use is a real problem.

shiandow 3y ago

Kalman filters might be one of those weird cases in mathematics where the 'simple' version is simplified beyond all recognition. I mean what you're really doing is take a measurement then simulate the possible future states and combine this information with the next measurement and repeat. You can imagine e.g. taking multiple pictures of a tennis-ball, estimate its position and speed from the first picture, simulate where it's going to end up, and compare this with the next picture to see which estimate is closer to the truth. Or more old school, measure the inclination of the sun and compare the resulting line of possible locations on a map to the spot you thought you were. Of course the exact calculations are beyond impractical. So you use sampling to simplify. However that still makes it difficult so you assume the distribution is somewhat close to a Gaussian distribution. And then you simplify even more by assuming the evolution of the system is just a linear transformation. And that's how you end up with the Kalman filter discussed here. I'd be amazed if anyone could really understand what's going on just based on the linear algebra.

jvanderbot 3y ago
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)

visarga 3y ago

Simply put, it is an "online" model that which means that it learns on the fly. Specifically, it is the optimal online learning algorithm for linear systems with Gaussian noise. In a way it is like a primitive RNN, it has internal state, inputs and outputs.

nayuki 3y ago

I like this previous explanation: https://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/ https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture... , https://news.ycombinator.com/item?id=13449229 https://news.ycombinator.com/item?id=13449229

swyx 3y ago
this is way better, and should be at the top.
Moduke 3y ago
I enjoyed the simplicity of this explanation as well: https://praveshkoirala.com/2023/06/13/a-non-mathematical-introduction-to-kalman-filters-for-programmers/ https://praveshkoirala.com/2023/06/13/a-non-mathematical-int... https://news.ycombinator.com/item?id=36971975 https://news.ycombinator.com/item?id=36971975
fho 3y ago
That's the one with the cute little robot, is it? I always liked that one the most :-)

richrichie 3y ago

[dead]

syntaxing 3y ago

One thing that clicked for me is that two uncertain distribution of measurements (a high variance in the distribution) makes a “more certain” measurement (a narrower distribution). Use this more certain measurement and combine it with the next measurement, then rinse and repeat and boom, you have a Kalman filter.

Symmetry 3y ago

I've used them in robotics and for tracking satellites going overhead via radar. Apparently they're also used by economists for guessing the state of the economy, along with other filters in the standard robotics toolkit.

mesofile 3y ago
Purely idle curiosity – I've heard a lot about the Kalman filter over the years, it's a popular subject here, but what are the other filters in the standard robotics toolkit?
- Symmetry 3y ago
  Particle filters would be the main other one I'd reach for. The ability to represent multiple hypotheses is a big advantage they have.
  - dplavery92 3y ago
    You can also construct multiple hypothesis trackers from multiple Kalman Filters, but there is a little more machinery. For example, Interacting Multiple Models (IMM) trackers may use Kalman Filters or Particle Filters, and a lot of the foundational work by Bar-Shalom and others focuses on Kalman Filters.
- elbear 3y ago
  Someone in another comment mentioned a book called Probabilistic Robotics. I think that covers everything.
- dplavery92 3y ago
  The Kalman filter has a family of generalizations in the Extended Kalman Filter (EKF) and Unscented Kalman Filter (UKF.) Also common in robotics applications is the Particle Filter, which uses a Monte Carlo approximation of the uncertainty in the state, rather than enforcing a (Gaussian) distribution, as in the traditional Kalman filter. This can be useful when the mechanics are highly nonlinear and/or your measurement uncertainties are, well, very non-Gaussian. Sebastian Thrun (a CMU robotics professor in the DARPA "Grand Challenge" days of self-driving cars) made an early Udacity course on Particle Filters.

01HNNWZ0MV43FF 3y ago

If I really needed a Kalman filter I'm sure I could read this, or the Wikipedia page, or an implementation's source code (https://github.com/LdDl/kalman-rs/blob/master/src/kalman/kalman_1d.rs https://github.com/LdDl/kalman-rs/blob/master/src/kalman/kal...) and figure it out. But IME everyone in the entire world is a "visual learner" who learns best by examples. So I'm surprised that the tutorial midway through the page doesn't put any example numbers into the formulas (maybe I glanced over it?) and the pictures only start after a page of "what is a Kalman filter" text, and the pictures are just of more formulas.

the__alchemist 3y ago
Another comment pointed out variable naming conventions as an obstacle to learning and understanding mathematical topics. I am sympathetic to that perspective, but even more so to this one you post. I am astounded by how common this is. A weaker form of this exists in software libraries that don't include code examples.

girzel 3y ago

No thread on Kalman Filters is complete without a link to this excellent learning resource, a book written as a set of Jupyter notebooks: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python/ https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt... That book mentions alpha-beta filters as sort of a younger sibling to full-blown Kalman filters. I recently had need of something like this at work, and started doing a bunch of reading. Eventually I realized that alpha-beta filters (and the whole Kalman family) is very focused on predicting the near future, whereas what I really needed was just a way to smooth historical data. So I started reading in that direction, came across "double exponential smoothing" which seemed perfect for my use-case, and as I went into it I realized... it's just the alpha-beta filter again, but now with different names for all the variables :( I can't help feeling like this entire neighborhood of math rests on a few common fundamental theories, but because different disciplines arrived at the same systems via different approaches, they end up sounding a little different and the commonality is obscured. Something about power series, Euler's number, gradient descent, filters, feedback systems, general system theory... it feels to me like there's a relatively small kernel of intuitive understanding at the heart of all that stuff, which could end up making glorious sense of a lot of mathematics if I could only grasp it. Somebody help me out, here!

bonoboTP 3y ago
Maybe check out Probabilistic Robotics by Dieter Fox, Sebastian Thrun, and Wolfram Burgard. It has a coherent Bayesian formulation with consistent notation on many Kalman-related topics. Also with the rise of AI/ML, classic control theory ideas are being merged with reinforcement learning.
- girzel 3y ago
  Thanks for the recommendation! It would never have occurred to me to look at robotics, but I can understand why that's very relevant. I read Feedback Control for Computer Systems not too long ago, which felt like yet another restatement of the same ideas; I guess that counts as "classic control theory".
- esafak 3y ago

ModernMech 3y ago

Close your eyes and walk around for a while. Imagine where you are. Now open your eyes. Is your actual location different from where you thought you were? That last bit, using an observation to update a belief on a state variable, that's what the Kalman filter does.

cocostation 3y ago

I really like this set of videos for explaining the KF. I 'got it' more than I did with the material on the original post. https://www.youtube.com/watch?v=CaCcOwJPytQ https://www.youtube.com/watch?v=CaCcOwJPytQ

lopatin 3y ago

Does anyone here use Kalman filter for pairs trading?

eclectic29 3y ago

Genuine question: why does kalman filter come up so frequently on HN? Is this something I'm missing? I'm a machine learning engineer, not a data scientist.

xchip 3y ago
It is considered a difficult topic and people want to show they understand it. A similar thing happens that had the word quantic or relativistic. I'm a physicist and we hardly talk about it, but here in HN we find people bringing in up every other day
scarmig 3y ago
ML and Kalman filtering try to solve similar problems. Some theories even suggest that Kalman filtering (or a similar algorithm) provides a basis for neurobiological learning. See predictive coding (e.g. https://arxiv.org/pdf/2102.10021.pdf https://arxiv.org/pdf/2102.10021.pdf) (Why I'm interested in it, at least.)

chubs 3y ago

Recently tasked with implementing a Kalman filter, I found it very very difficult to find good resources that explained it in language that made sense to a developer like me. So after spending a month learning it, I wrote a couple posts on it, perhaps someone might find it helpful? https://www.splinter.com.au/2023/12/14/the-kalman-filter-for-programmers/ https://www.splinter.com.au/2023/12/14/the-kalman-filter-for... https://www.splinter.com.au/2023/12/15/the-kalman-filter-with-velocity/ https://www.splinter.com.au/2023/12/15/the-kalman-filter-wit... As a developer I found the maths made sense only after implementing it, ironically. I guess we learn by building on top of what we already know? Is there a term for that?

Subdivide8452 3y ago
Off topic, but why are you one of those people who do a full screen “subscribe to my mailing list” overlay? I never understand why you’d wanna do that.
- fransje26 3y ago
  Install ublock origin. No overlay to be seen.
- chubs 3y ago
  Oh, many years ago I bought into the whole 'write a blog, collect subscribers, create a training product and sell it to them, retire on the beach' idea and gave it a go. I now think that's exceedingly unlikely, of course. Sorry you find it annoying, i'll have to get around to removing it sometime.

deleted 3y ago

[deleted]