Module Dagger.Resampling

Resampling functions

Resampling consists in sampling N new particles from a given population such that the resulting population is distributed identically to the initial one (ie is unbiased) and such that the statistical quality of the resulting population is improved.

This module provides an API allowing users to specify their own resampling schemes. It also provides some well-known resampling strategies via the Resampling.Make_predefined functor.

Example

A straightforward strategy is to sample from a multinomial distribution with parameters N and the normalized scores of the given population. An implementation of corresponding algorithm using the API of this module is described here. Note that better-performing schemes are used in practice.

API

A resampling algorithm takes as input a "current" population of particles and must produce the "next" population. The only operations available to do so are accessed through a first class module of type Particles.

module type Particles = sig ... end

A Particles module exposes primitives available to resampling algorithms.

type ('o, 'r) particles = (module Particles with type o = 'o and type r = 'r)

Implementation of resampling must be generic in the implementation of particles, hence we abstract their types away.

type ('o, 'r, 'resampling_state) strategy = target_size:int -> ('o, 'r) particles -> 'resampling_state -> RNG.t -> 'resampling_state

strategy is the type of resampling steps.

  • The first argument corresponds to the target size of the population.
  • The second argument represents the particles on which resampling is to be performed.
  • The third argument is the previous resampling state.
  • The fourth argument is the random number generator state.

Resampling strategies are called once every resampling step.

module Make_predefined (F : Intf.Field) (Sampler : sig ... end) : sig ... end

Make_predefined (F) (Sampler) produces implementations of stratified and systematic resampling over a field F and given a uniform sampler Sampler.