加权储层采样的测试用例

Question

我需要实现加权储层采样。我已经参考了本博客中提到的论文。我想为我的实现编写单元测试用例，并且对如何计算不同元素在储层中的预期概率感到困惑。

我认为它应该对(weight_of_element/weight_of_all_elements)具有预见性，但这里提到的测试用例以不同的方式计算它。我应该怎么做？

Answer 1

为了编写测试用例，您确实可以估计选择元素的概率。假设您分配了如下权重：
权重 = [1， 5， 8， 2， 5]

现在，您正在执行加权储层采样以绘制一个元素。元素出现在结果中的概率是多少？它们完全(weight_of_element/weight_of_all_elements)：
prob = [0.048， 0.238， 0.381， 0.095， 0.238]

换句话说，如果重复绘制一个元素 10⁶ 次，则应该有第三个元素的 0.381 * 10 6 个实例，第一个元素的 0.048 * 10⁶ 个实例，依此类推。当然，大约是。

因此，您可以查看第一个元素在 10⁶ 次试验中出现的次数百分比。这必须是大约 (weight_of_first_element/weight_of_all_elements) .比较这些值，看看它们是否彼此接近。

所以测试用例可能看起来像这样（伪代码）：

numTrials = 1000000
histogram = map<int, int>
for i = 1..numTrials:
  element = WeightedReservoir.sample(weights, 1) # draw one element
  histogram[element]++
for i = 1..len(weights):
  real_probability = weights[i] / sum(weights)
  observed_probability = histogram[elements[i]] / numTrials
  assert(abs(real_probability - observed_probability) <= epsilon) # measuring absolute difference, but you can switch to relative difference

有关 Java 中的特定实现，请参阅此线程。

至于你指出的Cloudera测试，它遵循不同的逻辑（我也在numpy.random.choice的Python包numpy测试中看到了这一点）：

1. 采样例程本质上是概率性的，即非确定性的;
2. 让我们为随机数生成取一个固定的种子值。将此值嵌入到测试用例中。现在它是完全确定性的：多次调用测试用例会产生相同的结果;
3. 由于结果是确定性的，我们可以手动获取它（对于小输入）。将预期结果嵌入到测试中。

如果无法控制种子值，则此方法不适合您。