- CVMアルゴリズムは、長いデータストリームにおける異なる項目数を近似し、リスト全体を保存しなくても固有項目数を推定する
- 入力全体がメモリを超える**固有項目問題（distinct elements problem）**に焦点を当てており、重複入力の多い大規模ログやイベントストリームに適用できる
- 限られたメモリに一部の項目だけを残し、容量がいっぱいになるたびにランダム削除を繰り返すことで、各項目が残る確率を均等にする
- Hamlet の例では、100語分のメモリで5回の平均として3,955個を推定し、実際の固有単語数3,967個に近かった。1,000語分のメモリでは平均3,964個に改善した
- メモリが大きいほど精度は高まり、すべての固有項目を収められるほど十分であれば100%の精度も可能
長いデータストリームで固有項目を数える
- 目的は、項目が1つずつ入ってくる長いリストから、重複を除いた固有項目数を効率的に推定すること
- 最も単純な方法は、これまで見たすべての項目を保存し、新しい項目が入るたびに既存リストと比較すること
- 野生動物調査では、すでに見た動物写真のリストを確認し続ける必要がある
- Facebookの日次ログインユーザー数のように、リストが数十億規模になると保存と比較が難しくなる
- CVMは、Sourav Chakraborty、Vinodchandran Variyam、Kuldeep Meelの名前に由来するアルゴリズム
- 単語、ベルトコンベア上の商品、高速道路の車両のように、項目が順番に入ってくるリストに適用できる
CVMアルゴリズムの中核アイデア
- CVMはすべての項目を保存せず、限られたメモリに入る一部の項目だけを保持する
- 各固有項目が最終リストに残る確率を制御するためにランダム性を使う
- Andrew McGregorは、このアルゴリズムは非常に単純で実装しやすいため、実際の固有項目問題における基本的なアプローチにもなり得ると見ている
Hamletの例で見る動作の仕組み
- Hamlet には合計30,557語があり、アルゴリズムはそのうち固有単語数を推定する
- メモリが100語分のホワイトボードだと仮定すると、最初は繰り返し出てくる単語を飛ばしながら、最初の100個の固有単語を書き留める
- 空きがなくなると、各単語ごとにコインを投げる
- 表なら単語を保持する
- 裏なら単語を削除する
- この予備段階の後には、約50個の固有単語が残る
ラウンドが進むほど厳しくなる保持条件
- Round 1では新しい単語を追加し続け、すでにリストにある単語が再び出てきたらコインを投げ、裏なら削除する
- リストが再び100語でいっぱいになると、100回のコイントス結果に応じて約半分を削除し、Round 1が終わる
- Round 2からは、単語が生き残るのがより難しくなる
- 繰り返し単語が出てきたら、裏なら削除する
- 表が出たらもう一度コインを投げ、2回目も表のときだけ保持する
- 第3ラウンドでは表が連続3回必要で、第4ラウンドでは連続4回必要になる
- 一般に、k番目のラウンドが終わるとき、各単語が残っている確率は1/2^kになる
推定値の計算と実験結果
- 最終リストに残った単語数を、残っている確率で割ると、全体の固有単語数を推定できる
- たとえば6ラウンド後に61語が残っていれば、確率1/2^6で割って3,904個という推定値を得る
- Hamlet の実際の固有単語数は3,967個
- メモリサイズが大きいほど、推定値は実際の値に近づく
- 100語分のメモリで5回実行した平均推定値は3,955個
- 1,000語分のメモリでは平均推定値が3,964個
- Variyamらは、この手法の精度がメモリサイズに応じてスケールすることを数学的に証明した
単純だが非自明な解決策
- CVMは、40年以上研究されてきた固有項目問題における重要な進展と評価されている
- William Kuszmaulは、非常に基本的でよく研究された問題にも、単純だが簡単には思いつきにくい解法が残っている可能性があると見ている
1件のコメント
Hacker Newsのコメント
このアルゴリズムの DNF の体積カウント版の実装に、著者たちと一緒に参加した。関連記事はこちら: https://www.msoos.org/2023/09/pepin-our-probabilistic-approx...
コードはこちら: https://github.com/meelgroup/pepin
ときには全体時間の30%がファイル読み込みI/Oに費やされるほど、このアルゴリズムはばかげて速い。ちなみに Knuth もアルゴリズムに貢献しており、彼のノートはこちら: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
TAOCP の作業から丸1か月を割いてこれをやっていて、想像どおり信じがたいほど優秀だった
このアルゴリズムは、論文でも引用されている HyperLogLog に似て見える。表/裏が連続して出るかどうかを追跡して推定値を得るという同じ洞察を使いつつ、そのアイデアを反転させ、記憶している値をコインの結果の連続性に応じて捨てる、より単純なアルゴリズムにした感じだ
ストリーミング状況で特に効率よく動作し、誤差率はあるものの、異なる要素数を数える「カウンター」のようなものを維持できる
HyperLogLog の利点は、ある意味でハッシュ集合のように振る舞うことだ。項目を追加し、異なる項目数を数え、重要なことに2つの HLL をマージして和集合を作れる。それでいて、数十億項目の集合でもメモリは数KBに固定される。分散データストアでは Elasticsearch/OpenSearch の cardinality agg、Redis/Redict の PFADD/PFMERGE/PFCOUNT がこのテクニックを使っている
CVM アルゴリズムが HLL と正確にどう比較されるのかはよく分からないが、Knuth のレビューを受けていて、学部生でも簡単に実装できるというのだから、かなり良いアルゴリズムなのだと思う
http://oertl.github.io/hyperloglog-sketch-estimation-paper/
以前の職場でまさにこのアルゴリズムを実装したが、各値の横に、その値が出現した回数の推定値も一緒に保存していた。おかげで、最も頻繁に出る値のおおよそのリストと、各値の推定カウントを作れた
以前病院で働いていたとき、DAT テープに保存されたレコードの小さな部分集合を作るために reservoir sampling を使ったことがある
論文を読むのに、ブログ記事を読むのとほぼ同じくらいの時間しかかからず、論文のほうが有益だった
https://arxiv.org/pdf/2301.10191
ストリームから現れた要素集合のカーディナリティを推定する内容。アルゴリズムがあまりに単純なので、論文を読みながら自分でコーディングして遊べる
著者らは、このアルゴリズムの想定読者と目的が学部生と教科書だと明確に述べている
Knuth が自ら査読したのだから、このアルゴリズムはそういう種類のものだと評したのかもしれない。だとすれば、著者らがそれをタイトルに入れたのは謙虚ではない自慢に見えるが、十分に自慢に値する
もともとはこの表現を Knuth のものだと記憶していたが、自分の記憶違いだった
https://en.wikipedia.org/wiki/Up_tack を説明するより、単にループを書くほうが面倒が少なそうに見える。[1]
[1] https://news.ycombinator.com/item?id=40388878
まず contradiction の扱いが、単にエラーやパニックのようなのに、なぜそう表現したのか分からない。それに 1..m という前提が分かりにくい。サイズを事前に知っている必要があるのかどうか確信が持てなかったが、さらに見るとそうではなさそうだ。しきい値を選び、ストリームサイズに応じて確率が変わるのに、アルゴリズムの説明は単一の出力を持つかのようになっていて混乱する
Chernoff 境界と delta/epsilon も論文ではまったく説明されておらず、さらに混乱した。Go で実装してみたコードはこちら: https://github.com/betamos/distinct
しきい値まわりを helper に切り出すほうが、誤ってメモリを割り当てすぎるよりずっと筋が通る。信頼度や誤差率を推定するメソッドもあるべきだと思う。ストリームサイズを事前に知っている人はいないので、進行中にこの値を更新するほうが自然だ
論文のテーマを考えると、脚注が特に魅力的だ
著者らは、昔からの著者名アルファベット順の慣例ではなくランダムな順序を選び、r⃝ で表示したとのこと。ランダム化の公開検証可能な記録はこちら: https://www.aeaweb.org/journals/policies/random-author-order...
[0]: https://arxiv.org/pdf/2301.10191
アルゴリズムの説明が間違っているように思わないか？
「リストにすでにある単語に遭遇したらもう一度コインを投げ、裏ならその単語を消す」という説明どおりに「リストにあるか確認してから削除」を実装すると、約20回繰り返され、推定値が 772800512 のようなとんでもないものになる
逆に、単語を先に保存してから同じ単語を削除すると、実際のユニーク単語数 7233 に近い 7240 が出る。つまり説明上は順序が重要なのに、誤って伝わっているようだ
論文を読んだ後は正しい推定値が出るようになり、問題は小さなelse 一つだった。Quanta の説明は「リストになければ追加し、そうでなければ確率に応じて削除する」と読めるが、正しい実装では、追加したかどうかに関係なく、その後で確率条件を適用しなければならない
集合のユニーク要素数を推定することと、集合のユニーク要素数を数えることはまったく別物だ。素晴らしい方法だが、タイトルはいまいちだ
たとえば選挙で「票を数える」と言うが、接戦なら「再集計」を行い、元のカウントとわずかに異なる数字が出ることは十分に予想される。ならば票数えも実際には票の推定であり、再集計はより狭い誤差境界を持つ推定にすぎない
「countless stones」の神話（https://en.wikipedia.org/wiki/Countless_stones）も、どれほど大きく硬く静的な立石のようなものでさえ、正しく数えたと過信はできないという民間的な注意喚起のように感じる
数えることが推定ではない場合は、数学的な状況くらいに限られる。すべての項目を漏れなく扱い、ある項目の同一性を別のものと混同していないと保証できる場合だ
たとえばモルは整数だが、その値は近似的にしか知られておらず、正確な値を気にする人もいない
こういう 枠の外で考える 例が本当に好きです。仕事上でも自分があまり得意でない部分なので、なおさらです。問題を解く正しい方法を学ぶだけでなく、抱えている問題をより簡単に、時には解けるものにしてくれる問いを見つけ出す過程が重要です
ここでは「正確な数は必要なく、定義されたパラメータの範囲内で確率的な範囲を定めればよい」という問いが核心です。別の問題には別の問いがあるはずです。こうした例を十分に見れば、その思考過程を内面化して適切に適用できるようになることを願っています
大企業で、同じくらい優秀なエンジニアたちと一日中ホワイトボードの前に座っていることに対して給料をもらえるなら、世間の人には「枠の外の解法」に見えるものをきっと生み出せるでしょう
しかし私たちの大半は JIRA の工場ラインで働くことに対して給料をもらっているので、ひとつの問題だけに取り組んで実験する時間は限られています
「Facebook で毎日ログインする異なるユーザー数を数えたい。しかも一部のユーザーは複数のデバイスや複数の時点でログインする場合は？」という例は、このアルゴリズムが実際に役立つ状況としてはあまり適切ではない気がします
ログインプロセスを設計する時点でこの情報が必要だと分かっているなら簡単です。各アカウントの最終ログイン日を保存し、保存されている値が現在の日付と異なる場合にだけユニークユーザーのカウンターを増やせばよいです
たとえそうでなくても、後からデータベース上のログインイベントストリームを「再生」して分析できるでしょう。すでに数年分のデータが蓄積されている場合は別かもしれません
カウントに関連して、ストリームから 上位 k 個の項目 を見つける、効率的で実装も簡単なアルゴリズムに触れておきたいです。思ったより知られていないようです
A Simple Algorithm for Finding Frequent Elements in Streams and Bags
Karp, Shenker & Papadimitriou
https://www.cs.umd.edu/~samir/498/karp.pdf
あなたの説明は、固定された k 個の項目を見つけ、それらが必ず最上位であることを保証するように聞こえます。要旨は、特定の値 k より大きいという条件を満たす、事前には個数が分からない項目を見つけるように聞こえます
「最年長のユーザー 100 人を見つける」と「30 歳を超えるすべてのユーザーを見つける」の違いのように見えるのですが、私があなたの話か要旨を誤解しているのでしょうか？ 英語が母語ではないので混乱しています
コンピュータ科学者たちが、部分集合のサイズをメモリ効率よく 推定 する方法を発明したのですね