Van Der Merwe, R., Doucet, A., De Freitas, N., & Wan, E. (2000). The Unscented Particle Filter. Advances In Neural Information Processing Systems, 13. Retrieved from http://papers.nips.cc/paper/1818-the-unscented-particle-filter.pdf

Summary

In this paper, van der Merwe et al. introduce a version of a particle filter called an unscented particle filter. The basic idea is to use as a proposal distribution an Unscented Kalman Filter (UKF) rather than the prior distribution (which is frequently used in PFs).

Methods

n/a

Algorithm

Standard particle filter

A particle filter is form of sequential Monte Carlo and is a way of estimating the underlying state in a HMM. It relies on a transition model, $p(x_{t+1}\vert x_t)$, and an observation model, $p(y_t\vert x_t)$. The goal is to recover the distribution $p(\mathbf{x}_{0:t}\vert \mathbf{y}_{1:t})$. To do this, the particle filter requires a proposal distribution $q(x_t\vert \mathbf{x}_{0:t-1},\mathbf{y}_{1:t})$. The algorithm at each step then looks like this:

First, propagate each particle:

$\tilde{x}_t^{(i)}\sim q(x_t\vert \mathbf{x}_{0:t-1},\mathbf{y}_{1:t})$

Second, compute importance weights and then normalize them:

$\begin{align*} \tilde{w}_i^{(i)}&=w_{t-1}^{(i)}\frac{p(y_t\vert \tilde{x}_t^{(i)})p(\tilde{x}_t^{(i)}\vert x_{t-1}^{(i)})}{q(\tilde{x}_t\vert \mathbf{x}_{0:t-1},\mathbf{y}_{1:t})}\\ w_t^{(i)}&=\frac{\tilde{w}_t^{(i)}}{\sum_{j=1}^N \tilde{w}_t^{(j)}} \end{align*}$

Third, resample particles according to the weights $w_t^{(i)}$ to obtain $x_t^{(i)}$.

Fourth, perform particle rejuvination. One way of doing this is by taking a MCMC step—i.e., sample a new $x_t^{\prime(i)}$ from the transition density, and then either accept or reject the sample based on the ratio $p(y_t\vert x_t^{\prime(i)})/p(y_t\vert \tilde{x}_t^{(i)})$. If the sample is accepted, then set $x_t^{(i)}=x_t^{\prime(i)}$; otherwise, set $x_t^{(i)}=\tilde{x}_t^{(i)}$.

Frequently, the proposal distribution is chosen to be the prior, i.e. $q(x_t\vert \mathbf{x}_{0:t-1},\mathbf{y}_{1:t})=p(x_t^{(i)}\vert x_{t-1}^{(i)})$, which causes the importance weights to reduce to just the likelihood.

Unscented particle filter

One problem with choosing the prior for the proposal distribution is that it may be quite different from the likelihood, thus causing few (if any) particles to survive. What we’d like to be able to do is instead move the particles towards the regions of high likelihood. Van der Merwe et al. suggest doing this by using an unscented Kalman Filter.

I tried to implement the UPF in this demo, but I couldn’t seem to get it to work quite right—the regular particle filter vastly outperforms the UPF. Also, my regular PF seems to do better than theirs does in the paper. So, I’m not entirely sure what’s up with that, but I need to move onto other papers now!