package prbnmcn-dagger

  1. Overview
  2. Docs

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

Algorithm description

A detailed treatment of the following algorithms is given in A Tutorial on Particle Filtering and Smoothing: Fifteen years lated (Doucet & Johansen) section 3.4.

In the following, we consider a family of scored particles (x_k, w_k) for k=1 \ldots K with total score W=\sum_k w_k.

The outcome of the resampling strategies described below is a map from each particle x_k to a replication count r_k, such that \sum_k r_k = N. The resulting population will consist in r_1 copies of x_1, r_2 copies of x_2, etc, all with equal score \frac{1}{W}.

Systematic resampling

Let U be sampled uniformly in [0,\frac{1}{N}]. Consider the set of points U_i = U + \frac{i-1}{N} for i=1 \ldots N-1. Associate to each particle x_k its cumulative score W_k = w_1 + ... + w_k and us set W_0 = 0. We set r_k to be the cardinal of the set of W \cdot U_i included in [W_{k-1}, W_k).

Stratified resampling

For each i in 1 \ldots N, let U_i be sampled uniformly in [0, \frac{1}{N}]. Associate to each i the particle x_k with the lowest k such that \frac{i-1}{N} + U_i < W_k/W. The replication count r_k is the number of times x_k was selected in this process.

Parameters

module F : Intf.Field
module Sampler : sig ... end

Signature

val stratified_resampling : ess_threshold:F.t -> ('o, F.t, 's) strategy

stratified_resampling ess_threshold executes stratified resampling if the estimated sample size P.ess of the population is below ess_threshold * P.size (), where P is the particles module passed to the strategy.

  • raises Invalid_arg

    if P.size < 2, if target_size < 2 or if ess_threshold is not in the unit interval.

val systematic_resampling : ess_threshold:F.t -> ('o, F.t, 's) strategy

systematic_resampling ess_threshold executes systematic resampling if the estimated sample size P.ess of the population is below ess_threshold * P.size () where P is the particles passed to the strategy.

  • raises Invalid_arg

    if P.size < 2, if target_size < 2 or if ess_threshold is not in the unit interval.

OCaml

Innovation. Community. Security.