Make_predefined (prbnmcn-dagger.Dagger.Resampling.Make

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.