AI Glossary / Probabilistic machine learning / Advanced
Multinomial resampling
Definition
Multinomial resampling replaces a weighted collection of particles with equally weighted copies selected randomly according to the original weights. Each new particle independently chooses a parent, conditional on the current particle collection. The resulting parent-copy counts follow a multinomial distribution. It is a basic resampling method in particle filtering and sequential Monte Carlo.
What it means
A particle is one possible state of a system, such as a vehicle's location or a machine's hidden operating condition. Its weight measures its relative contribution to the current approximation. When most weight concentrates on a few particles, repeatedly processing all the others can become inefficient. Resampling gives more future computational effort to states currently carrying more weight.
The operation changes the representation of existing information. It does not provide another sensor reading or establish that a highly weighted state is correct. Copies can subsequently move apart through the model's transition or a suitable rejuvenation procedure, but copying itself introduces no new state values.
How it works
Normalize nonnegative weights so they sum to one, and choose an output population size N. Draw N parent indices independently, with selection probability equal to each parent's normalized weight. Copy the selected states and give each output weight 1/N. Sampling permits repeated parents and may omit others entirely.
One implementation forms cumulative weight intervals and locates independent uniform random numbers within them. Implementations can return indices in a different order while preserving the same count distribution; ordering is usually immaterial when the following particle operations treat copies symmetrically. Reproducible random seeds help investigate differences between runs.
For parent i, the expected copy count is N times its weight, but the realized count is an integer and fluctuates. Conditional on the input collection, the expected resampled average of any fixed particle quantity equals its original weighted average. This conditional property does not make an approximate filtering distribution exact. Residual and stratified alternatives can reduce conditional resampling variance; systematic resampling does not have an unrestricted variance-dominance guarantee.
Three practical examples
- A warehouse robot represents possible positions with particles. After a distinctive landmark observation, resampling allocates more particles to plausible positions. Future motion uncertainty can separate copies, while an incorrect landmark interpretation can still mislead the whole population.
- An equipment monitoring system tracks hidden wear levels. Multinomial resampling can concentrate effort on levels supported by recent measurements. Engineers should check whether repeated copying eliminates plausible alternatives too early during noisy operating periods.
- A simulated delivery tracker maintains possible vehicle trajectories between observations. Resampling selects trajectory ancestors, then a motion model extends them. A large number of output particles does not imply an equally large number of distinct historical trajectories.
Think of it this way
Imagine a jar containing colored tickets in proportions matching three weights. Draw a ticket, record its color, return it, and repeat. Popular colors usually appear more often, but a short sequence can differ substantially from the jar's proportions. Returning each ticket is essential: the selections are made with replacement.
Worked example
Consider three particles A, B, and C, whose scalar states are 0, 4, and 10. Their normalized weights are 0.5, 0.3, and 0.2. Choose five output particles; using a different output size from the input count is allowed in this illustration.
The cumulative intervals are (0, 0.5], (0.5, 0.8], and (0.8, 1]. Five illustrative independent uniform draws, 0.05, 0.18, 0.52, 0.65, and 0.93, select A, A, B, B, and C. Output states are therefore 0, 0, 4, 4, and 10, each with weight 0.2.
The original weighted mean is 0.5 × 0 + 0.3 × 4 + 0.2 × 10 = 3.2. This particular resampled mean is 18/5 = 3.6. That difference is expected random variation, not a contradiction of unbiasedness. Over repeated resampling of this same input, the expected counts are 2.5, 1.5, and 1, giving expected mean 3.2.
The original weighted second moment is 24.8. Independent selection makes the conditional variance of the output mean (24.8 − 3.2²)/5 = 2.912. This describes resampling noise around the current weighted estimate, not the full uncertainty of the hidden state or the error relative to reality.
Illustrative case study
Fictional company Cedar Tracking tests a particle filter for moving packages on an automated sorting line. Its engineers compare multinomial resampling with stratified resampling using the same recorded observations and motion model. They repeat each experiment with several random seeds and record tracking error, processing time, and the number of surviving ancestors.
They also test ambiguous observations where premature loss of alternatives could matter. The proposed decision depends on those measurements rather than on a single visually smooth tracking demonstration. This is an invented evaluation scenario; no performance improvement or deployment result is claimed.
Common misconceptions and mistakes
Equal output weights do not establish that all output particles contain independent information: several may be exact copies. Conversely, independent parent draws should not be confused with independent offspring counts, because those counts must sum to N.
Rounding every expected count separately is not multinomial resampling and may produce the wrong total. Resampling at every possible step is not automatically beneficial; unnecessary operations add random variation and can accelerate ancestry loss. Finally, invalid or all-zero weights require investigation before sampling, rather than arbitrary normalization that conceals a failed likelihood calculation.
Business use
Treat resampling as an engineering choice within a complete tracking or inference system. Compare accuracy, runtime, stability across seeds, and recovery after unusual observations. Set acceptance criteria around the operational decision that uses the estimate, such as locating a package within a tolerance, rather than celebrating equal weights alone.
People also ask
Can a low-weight particle survive?
Yes; positive weight gives it a positive selection probability.
Can a high-weight particle disappear?
Yes, unless its weight is one; disappearance can be unlikely but possible.
Does resampling create new observations?
No. It reallocates copies of existing hypotheses.
Check your understanding
Why can the example's mean change from 3.2 to 3.6?
Answer: It is one random sample.
Why are expected counts fractional?
Answer: They average integer counts over repeated runs.
How many distinct input states survive in the example?
Answer: Three, despite five output particles.
Related terms
- Sequential Monte Carlo
- Effective sample size
- Stratified resampling
- Particle filter
- importance weight
- residual resampling
- particle impoverishment
Learn next
Compare resampling schemes on repeated identical inputs, then study adaptive resampling thresholds and valid particle rejuvenation steps.
More in Probabilistic machine learning
- Monte Carlo expectation maximization - Monte Carlo expectation maximization, or MCEM, replaces an analytically difficult expectation in the EM algorithm with an estimate obtained through simulation.
- Multimodal variational autoencoder - A multimodal variational autoencoder is a generative model that learns latent representations from more than one type of data, such as images, text, or...
- Multinomial principal component analysis - Multinomial principal component analysis is a probabilistic latent-factor model for categorical observations.
- Multivariate Student distribution - The multivariate Student distribution, usually called the multivariate Student-t distribution, is a probability distribution for a vector of continuous...
- Multiview representation learning - Multiview representation learning learns useful features by considering two or more related descriptions of the same objects, events, or observations.
- N-pairs loss - N-pairs loss is a family of training objectives and batch constructions for learning similarity-based representations.
Sources
Douc, Cappé, and Moulines, Comparison of Resampling Schemes for Particle Filtering (2005): https://arxiv.org/pdf/cs/0507025 . TensorFlow Probability, resample_independent documentation: https://www.tensorflow.org/probability/api_docs/python/tfp/experimental/mcmc/resample_independent . The arithmetic example and Cedar Tracking scenario are original illustrations. Sections 2–3 independently consulted for independent draws and conditional variance; official documentation confirms sorted-output implementation.
Previous: Multinomial probit Next: Multinomial test