prbnmcn-dagger
  1. Overview
  2. Docs

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:

  • systematic resampling
  • stratified resampling

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.

Systematic resampling

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].

Stratified resampling

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.

References

A Tutorial on Particle Filtering and Smoothing: Fifteen years lated (Doucet & Johansen)

module type Particle = sig ... end

A 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

The 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
module Make_float (P : Particle with type field = float) : S with type field = float and type particle = P.t

Make_float instantiates Make over the field of floats.