AI Glossary / Probabilistic machine learning / Advanced

Systematic resampling

Definition

Systematic resampling is a particle-filtering procedure that replaces weighted particles with equally weighted copies by placing evenly spaced selection points along a cumulative-weight interval. A single random starting offset determines the entire set of selection points. Particles with larger weights generally receive more copies, while some particles receive none.

What it means

A particle filter represents uncertainty using many candidate states and associated weights. After observations are incorporated, a few candidates may carry nearly all the weight. Resampling reallocates computational effort toward these candidates before subsequent propagation.

Systematic resampling uses one randomized grid instead of drawing every selection independently. Its simplicity makes it attractive, but the shared random offset links the selections. The operation changes the representation of the current weighted distribution; it does not create new observational evidence or make the underlying model correct. Repeated copies are still copies of existing states until a later transition or rejuvenation step changes them.

How it works

Normalize the input weights so that they are nonnegative and sum to one. Build their cumulative sums in a specified particle order. If the required output population has N particles, draw one offset U uniformly between zero and 1/N.

Construct selection positions U, U + 1/N, through U + (N minus 1)/N. At each position, select the particle whose cumulative-weight interval contains that position. Give every selected copy weight 1/N.

A cumulative scan processes the ordered positions efficiently. Boundary conventions should be consistent, and the final cumulative sum should be handled robustly against floating-point rounding. The random offset must genuinely cover its interval; always selecting its midpoint changes the procedure.

For each input particle, the expected number of copies equals N times its normalized weight. This is a conditional expectation over the random offset, not a promise that every resampled population preserves every weighted average exactly. Output selections are dependent, and particle ordering affects their joint behavior.

Three practical examples

1. A mobile robot resamples candidate positions after a sensor observation gives high weight to locations consistent with a visible landmark.

2. A forecasting prototype reallocates particles representing hidden demand conditions after incorporating a new measurement.

3. A tracking system uses an effective-sample-size trigger to decide when weights have become concentrated enough to justify resampling, then applies the systematic procedure.

Think of it this way

Think of a strip divided into colored segments whose lengths represent weights. Lay a comb with equally spaced teeth over the strip, choosing its starting position at random. Each tooth copies the color beneath it. Moving the comb shifts every tooth together, explaining why the selections are related rather than independent.

Worked example

Suppose four particles A, B, C and D have states 0, 2, 5 and 9, with weights 0.1, 0.2, 0.3 and 0.4. Their cumulative weights are 0.1, 0.3, 0.6 and 1.0. We want four output particles.

Choose offset U = 0.08 within the interval from zero to 0.25. The four selection positions are 0.08, 0.33, 0.58 and 0.83. They select A, C, C and D. The resulting equal-weight mean is (0 + 5 + 5 + 9)/4 = 4.75. The original weighted mean is 0.1 times 0 + 0.2 times 2 + 0.3 times 5 + 0.4 times 9 = 5.5.

A different offset, U = 0.18, produces positions 0.18, 0.43, 0.68 and 0.93, selecting B, C, D and D. That population has mean 6.25.

Neither individual result must equal 5.5. Averaged over the uniform offset, expected copy counts are 0.4, 0.8, 1.2 and 1.6, giving expected output mean 5.5. The example illustrates unbiased resampling of this existing weighted estimate, not an unbiased estimate of every real-world state.

Illustrative case study

Fictional case: Rowan Robotics notices that a localization prototype spends most computation propagating particles with negligible weight. Its engineers add systematic resampling when a monitored weight-concentration threshold is crossed.

They also track the number of distinct ancestors and test several particle orderings on recorded routes. Faster processing is useful only if localization error and recovery behavior remain acceptable. When many copies share one ancestor, the team investigates proposal quality and motion uncertainty instead of treating the equal post-resampling weights as proof that uncertainty is adequately represented.

Common misconceptions and mistakes

Systematic resampling is not independent sampling within each interval; that describes stratified resampling. Here every interval uses the same relative offset.

It is also incorrect to claim that systematic resampling always has lower conditional variance than multinomial resampling. Such universal dominance does not hold, and ordering can matter.

Equal output weights do not mean distinct output states. A high effective sample size calculated immediately after resetting weights can coexist with severe loss of particle diversity. Resampling too frequently may worsen ancestry collapse, while resampling too rarely can leave most computational effort attached to negligible weights.

Business use

Business applications include tracking, simulation-based forecasting and inference for evolving hidden conditions. The practical appeal is a simple resampling step with modest random-number requirements. Evaluation should include state-estimation quality, execution time, distinct-particle counts and sensitivity to ordering. A resampling choice should be tested inside the complete inference workflow, because good standalone behavior may not resolve a poor transition model or observation likelihood.

People also ask

Is it deterministic?

No. One random offset controls an otherwise deterministic selection grid.

Can one particle appear several times?

Yes, especially when its weight is large.

Does it move particles to new locations?

The basic resampling step only selects copies. Movement requires a separate propagation or mutation operation.

Check your understanding

Why does the worked example produce different means?

Answer: Each offset produces a different finite population, although the conditional expected mean is preserved.

What distinguishes systematic from stratified resampling?

Answer: A shared offset versus independently randomized positions within the intervals.

Related terms

• Sequential Monte Carlo
• Multinomial resampling
• Stratified resampling
• particle filter
• importance weights
• effective sample size and particle impoverishment

Learn next

Next, compare resampling schemes on the same weighted particles and measured function. Then study when to trigger resampling and how proposal design or rejuvenation can maintain useful diversity.

More in Probabilistic machine learning

• Supervised principal component analysis - Supervised principal component analysis uses outcome information to guide a lower-dimensional representation of predictors.
• Surrogate loss - A surrogate loss is an alternative training objective used in place of a task loss that is difficult to optimize directly.
• Symmetric stochastic neighbor embedding - Symmetric stochastic neighbor embedding is a method for arranging high-dimensional observations in a low-dimensional map by matching symmetric probabilities...
• TD(lambda) - TD(lambda), written TD(λ), is a family of temporal-difference learning methods that use eligibility traces to spread prediction errors across recently...
• Test-time adaptation - Test-time adaptation is the adjustment of a trained model or its inference statistics using data encountered during deployment or evaluation.
• Tied covariance in Gaussian discriminant analysis - Tied covariance in Gaussian discriminant analysis means that all modeled classes share one covariance matrix, while retaining their own mean vectors and...

Sources

Primary source: Randal Douc, Olivier Cappé and Eric Moulines, Comparison of Resampling Schemes for Particle Filtering, especially the systematic-resampling construction and its variance counterexample: https://arxiv.org/pdf/cs/0507025

The numerical example and fictional case are original teaching material. Claims of expected preservation are conditional on the supplied particles and weights.

Independent review consulted Sections 2.4 and 3.4 of the original resampling comparison, including its variance counterexample.

Previous: System prompt Next: Systemic bias