Post Reply 
Apollo 11 + Kalman filter = Particle filter for epidemic modeling ?
04-19-2020, 06:49 PM
Post: #1
Apollo 11 + Kalman filter = Particle filter for epidemic modeling ?
from Understanding the Unseen
"When NASA first decided to put a man on the Moon, they had a problem. Actually, they had several problems … One of the biggest stumbling blocks was estimating the spacecraft's trajectory: how could NASA send astronauts to the Moon if they didn't know where they were?

Randomness and errors
Working out the trajectories had proven difficult for the researchers because they were really trying to solve two problems at once. The first was that spacecraft don't accelerate and move smoothly in real life, as they might in a physics textbook. They are subject to variable effects like lunar gravity, which are often unknown. This randomness meant that even if the scientists could have observed the craft's exact position, the trajectory wouldn't follow a neat, predictable path.

But that was their second problem: they couldn't observe its exact position. Although onboard sensors included a sextant, which calculated the angle of the Earth and Moon relative to the spacecraft, and gyroscopes, it wasn't clear how this data – which inevitably contained measurement errors – could be accurately translated back into position and velocity.

The Kalman filter
Kalman's technique was called a filter and worked in two steps. The first used Newtonian physics to make a prediction about the current state of the system (in NASA's case the location of the spacecraft) and the level of uncertainly due to possible random effects. The second step then used a weighted average to combine the most recently observed measurement, which inevitably had some degree of error, with this prediction … But the Kalman filter does something cleverer than this. It takes the level of randomness that went into the prediction, and the amount of error we think there is in the measurement, and combines them to give the optimal value for the relative confidence $K$. If the prediction was trusted more than the measurement, more weight is given to the prediction. Conversely, if the measurements were more plausible, then these are given more preference.

From trajectories to transmission
Decades after the Moon landings questions still remain about how best to estimate hidden information, and it's not just engineers asking them. Disease researchers have long wondered how to understand the true spread of an infection (which they can't see) using hospital case reports (which they can). In some ways it's not that different from the problem NASA had. Even if researchers try and make predictions by assuming a disease transmits in a certain way, its spread will still be affected by randomness. And it's unlikely the proportion of infected people who go and see a doctor will remain constant, which means any measurement method – for example, assuming hospital reports represent a certain fraction of total infections – is also subject to error.
Unfortunately NASA's solution isn't much help when it comes to epidemics. The Kalman filter only works for specific types of problem in which we can write down an equation for what the system should be doing in theory. That might be the case for spacecraft trajectories and other physics-based puzzles, but it's less so when dealing with complex biological systems. Instead, we are forced to simulate lots of outbreaks, each influenced by random effects, in the hope of discovering which ones line up with the hospital data.
Of course running a huge number of simulations requires a lot of effort. Ideally we want a way of keeping predictions that agree with the case reports over time, and throwing out the ones that don't. This can be done with a method known as a particle filter. Whereas the Kalman filter makes a single prediction at each point in time, then adjusts it using the observed data, a particle filter uses simulations to make a large number of predictions (the particles) at each point in time. These particles – which are all different because of the randomness in the system – are then weighted based on how likely they are to produce the observed data, and the "lighter" particles pruned away (the filter). In essence, it's a process of natural selection: over time, the best predictions survive, and the weaker ones fall by the wayside.
Making the right predictions
Particle filters rely on computer simulations which assume that the disease transmits in a particular way. In other words, we are assuming that a specific mathematical model is a good reflection of reality. The reason why one model can give rise to lots of different simulations is that the model incorporates randomness, so each time we run it you get a different outcome. But what if – as is often the case – we don't know how an infection actually spreads? Cholera is a good example: outbreaks in India and Bangladesh have puzzled researchers for years.
Most cholera infections don't result in symptoms, which means it is very difficult to know where new infections come from, or how many there really are. As a result there are many unanswered questions about why cholera outbreaks happen. Do infections come from mainly from other people or local water sources? How quickly do previously infected people lose immunity to the disease? What effect do the symptomless infections have on the spread of cholera bacteria?
There are several possible answers to such questions and therefore several different models we could use to simulate outbreaks. We really need a way to compare the various models …

