Particle Filter

The linear and quasi-linear approaches proposed by Kalman can be used for problems in which the state is Gaussian or approximately Gaussian with a unimodal distribution: the state estimate at time $k$ is a direct function of the single state estimate at time $k-1$ and the covariance of that estimate.

When it is necessary to derive the non-Gaussian probability distribution of the system state $p(x_k; u_{k-1}; z_{k})$ at time $k$ as a function of the inputs and observations, Kalman-based approaches are no longer adequate.

Grid-based approaches are suitable for those problems, uncommon in practice, in which the state is finite and discretizable. Histogram-based/occupancy grid approaches apply to a broader class of problems, but scale very poorly as the dimensionality increases because of the uniform sampling of the state.

Consider again the result expressed by equation (2.4): to extract a generic statistic $h(\cdot)$, such as the mean or variance, from a probability distribution $p(x)$, one uses the expression

$$\bar{h} \stackrel{def}{=} \int_X h(x) p(x) dx$$ (3.41)

If this estimate cannot be obtained analytically, it can nevertheless be derived indirectly by analyzing $x_i$ independent samples, with $1 \leq i \leq N$, drawn randomly from the exact distribution $p$.

Given the samples $x_i$ generated in this way, the Monte Carlo estimate of $h(\cdot)$ is

$$\bar{h} \approx \frac{1}{N} \sum_{i=1}^{N} h(x_i)$$ (3.42)

Monte Carlo methods do not solve every problem, nor do they indicate how to obtain random samples efficiently. The problem becomes critical in multidimensional cases, where the regions in which the probability takes significant values are extremely small. The objective of Importance Sampling (IS) is to sample the distribution $p(x)$ in “important” regions so as to maximize computational efficiency.

The idea behind Importance Sampling is to use a simpler distribution $q(x)$ (importance density) instead of the true distribution $p(x)$, which is normally difficult to sample from or reproduce, making the substitution

$$\int_X h(x) p(x) dx = \int_X h(x) \frac{p(x)}{q(x)} q(x) dx = \int_X h(x) w(x) q(x) dx$$

and introducing the system of weights $w(x)$. By using suitable weights, equation (3.42) can therefore be rewritten as

$$\bar{h} \approx \frac{1}{N} \sum_{i=1}^{N} w_i h(x_i)$$ (3.43)

where $w_i \propto W_i = p(x_i)/q(x_i)$ is a correction weight, or importance factor (importance weight), for converting the proposal distribution $q$ into the true distribution $p$. The weights $W_i$ must be normalized

$$w_i = \frac{W_i}{\sum W_i}$$ (3.44)

before they can be used.

The more similar the distribution $q(x)$ is to $p(x)$, the more accurate the estimate will be. On the other hand, the distribution $q(x)$ must be very easy to sample from, for example by choosing a uniform or Gaussian distribution.

Given knowledge of Bayesian filters and Monte Carlo techniques, particle-filter theory can be developed. The state at time $k$ is represented by a set of samples (particles), and each sample is a hypothesis about the state to be evaluated. One can consider a set of particles obtained a priori to the observation by applying equation (3.43) to the state-evolution function.

If Bayesian theory is applied directly to samples from the estimated distribution, the weights $w_i$ associated with the samples can be modified using the system and observation models simultaneously (Sequential Importance Sampling):

$$w_{k,i} \propto w_{k-1,i} \frac{ p (z_k \vert x_{k,i} ) p (x_{k,i} \vert x_{k-1,i} ) } { q (x_{k,i} \vert x_{k-1,i}, z_k ) }$$ (3.45)

In this way, the initial samples remain unchanged, while only their associated weights $w_i$ change.

When possible, it is convenient to use the prior distribution as the importance density:

$$q (x_{k,i} \vert x_{k-1,i}, z_k ) = p (x_{k,i} \vert x_{k-1,i} )$$ (3.46)

so that, when substituted into (3.45), it gives

$$w_{k,i} \propto w_{k-1,i} p (z_k \vert x_{k,i} )$$ (3.47)

The problem with the SIS approach is that after a few iterations only a few particles have non-negligible weights (weight degeneracy).