論文翻訳: Weighted Random Sampling (2005; Efraimidis, Spirakis)

Table of Contents

1. 1 問題定義
2. 2 主要な結果
3. 3 アプリケーション
4. 4 未解決問題
5. 5 実験結果
6. 6 データセット
7. 7 コードの URL
8. 8 クロスリファレンス
9. 9 推奨文献
10. 翻訳抄

1 問題定義

非復元ランダムサンプリング (RS; random sampling without replacement) 問題はサイズ \(n\) の母集合から \(m\) 個の異なるアイテムをランダムに選択することである。1 パスでの一様ランダムサンプリングについては [1, 5, 10] で論議されている。データストリーム上のリザーバー (reservoir) 型一様サンプリングアルゴリズムは [11] で論議されている。並列一様サンプリングアルゴリズムは [9] で与えられる。重み付きランダムサンプリング (WRS; weighted random sampling) ではアイテムが重み付けされており、選択されるそれぞれのアイテムの確率は相対的な重みによって決定される。WRS は以下のアルゴリズム D で定義できる:

アルゴリズム D, WRS の定義

入力: \(n\) 個の重み付けされたアイテムの母集合 \(V\)
出力: サイズ \(m\) の WRS を持つ集合 \(S\)
For \(k=1\) to \(m\) do
　　ラウンド \(k\) でアイテム \(v_i\) が選択される確率を \(p_i(k)=w_i / \sum_{S_j \in V - S} w_j\) とする
　　アイテム \(v_i \in V - S\) をランダムに選択し \(S\) に追加する
End-For

問題 1 (WRS).
入力: \(n\) 個の重み付けされたアイテムの母集合 \(V\)
出力: サイズ \(m\) の WRS を持つ集合 \(S\)

WRS の最も重要なアルゴリズムは、Alias Method, Partial Sum Tree と Acceptance/Rejection Method である (WRS アルゴリズムの概要については [8] を参照)。これらのアルゴリズムはいずれも 1 パス WRS には適していない。この研究では WRS に対するアルゴリズムが提示されている。アルゴリズムは単純で、非常に柔軟性があり、データストリーム上で WRS 問題を解決する。エントリー著者の知る限りこれがデータストリーム上の WRS に対する最初のアルゴリズムであり、並列または分散環境下での WRS のためのアルゴリズムである。

定義: 1 パス WRS は母集団上を 1 回の走査で重み付きランダムサンプリングを生成する問題である。さらに、母集団のサイズが開始時点で未知の場合 (例えばデータストリーム)、ランダムサンプリングは Reservoir サンプリングアルゴリズムを用いて生成することができる。これらのアルゴリズムは補助的な保存域であるリザーバー (reservoir) を使用する。

表記と仮定: アイテムの重みは初期では未知であり、厳密に正の実数である。母集団のサイズを \(n\)、ランダムサンプルのサイズを \(m\)、アイテム \(v_i\) の重みを \(w_i\) とする。関数 \({\it random}(L,H)\) は \((L,H)\) の一様乱数を生成する。\(X\) は乱数を表している。無限精度の演算を仮定する。特に指定がない限り、全てのサンプリング問題は Replacement なしである。文脈に応じて WRS は重みづけられてランダムに採取された標本、または重み付けランダムサンプリングの操作を表す。

2 主要な結果

この研究の WRS アプローチの要点は次のアルゴリズム A で与えられる:

アルゴリズム A
入力: \(n\) 個の重み付けされたアイテムの母集合 \(V\)
出力: サイズ \(m\) の WRS
1: 全ての \(v_i \in V\) に対して \(u_i = {\it random}(0,1)\)、\(k_i = v_i^{(1/w_i)}\) とする
2: 最も大きいキー \(k_i\) を持つ \(m\) 個のアイテムを WRS として選択する

定理 1. アルゴリズム A は WRS を生成する

