machine-learning - 加权储层采样测试用例

Question

我需要实现加权水库采样。我引用了这篇blog中提到的论文。我想编写测试用例来对我的实现进行单元测试，但对如何计算储层中不同元素的预期概率感到困惑。

我认为它应该与(weight_of_element/weight_of_all_elements)成比例，但测试用例提到 here计算方式不同。我该怎么做？

Answer 1

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

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

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

因此，您可以查看第一个元素在 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

参见this Java中的线程具体实现。

对于Cloudera test你已经指出，它遵循不同的逻辑(我也在Python包numpy测试numpy.random.choice中看到了这一点):

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

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