リザーバサンプリング: サイズ不明のデータから公平に無作為抽出する方法
(samwho.dev)- リザーバサンプリングは、全体のサイズが分からないデータストリームでも、決められた個数だけをメモリに保持しながら、すべての項目に同じ選択機会を与える抽出手法である
- サイズが分かっている配列なら、シャッフルやランダムなインデックス選択で十分だが、一度通り過ぎた項目に戻れないストリームでは別のアプローチが必要になる
- 単一項目の選択では、n番目の項目を1/n の確率で採用し、新しい項目の選ばれる可能性と既存項目の生存可能性をバランスよく一致させる
- 複数項目を選ぶときは、保持数 k に合わせて新しい項目をk/n の確率で採用し、必要なら現在保持中の項目のうち1つをランダムに置き換える
- ログ収集に適用すると、1秒あたり最大5件といった処理上限を超えないようにしながら、静かな区間でのログ損失とメモリ使用量を同時に減らせる
サイズが分かっている集合でのサンプリング
- 10枚のカードから3枚をランダムに選ぶなら、全体をシャッフルして先頭の3枚を取るだけで、各カードに同じ選択確率を与えられる
- カードが100万枚に増えると直接シャッフルするのは難しいが、配列のようにインデックスでアクセスできる構造なら、ランダムなインデックスを3つ選べば同じ目的を達成できる
- メモリ上の配列は特定インデックスへのアクセスが容易だが、カードの山から436,234番目のカードを数えるような作業は現実的には時間がかかる
サイズ不明のストリームで生じる制約
- 一度にカードを1枚だけ見て、同時に1枚しか持てず、通り過ぎたカードに戻れないなら、全体の枚数が分からないまま最終的な1枚を選ばなければならない
- ログ収集サービスも似た形の問題に直面する
- 他のサービスからログメッセージを受け取り、1か所に保存する
- 悪いリリースやトラフィック急増でログが殺到すると、収集サービスが圧倒される可能性がある
- 例のログ収集サービスには、1秒あたり5件のログを処理できるしきい値がある
- ログの10%だけ送る方式は、急増区間ではしきい値を超えないようにできるが、静かな区間でも不要に90%のログを捨ててしまう
- 望ましい動作は、静かな区間ではすべてのログを送り、急増区間では1秒あたり最大5件だけ送る方式である
- 毎秒最初に見た5件のログだけを送ると、後から到着したログが選ばれる機会を失うため、公平ではない
単一項目のリザーバサンプリング
- リザーバサンプリングは、全体件数が分からない状態でも、これまでに見た項目の中から公平なサンプルを維持する
- すべてのメッセージをメモリに保存して後で選ぶこともできるが、スパイクの規模が分からないと必要メモリ量も予測しにくい
- この方法は、要求したサンプル数を超えるメモリを使わずに同じ問題を解決する
- 1枚のカードを選ぶ規則はシンプルである
- 1枚目のカードは常に保持する
- n枚目の新しいカードは1/n の確率で保持する
- 新しいカードを保持すると決めたら、既存の保持カードは捨てる
- 各カードごとに50%の確率で置き換えると、後ろのカードが有利になって公平ではない
- 1枚目のカードは、10枚目のカードを見た後にも残るには、何度もの置き換え機会をすべて生き残らなければならない
- 最後のカードは、一度だけ選ばれれば手元に残れる
- 1/n ルールは、新しいカードの選択確率だけでなく既存カードの生存確率も一致させる
- 1枚目のカードは 1/1、つまり100%の確率で保持される
- 2枚目のカードでは、新しいカードが 1/2 の確率で選ばれ、1枚目のカードも 1/2 の確率で残る
- 3枚目のカードでは、新しいカードが 1/3 の確率で選ばれ、既存の保持カードも 50% × 2/3 で 1/3 の確率になる
- 一般に n 番目の段階で既存カードが残る確率は
1/(n-1) * (1-(1/n))であり、新しいカードが選ばれる確率は1/nとなって一致する
複数項目を選ぶ拡張
- 単一項目の選択は複数項目の選択へ拡張できる
- k 個の項目を選ぶには、規則のうち2つが変わる
- 新しい項目は
1/nではなくk/n の確率で選ばれる - 置き換えが必要なら、現在保持中の k 個の項目から1つをランダムに選んで新しい項目に置き換える
- 新しい項目は
- 既存項目の選択確率は
k/(n-1)で表され、そこに新しい項目で置き換えられない確率を掛けることで公平性が保たれる - 保持中のすべての項目が同じ確率で置き換え対象になるため、各段階でどの項目が残り続ける可能性も等しく維持される
- 実装はサイズ k の配列を置く形で整理できる
- 新しい項目ごとに 0 から n までのランダムな数を生成する
- そのランダムな数が k より小さければ、そのインデックスの項目を新しい項目で置き換える
- そうでなければ新しい項目を捨てる
ログ収集サービスへの適用
- ログ収集の例では
k=5に設定し、一度に最大5件のログメッセージだけを保持する - 毎秒、選ばれたログをログ収集サービスへ送り、その後サイズ5の配列を空にして再開する
- この方式は、リアルタイムのログストリームではなく、一定間隔でログのまとまりを送る塊状のパターンを作る
- その代わり、送信されるログ数はしきい値を超えず、静かな区間では全体のログ数と送信ログ数がほぼ一緒に動く
- 静かな区間ではログを失わず、急増区間では1秒あたりのしきい値を超えるログを送らず、保存領域も
k=5件のログを超えない
重み付けが必要な場合
- 一部のログは他のログより価値が高いことがある
- たとえばエラーログはすべて保持したいかもしれない
- その場合は、重み付きリザーバサンプリング の変種を使える
- リザーバサンプリングは、一見不可能に思えるストリームサンプリング問題を少ないメモリで解けるようにするアルゴリズムである
1件のコメント
Hacker News のコメント
子どものころ田舎に住んでいたのですが、父の友人は仕事柄、毎年山でライチョウの個体数を数えなければならなかったそうです。
決められたルートを歩き、一定間隔ごとに鳥を驚かせて飛び立たせてから数を数え、その合計を役所に提出すると、全体の個体数推定に使われていたとのことです。
ある年、調査時期に海外へ行かなければならなくなり、友人に方法を詳しく教えて代わりを頼んだところ、その友人は当日に忘れてしまい、面倒でもあったので、それらしい数字を適当に提出したそうです。
翌年、地元紙の1面にライチョウ個体数が記録的増加という見出しが載りました。その推定値が狩猟許可数を決めるのに使われることを、その友人は考えていなかったのです。
https://en.wikipedia.org/wiki/Rock_ptarmigan
以前、かなり大きなスキーリゾート群の予約システムを作っていたのですが、スケジュールが遅れて徹夜作業をしていたとき、最後に仕上げる必要があったものの1つが、政府が発表する宿泊客数のような公式統計レポートでした。
その年の統計は現実とはほとんど関係がなかった、とだけ言っておきます。
この記事の著者です。質問があれば答えられますし、フィードバックも歓迎します。
すべての記事のコードは https://github.com/samwho/visualisations にあり、MITライセンスなので自由に使って構いません。
リザーバサンプリングをさらに面白く拡張すると、各項目ごとに乱数を引いて置き換えるかどうかと対象を決める代わりに、幾何分布から値を引いて、次の置き換えまで安全にスキップできる項目数を決めることができます。
テープドライブを早送りできるが全体の長さは分からない場合や、スキップ中にシステムの大部分を省電力状態にできる場合のように、多くの項目を低コストで飛ばせるなら特に有用です。
n個からk個を選ぶとき、この方式はおおよそ O(k * log (n/k)) 回のサンプリングとスキップを行います。
概念的には、各カードが到着したときに固定のランダムな優先度を割り当て、優先度上位k個だけを保持するリザーバサンプリングのバージョンのほうが好みです。
ここから続く問題は、長さが分からないストリームから上位k個を O(n) 時間、O(k) 空間で選ぶことです。単純に最小ヒープを維持すれば O(k) 空間にはなりますが、時間は O(n log k) かかります。
代わりに最大2k容量の順序なしバッファを用意し、項目を追加していって満杯になったら、ランダム化quickselectやmedian-of-mediansで O(k) で上位k個だけを残します。全体のn個に対してk個ごとに O(2k) の作業をするので、実行時間は O(n) になります。
関連する話題として rendezvous hashing もあります: https://en.wikipedia.org/wiki/Rendezvous_hashing
余談ですが、離散確率分布からサンプリングするエイリアス法についてのよい記事もあります: https://www.keithschwarz.com/darts-dice-coins/
ただ、最初は10枚または436,234枚のデッキからカード3枚をランダムに選ぶ話だったのに、急にカード1枚だけを選ぶ話に変わったので、少し混乱しました。
「ここからは、カード3枚ではなく1枚だけを持ち、デッキサイズも分からないという単純化した前提に切り替える」といったセクション見出しが “Now let me throw you a curveball...” の前にあると、もっと明確になりそうです。
ただ、このアプローチの統計的妥当性をきちんと理解できたかは分かりません。特定期間のすべてのログが含まれる確率が同じだということは分かりますが、それなら「遅い時間帯」に発生したログが全体の指標で過大に代表されるのではないでしょうか？
例えば、フリート全体の総コスト（CPU秒など）を減らすために、どのエンドポイントが最も時間を使っているのか知りたい場合、バースト的なトラフィックを受けるエンドポイントは、継続的なトラフィックを受けるエンドポイントより過小に代表される可能性があり、この方法は不適切に見えます。
そうすると、実際にはトラフィックが多くないエンドポイントの最適化に時間を浪費してしまうかもしれません。
サービス別のキャパシティプランニングでも、バースト的なトラフィックを受けるサービスが過小に代表されることになるのか気になります。
リザーバサンプリングはどのようなユースケースに適していて、返されたデータでどのような統計分析ができるのか知りたいです。
記事も説明も素晴らしい
実務的な観点では、それでもログ収集にこの方式を使うのは最後の手段になりそう。急増が起きれば何かは捨てなければならない、という点は理解できるが、何を捨てるべきかが核心
何を捨てるかを「公平に」決めることに大きな意味があるようには見えない
低優先度のログから捨てるほうがよく、debug/info/warning/error のようなログレベルがあるなら、深刻度の高いイベントを優先し、冗長な debug ログを先に捨てられる
また、ログのシーケンスを1つの活動の一部としてまとめ、成功した活動については開始と終了、または重要な状態変化だけを記録し、反復的な中間ログは省く方法も可能
急増時にすべてのログ行を保存するより、似たメッセージや重複したメッセージを集計・要約すれば、量も減り、傾向もより見えやすくなる
そして、収集されるログ行全体の数も、より大きな予算で制限したい。貯水池サンプリングはこれらをすべて処理できる
公平な貯水池サンプリングも、制御された形で不公平にできる。たとえば、内容が特に興味深い項目は保持確率を高められる
最後の手段としては、原則性の低い偏ったランダム選択や、ランダムですらない選択アルゴリズムと競合する手法である
本当にうまく書かれ、うまく可視化された記事
高度な拡張としては、レコードごとに試行する代わりに、スキップするレコード数を計算するアルゴリズムがある。これについての良い記事はこちら: https://richardstartin.github.io/posts/reservoir-sampling
重み付き貯水池サンプリングの変種は ReSTIR（リアルタイムレイトレーシングのための時空間貯水池再サンプリング）で使われている。これは組み込みの時空間ノイズ除去を備えた確率的な光輸送推定器である
光輸送推定器は、シーンを通過する光の量を計算しようとする（https://en.wikipedia.org/wiki/Radiance）。そのためには、エネルギー保存を保ちながら、光が取り得るすべての経路の radiance を積分する必要がある（https://en.wikipedia.org/wiki/Rendering_equation）
ごく単純な場合を除けば、レンダリング方程式におけるこの積分には扱いやすい閉形式解がないため、確率的に解く必要がある
基本的な考え方はモンテカルロ法（https://en.wikipedia.org/wiki/Monte_Carlo_method）で、可能な経路をランダムに大量にサンプリングして平均を取るというもの
その後の数十年で、重要度サンプリング（IS）、多重重要度サンプリング（MIS）、サンプル重要度リサンプリング（SIR）、リサンプリング重要度サンプリング（RIS）、重み付き貯水池サンプリング（WRS）、そして RIS と WRS を組み合わせた ReSTIR のような、より洗練された戦略が発展した
詳しい記事はこちら: https://agraphicsguynotes.com/posts/understanding_the_math_b...
これを見て、連合国がシリアル番号からドイツ戦車の数を推定したアルゴリズムについて、もっと考えてみるべきだと思った
現場での推定は実際の生産量のおよそ5倍だったが、シリアル番号を使う手法は90%以上正確だった
良い記事で、説明も素晴らしい。これは Vitter がたぶん最初に説明した Algorithm R を扱っているように見える: https://www.cs.umd.edu/~samir/498/vitter.pdf
Vitter の以前の論文 https://dl.acm.org/doi/10.1145/358105.893 は Knuth の TAOCP 第2巻を引用しており、Knuth にはさらに引用がない
データサイエンスの観点では、データ量そのものも非常に重要な情報を含むため、各データポイントがいくつを代表しているかもログに残すとよい
たとえばサンプリング比率が10%なら、10を保持するフィールドを置けば、count・sum・average など、ほとんどの統計を再構成して推定できる
構成もよく、説明もわかりやすい。重み付き版が気になるなら、ここで少し説明したことがある: https://gregable.com/2007/10/reservoir-sampling.html
MapReduceで簡単に作れる分散版もある
ごく単純なアルゴリズムとしては、ストリームの各項目ごとにランダムなペアを作り、そのランダム値を基準に上位N個を維持する方法も可能
まず、
POW(RANDOM(), 1.0 / weight)で順位付けしてから上位N個を選ぶ直感的な実装には、重みが非常に大きいまたは小さいときに数値安定性の問題がある次に、結果のサンプルは期待値ベースでも元の母集団と同じ分布にはならない。総重みが少数の母集団要素に集中するほど特にそうだが、多くの場合は使える近似である
これらの問題についてはここでさらに扱っている: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....
すばらしい記事で、取っつきやすく、可視化も優れている
$WORKではこれに似た変形を使って、実行中のストリームからあるパーセンタイルを推定する関連問題を解いている
選びたいパーセンタイルはたまに変わるが、概ね1兆回以上の反復の間は固定されており、基礎データは準定常的であるという制約がある
この過程をスプレー木で支えると、償却O(1)のパーセンタイル推定が可能になる。同じRAM使用量では他の多くの手法より誤差範囲は大きいが、非常に高速である
置換確率を調整して、時間または個数ベースの「データ半減期」を設け、直近のイベント寄りに推定を偏らせることもでき、このほうが適している問題もある