5
$\begingroup$

I'm learning about particle filters, and most expositions start with importance sampling, so now I'm learning about importance sampling. I'm not sure if I'm correctly interpreting a paragraph in this article:

Arulampalam, Maskell, Gordon, and Clapp (2002), "A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking" (PDF), page 178, left column, near the middle:

We therefore have a discrete weighted approximation to the true posterior, $p(\mathbf x_{0:k}|\mathbf z_{1:k})$. The weights are chosen using the principle of importance sampling [3], [12]. This principle relies on the following. Suppose $p(x)\propto\pi(x)$ is a probability density from which it is difficult to draw samples but for which $\pi(x)$ can be evaluated [as well as $p(x)$ up to proportionality]. In addition, let $x^i\sim q(x),i=1,\ldots,N_s$ be samples that are easily generated from a proposal $q(\cdot)$ called an importance density. Then, a weighted approximation to the density $p(\cdot)$ is given by $$p(x)\approx\sum_{i=1}^{N_s}w^i\delta(x-x^i)$$ where $$w^i\propto\frac{\pi(x^i)}{q(x^i)}$$ is the normalized weight of the $i$th particle.

I take this to mean the following:

  • $p(x)$ is a probability density, meaning $\int p=1$, which we want to approximate. Unfortunately, it happens to be difficult to sample from $p(x)$. Additionally, it is hard to evaluate $p(x)$ for a given $x$.
  • $\pi(x)$ is a density which is proportional to $p(x)$, meaning there is some constant $M>0$ such that $\pi(x)=Mp(x)$ for all $x$. We don't call $\pi(x)$ a "probability" density because $M=\int \pi$ is not necessarily equal to $1$, and in fact computing $M$ may be difficult. But it so happens that computing $\pi(x)$ for a given $x$ is easier than computing $p(x)$. Still, it's difficult to sample from $\pi(x)$, which would be the same as sampling from $p(x)$.
  • $q(x)$ is some other density, which must be nonzero wherever $\pi(x)$ is nonzero, but otherwise doesn't need to resemble $\pi(x)$ too closely. The density $q(x)$ is not necessarily a probability density, so $\int q$ is not necessarily $1$ (?), although it doesn't seem to matter for what follows. It must be easy to sample from $q(x)$, and it must be easy to evaluate $q(x)$ for a given $x$.

I'm still hung up on the "as well as" language in square brackets in the source. It may just a wording issue, but I don't know what they're trying to convey there, and I hope I'm not missing something. The other problem is that one of their references is Doucet, Godsill, and Andrieu (2000), "On sequential Monte Carlo sampling methods for Bayesian filtering" (PDF), which uses the letter $\pi$ to represent the importance function instead, and which doesn't introduce any auxiliary density proportional to the target distribution $p$.

  1. Am I right so far?
  2. Is there some subtle reason why these two articles use $\pi$ to represent different things? Or is it just an unlucky coincidence?
$\endgroup$
5
$\begingroup$

The key point in importance sampling is that you transform a desired expectation multiplying by one.

Suppose that you have a random variable $X$ with density $f$. The law of the unconscious statistician tells you that for some function $g$, the expectation of $g(X)$ is $$ \mathrm{E}[g(X)] = \int g(t)\,f(t)\,dt \, . $$ Now, suppose that you have another probability density $h>0$ which is easy to sample from. Multiplying by one, we have $$ \mathrm{E}[g(X)] = \int g(t)\,\frac{f(t)}{h(t)}\,h(t)\,dt = \mathrm{E}\!\!\left[g(Y)\frac{f(Y)}{h(Y)}\right] \, , $$ in which $Y$ has density $h$. The strong law of large numbers tells us that if $Y_1,Y_2,\dots$ is an IID sample from $h$, then $$ \frac{1}{N}\sum_{i=1}^N g(Y_i)\frac{f(Y_i)}{h(Y_i)} \longrightarrow \mathrm{E}\!\!\left[g(Y)\frac{f(Y)}{h(Y)}\right] $$ with probability one, when $N\to\infty$.

You can interpret the sum above as the integral $\int g\,d\xi$, in which $\xi$ is a discrete measure that puts mass $f(Y_i)/(N\,h(Y_i))$ on each $Y_i$. Physicists like to talk about the "density" of $\xi$ using Dirac deltas. That's what your book does.

$\endgroup$
  • $\begingroup$ Thanks, that makes sense, and it's quite simple! So it seems like I'm not missing anything from the quoted description...? $\endgroup$ – Chris Culter Jan 4 '14 at 3:54
  • $\begingroup$ Looks good, Chris. Also, do some simple simulations to see it working. For example, find the mean of a Gamma rv sampling from a standard lognormal rv. It takes only a bunch of lines of R code. $\endgroup$ – Zen Jan 4 '14 at 20:09
  • $\begingroup$ Okay, good idea! $\endgroup$ – Chris Culter Jan 5 '14 at 1:05

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.