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

Documentation at: https://filterpy.readthedocs.org

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

This is licensed under an MIT license. See the readme.MD file for more information.

---

filterpy.monte_carlo.residual_resample(weights)

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 [1]

Parameters:

weightslist-like of float

list of weights as floats

Returns:

indexesndarray of ints

array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes[0], etc.

References

[1]

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)

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:

weightslist-like of float

list of weights as floats

Returns:

indexesndarray of ints

array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes[0], etc.

---

filterpy.monte_carlo.systematic_resample(weights)

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:

weightslist-like of float

list of weights as floats

Returns:

indexesndarray of ints

array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes[0], etc.

---

filterpy.monte_carlo.multinomial_resample(weights)

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:

weightslist-like of float

list of weights as floats

Returns:

indexesndarray of ints

array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes[0], etc.