6
$\begingroup$

In theory, the importance weight of a particle has to be a probability, i.e., $w_{s_t} = p(z_t|s_t)$.

My question is: Since we eventually normalize the weights with their sum and get a probability distribution, do importance weights themselves have to be probabilities in practice? Can't we just use a function of our choice which yields non-negative numbers?

$\endgroup$
5
  • $\begingroup$ You have to use $p(z_t|s_t)$ to calculate the weights in order to obtain a weighted sample from the filtering distribution $p(z_t|s_{1:t})$. This is the "update" step of the SIR particle filter. If you substitute $p(z_t|s_t)$ with another function you won't get a sample from the filtering distribution. Why are you considering using something else? $\endgroup$ – Matteo Fasiolo Feb 4 '13 at 9:15
  • $\begingroup$ I want to use a fitness function to check how good a particle is. This function produces non-negative values, but it is not necessarily a probability function, i.e. it can take values like, {0, 25, 2, 17.3, ...}. However, if I normalize this set of numbers with their sum, I get a post. probability distribution. Right? Can I weigh the particles with these normalized versions or am I missing something? $\endgroup$ – Zoran Feb 4 '13 at 14:26
  • 2
    $\begingroup$ I think that to propagate the particles forward in the correct manner you still have to weight them according to $p(z_t| s_t)$. Then if you want to use your fit function in parallel to check the fit of the particles that's not a problem. The posterior is likelihood (which is $p(z_t| s_t)$ in your case) times prior, so if you substitute the likelihood with another function you will NOT get a sample from the posterior. Normalizing change this fact. $\endgroup$ – Matteo Fasiolo Feb 4 '13 at 18:07
  • $\begingroup$ @MatteoFasiolo but how to decide the likelihood function to evaluate the particles/hypothesis? i thought having a function that get some kind of score based on an observation could be a valid way to assign a weight to a particle $\endgroup$ – nkint Dec 26 '13 at 22:04
  • $\begingroup$ @nkint The likelihood is determined by your model, if you have one. For example you might guess or know that the observations are normally distributed around the hidden state. In other words: $z_t \sim N(s_t, \sigma)$. That entails that your likelihood function is a Gaussian density. To chose the likelihood you should try to approximate the process that generated the data. Generally I would use a Gaussian unless you have a good reason not to (ex. discrete data, outliers, etcetera). $\endgroup$ – Matteo Fasiolo Dec 27 '13 at 14:41
1
$\begingroup$

Short Answer:

No, you can't do that. It doesn't make sense.

Notation:

Let $s_{1:t}$ be the states from time $1$ to time $t$. Let $z_{1:t}$ denote the observations. Let $q(s_{1:t}|z_{1:t})$ be the proposal distribution that you sample from to approximate the entire sequence of unobserved states. This proposal distribution is assumed to be factorizable, so you can sample at each time point as new $z_t$ data arrives. So say you have samples up to time $t-1$, then you sample the new states at time $t$ with $q_t(s_t|s_{t-1},z_t)$--this gives you samples form $$ q_t(s_t|z_{1:t},s_{1:t-1}) q(s_{1:t-1}|z_{1:t-1}). $$ And so on and so forth. Every time you extend the sample paths, you adjust the weights with some weight adjustment.

Background:

Here is the decomposition that suggests Sequential Import Sampling (SIS). This is Sequential Importance Sampling with Resampling (SISR/SIR) without the resampling. It is the simplest possible particle filter that will answer your question. \begin{align*} p(s_{1:t}|z_{1:t}) &= C_t^{-1} \frac{p(s_{1:t},z_{1:t})}{q(s_{1:t}|z_{1:t})}q(s_{1:t}|z_{1:t}) \\ &= C_t^{-1} \frac{g(z_t|s_t)f(s_t|s_{t-1})}{q_t(s_t|z_{1:t},s_{1:t-1}) } \frac{p(s_{1:t-1},z_{1:t-1})}{ q(s_{1:t-1}|z_{1:t-1})} q_t(s_t|z_{1:t},s_{1:t-1}) q(s_{1:t-1}|z_{1:t-1}). \end{align*}

Here's the progression. At the previous time, time $t-1$, you have samples distributed according to $q(s_{1:t-1}|z_{1:t-1})$, and their weights are $\frac{p(s_{1:t-1},z_{1:t-1})}{ q(s_{1:t-1}|z_{1:t-1})} $. Then, at time $t$, you sample and extend the particle paths by sampling from $q_t(s_t|z_{1:t},s_{1:t-1})$, and multiplying your old weights by $\frac{g(z_t|s_t)f(s_t|s_{t-1})}{q_t(s_t|z_{1:t},s_{1:t-1}) }$ to give you new, adjusted, and un-normalized weights at time $t$. $C_t^{-1}$ is a normalizing constant. $g(z_t|s_t)$ is the observation density, and $f(s_t|s_{t-1})$ is the state transition density or "motion model." In the other answer he assumes that $q_t(s_t|s_{t-1},z_t)$ is the same as $f(s_t|s_{t-1})$, so they cancel in the weight adjustment term.

Answer:

So yes, your un-normalized weights have to involve a probability distribution. It's a ratio, with the denominator being the guy you just sampled from. You can't sample from a thing that isn't a probability distribution. And the numerator has to be $g$ and $f$, otherwise you aren't using a state space model, and particle filtering won't make sense (there are probably ways to use Sequential Monte Carlo/particle filters on models that aren't state space models, but I have never done it).

$\endgroup$
0
$\begingroup$

There is a reason why the weights turn out to be probabilities. In most simple implementations of SIR particle filters, the proposal distribution is the motion model. Under this setting the weight update equation simplifies to measurement likelihood.

Check these resources:
http://www.cs.berkeley.edu/~pabbeel/cs287-fa12/slides/ParticleFilters.pdf
http://www.cns.nyu.edu/~eorhan/notes/particle-filtering.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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