Years after the Apollo program finished, Stanley Schmidt and one of his colleagues produced a report documenting their work on the trajectory predictions. As expected they had plenty of praise for the Kalman filter. "The broad application of the filter to seemingly unlikely problems suggests that we have only scratched the surface when it comes to possible applications," they wrote, "and that we will likely be amazed at the applications to which this filter will be put in the years to come."

It turned out to be a shrewd prediction. Disease researchers now employ filters to work out what causes outbreaks … The techniques may have begun as a way to guide three men to the Moon, but they have since evolved into a valuable set of tools for tackling problems back here on Earth."

The FULL article is an excellent read!

BEST!
SlideRule
Find all posts by this user
Quote this message in a reply
04-19-2020, 08:53 PM
Post: #2
RE: Apollo 11 + Kalman filter = Particle filter for epidemic modeling ?
Thanks for this!

Weather forecasters do something similar in looking at the various global, regional, and mesoscale numerical prediction and ensemble model runs. They are subject to observational errors, missing data, far from complete coupling of atmospheric processes to oceanic processes as well as orography, albedo, and vegetative state of land surfaces. Details are dependent on grid scale size and vertical layers being sampled/modeled. The various models have differing mathematical assumptions with regard to the physics of the processes, and due to computational/knowledge/observational limitations, much is parameterized, often with one size fits all parameterizations. A forecaster is constantly doing the Kalman type of thing with what the models are spitting out, with real time observations, and with a knowledge of the strengths and weaknesses of the various models.

Most of the time, the “landing” is a soft one...amazing to see how my science has progressed in the course of a 44 year career, and how intertwined the atmospheric sciences are with other scientific disciplines. Also, the recognition over the years that we need help from the social sciences in constructing forecasts that are understood by the user, and that they produce an appropriate response by the consumer (thinking of flash flood, severe thunderstorm, tornado, hurricane watches and warnings)!
Find all posts by this user
Quote this message in a reply
04-20-2020, 06:14 AM
Post: #3
RE: Apollo 11 + Kalman filter = Particle filter for epidemic modeling ?
We were using Kalman filters for vehicle guidance back when I was doing GPS related stuff. The really clever part is the difference between the prediction and the measured outcome can be used to adapt the model on the fly. This means that the filter actually learns what its parameter values are.

We used this to refine GPS placement and orientation on the vehicle as it went about it usual work.

Pauli
Find all posts by this user
Quote this message in a reply
04-20-2020, 04:32 PM (This post was last modified: 04-20-2020 04:35 PM by SammysHP.)
Post: #4
RE: Apollo 11 + Kalman filter = Particle filter for epidemic modeling ?
Some kind of Kalman filter is still used in most localization / sensor fusion algorithms. Even a simple, generic EKF can handle many situations quite well. Once you have understood it, it's a simple and powerful tool.

PS: Working as a software developer in the vehicle automation business with a focus on location/navigation.
Visit this user's website Find all posts by this user
Quote this message in a reply
04-20-2020, 06:15 PM
Post: #5
RE: Apollo 11 + Kalman filter = Particle filter for epidemic modeling ?
(04-20-2020 06:14 AM)Paul Dale Wrote:  We were using Kalman filters for vehicle guidance back when I was doing GPS related stuff. The really clever part is the difference between the prediction and the measured outcome can be used to adapt the model on the fly. This means that the filter actually learns what its parameter values are.

We used this to refine GPS placement and orientation on the vehicle as it went about it usual work.

Pauli

We were developing a GPS receiver when the GPS constellation was still being launched into orbit. I developed Kalman filters, written in C, to lock onto the GPS signal and decode the GPS p-code and CA-code. It was a fun endeavor and one of my first efforts out of college, self taught C for this project. Thanks for posting the article. This brought back fond memories.
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)