Auxiliary particle filter

The auxiliary particle filter is a particle filtering algorithm introduced by Pitt and Shephard in 1999 to improve some deficiencies of the sequential importance resampling (SIR) algorithm when dealing with tailed observation densities.

Motivation

Particle filters approximate continuous random variable by $M$ particles with discrete probability mass $\pi _{t}$, say $1/M$ for uniform distribution. The random sampled particles can be used to approximate the probability density function of the continuous random variable if the value $M\rightarrow \infty$.

The empirical prediction density is produced as the weighted summation of these particles:

${\widehat {f}}(\alpha _{t+1}|Y_{t})=\sum _{j=1}^{M}f(\alpha _{t+1}|\alpha _{t}^{j})\pi _{t}^{j}$, and we can view it as the "prior" density. Note that the particles are assumed to have the same weight $\pi _{t}^{j}={\frac {1}{M}}$.

Combining the prior density ${\widehat {f}}(\alpha _{t+1}|Y_{t})$ and the likelihood $f(y_{t+1}|\alpha _{t+1})$, the empirical filtering density can be produced as:

${\widehat {f}}(\alpha _{t+1}|Y_{t+1})={\frac {f(y_{t+1}|\alpha _{t+1}){\widehat {f}}(\alpha _{t+1}|Y_{t})}{f(y_{t+1}|Y_{t})}}\propto f(y_{t+1}|\alpha _{t+1})\sum _{j=1}^{M}f(\alpha _{t+1}|\alpha _{t}^{j})\pi _{t}^{j}$, where $f(y_{t+1}|Y_{t})=\int f(y_{t+1}|\alpha _{t+1})dF(\alpha _{t+1}|Y_{t})$.

On the other hand, the true filtering density which we want to estimate is

$f(\alpha _{t+1}|Y_{t+1})={\frac {f(y_{t+1}|\alpha _{t+1})f(\alpha _{t+1}|Y_{t})}{f(y_{t+1}|Y_{t})}}$.

The prior density ${\widehat {f}}(\alpha _{t+1}|Y_{t})$ can be used to approximate the true filtering density $f(\alpha _{t+1}|Y_{t+1})$:

• The particle filters draw $R$ samples from the prior density ${\widehat {f}}(\alpha _{t+1}|Y_{t})$. Each sample are drawn with equal probability.
• Assign each sample with the weights $\pi _{j}={\frac {\omega _{j}}{\sum _{i=1}^{R}\omega _{i}}},\omega _{j}=f(y|\alpha ^{j})$. The weights represent the likelihood function $f(y_{t+1}|\alpha _{t+1})$.
• If the number $R\rightarrow \infty$, than the samples converge to the desired true filtering density.
• The $R$ particles are resampled to $M$ particles with the weight $\pi _{j}$.

The weakness of the particle filters includes:

• If the weight {$\omega _{j}$} has a large variance, the sample amount $R$ must be large enough for the samples to approximate the empirical filtering density. In other words, while the weight is widely distributed, the SIR method will be imprecise and the adaption is difficult.

Therefore, the auxiliary particle filter is proposed to solve this problem.

Auxiliary particle filter

Auxiliary variable

Comparing with the empirical filtering density which has ${\widehat {f}}(\alpha _{t+1}|Y_{t+1})\propto f(y_{t+1}|\alpha _{t+1})\sum _{j=1}^{M}f(\alpha _{t+1}|\alpha _{t}^{j})\pi _{t}^{j}$,

we now define ${\widehat {f}}(\alpha _{t+1},k|Y_{t+1})\propto f(y_{t+1}|\alpha _{t+1})f(\alpha _{t+1}|\alpha _{t}^{k})\pi ^{k}$, where $k=1,...,M$.

Being aware that ${\widehat {f}}(\alpha _{t+1}|Y_{t+1})$ is formed by the summation of $M$ particles, the auxiliary variable $k$ represents one specific particle. With the aid of $k$, we can form a set of samples which has the distribution $g(\alpha _{t+1},k|Y_{t+1})$. Then, we draw from these sample set $g(\alpha _{t+1},k|Y_{t+1})$ instead of directly from ${\widehat {f}}(\alpha _{t+1}|Y_{t+1})$. In other words, the samples are drawn from ${\widehat {f}}(\alpha _{t+1}|Y_{t+1})$ with different probability. The samples are ultimately utilized to approximate $f(\alpha _{t+1}|Y_{t+1})$.

Take the SIR method for example:

