Particle filter

Introduction to Particle Filter
Sampling Algorithm in PF
Bayesian Estimation
Monte Carlo Integration Methods
Importance Sampling (IS)
Sequential Importance Sampling (SIS)
Sequential Importance Resampling

1. In the Name of God Title: Particle Filter and Sampling Algorithms     By : Mohammad Reza Jabbari Email: [email protected] January 2017

2. Outline 1. Estimation Concepts 2. Bayesian Estimation 3. Monte Carlo Integration Methods 4. Particle Filter 5. Sampling Algorithms 6. Application 7 . Summery 8. End 2/18 2/19

3. 1.Estimation Concepts The purpose of estimation is to obtain an Approximate Value of an Unknown Parameter , based on Noisy Observations made from measurements . Estimation Theory Classic (Estimation of a Parameter) Bayesian (Estimation of a Random Variable) Point Estimation Interval Estimation Method of Moment Maximum Likelihood (ML) Kalman Filter (KF) Extended Kalman Filter (EKF) Unscented Kalman Filter (UKF) Particle Filter (PF) Linearity / Gaussian low nonlinearity / Gaussian high nonlinearity / Gaussian Recursive form nonlinearity / non Gaussian Definition And Classification 3 /18 3/19

4. Representation of Systems (Modeling) State-Space Model Many Process and systems can described with by state-space models System Equation: Dynamic Equation Measurement Equation     System State at time instant t State Transition Function Process Noise   Observation at time instant t Observation Function Obseravtion Noise       Probabilistic form Probabilistic form Likelihood Density State Transition Density 4/19

5. 2. Bayesian Estimation The Goal The goal of a Bayesian estimator is to approximate the unknown state base on base on previous measurements : =   Aposterior Density By knowing posterior distribution, all kind of Estimation can be compute The goals of Bayesian estimator Find Aposterior Distribution 5/19

6. Bayesian Estimator Recursive Equations Updating: Prediction:     State transition density Aprior at time t Aposteriori at time t-1 Aposteriori at time t Aprior at time t Likelihood         Prediction Prediction Update Update Update         Time instant t=0 Time instant t=1 Time instant t=2

7. Problems The solution is conceptual because integral are not tractable Close form solution are possible in a small number of situation Solution Use Monte Carlo Integration Methods For linear systems with Gaussian noise distribution Optimal Estimation Using the Kalman Filter (KF ) 7/19

8. 3. Monte Carlo Integration Methods Monte Carlo Integration is a Simple but Powerful technique for approximating complicated integrals. Assume we are trying to estimate the integral of a function f over some domain D : Assume that we have a PDF p defined over a domain D : Its means that we generate samples according to p , computing f/p for each sample, and finding the average of these values. This equality is true for any PDF on D , as long as p(x ) whenever f(x)   9/19

9. Question What happens when we generate a random sample where the value of p is very small? if p is very small for a given sample, f/p will be arbitrarily large. This large sample will greatly skew the sample mean away from the true mean, and the sample variance will also increase greatly. Bad Samples but one general rule of thumb to follow is that p should “look like” f (Importance Sampling) Answer 10/19

10. 4. Particle Filter The particle filter is technique for implementing Recursive Bayesian Filter By Monte Carlo Sampling Particles , with corresponding Weights are used to form an approximation of a probability density function (PDF)       Time instant t-1 Time instant t       Prediction   Update     N ormalization 11/19

11. Sample Representation of the posterior pdf The representation of the posterior pdf in the form of a set of samples is very convenient For example: threat analysis, decision and control problems,   In many cases, the requirement is find some particular function of the posterior , and the sample representation is often ideal for this.   Empirical Distribution 12/19

12. Unfortunately, it’s usually impossible to sample efficiently from the posteriori distribution at any time t , because being multivariate , non standard and only known up to a proportionality constant. Importance Sampling Generate sample from another distribution (Proposal Distribution) Weight them according to how they fit the Posterior distribution Notice: Free to choose proposal density but: It should be easy to sample from proposal density Proposal density should resemble the original density as closely as possible Problem Solution 13/19

13. 5 . Sampling Algorithms Importance Sampling (IS)   Importance Weight   14/19

14. Sequential Importance Sampling ( S IS) Importance sampling in its simplest form, it’s not adequate for recursive estimation. Because, it needs to get all data before estimating . So the computational complexity increase with time.     If we can consider:     If Proposal distribution equal to A priori distribution 15/19

15. Sequential Importance Resampling (SIR) Problem: The problem encountered by the SIS method is that, as t increase, the distribution of the importance weight becomes more and more skewed. And after a few time step, only one particle has a non-zero importance weight. (Degeneracy) Solution: the key idea is to eliminate the particles having low importance weights and multiply particles having high importance weigh (Resampling) 16/19

16. Problem of Resampling Impoverishment of the sample set particles with large weights may be selected many times so that the new set of samples may contain multiple copies of just a few distinct values. Solution: Effective Sample Size   17/19

17. 6. Application Image Processing Sound Processing Tracking and Navigation Channel E stimation Biology …. Base on image 1. Image Processing and Extract features 2 . Estimation 18/19

18. 7 . Summary Particle filter is very powerful framework for estimating parameter in nonlinear / non Gaussian model Adapting with state-space model Finding new application for particle filter Developing new implementation to reduce complexity Finding a mechanism to optimize number of particle Advantages Disadvantages High Computational Complexity It’s difficult to determine optimal Number of Particles Increasing particle with increasing model dimension Choice of importance density Main Research Directory 19/19

19. The END