Particle Filter Derivation based on Forward Algorithm

Question

I have been studying the particle filter, sequential monte carlo methods, and sequential importance sampling.

I am interested in apply the particle filter equations to the standard forward algorithm:

$$ p(x_t | z^t) \propto p(z_t | x_t) \int p(x_t |x_{t-1}) p(x_{t-1} |z^{t-1}) dx_{t-1} $$

Where $z^t \triangleq [z_1, z_2, ... , z_t] $

To start, what I would like to find is an empirical sampled density of $p(x_t|z^t)$

I denote the form of the sampled density (for N samples) as

$$ \hat{p}(x_t|z^t) \propto \frac{1}{N} \sum_{i=1}^N w(x^{t(i)},z^t) \delta(x_t- x_t^{(i)}) $$

Where the samples of $x_t$ are denoted $x_t^{(i)}$.

To get rid of the proportion sign, we can calculate $p(z^t)$,

$$ \hat{p}(z^t) = \int p(x_t,z^t) dx_t = \int \frac{1}{N} \sum_{i=1}^N w(x^{t(i)},z^t) \delta(x_t- x_t^{(i)}) dx_t \\ =\frac{1}{N}\sum_{i=1}^N w(x^{t(i)},z^t) $$

Thus, dividing by $\hat{p}(z^t)$ normalizes the importance weights in our posterior distribution. I denote the normalized weights as $\tilde{w}(x^{t(i)},z^t)$.

$$ \hat{p}(x_t|z^t) = \sum_{i=1}^N \tilde{w}(x^{t(i)},z^t) \delta(x_t- x_t^{(i)}) $$

I now substitute the sampled empitical density into the forward algorithm (at time $t-1$),

$$ \hat{p}(x_t | z^t) \propto p(z_t | x_t) \int p(x_t |x_{t-1}) \sum_{i=1}^N \tilde{w}(x^{t-1(i)},z^{t-1}) \delta(x_{t-1}- x_{t-1}^{(i)}) dx_{t-1} $$

Rearranging terms, we have

$$ \hat{p}(x_t | z^t) \propto \sum_{i=1}^N \tilde{w}(x^{t-1(i)},z^{t-1}) p(z_t | x_t) \int p(x_t |x_{t-1}) \delta(x_{t-1}- x_{t-1}^{(i)}) dx_{t-1} $$

Applying the integral we have

$$ \hat{p}(x_t | z^t) \propto \sum_{i=1}^N \tilde{w}(x^{t-1(i)},z^{t-1}) p(z_t | x_t) p(x_t |x_{t-1}^{(i)}) $$

Now I notice that the above formula is in terms of our observation density $p(z_t|x_t)$, and our transition density $p(x_t|x_{t-1})$, which are both distributions that we assume to know. Further, I assume that we have observed $z_t$ and know its value.

Issue Starts Here: In order to find $\hat{p}(x_t|z^t)$, we need to sample $x_t^{(i)} \sim p(x_t|x_{t-1}^{(i)})$. Denote the sampled density of $p(x_t|x_{t-1}^{(i)})$ as

$$ \hat{p}(x_t|x_{t-1}^{(i)}) = \sum_{i=1}^N \alpha_i \delta(x_t- x_t^{(i)}) $$

Where $\alpha_i =p(x_t^{(i)}|x_{t-1}^{(i)})$

A single sample from this density is $\hat{p}(x_t^{(i)}|x_{t-1}^{(i)}) = \alpha_i \delta(x_t - x_t^{(i)})$

Then substitute our sample back into the equation.

$$ \hat{p}(x_t | z^t) \propto \sum_{i=1}^N \tilde{w}(x^{t-1(i)},z^{t-1}) p(z_t | x_t) \alpha_i \delta(x_t - x_t^{(i)}) $$

Therefore, we have

$$ \hat{p}(x_t | z^t) \propto \sum_{i=1}^N \alpha_i \tilde{w}(x^{t-1(i)},z^{t-1}) p(z_t | x_t^{(i)}) \delta(x_t - x_t^{(i)}) $$

Comparing this to the original equation, we have a recursive relationship between the importance weights. $$ \frac{1}{N} w(x^{t(i)},z^t) = \alpha_i \tilde{w}(x^{t-1(i)},z^{t-1}) p(z_t | x_t^{(i)}) $$

This is not completely correct, I have an extra term of $\alpha_i = p(x_t^{(i)}|x_{t-1}^{(i)})$. This should have been cancelled out.

I believe the correct weight update should be $$ w(x^{t(i)},z^t) = \tilde{w}(x^{t-1(i)},z^{t-1}) p(z_t | x_t^{(i)}) $$

I believe the issue begins where I bolded above. If anyone can provide some insight, it would be very helpful. Thanks!

Answer 1

I think I have answered my own question. When you have a known distribution that you are sampling from like $p(x_t|x_{t-1})$, the monte carlo approximation for the distribution is

$$ p(x_t|x_{t-1}) = \frac{1}{N}\sum_{i=1}^N \delta(x_t- x_t^{(i)}) $$

For example, if $p(x_t | x_{t-1})$ follows a gaussian distribution, the monte carlo approximation of this distribution $\hat{p}(x_t|x_{t-1})$ will be a cluster of impulses each with amplitude $1/N$ that mostly lie in the region near the mean of the original distribution.

This makes sense, because if you want to calculate the probability, say in a region over a gaussian $P(a \le x_t \le b)$, then the monte carlo approximation is

$$ E[I(a \le x \le b)] = \int_{a}^{b}\hat{p}(x) dx \\ = \frac{1}{N}\sum_{i=1}^N \int_{a}^{b}\delta(x- x^{(i)}) dx \\ $$

The integral evaluates to zero for particles $x^{(i)}$ not in the region $[a,b]$.

If we define the set of particles over the region $[a,b]$ as $X = \{x^{(i)} | \ a \le x^{(i)} \le b \}$ and index the set with $j$, the probability is

$$ = \sum_j\frac{1}{N} $$

Thus, in regions where the particles are more densily packed, the probability will be higher, which is what we expect from the target distribution.