- リザーバサンプリングは、データのサイズが分からないときに公平に無作為サンプルを抽出するための、独特で効率的な手法
- 従来の方法では対応できない状況を効率よく解決できるため、リアルタイムログ収集などさまざまな分野で活用される
- 核心となるアイデアは、新しい要素が現れるたびに 1/n の確率で保存領域を更新し、すべての要素に同じ選択機会を与えること
- 複数のサンプルを選ぶ場合は確率を k/n に拡張し、その確率に応じて既存サンプルをランダムに置き換える
- このアルゴリズムは少ないメモリ使用量でも公平なサンプリングを保証し、リアルタイム処理の効率性と信頼性を高める
リザーバサンプリングの概念と必要性
- リザーバサンプリングは、全体のサイズが分からないデータ集合から公平にサンプルを抽出する効率的な手法
- 一般的には、データのサイズが分かっている場合は無作為なインデックスを選ぶ方法が有効だが、サイズが分からない場合にはその方法は使えない
- 線形に到着する大量データ（例：ログストリーム）ではメモリ使用量を制限する必要があり、同時に各データが同じ確率で選ばれる必要がある
サイズが分かっている場合のサンプリング
- サイズが限られた集合（例：10枚のカード）では、すべての項目を混ぜて先頭から必要な数だけ選ぶシャッフル方式が公平性の保証に適している
- コンピュータの配列構造を使えば、直接無作為なインデックスを選んで高速にサンプルを抽出できる
- しかし実際に数百万件のデータやサイズ不明のストリームでは、この方法は非効率である
サイズが分からない場合のサンプリング：問題点と必要性
- データを1件ずつ順番に受け取りながら、1件しか保存できず、すでに過ぎたデータを取り戻せない状況は現実でよく発生する
- ログ収集システムなどでは突然トラフィックが急増することがあり、サーバ過負荷を防ぐために一部だけをサンプリングして送る必要がある
- 最初の数件だけを選ぶような任意の方法では、すべての項目に同じ機会を与えられないため、公平性が不足する問題が生じる
リザーバサンプリングアルゴリズムの原理
- 各データが入ってくるたびに、ここまでに受け取った件数 n を数え、新しいデータが 1/n の確率で選ばれるようにする
- 最初のデータは必ず選ばれ、その後の新しいデータは徐々に低い確率で既存データを置き換えることで、同一の選択確率を維持する
- 最後まで保存されるデータが全体のどの要素であっても、確率は一様になる
- コイン投げではなく 1/n の確率を使う方式によって、すべてのデータに公平な機会を保証できる
数学的な直感（カードの例を使った説明）
- 1番目のデータ：必ず選ばれる（確率は 1/1）
- 2番目のデータ：1/2 の確率で選ばれ、既存データが残る確率は 50%
- 3番目のデータ：新しいデータは 1/3 で選ばれ、既存データはその補数の確率だけ生存確率が累積する
- 一般化すると、n番目のデータまで含めたとき、すべてのデータは常に 1/n の確率を持つ
複数サンプルの選択への拡張（k-out-of-n）
- k 個のサンプルを選ぶには、新しいデータが k/n の確率で選ばれ、選ばれた場合は現在保存されている項目のうち1つをランダムに置き換える
- この方式でも、保存されるすべての項目が同じ確率でサンプルとして残る
- 一定のメモリ（k個分）だけを使いながら、大きなデータストリームからでも公平に複数サンプルを抽出できる
ログ収集サービスでのリザーバサンプリング活用
- 毎秒流入するログのうち最大 k 件（例：5件）だけをリザーバサンプリングで選び、そのサンプルだけをサーバへ送信する
- データが少ないときはすべてのログが送信されて損失がなく、トラフィック急増時でも k 件を超えて送信しないため、サービスの安定性保証が可能になる
- 一定周期でサンプルを送ることでリアルタイム性に多少の遅延はあるが、全体として安定性とコスト効率の確保に役立つ
追加の応用と参考資料
- 一部のデータ（例：エラーログ）がより重要なら、重み付きリザーバサンプリング（Weighted Reservoir Sampling）の変種を使える
- 発展的な概念は Wikipedia など外部資料にも載っているが、基本原理は公平性の維持である
結論
- リザーバサンプリングは、サイズ不明のデータストリームに対して、メモリ効率よく公平にサンプリングできる非常にエレガントで実用的なアルゴリズムである
- リアルタイムデータ処理において、迅速性、一貫性、低い資源使用量という利点から、多くの分野で活用価値が高い
1件のコメント
Hacker Newsのコメント
子どものころ田舎に住んでいたのだが、父の友人が毎年仕事として山の中の ptarmigan（ライチョウ）の個体数を調査しなければならなかった。
決められたルートに沿って一定時間ごとに鳥を驚かせて飛ばし、その数を数える方式だった。
その数値を担当部署に提出すると、部署の側で全体の個体数を推定していた。
ある年、その友人が海外にいて、別の友人に方法を詳しく説明して代役を頼んだ。
ところが実際の調査日になると、その友人はすっかり忘れてしまい、面倒だったのでそれらしく見える数値を適当に提出した。
翌年、地元新聞の1面に「ptarmigan の個体数が記録的に増加」という見出しが載った。
こうした急激な変化がニュースになったのは、その数値が狩猟許可を決める基準に使われていたからだった。友人はそこまで考えていなかったのだ。
以前、大きなスキーリゾートの予約システムの作業をしていたとき、公的な統計報告書（宿泊者延べ日数などを示して政府に提出するもの）を仕上げなければならなかった。
時間が足りず徹夜で作業する状況で、その年の統計データは実際の値と大きくずれていた。
こんにちは！ o/
この記事の作者です。質問やフィードバックを歓迎します。
すべての投稿のコードは https://github.com/samwho/visualisations で MIT ライセンスのもと提供しています。自由に使ってください。
とても良い記事だと思う。
Reservoir sampling を最適化する別の方向として、各アイテムごとに置き換えるかどうかを判定するために乱数を引く代わりに、Geometric 分布からスキップ長を引く方法がある。
Tape drive のように安価に複数項目を飛ばせる場合に興味深い（テープの長さは事前には分からないが、スキップしている間はシステムの大半をスリープ状態にしておける）。
n 個の中からサンプル k 個を取るなら、おおよそ O(k * log(n/k)) 回のサンプリングとスキップだけで済む。
それと私が気に入っている考え方に、各カードが到着したときにランダムな優先度を与え、上位 k 枚を維持するというものがある。
ここで関連する問題として、長さの分からないストリームから上位 k 個のアイテムだけを O(n) 時間、O(k) 空間で選ぶ方法がある。
サイズ 2*k の未ソートバッファに全部入れて、いっぱいになったら randomized quickselect や median-of-medians を使って上位 k 個だけを残す。
この処理を n 回さばけば O(n) 時間で済む。
さらに関連技術として rendezvous hashing も面白い。
また alias method については https://www.keithschwarz.com/darts-dice-coins/ の記事が参考になる。
この方法を入れ子にして使えるのか気になる。
たとえば、自分のサービスで reservoir sampling を行い、ログ収集サービス側でも reservoir sampling を行った場合、それはログ収集サービスだけで1回行うのと同じになるのだろうか、という質問だ。
アニメーションと説明が特に気に入った。
とくにグラフ上で100回シャッフルするなど、いろいろなインタラクションが印象的だった。
最初は10枚または436,234枚から3枚を選ぶ話をしていたのに、突然1枚ずつ見ながら1枚だけ選ぶ例に移ったので少し混乱した。
「では曲線を投げてみましょう！」のところでセクション区切りが1つ入ると、もっと理解しやすくなると思う。
ここからは1枚しか手元に持てず、デッキの大きさも分からない状況だと考えるわけだ。
サイトのデザインが特に気に入った。
インタラクション、犬のキャラクター、フォントや色使い、全体のレイアウト、どれも良かった。
ブログ全体が宝の山のように感じられる。
見つけられてうれしい。
グラフィックは気に入った。
ただ、この方法が統計的に完全に妥当なのかは確信が持てない。ある期間内のすべてのログが同じ確率で選ばれるとしても、「遅い期間」に発生したログが全体統計で過大にサンプリングされないか心配だ。
たとえば、システム全体でどのエンドポイントが最も CPU を使っているかを調べて最適化したい場合、トラフィックが一時的に急増するエンドポイントのログが過少に表現され、本当に多く使われていたエンドポイントを正しく評価できなくなるのではないか、という疑問がある。
あるいはサービスごとのキャパシティプランニングでも、バースト的なトラフィックを持つサービスが過少に表現されそうだ。
Reservoir sampling がうまく合う用途は何なのか、この方法で可能な統計分析の種類は何なのか気になる。
とても良い記事だ。数学や統計はこういうふうに教えた方が楽しく学べると思う。
https://distill.pub/ に近い雰囲気を感じた。
「Sometimes the hand of fate must be forced」という一文が印象に残った。
インタラクティブな作りが特に気に入った。
サイトデザインと教え方が本当に美しいと思う。ありがとう。
ブログに RSS フィードはあるのだろうか。
とても明快で、図解も優れた記事だ。
より高度な拡張として、基本手法の代わりに何件かまとめてスキップする量を計算するアルゴリズムもある。
詳しくは https://richardstartin.github.io/posts/reservoir-sampling が参考になる。
良い記事と解説だ。
実際のログ収集では、最後の手段として公平性（fairness）に頼る前に、さまざまな方法を試す方向を勧めたい。
たとえばログに優先度を付けて、priority が低い（verbosity が高い）ログから先に捨てる。
意味的に1つの活動を構成するログについては、中間の繰り返しログを減らし、開始・終了・主要な状態変化だけを保存する。
類似・重複ログを集計して要約として保存すれば、全体容量も減り、トレンド把握にも有利だ。
最近 observability まわりをかなり調べているのだが、挙げられている方法は head/tail sampling の混合方式だ。
https://docs.honeycomb.io/manage-data-volume/sample/ に関連する説明がある。
記事でもこの点は扱っている。
実際には、すべての low priority ログを捨てるより、「予算」の概念を適用して制限することが重要だ。
全体のログ数そのものも、別の上位予算として制限できる。
Reservoir sampling はこうした制約にもよく対応できる。
良い記事と解説だ。
Vitter の論文では「Algorithm R」が説明されており、これは reservoir sampling の方式だ。
https://www.cs.umd.edu/~samir/498/vitter.pdf を参照できる。
Vitter の以前の論文 https://dl.acm.org/doi/10.1145/358105.893 は Knuth の TAOCP 第2巻を引用しているが、Knuth のほうにも明確な出典はない。
とてもよくまとまっていて、weighted reservoir sampling に興味があるなら https://gregable.com/2007/10/reservoir-sampling.html で説明されている。
分散環境に map-reduce で簡単に適用できる方法もあるし、非常に単純なやり方として各アイテムにランダム値を対応付けて Top N を維持する方法もある。
各アイテムごとに
POW(RANDOM(), 1.0 / weight)で優先度を引き、Top N を選ぶ基本的な方法は、weight が極端に大きい・小さい場合に数値的安定性を失う問題がある。また、得られる標本が元の母集団の分布を十分に反映しないこともある。特に全体の weight が少数のアイテムに集中していると、その傾向が強くなる。
それでも、たいていの状況では十分に良い近似だ。
詳細は https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html で説明されている。
この記事を読んで、連合軍が第二次世界大戦中にドイツ戦車の生産数をシリアル番号から推定した方法を思い出した。
当時の現場要員は実際の生産量の約5倍と見積もっていたが、シリアル番号を使う方法は90%を超える精度だった。
素晴らしい投稿で、可視化も本当に優れている。
実運用ではこれに似た変種を使って、変動する percentile 値を非常に大きなストリームからリアルタイムで推定している。
percentile 値はたまに変わるものの、通常は非常に多くの反復のあいだ維持される。基になるデータは quasi-stationary だ。
splay tree で補助すると、他の方法より RAM 使用量あたりの誤差範囲は広いが、amortized O(1) 時間で推定できる。
置換確率を調整してデータの「half-life」を短くすることもでき、つまり最近のデータをより重視するように推定値へバイアスをかけることも可能だ。
データサイエンスの立場では、データ量そのものが重要な情報を持つので、サンプリング率は必ず一緒に記録すべきだと思う。
たとえばサンプリング率が10%なら、各サンプルに 10 を記録しておけば、全体のカウント、合計、平均などを正しく復元・推定できる。
この投稿は telemetry（トレース、ログ、メトリクス）収集におけるトレードオフをうまく示している。
この種のデータ分析分野は参入障壁が高く、多くの開発者が見落としがちな領域だ。
同じように見えるデータでも、どの方法でサンプリングしたかによって観測されるグラフはまったく変わり得るのに、多くの人がその点を見落としている。