AI Glossary / Probabilistic machine learning / Intermediate
Stratified resampling
Definition
Stratified resampling is a particle-resampling method that divides the unit interval into equally sized strata, draws one independent uniform value within each stratum, and maps those values through the cumulative particle weights. It converts a weighted particle population into an equally weighted one while reducing resampling variability relative to ordinary multinomial resampling for a fixed population and test function.
What it means
Particle methods represent uncertainty using candidate states and their weights. After incorporating observations, a few candidates may carry most of the weight. Resampling reallocates computational effort by making more copies of important candidates and fewer copies of unimportant ones.
Stratified resampling spreads its random selections across the cumulative probability interval. The strata are intervals of probability mass, not bins of state values or business categories. A particle whose weight spans multiple strata can still be selected repeatedly. The method does not generate new state locations or restore possibilities that were already absent.
How it works
Normalize the particle weights and form their cumulative sums in a specified order. If N output particles are required, divide zero to one into N equal intervals. Independently draw one uniform position in each interval. Select the first cumulative weight reaching each position, using a consistent boundary convention.
Copy the selected particles and assign each weight 1 divided by N. Individual positions have different stratum-specific distributions, but the expected total offspring count for particle i is N times its original weight. Thus the resampled average of any fixed particle function preserves the original weighted average in conditional expectation.
This is not systematic resampling, which uses one shared random offset for a whole evenly spaced grid. Independent within-stratum draws define stratified resampling. Particle ordering can affect its conditional variance, and the resampling schedule remains a separate design choice, often informed by a weight-degeneracy diagnostic.
Three practical examples
1. Object tracking: allocate more particle copies to states consistent with a new sensor observation. Propagation afterward can create new positions, while resampling itself only chooses existing ancestors.
2. Sequential forecasting: replace a sharply weighted population with equal-weight representatives before further simulation. Check that resampling frequency does not cause excessive loss of distinct histories.
3. Probabilistic simulation: compare resampling schemes using the same weighted input population. Evaluate variation in relevant estimates over repeated resampling runs rather than ranking schemes from one favorable random draw.
Think of it this way
Think of a weighted ticket strip laid along a ruler. Instead of dropping all selection marks anywhere on the strip, divide the ruler into equal sections and place one random mark in each. Large ticket blocks can receive several marks, but the marks cover the ruler more evenly than unrestricted independent placements.
Worked example
Consider an original population with states A = 0, B = 2, C = 5, and D = 9. Their weights are 0.1, 0.2, 0.3, and 0.4, giving cumulative weights 0.1, 0.3, 0.6, and 1. The weighted mean is 0 + 0.4 + 1.5 + 3.6 = 5.5.
For four output particles, draw one position in each quarter of the unit interval. Suppose the realized positions are 0.05, 0.40, 0.55, and 0.90. They select A, C, C, and D. The equal-weight resampled mean is (0 + 5 + 5 + 9) divided by 4 = 4.75. It need not equal 5.5 in one realization.
The expected offspring counts are 0.4, 0.8, 1.2, and 1.6. For this ordering, the selected state in the first stratum is A with probability 0.4 or B with probability 0.6. The second selects B with probability 0.2 or C with probability 0.8; the third selects C with probability 0.4 or D with probability 0.6; the fourth always selects D.
Their variances are 0.96, 1.44, 3.84, and zero. Independence across strata gives variance of the resampled mean equal to their sum divided by 16, or 0.39. Multinomial resampling gives (40.7 minus 5.5 squared) divided by 4 = 2.6125. This comparison concerns conditional resampling variance, not the total error of a complete filter.
Illustrative case study
Fictional case: Elm Tracking compares resampling choices for a simulated warehouse vehicle. Analysts save several weighted populations, apply each resampler repeatedly to the same populations, and inspect the variability of estimated position and the number of distinct ancestors.
They separately evaluate the full filter under missed observations and difficult trajectories. A reduction in resampling variance is not treated as proof that the motion model is correct. The team documents particle order and random seeds so unexpected differences can be reproduced. This fictional evaluation makes no claim of measured performance on a deployed vehicle.
Common misconceptions and mistakes
Stratified resampling is not stratified sampling of the original dataset. It does not guarantee every particle survives or that every realization improves an estimate. Equal output weights can conceal duplicated particles and lost ancestry. Also avoid extending its conditional-variance comparison with multinomial resampling into a universal claim that it produces the best full filtering result in every problem.
Business use
The benefit is controlled resampling variability with a simple procedure. The operational questions include particle count, cumulative-weight numerical stability, ordering, and when resampling occurs. Teams should inspect both weight concentration and ancestry diversity. After weights become equal, a weight-based effective sample size can look ideal even when many particles are copies, so that number alone is an incomplete quality check.
People also ask
Does each stratum correspond to one original particle?
No; a stratum can overlap several particle weight intervals.
Is it deterministic?
No. Each stratum contains an independent random draw.
Why can the sample mean change?
Resampling is unbiased conditionally, but it still introduces finite-population randomness.
Check your understanding
Answer: 1.
Which particles are selected in the worked example?
Answer: A, C, C, and D.
Answer: 2.
Does the mean 4.75 contradict unbiasedness?
Answer: No. Unbiasedness concerns repeated resampling expectations, not every realization.
Answer: 3.
What distinguishes systematic resampling?
Answer: Its positions share a single random offset instead of independent within-stratum draws.
Related terms
- Sequential Monte Carlo
- Multinomial resampling
- Systematic resampling
- Effective sample size
- Particle filter
- residual resampling
- particle impoverishment
Learn next
Construct a cumulative weight function for a small population and compare resampling outputs across seeds. Then derive conditional means and variances and study how resampling interacts with propagation and ancestry loss.
More in Probabilistic machine learning
- Stochastic weight averaging - Stochastic weight averaging, or SWA, forms a single neural-network model by taking an equal average of selected parameter vectors along a training trajectory.
- Stochastic weight averaging Gaussian approximation - Stochastic weight averaging Gaussian approximation, usually called SWA-Gaussian or SWAG, fits a Gaussian distribution over neural-network parameters using...
- Straight-through estimator - A straight-through estimator is a training rule that substitutes a usable derivative for the derivative of a hard or discrete operation during backpropagation.
- Structural time series model - A structural time series model represents an observed series through interpretable latent components, such as a changing level, trend, seasonality, cycle...
- Structured kernel interpolation - Structured kernel interpolation, or SKI, approximates a covariance kernel using interpolation from a set of inducing or interpolation points.
- Structured mean field variational inference - Structured mean field variational inference approximates a difficult posterior using a tractable distribution that preserves selected dependencies among...
Sources
Douc, Cappé and Moulines, Comparison of Resampling Schemes for Particle Filtering, defines stratified resampling and its conditional-variance comparison: https://arxiv.org/pdf/cs/0507025
The four-state calculation and Elm Tracking case are original teaching examples; the case is fictional.
Independent review consulted Sections 2.3–2.4 and 3.3 of the original resampling comparison.
Previous: Stratified randomization Next: Stratified sampling