Resampling is used to improve the statistical quality of a population of weighted particles.
Informally, resampling consists in sampling
N new particles (each with weight
1/N) from a given population such that the resulting population is distributed identically to the target one (ie is unbiased).
An straightforward to proceed would be to sample from a multinomial distribution with parameters
N and the normalized weights of the given population. Other schemes are used in practice.
We consider the following schemes:
- systematic resampling
- stratified resampling
In the following, we consider an (ordered, even if arbitrarily) family of particles
(x_k, w_k) for
The outcome of resampling is a map from each particle
x_k to a replication count
U be sampled uniformly in
[0,1/N]. Consider the partition of the
[0,1) interval in
N sub-intervals given by the points
U_i = U + (i-1)/N for
Associate to each particle
x_k its cumulative weight
W_k = w_1 + ... + w_k and let us set
W_0 = 0.
r_k to be the cardinal of the set of
U_i included in
U_i be sampled uniformly in
[0, 1/N] and consider the family of intervals
(i-1)/N, (i-1)/N + U_i for
i=1...N. We associate to each
i the particle
x_k with the lowest
k such that
(i-1)/N + U_i < W_k.
The replication count
r_k is the number of times
x_k was selected in this process.
A Tutorial on Particle Filtering and Smoothing: Fifteen years lated (Doucet & Johansen)
module type Particle = sig ... end
Particle is any abstract type from which a
weight can be computed.
module type S = sig ... end
The module type exposing resampling functions.
module Make (F : Intf.Field) (P : Particle with type field = F.t) (Sampler : sig ... end) : S with type field = F.t and type particle = P.t
Make functor is generic over a field
F and a uniform sampler. Genericity over the underlying field is especially useful for testing, using arbitrary-precision rationals.
module Float_field : Intf.Field with type t = float