0
$\begingroup$

In particle filters when one is doing sequential importance sampling, the quantity of interest that is being approximated is usually a weighted sum:

$$\hat x_t = \sum_{i=1}^M \Bigl [f(v^{(i)}_{t}) \times w(v^{(i)}_t) \Bigr] \tag 1$$

where $t$ denotes a time or step index and $i$ denotes a particle/sample index.

and when you're doing resampling it's:

$$\hat x_t = {1\over M} \sum_{i=1}^M f(v^{(i)}_{t}) \tag 2$$

where $w(v)$ is the importance weight and $f(v)$ is the function estimate, suppose you don't resample on every step but only when the effective sample size goes below some threshold, does that mean that you perform $(1)$ on the time steps you didn't resample and $(2)$ on the time steps you did resample on?

Improve this question
$\endgroup$
3
  • $\begingroup$ I’m having a hard time following a few things. Usually you approximate expectations with a weighted sum. Also, your second expression might be incorrect; you might need to get rid of the $w$ part because after resampling each particle has the same uniform weight. Also, I don’t understand how you can “perform” either one or two. $\endgroup$
    – Taylor
    Commented Aug 29, 2018 at 0:20
  • $\begingroup$ @Taylor right sorry, since the particles are resampled according to the weights, by some strategy (i.e. stratified resampling) , then you just compute the mean. About the other point of how either 1 or 2 can be performed, at each step you compute importance weights according to the ratio of the target/proposal distribution, and if the effective sample size is below a threshold, then you resample, so isn't it the case that on some steps the expectation is approximated by a weighted some and on others its the mean of the resampled particles? $\endgroup$
    – atomsmasher
    Commented Aug 29, 2018 at 20:50
  • 1
    $\begingroup$ yes, but I prefer to think of it like this: I am always calculating (1), and the weights may or may not be uniform. They're uniformed if I've just resampled, and they aren't if I haven't in a while. $\endgroup$
    – Taylor
    Commented Aug 29, 2018 at 20:54

1 Answer 1

Reset to default
1
$\begingroup$

Explanation:

(1) is a Monte Carlo estimate of an expectation of the system we are approximating, with the help of incomplete observations.

The weight of a particle represents how likely our observations of the system are, assuming that the state of the system is described by that particle. The estimate is then a weighted average of the particles (samples), where the more likely ones have higher weight.

The effective sample size is used to keep track of how many particles contribute to the Monte Carlo estimate.

When it falls below a certain threshold (e.g. 1/2 of the original sample size M), we resample to get fresh particles that all contribute evenly to the Monte Carlo estimate.

Then the weights are uniform: all are 1/M.

Answer:

You always use the weighted average in (1) to approximate the expectation of a function f at time t. At the time step right after resampling, (1) reduces to (2) because the weights are uniform.

Improve this answer
$\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.