Interactive demo · Probabilistic Machine Learning: Advanced Topics · Chapter 13

Resampling schemes: multinomial, stratified, systematic

Resampling turns a weighted particle set into an unweighted one by choosing N ancestors: draw points U1, …, UN in (0, 1) and give each the particle whose step of the cumulative weight they land in (the staircase). The three schemes differ only in how the points are drawn: independently (multinomial), one per stratum of width 1/N (stratified), or on an evenly spaced grid shifted by one common random number (systematic). All three give the right number of offspring on average, N Wn, but the variance differs: the exact values are shown as lines, simulated values as dots. With equal weights a multinomial draw loses about 37% of the particles (they receive no offspring), while stratified and systematic resampling keep every one.

Particles N

Weight spread σ (W ∝ exp(σ g), g standard normal)

Scheme shown in the single draw

Simulated resamplings

Try these

Weights Wn = exp(σ gn)/Σexp(σ gm). Exact offspring variances: multinomial N W(1 − W); systematic frac(N W)(1 − frac(N W)); stratified Σk pk(1 − pk), where pk is the chance that the point of stratum k lands in the particle's step. The estimate is the mean of f(zAj) over the resampled set for a fixed standard-normal f; its target is ΣWn fn. Each scheme is simulated with its own seeded generator.

In the lecture notes