リザーバーアルゴリズム A (A-Res)
入力: \(n\) 個の重み付けされたアイテムの母集合 \(V\)
出力: サイズ \(m\) の WRS を持つリザーバー \(R\)
1: \(V\) の最初の \(m\) 個のアイテムを \(R\) に追加する
2: \(v_i \in R\) の全てのアイテムに対して: キー \(k_i=u_i^{(1/w_i)}\) を計算する, ここで \(u_i={\it random}(0,1)\) とする
3: \(i=m+1,m+2,\ldots,n\) に対して 4-7 ステップを繰り返す
4: 　　\(R\) 内の最も小さなキーが現在のしきい値 \(T\) である
5: 　　アイテム \(v_i\) に対して: キー \(k_i=u_i^{(1/w_i)}\) を計算する, ここで \(u_i={\it random}(0,1)\) とする
6: 　　もしキー \(k_i\) が \(T\) より大きい場合:
7: 　　　　\(R\) における最小のキーのアイテムは \(u_i\) と置き換えられる

アルゴリズム A-Res はアルゴリズム A で必要とされる計算を実行し、したがって A-Res は定理 1 に基づいて WRS を生成する。アルゴリズム A-Res のためのリザーバー操作の回数は次の命題のよって与えられる。

定理 2 . 重み \(w_i \gt 0\) が同一の連続分布を持つ独立したランダム変数であるような、\(n\) 個の重み付けされたアイテムに適用された場合、リザーバー挿入の期待数 (初期の \(m\) 個の挿入は含まない) は: \[ \sum_{i=m+1}^n P\left[ \mbox{item $i$ is inserted into $S$} \right] = \sum_{i=m+1}^n \frac{m}{i} = O \left( m \cdot \log \left( \frac{n}{m} \right) \right) \]

\(S_w\) を、新しいアイテムがリザーバーに入るまで A-Res にスキップされるアイテムの重みの合計とする。\(T_w\) はリザーバーに入るための現在のしきい値とすると、\(S_w\) は指数分布に従う連続ランダム変数である。各アイテムのキーを生成する代わりに合計 \(S_w\) に対応するランダムジャンプを生成することが可能である。同様の技術が一様ランダムサンプリングに適用されている (例えば [3] を参照)。以下のアルゴリズム A-ExpJ はアルゴリズム A の指数ジャンプ (exponential jump) タイプの適応である:

指数ジャンプアルゴリズム A (A-ExpJ)
入力: \(n\) 個の重み付けされたアイテムの母集合 \(V\)
出力: サイズ \(m\) の WRS を持つリザーバー \(R\)
1: \(V\) の最初の \(m\) 個のアイテムを \(R\) に追加する
2: \(v_i \in R\) の全てのアイテムに対して: キー \(k_i=u_i^{(1/w_i)}\) を計算する, ここで \(u_i={\it random}(0,1)\) とする
3: しきい値 \(T_w\) は \(R\) の最小キーである
4: 母集団が尽きるまで 5-10 ステップを繰り返す
5: 　　\(r={\it random}(0,1)\), \(X_w=\log(r)/\log(T_w)\) とする
6: 　　現在のアイテム \(v_c\) から次のような \(v_i\) までのアイテムをスキップする:
7: 　　\(w_c+w_{c+1}+\ldots+w_{i-1} \lt X_w \le w_c+w_{c+1}+\ldots+w_{i-1}+w_i\)
8: 　　最小のキーを持つ \(R\) 内のアイテムはアイテム \(v_i\) に置き換えられる
9: 　　\(t_w=T_w^{w_i}\), \(r_2={\it random}(t_w,1)\) そして \(v_i\) のキーを \(k_i=r_2^{(1/w_i)}\) とする
10:　　新しいしきい値 \(T_w\) は \(R\) の新しい最小値である

定理 3 . アルゴリズム A-ExpJ は WRS を生成する。

A-ExpJ の指数ジャンプ数は命題 2 によって与えられる。したがって、アルゴリズム A-ExpJ は、生成する必要のあるランダム変数の数を \(O(n)\) (A-Res に対して) から \(O(m \log(n/m))\) に削減する。高品質なランダム変数の生成はコストの掛かる操作であるため、これはサンプリングアルゴリズムの複雑さを大幅に改善する。

