# resampling¶

Routines for resampling particles from particle filters based on their current weights. All these routines take a list of normalized weights and returns a list of indexes to the weights that should be chosen for resampling. The caller is responsible for performing the actual resample.

Copyright 2015 Roger R Labbe Jr.

filterpy library. http://github.com/rlabbe/filterpy

Supporting book at: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python

filterpy.monte_carlo.residual_resample(weights)[source]

Performs the residual resampling algorithm used by particle filters.

Based on observation that we don’t need to use random numbers to select most of the weights. Take int(N*w^i) samples of each particle i, and then resample any remaining using a standard resampling algorithm 

Parameters: weights : list-like of float list of weights as floats indexes : ndarray of ints array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes, etc.

References

  J. S. Liu and R. Chen. Sequential Monte Carlo methods for dynamic systems. Journal of the American Statistical Association, 93(443):1032–1044, 1998.

filterpy.monte_carlo.stratified_resample(weights)[source]

Performs the stratified resampling algorithm used by particle filters.

This algorithms aims to make selections relatively uniformly across the particles. It divides the cumulative sum of the weights into N equal divisions, and then selects one particle randomly from each division. This guarantees that each sample is between 0 and 2/N apart.

Parameters: weights : list-like of float list of weights as floats indexes : ndarray of ints array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes, etc.

filterpy.monte_carlo.systematic_resample(weights)[source]

Performs the systemic resampling algorithm used by particle filters.

This algorithm separates the sample space into N divisions. A single random offset is used to to choose where to sample from for all divisions. This guarantees that every sample is exactly 1/N apart.

Parameters: weights : list-like of float list of weights as floats indexes : ndarray of ints array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes, etc.

filterpy.monte_carlo.multinomial_resample(weights)[source]
This is the naive form of roulette sampling where we compute the
cumulative sum of the weights and then use binary search to select the resampled point based on a uniformly distributed random number. Run time is O(n log n). You do not want to use this algorithm in practice; for some reason it is popular in blogs and online courses so I included it for reference.
Parameters: weights : list-like of float list of weights as floats indexes : ndarray of ints array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes, etc.