From: Stefan B. Sigurdsson (stebbi_at_cs.washington.edu)
Date: Fri Apr 25 2003 - 08:57:51 PDT
Welch and Bishop
Siggraph 2001 Kalman filter tutorial notes
Summary - Kalman filters are applicable to the observation of linear stochastic systems subject to system and measurement noise. Intuitively (as I understand it) the filter plays off measurement observations against history-based prediction, to minimize the effects of noise. Linear approximation (e.g. Taylor approximation) leads to extensions to non-linear systems. Discrete and continuous systems can be handled in the usual way, e.g. trading discrete updates (difference equations) for differential/integral equations.
Key ideas
- Recursive computation; the current value of an applicable stochastic process is decided by the preceding history of the process combined with white noise. The Kalman filters can be computed recursively which means that each discrete step in the progress of the process can be computed using the outcome of the previous step rather than the entire history. This is computationally efficient.
- Theoretically optimal; if I understood correctly from the perfunctory reading I did then the correction achieved by filter application is information-theoretically optimal. I think the message is that you can't find a more correct technique for minimizing the effects of noise on observations, which means the previous comments on efficient, recursive computation is even more important. But maybe I misunderstood, fell off the proverbial limb already...
Questions/Issues, but not really Flaws
- I need more anecdotes, more examples, to understand the specific types of applicable problems.
- Kalman filters appear to belong in a stable of powerful, mathematically intricate techniques that are seeing fairly widespread and increasing use in CS. Other tools of the same ilk include Merkle trees, Bloom filters and erasure codes. A key issue is matching the underlying assumptions to the application at hand - this has to be done carefully and correctly in order for the results to be valid. For example, erasure codes are probabilistic and have been applied to correct for packet losses in the Internet. However, the underlying assumption is that the communication channel over which the erasure-coded data moves, exhibits a random loss pattern. Internet losses, on the other hand, are bursty, e.g. the probability of loss of packet N is very dependent on the loss of packet N-1. In order to apply erasure codes data therefore has to be coded and sent in a randomized order, to give the receiver the illusion of random, uniform losses. (Some of) the Kalman filter assumptions are that both system and measurement noise are perfectly white. In other words, the process is determined perfectly by its history, except for the addition of a random factor. Many applications may have to be fiddled with in delicate ways to lend themselves to this simple model, and that can lead to subtle tradeoffs - for example, erasure codes wind up being useless for data that requires ordered delivery, because of the randomization required to fit the assumptions underlying the code mathematics.
Directions
- Reading the tutorial notes was an excellent idea; figuring out how the Kalman filters are applicable to planning is good sport. I haven't read anything about Kalman filter-based planning yet, but presumably the application is to fairly sophisticated planning problems with incomplete information/imperfect observation. The most direct fit seems to be to problems where the effects of actions can be modeled stochastically, with the addition of a random element (the Kalman filter system noise) to represent non-determinism - in other words, contingent planning problems. The plan execution then should only be observable with probabilistic accuracy, modeled with the linear measurement expression and measurement noise. Am I in free-fall yet?
- If we can trade difference equations for discrete equations and my planning application guess isn't braindead, then extension to real-valued contingency planning should be question of computational efficiency as opposed to mathematical complexity.
- Also an excellent exercise in bluffing one's way through a review, to be honest. This isn't the kind of subject I can make sense of in an hour or two, which is all I had. Much fun guessing though - looking forward to the lecture, should be good stuff!
This archive was generated by hypermail 2.1.6 : Fri Apr 25 2003 - 08:57:51 PDT