3 アプリケーション

ランダムサンプリングはデータベース ([4, 8] とその中の参考文献を参照)、データマイニング、近似アルゴリズム、およびランダム化アルゴリズム [6] を含む多くの分野で応用されているコンピュータサイエンスの基礎的な問題である。したがって WRS に対するアルゴリズム A はランダム化アルゴリズムの設計に応用を見出すことのできる一般的なツールである。例えば、アルゴリズム A は \(k\) 平均法の近似アルゴリズムで使用することができる [6]。

アルゴリズム A に対するリザーバーに基づくバージョンである A-Res および A-ExpJ は補助記憶領域に対する要件が非常に小さく (ヒープとして編成された \(m\) 個の鍵)、サンプリング処理の間、それらのリザーバーにはその時点までに処理されたデータの中から有効な重み付きランダムサンプルが継続的に含まれている。これにより、このアルゴリズムはデータストリーム処理アルゴリズムの新興分野に適用可能となる ([2, 7])。

アルゴリズム A-Res と A-ExpJ はデータストリームに対する重み付き復元ランダムサンプリングに使用することができる。特に、A-Res または A-ExpJ をそれぞれ \(k\) インスタンスで同時に実行することにより、サイズ \(k\) の重み付き復元ランダムサンプルを生成することが可能である。各アルゴリズムインスタンスはサイズ 1 の単純なリザーバーで実行すると、最終的に全てのリザーバーの和集合は復元 WRS である。

4 未解決問題

何も報告されていない。

5 実験結果

何も報告されていない。

6 データセット

何も報告されていない。

7 コードの URL

この研究で提示されたアルゴリズムは実装が単純である。Java での実験的な実装は: http://utopia.duth.gr/˜pefraimi/projects/WRS/index.html

8 クロスリファレンス

何も報告されていない。エントリエディタは自由に追加してください。

9 推奨文献

1. J. H. Ahrens and U. Dieter, Sequential random sampling, ACM Trans. Math. Softw., 11 (1985), pp. 157–169.
2. B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom, Models and issues in data stream systems, in Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, ACM Press, 2002, pp. 1–16.
3. L. Devroye, Non-uniform Random Variate Generation, Springer Verlag, New York, 1986.
4. C. Jermaine, A. Pol, and S. Arumugam, Online maintenance of very large random samples, in SIGMOD ’04: Proceedings of the 2004 ACM SIGMOD international conference on Management of data, New York, NY, USA, 2004, ACM Press, pp. 299–310.
5. D. Knuth, The Art of Computer Programming, vol. 2 : Seminumerical Algorithms, AddisonWesley Publishing Company, second ed., 1981.
6. J.-H. Lin and J. Vitter, \(\epsilon\)-approximations with minimum packing constraint violation, in 24th ACM STOC, 1992, pp. 771–782.
7. S. Muthukrishnan, Data streams: Algorithms and applications, Foundations & Trends in Theoretical Computer Science, 1 (2005).
8. F. Olken, Random Sampling from Databases, PhD thesis, Department of Computer Science, University of California at Berkeley, 1993.
9. V. Rajan, R. Ghosh, and P. Gupta, An efficient parallel algorithm for random sampling, Information Processing Letters, 30 (1989), pp. 265–268.
10. J. Vitter, Faster methods for random sampling, Communications of the ACM, 27 (1984), pp. 703–718.
11. ──────, Random sampling with a reservoir, ACM Trans. Math. Softw., 11 (1985), pp. 37–57.

翻訳抄

重み付きランダムサンプリング (乱択) のアルゴリズムに関する 2005 年の論文。重み付き非復元ランダムサンプリング (weighted random sampling without replacement) に基づいて、開始時点でサイズが未知の母集団から 1 パスでサイズ \(m\) の部分集合を生成することができる。

1. Efraimidis P, Spirakis P. Weighted Random Sampling In: Kao MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY