13 ms·

A non-mathematical introduction to Kalman filters for programmers

660 points by pkoird 3y ago

TekMol 3y ago
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?
- ckrapu 3y ago
  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.
- asimeqi 3y ago
  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.
  - a_wild_dandan 3y ago
    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.
    - asimeqi 3y ago
      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.
    - bee_rider 3y ago
      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.
      - tnecniv 3y ago
        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.
- sdfghswe 3y ago
  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.
- JHonaker 3y ago
  > 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.
- willow8349 3y ago
  [dead]
- trollerator23 3y ago
  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.
- alfanick 3y ago
  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.
  - tnecniv 3y ago
    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.
- kxyvr 3y ago
  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.
- tnecniv 3y ago
  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.
- mordae 3y ago
  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.
thot_experiment 3y ago
I've been wanting to make a deeper study of Kalman filters and related sensor fusion techniques for a while now, this looks like a decent resource but perhaps the hacker news horde has some even better suggestions for articles/textbooks/videos. If there is a particular piece of media that has really helped you grok this sort of thing please leave a link below!
- sdfghswe 3y ago
  The HN horde will tell you that math is bad and you should just "get your hard dirty".
  - antegamisou 3y ago
    Nice typo but 100% agree, and if you dare tell anyone some freshman college math is necessary to understand some moderate-advanced subject, you're "gatekeeping" knowledge.
    - tnecniv 3y ago
      This is the thing with math and programming. The anti-math programmers are right: you don’t need much math to have a career as a programmer because lots of applications (e.g. web pages) don’t need much math. However the more math you know, the more tools you have available to tackle problems and the more diverse the set of projects you can tackle are. You’ll spend less time reinventing the wheel and you don’t need to come up with shoddy heuristic solutions to problems because you can formally specify the problem and apply the right tool to solve it.
      - antegamisou 3y ago
        We're talking about a specific subset of people working in Computer Science. No one right in their head would claim that knowledge of 'only' HS math is insufficient when it comes to having a successful career in Front-End, Back-End, Ops, Cloud etc and many other positions pertaining to web technologies. I have no idea what people in this sector do but I'd highly doubt advanced math knowledge would even benefit their career considering they are remaining there. However the fact that there are people on this very platform saying that those who say Linear Algebra mastery is "gatekeeping" to people aspiring to become Machine Learning engineers demonstrates, at the very least, poor critical thinking on their part about the inefficiency of self - learning math only through 'pleasant' means such as: I will only watch this cool video with animations,laying on my bed, about this hard math concept instead of grabbing some paper and pencil and carefully study some high quality textbook. I need to built intuition ASAP !!! as well as showing that various different AI Bootcamp: Become an ML expert in only two weeks!! type of cashgrab scammers are sadly growing exp. in popularity.
bachmeier 3y ago
Generic warning for anyone implementing the Kalman filter. Read the first few pages of https://www.stat.berkeley.edu/~brill/Stat248/kalmanfiltering.pdf https://www.stat.berkeley.edu/~brill/Stat248/kalmanfiltering... for ways to handle numerical instability.
- davidw 3y ago
  David's random thoughts: for some reason I pictured Wile-e-coyote not handling numerical instability correctly and getting, as per usual, blown up.
- tnecniv 3y ago
  That paper contains an interesting reference to an exact generalization of the KF to a flat initial condition. I hadn’t seen that before and solves numerical issues that come from the common practice of just picking a large initial covariance. In practice, I haven’t seen any notable numerical artifacts from doing that, but it’s quite an appealing fix!
max_ 3y ago
Are Karlman filtres useful for applications that involve financial markets? If so, how?
- KRAKRISMOTT 3y ago
  That's like asking if moving averages are useful. Of course they are, because they are components of basic signal processing. What you do with the data however is entirely on you. Most of these techniques are to improve the signal-to-noise ratio, but they won't help if you don't have an idea of what you are trying to look for in the first place. More broadly, financial markets (in certain cases and depending on asset) can generally be modeled by a random walk, and that's something Kalman filters can help with as mentioned in another comment.
- esafak 3y ago
  "Linear and non-linear filtering in mathematical finance: A review" https://bura.brunel.ac.uk/handle/2438/12433 https://bura.brunel.ac.uk/handle/2438/12433
sowbug 3y ago
I'm nearsighted, and I have astigmatism. I've noticed that when I close one eye and look at something like a clock on the wall, each eye produces a differently distorted image. Each eye is a bit different. But when I look at the clock with both eyes, the image is much sharper, and better than either eye alone. The article's scenario of 1,000 ship passengers reporting their individual GPS coordinates reminded me of this phenomenon. I bet that brains use clever algorithms like Kalman filters extensively.
- bhattid 3y ago
  If you're interested in the term, what you noticed with your eyesight is an example of hyperacuity. Coincidentally, I learned about it making the same observation with my own eyes. :)
  - sowbug 3y ago
    Cool! When I asked my eye doctor, he didn't have that term for me, but he did agree that the brain is pretty amazing.
recursive 3y ago
A faulty sensor that always reads "6.8" is going to have zero variance. That would seem to make it the most trustworthy estimation. I'm sure real Kalman filters aren't so naıve, but that does seem to be a tricky part.
- sowbug 3y ago
  If I'm understanding the article, then an aspect of variance is how much a sensor deviates from the wisdom of the crowds. So the 6.8 is harmless if it happens to be close to the right answer, and downweighted if not. Which, if correct, means that Kalman filters are useful to detect malicious input to crowdsourced data like surveys, reviews, etc.
  - rcxdude 3y ago
    The kalman filter depends on having an accurate estimate of the variance to work, if you incorrectly weight an input as being far more trustworthy than it actually is then it won't work very well.
