1

Weighted Reservoir Sampling を実装する必要があります。このブログで言及されている論文を参照しました。実装を単体テストするためのテストケースを書きたいのですが、貯水池にあるさまざまな要素の期待確率を計算する方法について混乱しています。

に比例するはずだと思っていましたが、ここで(weight_of_element/weight_of_all_elements)言及されているテストケースでは計算が異なります。どうすればいいですか？

4

1 に答える 1

0

テストケースを書くために、要素が選択される確率を実際に見積もることができます。次のような重みを割り当てたとします:
weights = [1, 5, 8, 2, 5]

ここで、 1 つの要素を描画するために加重リザーバー サンプリングを実行しています。結果に要素が現れる確率は? それらは正確に(weight_of_element/weight_of_all_elements):
prob = [0.048, 0.238, 0.381, 0.095, 0.238]

つまり、1 つの要素を 10 6回繰り返し描画すると、3 番目の要素のインスタンスは 0.381 * 10 6 回、最初の要素のインスタンスは0.048 * 10 6回、というようになります。もちろん、およそ。

したがって、10 6回の試行のうち最初の要素が出現した回数の割合を見ることができます。これはおよそ でなければなりません(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. 結果は決定論的であるため、手動で取得できます(小さな入力の場合)。期待される結果をテストに組み込みます。

シード値を制御できない場合、この方法は適していません。

于 2015-09-22T08:43:28.020 に答える