Why does the low variance resampling algorithm for particle filters work?

Question

I am studying and coding particle filters and I am using the Low variance sampling algorithm suggested in the Probabilistic Robotics book. I understand the procedure for the algorithm. A random number r is picked from the interval (0, 1 / M) and a variable U, calculated based on r is used to navigate the sample space systematically. A variable c(cumulative sum) is initialized with the first weight, and incremented by adding weights until it is higher than U. Once the cumulative sum is higher than U, it picks the sample corresponding to the weight last added.

The problem that I have is that I don't see how this picks up a good sample set for the next iteration. This seems very random or at least favorable to lower valued weights. If the initial value of r is very low, U is also low initially and it may pick a sample whose weight is low, unless weight vector is sorted from high to low (Is it sorted?). However, this video suggests that particles with higher weight have a better chance of getting picked. The algorithm doesn't convey this idea to me. Please help if you have an explanation.

Answer 1

The algorithm can be understood by taking an example (using variables used in Probabilistic Robotics and algorithm in table 4.4 in page 110 in the same book).

Algorithm: (Couldn't get math mode to work inside code mode. Hence the picture.)

Consider $M = 100$

$M^{-1} = 0.01$

Let $r = 0.005$

So, $U = 0.005, 0.015,......., 0.995$ as loop progresses.

If the weight is assumed to be initialized with a value of 1/no. of particles, the first iteration of the algorithm will pick a particle, due to low value of U. Here no. of particles is 100. But in later iterations, the value of U will be larger and that would mean that by the time the value of c catches up with U, a lot of particles corresponding to lower weights will be skipped due to the inner while loop. At the same time, if c had a large increment due to large weight, it will take a while for U to catch up with c. This means the while loop will be skipped and high weight particle will be added to the output set multiple times. This is how high weight particles are picked by the algorithm. Also, the maximum value of U is 0.995, in this case. Even if r is higher, this maximum value will not exceed 1. This means, at some point, c will catch up with U resulting in selection of particles, assuming weights are normalized.

Answer 2

The algorithm does seek to favour picking samples with a greater weight.

If you think about the samples arranged in a line (actually a circle), and the length of each sample is proportional to it's weight. Then if you move along the line in small random increments and pick samples, because the higher weight samples are longer you will more often pick a higher weight sample.

Answer 3

1. What is this algorithm doing?

Imagine laying out a yardstick and partitioning it proportionally according to the individual parents’ fitnesses. For $M$ offspring particles, you want to find $M$ equally spaced points (think np.linspace) along this yardstick. The partition that the $i$’th point lies in determines the parent that gets to produce the $i$’th offspring. The $r$ in the algorithm is simply choosing a uniform-at-random starting point for your linspace, which of course needs to be in the interval $(0, \frac{1}{M})$ for you to be able to fit all $M$ of your points. This randomness ensures that the resampling is fair and also not completely deterministic.

2. Why does this strategy work?

TLDR; A particle filter’s convergence rate is inversely proportional to the variance in the parents’ offspring counts. Low variance means fast convergence.

NOTE: Below, I discuss (but never explicitly mention) the concept of variance effective population size.

The effectiveness of this resampling strategy makes a lot of sense when you consider that the particle filter is, at its core, an evolutionary algorithm (EA). All EAs tend to lose diversity because of the random sampling step, at a rate proportional to the variance in how many offspring the parents produce. This effect is known as genetic drift, and it adversely affects biological populations as well. As a result of this diversity loss, the EA prematurely converges to suboptimal solutions. This is bad news.

Intuitively, genetic drift makes sense. When parents are chosen at random (the most common setup), those with low fitness/quality are likely to get skipped and produce zero offspring and be eliminated from the gene pool, thus reducing the population’s diversity. Now, the rate at which natural selection improves a population’s fitness is directly proportional to the population’s diversity—diversity is literally the fuel that drives natural selection. Genetic drift reduces the the diversity, thus decreasing the rate at which the population’s fitness can improve and causing the aforementioned bad news.

Let’s now look at the low-variance resampling method. This method gives almost every parent exactly the number of offspring that they would be expected to get with the random sampling, without the extra uncertainty (variance). This reduces genetic drift and greatly increases the efficiency with which the particle filter can improve its solution and/or adapt to changing conditions.