- tnecniv 3y ago
  If your only sensor is broken and tells you nothing, then your system is unobservable with such a sensor and the only thing you can do is propagate your initial uncertainty through the dynamics. The Kalman filter will do exactly that in this case.
  - rcxdude 3y ago
    not if you incorrectly estimate that the broken sensor has zero variance. In that case the kalman filter will discard all the other information and trust it completely. I think that's the point the poster is making (the article uses a somewhat naive estimate of variance)
- rcxdude 3y ago
  Yeah, actually working out the variance of your input is often the tricky bit (in a lot of cases it's just estimated once and then hardcoded, but more sophisticated approaches to try to estimate it dynamically are possible)
the__alchemist 3y ago
Nice article on an important tool. My understanding is that linear Kalman filters are an optimal solution to linear problems. Linear Kalman filters are relatively easy to understand and implement. Most applications I've found are non-linear. Extended (and unscented) Kalman filters are much tougher to grasp and implement. Resources and libraries are fewer and less useful. For example, I have an AHRS/GNSS CAN device intended for small UAVs. Extended Kalman filters for these I've come across (like for PX4 and Ardupilot) are very complex, and have many parameters. I've found it more straightforward to take an ab-initio approach using quaternion fundamentals, and nudging the gyro solution towards the accelerometer "up", and the magnetometer inclination vector. If the accelerometer magnitude differs much from 1G or the mag vector differs much from the local earth mag field strength, downweight or skip the update from that sensor, letting the gyro coast. Likely, an EKF would be the correct play, but I've given up trying to understand one, or make or adapt one that would work or be easier to tune and diagnose than the ab-initio approach.
- toasted-subs 3y ago
  Yea, when you know what you are trying to model it's extremely easy to write a model that represents a traditional linear Kalman filter. But there are many ways to write a Kalman filter; depending on where you start non-linear transformation becomes extremely cumbersome to get right.
- nextos 3y ago
  A probabilistic programming language can make it much easier to implement a non-linear filter. Essentially, you implement the generative model, and you get inference compiled for you. Interesting options to look at include ForneyLab.jl, Infer.net, Gen.jl, and Pyro.
  - tnecniv 3y ago
    This can work if the time scale of inference is smaller than the time scale of your measurements. I’m skeptical that this would work on a quadrotor that requires a fast control loop. However, model predictive control (determining actions given a state and dynamic model; the Kalman filter is model predictive estimation) first found major use in chemical plants because they could crunch the numbers on a big computer that didn’t need to fit on a robot and the real time between each time step was large. For such a situation, you might be able to get MCMC to work.
tnecniv 3y ago
There seems to be a lot of confusion about what Kalman filters are for in this thread. Perhaps that’s what happens when you seek a non-mathematical introduction to a mathematical topic but nevertheless I’m going to try and clear this up. Specifically, the Kalman filter is a recursive way to estimate the state of a dynamical system. That is, specifically, the thing you want to estimate varies is a function of time. It doesn’t matter if that thing is the position and momentum of a robot or a stock price. What does matter are the following: 1. The dynamics are linear with additive Gaussian noise. That is, the next state is a linear function of the current state plus a sample from a Gaussian distribution. Optionally, if your system is controlled (i.e., there is a variable at each moment in time you can set exactly or at least with very high accuracy), the dynamics can include a linear function of that term as well. 2. The sensor feeding you data at each time step is a linear function of the state plus a second Gaussian noise variable independent of the first. 3. You know the dynamics and sensor specification. That is, you know the matrices specifying the linear functions as well as the mean and covariances of the noise models. For a mechanical system, this knowledge could be acquired using some combination of physics, controlled experimentation in a lab, reading data sheets, and good old fashioned tuning. For other systems, you apply a similarly appropriate methodology or guess. 4. The initial distribution of your state when you start running the filter is Gaussian and you know it’s mean and covariance (if you don’t know those, you can guess because given the filter runs for a long enough time they become irrelevant) The Kalman filter takes in the parameters of the model described in (3) and gives you a new linear dynamical system that incorporates a new measurement at each time step and outputs the distribution of the current state. Since we assumed everything is linear and Gaussian, this will be a Gaussian distribution. From a Bayesian perspective, the state estimate is the posterior distribution given your sensor data, model, and initial condition. From a frequentist / decision theory perspective, you get the least squares estimate of the state subject to the constraints imposed by your dynamics. If your dynamics and sensor are not linear, you either need to linearize them, which produces the “extended Kalman filter” that gives you a “local” estimate of the state or you need another method. A common choice is a particle filter. If your model is garbage, then model based methods like the Kalman filter will give you garbage. If your sensor is garbage (someone mentioned the case where it outputs a fixed number), the Kalman filter will just propagate your uncertainty about the initial condition through the dynamics.
hazrmard 3y ago
Complementary to this, if you are looking for a thorough, mathematical introduction to Kalman Filters and family, I will highly recommend this book[1] - Written by a software engineer who had to implement kalman filters for his job. How he motivates and conveys concepts may resonate with this audience. - Written as interactive Jupyter notebooks. You can clone the repository and run through the lessons. - Incremental improvements. Starting from a simple filter, incorporating Bayes' rule, and extending to probability distributions. It provides a gentle on-ramp to Kalman filters. [1]: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python/ https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
- ozim 3y ago
  Was going to ask about applications - but applications are there in GitHub in description. Thanks seems like something I might use one day.
frankreyes 3y ago
I've always wanted to write a numerical Kalman Filter code, to just plug a function and then get it's derivative. It would be slow but it would be easier to use
akhayam 3y ago
Wow... you left me wondering why signal processing teachers in college don't teach Kalman Filters with this simplicity. I know mathematical concepts are best taught mathematically, but that does led to information loss for those who don't have the background requisites. I used to teach Discrete Cosine Transform and Wavelet Transform through images alone and would always find this teaching method of "intuition before rigor" work better than the other way around.
- kccqzy 3y ago
  Totally agreed. One of the favorite professors in college would introduce a theorem, and instead of jumping into proving it, would first show us useful applications of the theorem, and then prove it afterwards.
  - _a_a_a_ 3y ago
    Aw god, Yes, Yes, Yes! I understand applications not abstractions so show me it's value and I'll understand it immediately, or give me a massive motivation to understand it if I don't. If they'd taken that approach at my schools and university I'd have been so much better off.
  - stjohnswarts 3y ago
    This is exactly what I did as a grad student when I taught classes for my prof. She preferred bottom up and I preferred top down. I wanted to give people a reason for learning what they were getting ready to learn rather than "let's start from first principles" that almost all my professors wanted to do.
    - p1necone 3y ago
      I prefer the exact same approach for learning to play board games too. Your 20 minutes of rules explanation will go completely over my head unless you start with "the goal/win condition of the game is to get more points/reach the end faster/collect all the macguffins".
MayeulC 3y ago
That other article had nice visualizations too: https://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/ https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture... Posted to HN three times already :)
esafak 3y ago
MSR's Christopher Bishop offers a more intuitive, Bayesian derivation of the Kalman filter: https://www.youtube.com/watch?v=QJSEQeH40hM https://www.youtube.com/watch?v=QJSEQeH40hM http://mlss.tuebingen.mpg.de/2013/2013/bishop_slides.pdf#page=86 http://mlss.tuebingen.mpg.de/2013/2013/bishop_slides.pdf#pag...
askvictor 3y ago
My first real programming job was implementing a Kalman filter for GPS car applications in the 90s. GPS still had crippled accuracy for civilians back then (about 100m), which made it useless for turn-by-turn navigation in your car. But assuming that you have an accurate location at the start of the journey, and that the car stays on roads (and that the road maps are accurate), then we could filter it down to a decent reading.
- travisjungroth 3y ago
  I wonder how the intentional noise in GPS handled this. The point was for other forces to not have it for combat purposes. But, it seems like even a mediocre inertial navigation system, speedometer, or airspeed sensor combined with a Kalman filter and GPS would be very accurate. Calculating position from velocity is very accurate, but suffers from drift. GPS does not. I wonder how accurate you can get with 1% variance velocity measurement and 100m variance GPS measurement on something doing 500km/h.
  - tnecniv 3y ago
    You can actually compute that! Model your agent’s dynamics (even just pick a double integrator, I.e., an agent where the acceleration is controlled, or something) and pick a value for the GPS covariance. You can compute the infinite-time limit of the variance of the Kalman filter exactly (your favorite numerical package has a function for solving algebraic Riccati equations which is all you need to do this). No simulated observations are necessary, just the dynamics and the GPS noise. My guess is that you’ll find the filter converges to a distribution that has a decently large covariance if the military didn’t want other forces using it to make good decisions.
    - travisjungroth 3y ago
      Thank you very much for the suggestion. There are enough words in it I don’t know that I’d need to spend a “new math domain to learn” token, and I’m out of those right now. Need to ship something to earn more. I will remain in a state of wonder for the time being.
inopinatus 3y ago
Thanks for this! tiny nitpick: the transparency in the ship illustrations becomes problematic when the page renders in dark mode.
phkahler 3y ago
There is one aspect missing. When taking the weighted average of a prediction and measurement, the weights can be time varying in a Kalman filter. Otherwise I believe it goes by a different name. A good example is a single sensor measuring a slowly changing quantity. A fuel Guage for example. A good estimate from second to second is that there is no change, but a measurement may have noise (fuel sloshing around in the tank). A Kalman filter in this case will look like a first order low-pass filter with an exponentially decaying gain. The cutoff frequency changes so you can find the starting level quickly (in seconds) but then ignore the noise with a very low frequency cutoff (0.01hz say).
tr_user 3y ago
More people should read this. A few weeks back some commenter on another thread was saying it makes perfect sense to break a sensor if you had more than one in order to get more certainty. Facepalm.
- antegamisou 3y ago
  This is your brain on LLMs!!!
- tnecniv 3y ago
  Ah yes, let me triangulate myself with one point
parentheses 3y ago
Don't know anything formal in this field but this is a really great explainer. It's worth mentioning that if devices are miscalibrated such that the distribution is not centered around ground truth, this approach breaks down. Maybe there are more sophisticated ways to solve this that work well with the approach described. Not sure, but curious.
- joeyo 3y ago
  That doesn't pose an issue: the "observation model" of a Kalman filer allows for affine transformations (e.g. scale, rotation, and offset) between the sensor data and the "true" latent state that you wish to estimate. Even better, it can appropriately handle correlational structure between your sensors. What the Kalman filter equations don't tell you, is how to estimate the parameters of such an observation model. You either have to write it down from first principles, estimate it from "fully observed" data (if you have such a luxury), estimate it (up to a rotation) using expectation maximization (EM), or guess.
havercosine 3y ago
This is a great post. Another aha! moment I had in understanding Kalman Filter came from a short note by John D. Cook (link: https://www.johndcook.com/blog/applied-kalman-filtering/ https://www.johndcook.com/blog/applied-kalman-filtering/) . A traditional calculus/differential equations based modelling of systems takes a view that there is no uncertainty in the data and everything is captured by system model. OTOH, data driven estimator will say that "it is all in the data", completely ignoring the model of the physical process that is generating the data. Beauty of Kalman filters is that it combines these two approaches.
graycat 3y ago
(1) Uh, just to mention, while sometimes some norms of math writing are not always made fully clear, in writing with math expressions it is important at least to define the symbols and also good to define the terms, motivate the discussion, give intuitive views, and give examples. In particular, (a) in physics it is standard to have some globally defined, understood, and accepted symbols, e.g., in F = ma, F for force, m for mass, and a for acceleration. (b) Uh, essentially that is not done in math and, instead, in each paper, discussion, text chapter, etc. really should start even from, say, R -- the set of real numbers n -- a positive whole number e -- the base of the natural logarithm etc. The paper that is the subject of this thread had some math notation without such definitions. (2) My standard, quite clear, go-to source on Kalman filters is the section in (with TeX syntax) David G.\ Luenberger, {\it Optimization by Vector Space Methods,\/} John Wiley and Sons, Inc., New York, 1969.\ \ That's a really good example of some really good math and writing of math.
bmitc 3y ago
This is great! Thanks for posting this. I'm going to have to definitely read through it more carefully later. Also, this reminds of a tutorial that covered PID controllers. There were very good, animated JavaScript diagrams and plots that showed individually why each of the P, I, and D were needed in such a control system with the animations supporting the argument. I have tried finding it before, but I can't find it. It was posted on Hacker News. Does anyone know of one like this?
fifilura 3y ago
My experience with kalman filters is that it is important to reflect that what you are measuring (the output) actually has one true value, and not a range of values. Determining a position of something has one true value (unless you go into quantum mechanics) while many things may not, such as hardness of a piece of wood, color of a car temperature in a lake etc. All of these may vary depending on the position you measure. You may be fooled by thinking that since the kalman filter outputs a value and an uncertainty that it actually incorporates the uncertainty in the output parameter. But it is not the same. An example. If you have a measurement between 0 and 1 that is 0.2. And then get another measurement that is 0.8. The filter will be more certain that the output is 0.5, than with only one measuerement of 0.2. Instead of widening the uncertainty as the intuition may tell you.
Chriswite 3y ago
[flagged]
neycoda 3y ago
So the human mind uses Kalman Filters.
arch-dawson 3y ago
I enjoyed reading your article, but I want to note that the implementation is incorrect. The biggest error is that you are not propagating uncertainty forward in time, and therefore are underestimating the error. This shows up in your plots---the error bounds should cover the true state most of the time, but they do not in your results. A couple more nits to pick: "In essence, each of the 1000 passengers are doing thus: take the last known position (at the time before the present), add the velocity, and also, knowing that the wind and the water waves are going to slightly alter the course, add some random estimated fluctuations to it." The passengers don't add noise to their estimate. For the passengers, the expected value of the state at time k+1 given the state at time k will just be `position_k+1 = position_k + velocity * Delta_t`. The /true/ dynamics include noise, which is accounted for in the filter by adding to the estimated covariance. Your code doesn't break because you're taking a bunch of samples of the dynamics (by having 1000 passengers) and numerically taking the variance of the results. This is very different than what is usually done in practice. It's a common misconception that GPS is affected by weather. It is not. You are using a very non-standard definition of consistency. In estimation theory, having an estimator be consistent means that as you get more and more data, your estimator will converge to the true value. Thank you for writing up the article and simplifying for a general audience, but there are a few misunderstandings here that seem to be causing problems. I am a graduate student in estimation theory and I would be happy to talk more about this if it would be helpful.
- sundarurfriend 3y ago
  > The /true/ dynamics include noise, which is accounted for in the filter by adding to the estimated covariance. Could you expand on this a bit? Specifically, what is the "estimated covariance", and what is added to it?
  - arch-dawson 3y ago
    Kalman Filters track both an estimate x_hat and the variance of that estimate, P. There is also some true state, x_true. The definition of the variance of the estimate is E[(x_true - x_hat)^2], where E[.] is the expected value operator. Using the example from the post, there is a known dynamics function that propagates the state one time step forward. That function is f(x, w) = x + velocity * Delta_t + w, where w is zero-mean Gaussian noise (meaning that E[w] = 0) with some known variance sigma_w^2 (meaning that E[w^2] = sigma_w^2). To update the true state, we do x_true_k+1 = f(x_true_k, w) = x_true_k + velocity * Delta_t + w. So what should the filter's estimate of the state at time t_k+1 be? Well, if our estimator has been working up to this point, then x_hat_k = E[x_true_k] (this is just saying that our estimate is the "best guess" of the true state). We also want it to be true that x_hat_k+1 = E[x_true_k+1]. Plugging in the true dynamics from earlier, we get that x_hat_k+1 = E[x_true_k + velocity * Delta_t + w] = E[x_true_k] + E[velocity * Delta_t] + E[w] = x_hat_k + velocity * Delta_t + 0. Note that we are not adding noise to the estimate. The filter has no way of knowing the noise that enters the system, the filter will just be correct /on average/ for the noise that comes up. It is also important to update the uncertainty in the estimate. State estimates are of little use without knowledge of the uncertainty. If the estimate is being fed into a self-driving car or something, "The car is here!" is pretty useless on its own. "The car is here, plus or minus 10 cm" means the car can drive as normal, but "The car is here, I think, or maybe in one of the surrounding states" means there's a problem. We already know that the definition of the variance is P_k=E[(x_true_k - x_hat_k)^2]. Let's say that at time t_k, P_k = sigma^2. To get the variance at time t_k+1, we can just apply the definition. P_k+1 = E[(x_true_k+1 - x_hat_k+1)^2] = E[((x_true_k + velocity * Delta_t + w) - (x_hat_k + velocity * Delta_t))^2] = <skipping some steps> = E[(x_true_k - x_hat_k)^2] + E[w^2] = P_k + sigma_w^2 = sigma^2 + sigma_w^2. So the variance at the new time is equal to the old covariance sigma^2, plus some uncertainty accounting for the noise added in the dynamics sigma_w^2. Sorry about the poor math formatting, but I hope that answers your question!
pidtuner 3y ago
[dead]

660 points by pkoird 3y ago

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?

ckrapu 3y ago
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.
asimeqi 3y ago
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.
- a_wild_dandan 3y ago
  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.
  - asimeqi 3y ago
    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.
  - bee_rider 3y ago
    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.
    - tnecniv 3y ago
      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.
sdfghswe 3y ago
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.
JHonaker 3y ago
> 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.
willow8349 3y ago
[dead]
trollerator23 3y ago
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.
alfanick 3y ago
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.
- tnecniv 3y ago
  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.
kxyvr 3y ago
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.
tnecniv 3y ago
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.
mordae 3y ago
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.

thot_experiment 3y ago

I've been wanting to make a deeper study of Kalman filters and related sensor fusion techniques for a while now, this looks like a decent resource but perhaps the hacker news horde has some even better suggestions for articles/textbooks/videos. If there is a particular piece of media that has really helped you grok this sort of thing please leave a link below!

sdfghswe 3y ago
The HN horde will tell you that math is bad and you should just "get your hard dirty".
- antegamisou 3y ago
  Nice typo but 100% agree, and if you dare tell anyone some freshman college math is necessary to understand some moderate-advanced subject, you're "gatekeeping" knowledge.
  - tnecniv 3y ago
    This is the thing with math and programming. The anti-math programmers are right: you don’t need much math to have a career as a programmer because lots of applications (e.g. web pages) don’t need much math. However the more math you know, the more tools you have available to tackle problems and the more diverse the set of projects you can tackle are. You’ll spend less time reinventing the wheel and you don’t need to come up with shoddy heuristic solutions to problems because you can formally specify the problem and apply the right tool to solve it.
    - antegamisou 3y ago
      We're talking about a specific subset of people working in Computer Science. No one right in their head would claim that knowledge of 'only' HS math is insufficient when it comes to having a successful career in Front-End, Back-End, Ops, Cloud etc and many other positions pertaining to web technologies. I have no idea what people in this sector do but I'd highly doubt advanced math knowledge would even benefit their career considering they are remaining there. However the fact that there are people on this very platform saying that those who say Linear Algebra mastery is "gatekeeping" to people aspiring to become Machine Learning engineers demonstrates, at the very least, poor critical thinking on their part about the inefficiency of self - learning math only through 'pleasant' means such as: I will only watch this cool video with animations,laying on my bed, about this hard math concept instead of grabbing some paper and pencil and carefully study some high quality textbook. I need to built intuition ASAP !!! as well as showing that various different AI Bootcamp: Become an ML expert in only two weeks!! type of cashgrab scammers are sadly growing exp. in popularity.

bachmeier 3y ago

Generic warning for anyone implementing the Kalman filter. Read the first few pages of https://www.stat.berkeley.edu/~brill/Stat248/kalmanfiltering.pdf https://www.stat.berkeley.edu/~brill/Stat248/kalmanfiltering... for ways to handle numerical instability.

davidw 3y ago
David's random thoughts: for some reason I pictured Wile-e-coyote not handling numerical instability correctly and getting, as per usual, blown up.
tnecniv 3y ago
That paper contains an interesting reference to an exact generalization of the KF to a flat initial condition. I hadn’t seen that before and solves numerical issues that come from the common practice of just picking a large initial covariance. In practice, I haven’t seen any notable numerical artifacts from doing that, but it’s quite an appealing fix!

max_ 3y ago

Are Karlman filtres useful for applications that involve financial markets? If so, how?

KRAKRISMOTT 3y ago
That's like asking if moving averages are useful. Of course they are, because they are components of basic signal processing. What you do with the data however is entirely on you. Most of these techniques are to improve the signal-to-noise ratio, but they won't help if you don't have an idea of what you are trying to look for in the first place. More broadly, financial markets (in certain cases and depending on asset) can generally be modeled by a random walk, and that's something Kalman filters can help with as mentioned in another comment.
esafak 3y ago
"Linear and non-linear filtering in mathematical finance: A review" https://bura.brunel.ac.uk/handle/2438/12433 https://bura.brunel.ac.uk/handle/2438/12433

sowbug 3y ago

I'm nearsighted, and I have astigmatism. I've noticed that when I close one eye and look at something like a clock on the wall, each eye produces a differently distorted image. Each eye is a bit different. But when I look at the clock with both eyes, the image is much sharper, and better than either eye alone. The article's scenario of 1,000 ship passengers reporting their individual GPS coordinates reminded me of this phenomenon. I bet that brains use clever algorithms like Kalman filters extensively.

bhattid 3y ago
If you're interested in the term, what you noticed with your eyesight is an example of hyperacuity. Coincidentally, I learned about it making the same observation with my own eyes. :)
- sowbug 3y ago
  Cool! When I asked my eye doctor, he didn't have that term for me, but he did agree that the brain is pretty amazing.

recursive 3y ago

A faulty sensor that always reads "6.8" is going to have zero variance. That would seem to make it the most trustworthy estimation. I'm sure real Kalman filters aren't so naıve, but that does seem to be a tricky part.

sowbug 3y ago
If I'm understanding the article, then an aspect of variance is how much a sensor deviates from the wisdom of the crowds. So the 6.8 is harmless if it happens to be close to the right answer, and downweighted if not. Which, if correct, means that Kalman filters are useful to detect malicious input to crowdsourced data like surveys, reviews, etc.
- rcxdude 3y ago
  The kalman filter depends on having an accurate estimate of the variance to work, if you incorrectly weight an input as being far more trustworthy than it actually is then it won't work very well.
tnecniv 3y ago
If your only sensor is broken and tells you nothing, then your system is unobservable with such a sensor and the only thing you can do is propagate your initial uncertainty through the dynamics. The Kalman filter will do exactly that in this case.
- rcxdude 3y ago
  not if you incorrectly estimate that the broken sensor has zero variance. In that case the kalman filter will discard all the other information and trust it completely. I think that's the point the poster is making (the article uses a somewhat naive estimate of variance)
rcxdude 3y ago
Yeah, actually working out the variance of your input is often the tricky bit (in a lot of cases it's just estimated once and then hardcoded, but more sophisticated approaches to try to estimate it dynamically are possible)

the__alchemist 3y ago

Nice article on an important tool. My understanding is that linear Kalman filters are an optimal solution to linear problems. Linear Kalman filters are relatively easy to understand and implement. Most applications I've found are non-linear. Extended (and unscented) Kalman filters are much tougher to grasp and implement. Resources and libraries are fewer and less useful. For example, I have an AHRS/GNSS CAN device intended for small UAVs. Extended Kalman filters for these I've come across (like for PX4 and Ardupilot) are very complex, and have many parameters. I've found it more straightforward to take an ab-initio approach using quaternion fundamentals, and nudging the gyro solution towards the accelerometer "up", and the magnetometer inclination vector. If the accelerometer magnitude differs much from 1G or the mag vector differs much from the local earth mag field strength, downweight or skip the update from that sensor, letting the gyro coast. Likely, an EKF would be the correct play, but I've given up trying to understand one, or make or adapt one that would work or be easier to tune and diagnose than the ab-initio approach.

toasted-subs 3y ago
Yea, when you know what you are trying to model it's extremely easy to write a model that represents a traditional linear Kalman filter. But there are many ways to write a Kalman filter; depending on where you start non-linear transformation becomes extremely cumbersome to get right.
nextos 3y ago
A probabilistic programming language can make it much easier to implement a non-linear filter. Essentially, you implement the generative model, and you get inference compiled for you. Interesting options to look at include ForneyLab.jl, Infer.net, Gen.jl, and Pyro.
- tnecniv 3y ago
  This can work if the time scale of inference is smaller than the time scale of your measurements. I’m skeptical that this would work on a quadrotor that requires a fast control loop. However, model predictive control (determining actions given a state and dynamic model; the Kalman filter is model predictive estimation) first found major use in chemical plants because they could crunch the numbers on a big computer that didn’t need to fit on a robot and the real time between each time step was large. For such a situation, you might be able to get MCMC to work.

tnecniv 3y ago

There seems to be a lot of confusion about what Kalman filters are for in this thread. Perhaps that’s what happens when you seek a non-mathematical introduction to a mathematical topic but nevertheless I’m going to try and clear this up. Specifically, the Kalman filter is a recursive way to estimate the state of a dynamical system. That is, specifically, the thing you want to estimate varies is a function of time. It doesn’t matter if that thing is the position and momentum of a robot or a stock price. What does matter are the following: 1. The dynamics are linear with additive Gaussian noise. That is, the next state is a linear function of the current state plus a sample from a Gaussian distribution. Optionally, if your system is controlled (i.e., there is a variable at each moment in time you can set exactly or at least with very high accuracy), the dynamics can include a linear function of that term as well. 2. The sensor feeding you data at each time step is a linear function of the state plus a second Gaussian noise variable independent of the first. 3. You know the dynamics and sensor specification. That is, you know the matrices specifying the linear functions as well as the mean and covariances of the noise models. For a mechanical system, this knowledge could be acquired using some combination of physics, controlled experimentation in a lab, reading data sheets, and good old fashioned tuning. For other systems, you apply a similarly appropriate methodology or guess. 4. The initial distribution of your state when you start running the filter is Gaussian and you know it’s mean and covariance (if you don’t know those, you can guess because given the filter runs for a long enough time they become irrelevant) The Kalman filter takes in the parameters of the model described in (3) and gives you a new linear dynamical system that incorporates a new measurement at each time step and outputs the distribution of the current state. Since we assumed everything is linear and Gaussian, this will be a Gaussian distribution. From a Bayesian perspective, the state estimate is the posterior distribution given your sensor data, model, and initial condition. From a frequentist / decision theory perspective, you get the least squares estimate of the state subject to the constraints imposed by your dynamics. If your dynamics and sensor are not linear, you either need to linearize them, which produces the “extended Kalman filter” that gives you a “local” estimate of the state or you need another method. A common choice is a particle filter. If your model is garbage, then model based methods like the Kalman filter will give you garbage. If your sensor is garbage (someone mentioned the case where it outputs a fixed number), the Kalman filter will just propagate your uncertainty about the initial condition through the dynamics.

hazrmard 3y ago

Complementary to this, if you are looking for a thorough, mathematical introduction to Kalman Filters and family, I will highly recommend this book[1] - Written by a software engineer who had to implement kalman filters for his job. How he motivates and conveys concepts may resonate with this audience. - Written as interactive Jupyter notebooks. You can clone the repository and run through the lessons. - Incremental improvements. Starting from a simple filter, incorporating Bayes' rule, and extending to probability distributions. It provides a gentle on-ramp to Kalman filters. [1]: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python/ https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...

ozim 3y ago
Was going to ask about applications - but applications are there in GitHub in description. Thanks seems like something I might use one day.

frankreyes 3y ago

I've always wanted to write a numerical Kalman Filter code, to just plug a function and then get it's derivative. It would be slow but it would be easier to use

akhayam 3y ago

Wow... you left me wondering why signal processing teachers in college don't teach Kalman Filters with this simplicity. I know mathematical concepts are best taught mathematically, but that does led to information loss for those who don't have the background requisites. I used to teach Discrete Cosine Transform and Wavelet Transform through images alone and would always find this teaching method of "intuition before rigor" work better than the other way around.

kccqzy 3y ago
Totally agreed. One of the favorite professors in college would introduce a theorem, and instead of jumping into proving it, would first show us useful applications of the theorem, and then prove it afterwards.
- _a_a_a_ 3y ago
  Aw god, Yes, Yes, Yes! I understand applications not abstractions so show me it's value and I'll understand it immediately, or give me a massive motivation to understand it if I don't. If they'd taken that approach at my schools and university I'd have been so much better off.
- stjohnswarts 3y ago
  This is exactly what I did as a grad student when I taught classes for my prof. She preferred bottom up and I preferred top down. I wanted to give people a reason for learning what they were getting ready to learn rather than "let's start from first principles" that almost all my professors wanted to do.
  - p1necone 3y ago
    I prefer the exact same approach for learning to play board games too. Your 20 minutes of rules explanation will go completely over my head unless you start with "the goal/win condition of the game is to get more points/reach the end faster/collect all the macguffins".

MayeulC 3y ago

That other article had nice visualizations too: https://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/ https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture... Posted to HN three times already :)

esafak 3y ago

MSR's Christopher Bishop offers a more intuitive, Bayesian derivation of the Kalman filter: https://www.youtube.com/watch?v=QJSEQeH40hM https://www.youtube.com/watch?v=QJSEQeH40hM http://mlss.tuebingen.mpg.de/2013/2013/bishop_slides.pdf#page=86 http://mlss.tuebingen.mpg.de/2013/2013/bishop_slides.pdf#pag...

askvictor 3y ago

My first real programming job was implementing a Kalman filter for GPS car applications in the 90s. GPS still had crippled accuracy for civilians back then (about 100m), which made it useless for turn-by-turn navigation in your car. But assuming that you have an accurate location at the start of the journey, and that the car stays on roads (and that the road maps are accurate), then we could filter it down to a decent reading.

travisjungroth 3y ago
I wonder how the intentional noise in GPS handled this. The point was for other forces to not have it for combat purposes. But, it seems like even a mediocre inertial navigation system, speedometer, or airspeed sensor combined with a Kalman filter and GPS would be very accurate. Calculating position from velocity is very accurate, but suffers from drift. GPS does not. I wonder how accurate you can get with 1% variance velocity measurement and 100m variance GPS measurement on something doing 500km/h.
- tnecniv 3y ago
  You can actually compute that! Model your agent’s dynamics (even just pick a double integrator, I.e., an agent where the acceleration is controlled, or something) and pick a value for the GPS covariance. You can compute the infinite-time limit of the variance of the Kalman filter exactly (your favorite numerical package has a function for solving algebraic Riccati equations which is all you need to do this). No simulated observations are necessary, just the dynamics and the GPS noise. My guess is that you’ll find the filter converges to a distribution that has a decently large covariance if the military didn’t want other forces using it to make good decisions.
  - travisjungroth 3y ago
    Thank you very much for the suggestion. There are enough words in it I don’t know that I’d need to spend a “new math domain to learn” token, and I’m out of those right now. Need to ship something to earn more. I will remain in a state of wonder for the time being.

inopinatus 3y ago

Thanks for this! tiny nitpick: the transparency in the ship illustrations becomes problematic when the page renders in dark mode.

phkahler 3y ago

There is one aspect missing. When taking the weighted average of a prediction and measurement, the weights can be time varying in a Kalman filter. Otherwise I believe it goes by a different name. A good example is a single sensor measuring a slowly changing quantity. A fuel Guage for example. A good estimate from second to second is that there is no change, but a measurement may have noise (fuel sloshing around in the tank). A Kalman filter in this case will look like a first order low-pass filter with an exponentially decaying gain. The cutoff frequency changes so you can find the starting level quickly (in seconds) but then ignore the noise with a very low frequency cutoff (0.01hz say).

tr_user 3y ago

More people should read this. A few weeks back some commenter on another thread was saying it makes perfect sense to break a sensor if you had more than one in order to get more certainty. Facepalm.

antegamisou 3y ago
This is your brain on LLMs!!!
tnecniv 3y ago
Ah yes, let me triangulate myself with one point

parentheses 3y ago

Don't know anything formal in this field but this is a really great explainer. It's worth mentioning that if devices are miscalibrated such that the distribution is not centered around ground truth, this approach breaks down. Maybe there are more sophisticated ways to solve this that work well with the approach described. Not sure, but curious.

joeyo 3y ago
That doesn't pose an issue: the "observation model" of a Kalman filer allows for affine transformations (e.g. scale, rotation, and offset) between the sensor data and the "true" latent state that you wish to estimate. Even better, it can appropriately handle correlational structure between your sensors. What the Kalman filter equations don't tell you, is how to estimate the parameters of such an observation model. You either have to write it down from first principles, estimate it from "fully observed" data (if you have such a luxury), estimate it (up to a rotation) using expectation maximization (EM), or guess.

havercosine 3y ago

This is a great post. Another aha! moment I had in understanding Kalman Filter came from a short note by John D. Cook (link: https://www.johndcook.com/blog/applied-kalman-filtering/ https://www.johndcook.com/blog/applied-kalman-filtering/) . A traditional calculus/differential equations based modelling of systems takes a view that there is no uncertainty in the data and everything is captured by system model. OTOH, data driven estimator will say that "it is all in the data", completely ignoring the model of the physical process that is generating the data. Beauty of Kalman filters is that it combines these two approaches.

graycat 3y ago

(1) Uh, just to mention, while sometimes some norms of math writing are not always made fully clear, in writing with math expressions it is important at least to define the symbols and also good to define the terms, motivate the discussion, give intuitive views, and give examples. In particular, (a) in physics it is standard to have some globally defined, understood, and accepted symbols, e.g., in F = ma, F for force, m for mass, and a for acceleration. (b) Uh, essentially that is not done in math and, instead, in each paper, discussion, text chapter, etc. really should start even from, say, R -- the set of real numbers n -- a positive whole number e -- the base of the natural logarithm etc. The paper that is the subject of this thread had some math notation without such definitions. (2) My standard, quite clear, go-to source on Kalman filters is the section in (with TeX syntax) David G.\ Luenberger, {\it Optimization by Vector Space Methods,\/} John Wiley and Sons, Inc., New York, 1969.\ \ That's a really good example of some really good math and writing of math.

bmitc 3y ago

This is great! Thanks for posting this. I'm going to have to definitely read through it more carefully later. Also, this reminds of a tutorial that covered PID controllers. There were very good, animated JavaScript diagrams and plots that showed individually why each of the P, I, and D were needed in such a control system with the animations supporting the argument. I have tried finding it before, but I can't find it. It was posted on Hacker News. Does anyone know of one like this?

fifilura 3y ago

My experience with kalman filters is that it is important to reflect that what you are measuring (the output) actually has one true value, and not a range of values. Determining a position of something has one true value (unless you go into quantum mechanics) while many things may not, such as hardness of a piece of wood, color of a car temperature in a lake etc. All of these may vary depending on the position you measure. You may be fooled by thinking that since the kalman filter outputs a value and an uncertainty that it actually incorporates the uncertainty in the output parameter. But it is not the same. An example. If you have a measurement between 0 and 1 that is 0.2. And then get another measurement that is 0.8. The filter will be more certain that the output is 0.5, than with only one measuerement of 0.2. Instead of widening the uncertainty as the intuition may tell you.

Chriswite 3y ago

[flagged]

neycoda 3y ago

So the human mind uses Kalman Filters.

arch-dawson 3y ago

I enjoyed reading your article, but I want to note that the implementation is incorrect. The biggest error is that you are not propagating uncertainty forward in time, and therefore are underestimating the error. This shows up in your plots---the error bounds should cover the true state most of the time, but they do not in your results. A couple more nits to pick: "In essence, each of the 1000 passengers are doing thus: take the last known position (at the time before the present), add the velocity, and also, knowing that the wind and the water waves are going to slightly alter the course, add some random estimated fluctuations to it." The passengers don't add noise to their estimate. For the passengers, the expected value of the state at time k+1 given the state at time k will just be `position_k+1 = position_k + velocity * Delta_t`. The /true/ dynamics include noise, which is accounted for in the filter by adding to the estimated covariance. Your code doesn't break because you're taking a bunch of samples of the dynamics (by having 1000 passengers) and numerically taking the variance of the results. This is very different than what is usually done in practice. It's a common misconception that GPS is affected by weather. It is not. You are using a very non-standard definition of consistency. In estimation theory, having an estimator be consistent means that as you get more and more data, your estimator will converge to the true value. Thank you for writing up the article and simplifying for a general audience, but there are a few misunderstandings here that seem to be causing problems. I am a graduate student in estimation theory and I would be happy to talk more about this if it would be helpful.

sundarurfriend 3y ago
> The /true/ dynamics include noise, which is accounted for in the filter by adding to the estimated covariance. Could you expand on this a bit? Specifically, what is the "estimated covariance", and what is added to it?
- arch-dawson 3y ago
  Kalman Filters track both an estimate x_hat and the variance of that estimate, P. There is also some true state, x_true. The definition of the variance of the estimate is E[(x_true - x_hat)^2], where E[.] is the expected value operator. Using the example from the post, there is a known dynamics function that propagates the state one time step forward. That function is f(x, w) = x + velocity * Delta_t + w, where w is zero-mean Gaussian noise (meaning that E[w] = 0) with some known variance sigma_w^2 (meaning that E[w^2] = sigma_w^2). To update the true state, we do x_true_k+1 = f(x_true_k, w) = x_true_k + velocity * Delta_t + w. So what should the filter's estimate of the state at time t_k+1 be? Well, if our estimator has been working up to this point, then x_hat_k = E[x_true_k] (this is just saying that our estimate is the "best guess" of the true state). We also want it to be true that x_hat_k+1 = E[x_true_k+1]. Plugging in the true dynamics from earlier, we get that x_hat_k+1 = E[x_true_k + velocity * Delta_t + w] = E[x_true_k] + E[velocity * Delta_t] + E[w] = x_hat_k + velocity * Delta_t + 0. Note that we are not adding noise to the estimate. The filter has no way of knowing the noise that enters the system, the filter will just be correct /on average/ for the noise that comes up. It is also important to update the uncertainty in the estimate. State estimates are of little use without knowledge of the uncertainty. If the estimate is being fed into a self-driving car or something, "The car is here!" is pretty useless on its own. "The car is here, plus or minus 10 cm" means the car can drive as normal, but "The car is here, I think, or maybe in one of the surrounding states" means there's a problem. We already know that the definition of the variance is P_k=E[(x_true_k - x_hat_k)^2]. Let's say that at time t_k, P_k = sigma^2. To get the variance at time t_k+1, we can just apply the definition. P_k+1 = E[(x_true_k+1 - x_hat_k+1)^2] = E[((x_true_k + velocity * Delta_t + w) - (x_hat_k + velocity * Delta_t))^2] = <skipping some steps> = E[(x_true_k - x_hat_k)^2] + E[w^2] = P_k + sigma_w^2 = sigma^2 + sigma_w^2. So the variance at the new time is equal to the old covariance sigma^2, plus some uncertainty accounting for the noise added in the dynamics sigma_w^2. Sorry about the poor math formatting, but I hope that answers your question!

pidtuner 3y ago

[dead]