package prbnmcn-dagger

  1. Overview
  2. Docs

Sequential Monte Carlo

Sequential Monte Carlo (SMC) represents a probability distribution by a family of particles weighted by their scores (the population in SMC parlance). The population is evolved by alternating importance sampling steps and resampling steps. The goal of resampling steps is to increase the statistical quality of the population, e.g. by removing zero or low-score particles and "reproducing" high-score ones.

At any point, one can obtain an approximation of the target distribution by normalizing the scores of the population.

Resampling steps must be unbiased: the resampled population must represent the same target distribution as the population before resampling. See Resampling for the API related to resampling strategies.

This module provides a convenient API for describing models to be run with SMC inference. It lets the user write the importance sampling part of the model and the resampling strategy modularly. Resampling points are marked using the yield primitive, which also acts as a message-passing bridge between each importance sampling step and the resampling step that follows it:

val yield : particle_output -> resampling_state t

In a nutshell:

  • particles give their current value as argument to yield, and the outcome of resampling (of type resampling_state) is broadcast to each particle as the value to which yield evaluates to.
  • Resampling steps take the outcome of the previous resampling step as argument.

Note: applications that do not require to maintain state across resampling steps can set resampling_state = unit. Non-trivial resampling states are mostly useful for programming advanced SMC constructs.

The flow of data is subsumed in the following diagram:

From an implementation perspective, SMC inference proceeds by letting particles, implemented as lightweight threads, evolve independently until the next resampling event. Resampling acts as a synchronization barrier for all particles. The output of the inference is a sequence of the scored values carried by the particles just before each resampling.

Have a look at the examples.

API of sequential Monte Carlo inference

module type S = sig ... end

The sequential Monte Carlo DSL.

module type Resampling_types_S = sig ... end

The SMC implementation is parametric in the type of values produced by the particles at each yield and in the type of state of resampling.

Make produces an SMC inference module specialized to the types given in Resampling_types.

Predefined instances of Make

module Unit_smc : sig ... end
module Float_smc : sig ... end

Predefined resampling strategies

val systematic_resampling : ess_threshold:float -> ('o, float, 's) Resampling.strategy
val stratified_resampling : ess_threshold:float -> ('o, float, 's) Resampling.strategy
OCaml

Innovation. Community. Security.