Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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?
No, you can't do that. It doesn't make sense.
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.
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.
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).
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
