ストリームデータから効率的にランダム抽出 Reservoir Samplingとは
引用元：https://news.ycombinator.com/item?id=43928315
子供の頃、田舎に住んでたんだ。親父の友達が仕事で山にいるptarmiganの数を毎年測っててね。決まったルートを歩いて、鳥を飛ばせて数えるやり方だったらしい。合計数を役所に提出すると、それが個体数推定に使われるんだ。ある年、友達が数えなきゃいけない日に海外に行っちゃって、代わりに別の友達に頼んだんだけど、その友達はやり方を忘れちゃって、適当な数を提出したんだ。そしたら次の年、地元新聞の一面トップに”ptarmiganの個体数が過去最高に増加”って出てね。なんで大ニュースになったかって言うと、この推定数が狩猟の割当量を決めるのに使われてたからなんだ。友達はそこまで考えてなかったみたい。適当な統計はマジやばいね。
統計なんて信用するな。昔、でかいスキーリゾートの予約システム作ってたんだ。納期遅れて夜中も作業してて、最後に終わらせなきゃいけなかったのが、政府が発表する宿泊者数とかの公式統計レポートだった。ぶっちゃけ、その年の統計は現実とほとんど関係なかったよ。締め切りに間に合わせるために適当に数字作ったんだ。
君は統計と予測をごっちゃにしてるね。統計は信頼できるし、そうすべきだよ。ただ、それが未来の行動とどう関連するかは、決して信頼しちゃいけないんだ。
＞ 統計は信頼できるし、そうすべきだよ。ただ、それが未来の行動とどう関連するかは、決して信頼しちゃいけないんだ。
俺が今まで会った人の99%は、統計と予測を同じ意味だと思ってるよ。特に政治的な意味合いでそう使われることが多いからね。
前の投稿者は、測定したりサンプリングしたりした統計じゃなくて、作り上げられた統計の話をしてると思うよ。そういう統計は、まあ当たり前だけど、あんまり信頼できないよね。
まあそうだね、でもこのケースではその嘘が政府の公式観光統計レポートとして発表されちゃったわけだし、そういうことが起こったのはこれが最初でも最後でもないだろうね、きっと。
とても良い投稿だね！Reservoir Samplingの別のアプローチとして、次に置き換える項目までのスキップ数を幾何分布から生成する方法があるよ。これはスキップが高速にできる場合に有効で、O(k * log (n/k))程度の処理で済むんだ。個人的には、項目にランダムな優先度を付けて上位k個を保持するバージョンが好きだな。関連する問題で、未知の長さのストリームからO(n)時間O(k)空間で上位k個を選ぶアルゴリズムもある。例えば2k容量のバッファに貯めて、一杯になったらQuickselectなどで上位k個に絞る方法だよ。関連トピックとして rendezvous hashing や alias method も面白いから見てみるといいかも。
実は、alias methodの投稿、この前読んだばっかりで、マジで感動したんだ。それについて自分でも投稿書いてみたいなって思ってる。あのリンクが言ってないことを付け加えることはできないだろうけど、もっと分かりやすくできると思うんだよね。
ウェブサイトのデザインめっちゃ好き！インタラクティブなとこも、観客としての犬キャラも、フォントとか色とかレイアウトまで全部最高だよ。記事もマジで良かった！
マジありがとう！トランプの犬たちはこの投稿のために特別にcommissionedしてもらったんだよ。全部wonderfulなandycarolan.comさんが作ってくれたんだ。色のpaletteはdavidmathlogic.com/colorblind/から学んだWong paletteなんだ。あ、そうそう、犬たちpetできるよ :)
この方法ってcomposeするの？例えばサービスとログコレクターの両方でreservoir samplingを実装した場合、ログコレクターだけが実装した場合と同じ結果になるの？
うん。
もし興味あったら、他にも協力できそうなトピックがあるよ。sorting algorithmsの視覚化や、heapのsimulate、soft heapsの実装、そしてalias methodについての記事とかね。以前読んだalias methodの記事がすごかったから、もっと分かりやすく書くのに挑戦したいと思ってるんだ。確か、分布の変更を効率的に扱う方法には触れてなかった気がするな。
これまで考えたことなかったけど、うまくいくって知れてcoolだね！
ただ、サンプリングするintervalが同じ場合だけstrictly trueだと思うな。Reservoir samplingは別の考え方もできるよ。各itemにpriorityをランダムに割り当てて、priorityが高いtop k個を残すって考えるんだ。こう考えると、アルゴリズムの組み合わせがcomposeするかどうか、top kを選べてるかで分かりやすいよ。
sorting algosを視覚化できるツール作ったよ https://xosh.org/VisualizingSorts/sorting.html 自分のalgoも追加できるから、よかったらどうぞ。
truly fairなsampleからtruly fairなsampleを得る方法って、必然的にtruly fairなsampleになるはずだと思うんだ。どう考えてもそうじゃない状況は想像できないな。
Alias tablesっていいね、あまり知られてないけど。昔、weighted distributionからsamplingするインタビューで、誰もこれを答えなかったんだ。ブログの解説は分かりやすいけど、別の説明の仕方もあってさ。bar chartにdartを投げるイメージから始めて、rectangleに収まるようにbarをchop upするんだ。greedy algorithmの証明もそんなに難しくないよ。
細かい工夫がいっぱいで、全体がすごく良くなってるね。Doe’s bandanaもクールだし、犬たちも君の面倒見の良さにきっと感謝してるよ！唯一の提案は、ログを遅くしたり＾Sで止めたりする方法かな。面白いメッセージがあっという間に流れちゃって、Reservoir Sampling使ってもちらっとしか見えなかったんだよね。「もっと絵文字が必要」ってことだね！
グラフィック最高！でもReservoir Samplingの統計的な妥当性が不明。トラフィック少ない時間のログが過多になり、バーストトラフィックは過小評価されるのでは？コスト最適化やキャパシティ計画に不適切？Reservoir Samplingの良い使い道や、データで何ができるか知りたい。
めっちゃ良い投稿！ありがとう。数学とか統計ってこうやって教えるべきだよね。Distill.pubを思い出したよ。
持ってるカードを緑、捨てたやつを赤にするのは簡単だったのにね。色覚異常の人にも優しい配色にしてくれてありがとう！私deuteranopiaだから助かるよ。
2つ目のやり方の方が、特定のケースに合わせやすそうだね。ビジネスルールでメッセージの優先度を変えれば、大事なイベントがログに残りやすくなるかも。
Doe’s bandanaは連帯と支持のつもりなんだ。気づいてくれて嬉しいよ！ログに一時停止ボタンも考えたけど、露骨すぎるし記事の内容から逸れるかなって。まあログ自体も邪魔だけどね、「reticulating splines」みたいにしたかったんだ。メッセージの作り方はここにあるよ：https：／／github．com／samwho／visualisations／blob／main／reservoir…
ちょっと前に、もっと分かりやすい実装作ってみたんだよね。これ→https://github.com/tmoertel/practice/blob/master/libraries%2…
整数のウェイトに限定したのは、アルゴリズムがちゃんと要求された分布を実装してるか検証しやすくするためなんだ。（同じディレクトリにあるテストファイル見てみて）
これ、正直良い面接問題じゃない気がするな。Alias method知ってるかだけ問われてるようなもんじゃない？
てか、ちょっと関連した質問なんだけどさ、めっちゃ長いテキストファイルがあったとして、そこからランダムに1行選ぶのってどうやる？全行が全く同じ確率で選ばれるようにね。理想は、ファイルサイズ分の前処理時間をかけずにやりたいんだけど。（これ自体が良い面接問題だとは思わないけど、面白い質問ではあるよね。）
一つの方法としては、ランダムに文字を選んでいって、たまたま改行に当たったところをその行の終わりとするってやり方かな。
その質問はもう使われてないんだよね（だから、そんなに良い質問じゃなかったって意見には反対しないよ）。Alias tables知ってることは期待されてなくて、それよりもバイナリサーチとか確率の理解があるかを見るのが目的なんだ。
君が提案してるMonte Carlo methodは、短い行が多いならいいけど、長い行が1つしかないケースだと失敗するよ。ランダムなバイトを読むコストはディスクからブロックを読むことだから、メモリ上でスキャンする方が速いだろうし。
よくできてるね、アニメーションと説明がすごく好きだな。特にグラフのやつとか、「100回シャッフル」をクリックできるところが良いね。
ちょっとだけ戸惑ったのは、最初に3枚選ぶ話から1枚だけ選ぶ話に切り替わったところかな。「今から1枚だけ選ぶ簡略化したケースの話だよ」っていう見出しがほぼ必要だった気がするんだよね。
素晴らしい記事と説明だね。
でも実践的なレベルで言うと、ログ収集にはこれが最後尾に来るかな。スパイク時には何かを捨てる必要はあるんだけど、何を捨てるかについて”公平”である必要はないと思うんだ。
公平性っていうのは、他のことを試した最後の手段として使うべきだと思うんだよね。例えば、低い優先度のログを捨てるとか、一連のログを一つのアクティビティとして扱って開始と終了だけ記録するとか、似たメッセージを集約して要約するとか。
最近、observabilityの沼にハマっててさ、君が説明してるのは多分head samplingとtail samplingのミックスだと思うよ：https://docs.honeycomb.io/manage-data-volume/sample/
もっとコメントを表示（1）
記事で触れられてたけどさ，低優先度のログを全部捨てるんじゃなくて，予算内で制限したいんだよね．あと，集めるログの総数も大元の予算で抑えたい．Reservoir samplingならそれ全部できるんだよ．
できるなら一部のエントリは捨てるかまとめるべきだけど，それでも重要なエントリが多くなりすぎて，詰まるよりはマシだからランダムに間引く必要があるんだよね．公平なReservoir samplingも，例えば内容が特に面白かったら残す確率を上げるとか，制御された形で不公平にできるよ．これは最後の手段として，もっと原則に基づかないバイアス付きのランダム（または非ランダム）選択アルゴリズムと競合するね．
この記事，すごく分かりやすくて図解もいいね！
もっと進んだ話だと，レコードごとに試すんじゃなくて，スキップするレコード数を計算するアルゴリズムもあるらしいよ．ここに良い解説があるから見てみて： https://richardstartin.github.io/posts/reservoir-sampling
これで思い出したんだけど，連合軍がGerman tanksをシリアル番号で数えたアルゴリズムについてもっと考えなきゃだ．現場の人たちは実際の5倍くらい生産されてるって見積もってたのに，シリアル番号のトリックは90%以上の精度だったらしいよ．
これはHyperLogLogがあんまり適切じゃない場所でも役に立ちそうだね．YouTubeのおすすめで数週間前にこの話のNumberphileの動画が出てきたんだ：https://youtube.com/watch?v=WLCwMRJBhuI
これの面白い帰結として，もしサンプルが1つしかなかったら，そのサンプルが中央値を示すことになるんだ．つまり，シリアル番号Nのアイテムを1つ見たら，だいたい2N個生産されたと推測できるってこと．
素晴らしい記事で，説明もいいね！
これはたぶん，最初にこれを解説したAlgorithm Rっていう論文，Vitterさんのこれだと思うな： https://www.cs.umd.edu/~samir/498/vitter.pdf
あの論文によると”Algorithm R（Alan WatermanによるReservoirアルゴリズム）”って書いてるけど、出典が載ってないんだって。
Vitterの前の論文（URLは省略）はKnuth TAOCP vol 2を出典にしてる。
Knuthには出典がないみたいだね。
KnuthもTAOCP vol 2の144ページで”Algorithm RはAlan G. Watermanによるもの”って言ってるよ。
Algorithm R（Reservoir sampling）のすぐ下だね。
WatermanがKnuthへの手紙で、Knuthの第一版の”reservoir sampling”の改良として伝えたらしい。
結局、Algorithm Rは1975年までにKnuthとWatermanに知られてて、1981年のTAOCP volume 2第二版で広まったみたいだね。
Weighted Reservoir Sampling（WRS）はReSTIR（リアルタイムレイトレーシング）で使われてるよ。
ReSTIRは確率的な光輸送推定器なんだ。
レイトレーシングは光の経路を積分するんだけど、解析的に解けないからモンテカルロ法で確率的に解くんだ。
基本的な方法から、IS, MIS, SIR, RIS, WRSのような高度な手法が開発されて、RISとWRSを組み合わせたのがReSTIRだよ。（詳細記事へのリンクは省略）
データサイエンスの視点だと、元のデータ量もすごく価値ある情報なんだ。
だから、各データポイントが元の何個分を表してるか記録しておくのが良いよ。
例えばサンプリング率が10%なら、10って値をフィールドに入れとくとか。
そうすれば、元のカウント、合計、平均みたいな統計量を再構築して推定できるからね。
すごくよくまとまってるね。
重み付きバージョンに興味があるなら、ここでちょっと説明しようとしてみたよ（リンクは省略）。
分散バージョンもあって、map reduceで簡単にできるんだ。
あるいはすごくシンプルなアルゴリズムとして、ストリームの各項目にランダムなペアを生成して、その乱数でソートして上位N個を保持する方法もあるよ。
重み付きバージョンについて2点注意があるよ。
まず、POW(RANDOM(), 1.0 / weight)でランク付けして上位N個を選ぶ素直な実装は、weightがすごく大きいか小さい場合に安定性の問題があるんだ。
次に、結果のサンプルは元の母集団と同じ期待値の分布にはならないんだ。
特に全体のweightが少数の要素に集中してる場合は顕著だよ。
でも多くの場合、そういうサンプルでも実用的な近似としては使えるんだ。（詳細はこちらのブログで：リンクは省略）
すごく分かりやすくて良い記事だね。
$WORKでは似た方法で、流れるストリームからパーセンタイルを推定する問題を解決してるよ。
データは膨大だけど準定常的なんだ。
splay treeを使うと、償却計算量O(1)でパーセンタイル推定ができるよ。
置換確率を変えて、”データ半減期”みたいに最近のデータに重みをつけることもできるんだ。
テレメトリ収集（traces, logs, metrics）におけるトレードオフもよく示してる素晴らしい記事だね。
ここはたくさんの開発者が知らないか、当たり前だと思ってるような、すごく大変な領域なんだ。
前に書こうと思ってたことなんだけど、サンプリングがグラフの線の形にどう影響するか、ってことなんだ。
同じ元のデータを違うサンプリング戦略で描画すると、結果のグラフが戦略によって全然違って見えるんだよ。
これはオブザーバビリティツールを見る時に、多くの人があまり考えてない見過ごされがちなことだと思うな。
うん、これchallengingだよね。俺はそういうtoolの仕事してるんだけど、countsをre-weightするのが一般的で正しい動きなんだけどさ、samplingをtuneするためにexact countsを探してる時とか、MoEが特定のcalculationやgranularity of dataに対してbadな時とか、それなりのsubtletiesがあるんだよね。Observabilityってcomputing分野で簡単にunderestimatedされてるの一つだよ。
Sampling theoremね。なんかみんなsampling mathematicsってmodemsとかRFにしかapplyしないと思ってんのがinterestingだよね。aliasingみたいなThingsはObservability/telemetryにはabsolutely matterするんだよ。
FWIWだけど、GNU coreutils’ shufはlarger inputsに対してreservoir samplingを使ってbounded memory operationを実現してるよ。
昔のgoogle interviewでこれが出てきたの覚えてるわ。interviewは俺がalgorithmを知らなくてfirst principlesからsolveしようとflounder aboutするのをreally expectingしてたんだよね。answerを知ってたからjust shortcut thingsできてfunだったな、あの時は。
Yeah、これ俺もgoogle interview questionだったわ。algorithm知らなくてfloundered around trying to solve the problem。1/nとk/n selection strategyはcame up withしたけどstill get the job lol。I think the guy who interviewed me was just killing time until lunch。
I like the visualizations in this article、really good explanation。
俺はそこ(google)でhiredされた後までalgorithmのこと知らなかったんだよね。It’s actually really useful in a number of contexts、but my favoriteはlexicographically sorted string keysをmappingするためのoptimal split points for shardingにusing itした時だったな。Often you will have a sorted table、but the underlying distribution of keys isn’t known、so uniform shardingはoften cause imbalances where some mappers end up doing far more work than others。I don’t know if there is a convenient open source class to do this。
Interesting idea、hadn’t that about that way to apply it。I knew it from before my interviewからa turbo pascal program I had seen that sampled dat tape backups of patient records from a hospital system。These samples were used for studies。That was a textbook example of it’s utility。
I guess the question in my mindは：would you expect a smart person who did not previously know this problem (or really much random sampling at all) to come up with the algorithm on the fly in an interview？ And if the person had seen it before and memorized the answer、does that provide any signal of their ability to code？
My gut instinctはno。I certainly don’t think I’d be able to derive this algorithm from first principles in a 60 minute whiteboarding interview、and I worked at Google for 4 years。
面接では分析的思考力を見られてたんだよ。合格するには常識的であればよかった。Reservoir Samplingを考え出せなくても、面接に落ちたわけじゃないからね！
いやいや、最初の選択とサンプル受け入れ基準を正確に理解してないと、その質問では不合格になっちゃうよ。
これで僕も面接突破したよ。最初は k/n って思いついたんだけど、今は [0, 1] の範囲で乱数生成して、k個の一番大きいやつをキープするのがいいかなって思う。
いいね！ これ Bartosz Ciechanowski の記事とほぼ同じレベルだよ - https://ciechanow.ski/
もっとコメントを表示（2）
Bartosz は僕にとって大きなインスピレーションなんだ。彼が自分の記事でやってることが、僕のでたくさん真似されてるって気づくだろうね。僕の仕事と彼のを比較してくれるのは、最高の褒め言葉かもしれない。ありがとう。
すごくクールだね - ログ収集の token-bucket rate limiting との対比を考えさせられたよ。面白い議論も見つけたんだ https://github.com/open-telemetry/opentelemetry-specificatio…
あの有名な Reservoir Sampling の4分解説だよ: https://www.youtube.com/watch?v=A1iwzSew5QY
これ、就職活動で出されるコーディングクイズの一つで知ったんだ。問題を復習してたら、これと全く同じのがあったんだよね。答えを読むまでどうやるか全然わからなかったけど、読んだら当たり前だって思ったよ。
Dropwizard Metrics とか、色々なところで使われてるよ。https://metrics.dropwizard.io/4.2.0/
Monte Hall problem にちょっと似てるなって思ったよ。条件付きの情報に基づいて確率を調整すると、直感に反する結果になることがあるんだよね。
絵も文章も素晴らしいね。本当に興味深い記事だったよ。
この記事、すごい良いね！
