Legend:
Library
Module
Module type
Parameter
Class
Class type

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.