• The particle filters draw $R$ samples from $g(\alpha _{t+1},k|Y_{t+1})$.
• Assign each samples with the weight $\pi _{j}={\frac {\omega _{j}}{\sum _{i=1}^{R}\omega _{i}}},\omega _{j}={\frac {f(y_{t+1}|\alpha _{t+1}^{j})f(\alpha _{t+1}^{j}|\alpha _{t}^{k})}{g(\alpha _{t+1}^{j},k^{j}|Y_{t+1})}}$.
• By controlling $y_{t+1}$ and $\alpha _{t}^{k}$, the weights are adjusted to be even.
• Similarly, the $R$ particles are resampled to $M$ particles with the weight $\pi _{j}$.

The original particle filters draw samples from the prior density, while the auxiliary filters draw from the joint distribution of the prior density and the likelihood. In other words, the auxiliary particle filters avoid the circumstance which the particles are generated in the regions with low likelihood. As a result, the samples can approximate $f(\alpha _{t+1}|Y_{t+1})$ more precisely.

Selection of the auxiliary variable

The selection of the auxiliary variable affects $g(\alpha _{t+1},k|Y_{t+1})$ and controls the distribution of the samples. A possible selection of $g(\alpha _{t+1},k|Y_{t+1})$ can be:
$g(\alpha _{t+1},k|Y_{t+1})\propto f(y_{t+1}|\mu _{t+1}^{k})f(\alpha _{t+1}|\alpha _{t}^{k})\pi ^{k}$, where $k=1,...,M$ and $\mu _{t+1}^{k}$ is the mean.

We sample from $g(\alpha _{t+1},k|Y_{t+1})$ to approximate $f(\alpha _{t+1}|Y_{t+1})$ by the following procedure:

• First, we assign probabilities to the indexes of $f(\alpha _{t+1}|\alpha _{t}^{k})$. We named these probabilities as the first-stage weights $\lambda _{k}$, which are proportional to $g(k|Y_{t+1})\propto \pi ^{k}f(y_{t+1}|\mu _{t+1}^{k})$.
• Then, we draw $R$ samples from $f(\alpha _{t+1}|\alpha _{t}^{k})$ with the weighted indexes. By doing so, we are actually drawing the samples from $g(\alpha _{t+1},k|Y_{t+1})$.
• Moreover, we reassign the second-stage weights $\pi _{j}={\frac {\omega _{j}}{\sum _{i=1}^{R}\omega _{i}}}$ as the probabilities of the $R$ samples, where $\omega _{j}={\frac {f(y_{t+1}|\alpha _{t+1}^{j})}{f(y_{t+1}|\mu _{t+1}^{j})}}$. The weights are aim to compensate the effect of $\mu _{t+1}^{k}$.

• Finally, the $R$ particles are resampled to $M$ particles with the weights $\pi _{j}$.

Following the procedure, we draw the $R$ samples from $g(\alpha _{t+1},k|Y_{t+1})$. Since $g(\alpha _{t+1},k|Y_{t+1})$ is closely related to the mean $\mu _{t+1}^{k}$, it has high conditional likelihood. As a result, the sampling procedure is more efficient and the value $R$ can be reduced.

Other point of view

Assume that the filtered posterior is described by the following M weighted samples:

$p(x_{t}|z_{1:t})\approx \sum _{i=1}^{M}\omega _{t}^{(i)}\delta \left(x_{t}-x_{t}^{(i)}\right).$

Then, each step in the algorithm consists of first drawing a sample of the particle index $k$ which will be propagated from $t-1$ into the new step $t$. These indexes are auxiliary variables only used as an intermediary step, hence the name of the algorithm. The indexes are drawn according to the likelihood of some reference point $\mu _{t}^{(i)}$ which in some way is related to the transition model $x_{t}|x_{t-1}$ (for example, the mean, a sample, etc.):

$k^{(i)}\sim P(i=k|z_{t})\propto \omega _{t}^{(i)}p(z_{t}|\mu _{t}^{(i)})$

This is repeated for $i=1,2,\dots ,M$, and using these indexes we can now draw the conditional samples:

$x_{t}^{(i)}\sim p(x|x_{t-1}^{k^{(i)}}).$

Finally, the weights are updated to account for the mismatch between the likelihood at the actual sample and the predicted point $\mu _{t}^{k^{(i)}}$:

$\omega _{t}^{(i)}\propto {\frac {p(z_{t}|x_{t}^{(i)})}{p(z_{t}|\mu _{t}^{k^{(i)}})}}.$

Sources

• Pitt, M.K.; Shephard, N. (1999). "Filtering Via Simulation: Auxiliary Particle Filters". Journal of the American Statistical Association. 94 (446). American Statistical Association: 590–591. doi:10.2307/2670179. JSTOR 2670179. Archived from the original on 2007-10-16. Retrieved 2008-05-06.