0
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ 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})$ ? $\endgroup$
    – sundaycat
    Commented Oct 5, 2022 at 8:46
  • $\begingroup$ @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. $\endgroup$
    – DarkLink
    Commented Oct 5, 2022 at 16:18

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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