Initialization of Weighted Reservoir Sampling (A-Chao implementation)

user_9634568 0
Viewed 380

I am trying to implement A-Chao version of weighted reservoir sampling as shown in https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Chao

But I found that the pseudo-code described in wiki seems to be wrong, especially on the initialization part. I read the paper, it mentions we need to handle over-weighted data points, but I still cannot get the idea how to initialize correctly.

In my understanding, on initialization step, we want to make sure all initial data points chosen should have same probability*weight to be chosen. However, I don't understand how the over-weighted points is related with that.

Code I implemented according to the wiki, but the results show it is incorrect.

const reservoirSampling = <T>(dataList: T[], k: number, getWeight: (point: T) => number): T[] => {
  const sampledList = dataList.slice(0, k);
  let currentWeightSum: number = sampledList.reduce((sum, item) => sum + getWeight(item), 0);
  for (let i = k; i < dataList.length; i++) {
    const currentItem = dataList[i];
    currentWeightSum += getWeight(currentItem);
    const probOfChoosingCurrentItem = getWeight(currentItem) / currentWeightSum;
    const rand = Math.random();
    if (rand <= probOfChoosingCurrentItem) {
      sampledList[getRandomInt(0, k - 1)] = currentItem;
    }
  }
  return sampledList;
};
reservoir-sampling sampling algorithm
1 Answers

The best way to get the distribution that Chao's algorithm produces is to implement VarOptk sampling as in the pseudocode labeled Algorithm 1 from the paper that introduced VarOptk sampling by Cohen et al.

That's an arXiv link and hence very stable, but to summarize, the idea is to separate the items into "heavy" (weight high enough to guarantee inclusion in the sample so far) and "light" (the others). Keep the heavy items in a priority queue where it is easy to remove the lightest of them. When a new item comes in, we have to determine whether it is heavy or light, and which heavy items became light (if any). Then there's a sampling procedure for dropping an item that treats the heavy → light items specially using weighted sampling and then falls back to choosing a uniform random light item (as in the easy case of Chao's algorithm).

The one trick with the pseudocode is that, if you use floating-point arithmetic, you have to be a little careful about "impossible" cases. Post your finished code on Code Review and ping me here if you would like feedback.

user_21446690
Related