Particle filter

Particle filters or Sequential Monte Carlo (SMC) methods are a set of Monte Carlo algorithms used to solve filtering problems arising in signal processing and Bayesian statistical inference. The filtering problem consists of estimating the internal states in dynamical systems when partial observations are made, and random perturbations are present in the sensors as well as in the dynamical system. The objective is to compute the posterior distributions of the states of some Markov process, given some noisy and partial observations. The term 'particle filters' was first coined in 1996 by Del Moral in reference to mean field interacting particle methods used in fluid mechanics since the beginning of the 1960s. The terminology 'sequential Monte Carlo' was proposed by Liu and Chen in 1998.    (Eq. 1) ∫ f ( x k ) p ( x k | y 0 , ⋯ , y k ) d x k ≈ N ↑ ∞ 1 N ∑ i = 1 N f ( ξ ^ k i ) = ∫ f ( x k ) p ^ ( d x k | y 0 , ⋯ , y k ) {displaystyle int f(x_{k})p(x_{k}|y_{0},cdots ,y_{k}),dx_{k}approx _{Nuparrow infty }{frac {1}{N}}sum _{i=1}^{N}fleft({widehat {xi }}_{k}^{i} ight)=int f(x_{k}){widehat {p}}(dx_{k}|y_{0},cdots ,y_{k})}     (Eq. 2) ∫ F ( x 0 , ⋯ , x k ) p ( x 0 , ⋯ , x k | y 0 , ⋯ , y k ) d x 0 ⋯ d x k ≈ N ↑ ∞ 1 N ∑ i = 1 N F ( ξ ^ 0 , k i , ξ ^ 1 , k i , ⋯ , ξ ^ k , k i ) = ∫ F ( x 0 , ⋯ , x k ) p ^ ( d ( x 0 , ⋯ , x k ) | y 0 , ⋯ , y k ) {displaystyle {egin{aligned}int F(x_{0},cdots ,x_{k})p(x_{0},cdots ,x_{k}|y_{0},cdots ,y_{k}),dx_{0}cdots dx_{k}&approx _{Nuparrow infty }{frac {1}{N}}sum _{i=1}^{N}Fleft({widehat {xi }}_{0,k}^{i},{widehat {xi }}_{1,k}^{i},cdots ,{widehat {xi }}_{k,k}^{i} ight)\&=int F(x_{0},cdots ,x_{k}){widehat {p}}(d(x_{0},cdots ,x_{k})|y_{0},cdots ,y_{k})end{aligned}}}     (Eq. 3)    (Eq. 4) Particle filters or Sequential Monte Carlo (SMC) methods are a set of Monte Carlo algorithms used to solve filtering problems arising in signal processing and Bayesian statistical inference. The filtering problem consists of estimating the internal states in dynamical systems when partial observations are made, and random perturbations are present in the sensors as well as in the dynamical system. The objective is to compute the posterior distributions of the states of some Markov process, given some noisy and partial observations. The term 'particle filters' was first coined in 1996 by Del Moral in reference to mean field interacting particle methods used in fluid mechanics since the beginning of the 1960s. The terminology 'sequential Monte Carlo' was proposed by Liu and Chen in 1998. Particle filtering uses a set of particles (also called samples) to represent the posterior distribution of some stochastic process given noisy and/or partial observations. The state-space model can be nonlinear and the initial state and noise distributions can take any form required. Particle filter techniques provide a well-established methodology for generating samples from the required distribution without requiring assumptions about the state-space model or the state distributions. However, these methods do not perform well when applied to very high-dimensional systems. Particle filters implement the prediction-updating updates in an approximate manner. The samples from the distribution are represented by a set of particles; each particle has a likelihood weight assigned to it that represents the probability of that particle being sampled from the probability density function. Weight disparity leading to weight collapse is a common issue encountered in these filtering algorithms; however it can be mitigated by including a resampling step before the weights become too uneven. Several adaptive resampling criteria can be used, including the variance of the weights and the relative entropy with respect to the uniform distribution. In the resampling step, the particles with negligible weights are replaced by new particles in the proximity of the particles with higher weights. From the statistical and probabilistic point of view, particle filters can be interpreted as mean field particle interpretations of Feynman-Kac probability measures. These particle integration techniques were developed in molecular chemistry and computational physics by Theodore E. Harris and Herman Kahn in 1951, Marshall N. Rosenbluth and Arianna W. Rosenbluth in 1955 and more recently by Jack H. Hetherington in 1984. In computational physics, these Feynman-Kac type path particle integration methods are also used in Quantum Monte Carlo, and more specifically Diffusion Monte Carlo methods. Feynman-Kac interacting particle methods are also strongly related to mutation-selection genetic algorithms currently used in evolutionary computing to solve complex optimization problems. The particle filter methodology is used to solve Hidden Markov Model (HMM) and nonlinear filtering problems. With the notable exception of linear-Gaussian signal-observation models (Kalman filter) or wider classes of models (Benes filter) Mireille Chaleyat-Maurel and Dominique Michel proved in 1984 that the sequence of posterior distributions of the random states of the signal given the observations (a.k.a. optimal filter) have no finitely recursive recursion. Various numerical methods based on fixed grid approximations, Markov Chain Monte Carlo techniques (MCMC), conventional linearization, extended Kalman filters, or determining the best linear system (in expect cost-error sense) have never really coped with large scale systems, unstable processes or when the nonlinearities are not sufficiently smooth. Particle filters and Feynman-Kac particle methodologies find application in signal and image processing, Bayesian inference, machine learning, risk analysis and rare event sampling, engineering and robotics, artificial intelligence, bioinformatics, phylogenetics, computational science, Economics and mathematical finance, molecular chemistry, computational physics, pharmacokinetic and other fields.