# Particle Filter Derivation based on Forward Algorithm

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!

• Hi, I wonder when you try to estimate $\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)})$. What is the target function that used to calculate the weight? Is $P(x_{0:t}, z_{1:t})$ or $P(x_{0:t} | z_{1:t})$ ? Oct 5, 2022 at 8:46
• @sundaycat I may be wrong but I believe at iteration zero it could be any educated guess. Some people may use uniform distributions or gaussian. Oct 5, 2022 at 16:18

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.