Resampling functions.
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:
In the following, we consider an (ordered, even if arbitrarily) family of particles (x_k, w_k) for k=1...K.
The outcome of resampling is a map from each particle x_k to a replication count r_k.
Let 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 i=1...N-1.
Associate to each particle x_k its cumulative weight W_k = w_1 + ... + w_k and let us set W_0 = 0.
We set r_k to be the cardinal of the set of U_i included in [W_{k-1}, W_k].
For each i in 1...N, let 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 W_k verifies (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 ... endA Particle is any abstract type from which a weight can be computed.
module type S = sig ... endThe 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.tThe 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