particles.resampling¶
Resampling and related numerical algorithms.
Overview¶
This module implements resampling schemes, plus some basic numerical functions related to weights and weighted data (ESS, weighted mean, etc). The recommended import is:
from particles import resampling as rs
Resampling is covered in Chapter 9 of the book.
Resampling schemes¶
All the resampling schemes are implemented as functions with the following signature:
A = rs.scheme(W, M=None)
where:
W
is a vector of N normalised weights (i.e. positive and summing to one).
M
(int) is the number of resampled indices that must be generated; (optional, set to N if not provided).
A
is a ndarray containing the M resampled indices (i.e. ints in the range 0, …, N-1).
Here the list of currently implemented resampling schemes:
multinomial
residual
stratified
systematic
ssp
killing
If you don’t know much about resampling, it’s best to use the default scheme (systematic). See Chapter 9 of the book for a discussion.
Alternative ways to sample from a multinomial distribution¶
Function multinomial
samples efficiently M times from the multinomial
distribution that produces output n with probability W[n]
. It does so
using an algorithm with complexity O(M+N), as explained in Section 9.4 of the
book. However, this function is not really suited:
if you don’t want to get ordered samples, but truly IID ones;
if you want to draw only once from that distribution;
If you do not know in advance how many draws you need.
The three functions below cover these scenarios:
multinomial_iid
multinomial_once
MultinomialQueue
Weights objects¶
Objects of class SMC
, which represent the output of a particle filter, have
an attribute called wgts
, which is an instance of class Weights
. The
attributes of that object are:
lw
: the N un-normalised log-weightsW
: the N normalised weights (sum equals one)ESS
: the effective sample size (1/sum(W^2))
For instance:
pf = particles.SMC(fk=some_fk_model, N=100)
pf.run()
print(pf.wgts.ESS) # The ESS of the final weights
The rest of this section should be of interest only to advanced users (who wish
for instance to subclass SMC
in order to define new particle algorithms).
Basically, class Weights
is used to automate and abstract away the computation of
the normalised weights and their ESS. Here is a quick example:
from numpy import random
wgts = rs.Weights(lw=random.randn(10)) # we provide log-weights
print(wgts.W) # the normalised weights have been computed automatically
print(wgts.ESS) # and so the ESS
incr_lw = 3. * random.randn(10) # incremental weights
new_wgts = wgts.add(incr_lw)
print(new_wgts.ESS) # the ESS of the new weights
Warning
Weights
objects should be considered as immutable: in particular method add
returns a new Weights
object. Trying to modify directly (in place) a
Weights
object may introduce hairy bugs. Basically, SMC
and the methods of
ParticleHistory
do not copy such objects, so if you modify them later, then
you also modify the version that has been stored at a previous iteration.
Other functions of interest¶
In particles, importance weights and similar quantities are always computed and stored on the log-scale, to avoid numerical overflow. This module also contains a few basic functions to deal with log-weights:
essl
exp_and_normalise
log_mean_exp
log_sum_exp
wmean_and_var
wmean_and_var_str_array
wquantiles
Functions
|
ESS (Effective sample size) computed from log-weights. |
|
Exponentiate, then normalise (so that sum equals one). |
|
Idiotic resampling. |
|
Inverse CDF algorithm for a finite distribution. |
|
Killing resampling. |
|
Returns log of (weighted) mean of exp(v). |
|
Log of the sum of the exp of the arguments. |
|
log_sum_exp for two scalars. |
|
Multinomial resampling. |
|
Multinomial resampling (IID draws). |
|
Sample once from a Multinomial distribution. |
|
|
|
Decorator for resampling schemes. |
|
Residual resampling. |
|
SSP resampling. |
|
Stratified resampling. |
|
Systematic resampling. |
|
Generate ordered uniform variates in O(N) time. |
|
Weighted mean and covariance matrix. |
|
Component-wise weighted mean and variance. |
|
Weighted mean and variance of each component of a structured array. |
|
Quantiles for weighted data. |
|
quantiles for weighted data stored in a structured array. |
Classes
|
On-the-fly generator for the multinomial distribution. |
|
A class to store N log-weights, and automatically compute normalised weights and their ESS. |