11
$\begingroup$

I am currently trying to understand particle filters and their possible uses in finance and I'm struggling quite a bit. What are the mathematical and statistical prerequisites I should revisit (coming from a background in quantitative finance) in order to (i) make the basics of particle filters accessible, and (ii) to later understand them thoroughly? I have a solid knowledge of graduate-level time series econometrics, with the exception of state-space models, which I have not covered yet.

Any hints are much appreciated!

$\endgroup$
2
  • 4
    $\begingroup$ Bayesian statistics is (IMHO) important to the subject. You don't need to know a bunch, just make sure you understand the terms associated with it (e.g. Prior, likelihood, posterior) and how they arise from modelling assumptions $\endgroup$
    – Yair Daon
    Jun 20, 2016 at 17:26
  • 1
    $\begingroup$ I think reading Doucet's papers is a great idea, he is a really good writer. On his website he has a comprehensive list of resources including slides/lectures and videos! He also includes another comprehensive list from one of his colleagues. $\endgroup$
    – bdeonovic
    Jun 22, 2016 at 22:20

2 Answers 2

11
+50
$\begingroup$

You can get shockingly far with just a few basic concepts. Notation, an explosion of variables etc... can make things look complicated, but the core idea of particle filtering is remarkably simple.

Some basic probability that you would need to (and likely already do!) understand:

  • Computing marginal distribution: $P(X = x) = \sum_i P(X = x, Y = y_i)$
  • Def. Conditional probability: $P(X \mid Y) = \frac{P(X,Y)}{P(Y)}$
  • Bayes Rule: $P(X \mid Y) = \frac{P(Y \mid X) P(X)}{P(Y)}$
  • Bayesian terms: eg. prior, likelihood, posterior (+1 @Yair Daon, I agree!)

The basic steps of a particle filter are incredibly simple:

First:

  • Start with some beliefs about some hidden state. For example, you may start with the belief that your rocket is on the launch pad. (In a particle filter, beliefs about the hidden state will be represented with a cloud of points, each point denotes a possible value of the hidden state. Each point is also associated with a probability of the state being the true state.)

Then you iterate the following steps to update from time $t$ to time $t+1$:

  1. Prediction step: Move forward location of points based upon law of motion. (eg. move points forward based upon rocket's current speed, trajectory etc...). This will typically expand out the cloud of points as uncertainty increases.
  2. Probability update step: Use data, sensor input to update probabilities associated with points using Bayes Rule. This will typically collapse back the cloud of points as uncertainty is reduced.
  3. Add some particle filtering specific steps/tricks. Eg. :
    • Occasionally resample your points so that each point has equal probability.
    • Mix in some noise, prevent your probability step (2) from collapsing your cloud of points too much (in particle filtering, it's important that there's at least one point with positive probability vaguely at your true location!)

Example:

Initialize your filter: - Look at your location, where you are standing. Now close your eyes.

Then iterate:

  1. Take a step forward with your eyes closed.
  2. Prediction step: given past beliefs about where you were standing, predict where you are now standing given a step forward. (Note how uncertainty expands because your step forward with your eyes closed isn't super precise!)
  3. Update step: Use sensors (eg. feeling around, etc...) to update your beliefs about where you're standing.

REPEAT!

The probability machinery required to implement is basically just basic probability: Bayes rule, computing marginal distribution etc...

Highly related ideas that might help understand the big picture:

In some sense, steps (1) and (2) are common to any Bayesian filtering problem. Some highly related concepts to possibly read about:

  • Hidden Markov model. A process is Markov if the past is independent of the future given the current state. Almost any time series is modeled as some kind of Markov process. A Hidden Markov Model is one where the state isn't directly observed (eg. you never directly observe the exact location of your rocket and instead infer it's location through a Bayesian filter).
  • Kalman Filter. This is an alternative to particle filtering that's commonly used. It's basically a Bayesian filter where everything is assumed to be multivariate Gaussian.
$\endgroup$
2
$\begingroup$

You should learn about easier-to-code state space models and closed-form filtering first (i.e. kalman filters, hidden markov models). Matthew Gunn is correct that you can get surprisingly far with simple concepts, but in my humble opinion, you should make this an intermediate goal because:

1.) Relatively speaking, there are more moving parts in state space models. When you learn SSMs or hidden markov models, there is a lot of notation. This means there are more things to keep in your working memory while you play around with verifying things. Personally, when I was learning about Kalman filters and linear-Gaussian SSMs first, I was basically thinking "eh this is all just properties of multivariate normal vectors...I just have to keep track of which matrix is which." Also, if you're switching between books, they often change notation.

Afterwards I thought about it like "eh, this is all just Bayes' rule at every time point." Once you think of it this way you understand why conjugate families are nice, as in the case of the Kalman filter. When you code up a hidden markov model, with its discrete state space, you see why you don't have to calculate any likelihood, and filtering/smoothing is easy. (I think I am deviating from the convential hmm jargon here.)

2.) Cutting your teeth on coding a lot of these up will make you realize how general the definition of a state space model is. Pretty soon you'll be writing down models you want to use, and at the same time seeing why you can't. First you will eventually see that you just can't write it down in one of these two forms that you're used to. When you think about it a little more, you write down Bayes' rule, and see the problem is your inability to calculate some sort of likelihood for the data.

So you will eventually fail at being able to calculate these posterior distributions (smoothing or filtering distributions of the states). To take care of this, there are a lot of approximate filtering stuff out there. Particle filtering is just one of them. The main takeaway of particle filtering: you simulate from these distributions because you can't calculate them.

How do you simulate? Most algorithms are just some variant of importance sampling. But it does get more complicated here as well. I recommend that tutorial paper by Doucet and Johansen (http://www.cs.ubc.ca/~arnaud/doucet_johansen_tutorialPF.pdf). If you get how closed form filtering works, they introduce the general idea of importance sampling, then the general idea of monte carlo method, and then show you how to use these two things to get started with a nice financial time series example. IMHO, this is the best tutorial on particle filtering that I have come across.

In addition to adding two new ideas to the mix (importance sampling and the monte carlo method), there's more notation now. Some densities you're sampling from now; some you're evaluating, and when you evaluate them, you're evaluating at samples. The result, after you code it all up, are weighted samples, deemed particles. They change after every new observation. It would be very hard to pick all of this up at once. I think it's a process.

I apologize if I'm coming across as cryptic, or handwavy. This is just the timeline for my personal familiarity with the subject. Matthew Gunn's post probably more directly answers your question. I just figured I would toss out this response.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.