画期的な CVM アルゴリズムが 40 年以上の計数の問題を解決します。コンピューター科学者がコインを投げて「ハムレット」を表す固有の単語を割り出す

数を数えるのは簡単そうに聞こえますが、実際に実行するのは非常に困難です。

野生動物の国勢調査を実施するために、手付かずの熱帯雨林に派遣されたと想像してください。動物を見かけたら必ず写真を撮りましょう。

デジタルカメラは追跡された動物の総数のみを記録しますが、固有の動物の数に興味がありますが、統計はありません。

では、このユニークな動物を手に入れる最良の方法は何でしょうか?

この時点で、あなたは間違いなく、「今から数え始めて、最後に各新種を写真とリストで比較してください」と言うでしょう。

ただし、この一般的なカウント方法は、数十億エントリに達する情報量には適さない場合があります。

インド統計研究所、UNL、およびシンガポール国立大学のコンピューター科学者は、新しいアルゴリズム CVM を提案しました。

長いリスト内のさまざまな項目の数を概算することができ、少数の項目を覚えておくだけで済みます。

論文アドレス: https://arxiv.org/pdf/2301.10191

このアルゴリズムは、スピーチ内のテキスト、商品など、一度に 1 つの項目が表示されるリストに適しています。ベルトコンベアや州間高速道路の車。

CVM アルゴリズムは 3 人の著者の頭文字にちなんで名付けられ、「異なる要素の問題」の解決において大きな進歩を遂げました。

この問題は 40 年以上コンピューター科学者を悩ませてきました。

それには、要素のストリーム (その合計数が使用可能なメモリを超える可能性があります) を監視し、その中にある一意の要素の数を推定する効率的な方法が必要です。

それでは、CVM アルゴリズムはどのように問題を解決するのでしょうか?

先駆的なCVMアルゴリズム、秘密は「ランダム化」にあります

「ハムレット」オーディオブックを聞いていると仮定してください。

このドラマには合計 30557 の単語がありますが、異なる単語はいくつありますか?

答えを見つけるには、聞きながら一時停止し、各単語をアルファベット順に書き、リストに既にある単語をスキップして、最後にリストにある各単語を数えるだけです。

この方法は実行可能ですが、人の「記憶力」をテストしすぎます。

研究者の Vinodchandran Variyam 氏は、「一般的なデータ フローの状況では、追跡する項目が数百万ある可能性があります。すべての情報を保存したくない場合もあります。

これは、アルゴリズムがよりシンプルな情報を提供できるクラウド サーバーです」と述べています。方法」。

その秘訣は「ランダム化」です。

Vinodchandran Variyam は、データ ストリーム内の個別の要素の数を推定するための CVM アルゴリズムの発明に貢献しました

「ハムレット」にはユニークな単語がいくつありますか?コイン投げチャレンジ

「ハムレット」に戻ります。あなたの「有効記憶」には 100 単語しか保持できないと仮定します。

音声の再生が開始されたら、最初に聞こえた 100 単語を書き留め、繰り返される単語はスキップします。

100 単語の録音が完了したら、残っているのは単語ごとにコインを投げることだけです –

ヘッズ、単語を守りましょう。裏面の場合は削除してください。

この予選を終えると、約 50 個の異なる単語が残ります。

ここで、チームがラウンド 1 と呼ぶものに進み、ハムレットを読み続け、新しい単語を追加します。

すでにリストにある単語に再び出会った場合は、記憶ホワイトボードに 100 単語が入るまでコインをもう一度投げます。

その後、100 回のコイン投げの結果に基づいて、単語の約半分が再びランダムに削除されます。ラウンド１はここで終了。

次に、Round2の2回戦に入ります。

最初のラウンドと同じように、単語の難易度を上げていきます。繰り返される単語に出会ったら、もう一度コインを投げます。

条件は、尻尾なら前と同じように削除することです。ただし、表の場合は、もう一度コインを投げます。単語は、2 回目に表に現れた場合にのみ保持されます。

メモリーホワイトボードがいっぱいになったらラウンドを終了し、100回投げた結果に基づいて単語の約半分を再度削除します。

ラウンド 3 では、言葉を守るためにコインの表を 3 回連続で裏返す必要があります。

4ラウンド目では、4回連続で前に言葉を残します。

最後に、第 k ラウンドでは、「ハムレット」の劇全体を聴きます。

この演習のポイントは、各単語の出現確率が同じであることを確認することです: 1/2 (k)。

ハムレットの音声の最後に、リストに 61 の単語があり、完了するまでに 6 ラウンドかかったとします。

61 を確率 1/2 (6) で割ることで、異なる単語の数を推定できます。このゲームの最終結果は 3904 です。

アルゴリズムの精度はメモリの量に比例します

研究者のChakraborty、Variyam、Meelは、CVMアルゴリズムの精度がメモリの量に比例することを数学的に証明しました。

そして、ハムレットには偶然にも 3967 個のユニークな単語があります。 (通常の数え方による)

100単語のメモリを使用した実験では、5回の実験結果の平均推定値は3955単語です。

1000 単語を記憶すると、平均記憶容量は 3964 語に増加しました。

ヴァリヤム氏は、「（メモリが）すべての単語を収容できるほど大きければ、100％の精度を達成できる」と述べました。

ハーバード大学のウィリアム・クスマウ氏は、「これは、非常に基本的で広く研究されている問題であっても、時には単純ではあるが明らかではない解決策がまだ発見されていない可能性があることを示す良い例です。」と述べました。