1

このMSDNの記事は、 ReservoirSamplingアルゴリズムの正しさを次

  1. 基本ケースは簡単です。k + 1番目のケースでは、位置<=kの特定の要素iがRにある確率はs/kです。

  2. iが置き換えられる確率は、k + 1番目の要素が選択される確率にiが置き換えられるように選択されることを掛けたものです。つまり、s /（k + 1）* 1 / s = 1 /（k + 1）であり、i置き換えられないのはk/k+1です。

  3. したがって、k + 1ラウンド後に続く任意の要素の確率は次のとおりです。（kステップで選択され、kステップで削除されない）= s / k * k /（k + 1）、つまりs /（k + 1）。

  4. したがって、k + 1 = nの場合、任意の要素が確率s/nで存在します。

ステップ3について：

  • 何がk+1 rounds言及されていますか？

  • 何chosen in k steps, and not removed in k stepsですか？

  • R最初のsステップの後にすでに含まれている要素についてのみこの確率を計算するのはなぜですか？

4

3 に答える 3

1

帰納法による証明はご存知ですか？ はアルゴリズムの中間ステップにすぎず、不変条件がずっとk真であることを証明していk-thます。s/kk

于 2010-04-12T13:51:23.780 に答える
0

k 個のアイテムのストリームから s 個のアイテムをサンプリングしています (k は非常に大きいため、アイテムごとにストリームを処理します)。

ストリームからの各アイテムの処理は「ラウンド」と呼ばれます。

ラウンド中に、すでに存在する要素の 1 つを新しいアイテムに置き換える場合があります。

「k ステップで選択」とは、アイテムがストリームに表示されたラウンド中に、他のアイテムをそれで置き換えることを選択したことを意味します (無視しませんでした)。「k ステップで削除されていません」とは、その瞬間から、このアイテムをストリームの新しいアイテムに置き換えることを選択していないことを意味します。

于 2010-04-11T10:57:16.860 に答える
0
  • 「k+1 ラウンド」は、「入力シーケンスの (k+1) 番目の項目が考慮された後」を意味します。
  • s/k は、与えられたアイテムが (帰納法により) k ステップ後にリザーバーにある確率です。k/(k+1) は、アイテムが (k+1) 番目に置き換えられない確率です。ステップ
  • すべての入力アイテムが同じ確率でリザーバーに残るようにしたいと考えています。そのため、計算では、各ステップでリザーバーに残っているアイテムのみに関心があります。
于 2010-04-11T11:01:58.367 に答える