ゲーム百科 · 抽出アルゴリズム

リザーバサンプリングとは|流れてくるデータから1件を均等に残す仕組み

総件数が分からないデータ列でも、n件目を1/nで入れ替えると、そこまでの全項目から1件を均等に保持できます。採用確率、途中経過、重複記録の扱いを具体的な数字で確認します。

約11分で読めますゲームの仕組み
抽出の対象を見分ける番号付きのボール
抽出の対象を見分ける番号付きのボール · elizaIO / CC BY-SA 2.0 · 写真クレジット

リザーバサンプリングは、次々に届くデータを全部保存せず、その中から均等に選んだ一定件数だけを残す方法です。1件だけ残す場合は、最初の項目を保持し、n件目が届くたびに1/nの確率で新しい項目へ入れ替えます。止まった時点で、それまでに届いた各項目が残る確率は同じになります。

先頭の項目は長く保持されるため有利に見えますが、その後も何度も入れ替えの対象になります。最後に届く項目は、その場で1/nの採用機会を得ます。この2つを計算すると、先に来た項目も後に来た項目も最終的な確率がそろいます。到着順の見た目と、最後に残る確率は別のものです。

ゲームの記録やイベント列を考えると、全件の順序を並べ替える処理と、代表として少数だけ残す処理を区別できます。リザーバサンプリングが行うのは後者です。実際のゲーム結果を決める装置や、次の結果を予測する機能とは異なります。番号付きの5件のデータを使うと、何を残し、どこで入れ替えるのかを手で追えます。

全件が見えないときに、何を保持するのか

データの総数が先に分かるなら、全件から番号を一つ選ぶ方法が使えます。終わりがまだ来ない列では、その総数を使えません。そこで、届いた件数に合わせて候補を更新します。

ストリームは到着するたびに処理する列

項目1、項目2、項目3という順番で記録が届くとします。項目を一つ読むたびに、件数のカウンターを1増やします。内容が同じでも別の到着記録なら、まずは別の項目として数えます。終わる前に全長を見積もる必要はなく、今まで何件読んだかが更新の基準になります。

列を一度しか読めない場合にも、この処理は順番に進められます。ただし、到着しなかった記録を補う機能はありません。もとの取得範囲に抜けがあれば、残る候補もその取得範囲の中から選ばれます。抽出の手順と、入力データがそろっているかどうかを区別して扱います。

リザーバは候補を入れておく小さな枠

1件だけ残すモデルでは、枠は一つです。枠の中には現在選ばれている項目、別に現在までの件数を持ちます。新しい項目が来ても、全部を後ろへ追加するのではなく、残すか入れ替えるかを決めます。過去の全項目を並べた一覧がなくても、更新を続けられます。

項目そのものが大きいときは、内容全部ではなく識別番号や参照先を保持する設計も考えられます。ただし、その参照先が後で消えれば、番号だけ残っても内容を読めません。必要な保存量は、候補の件数と一件の表現方法を合わせて考えます。『1件』は必ずしも『1バイト』ではありません。

均等に残す対象を先に決める

10件のイベントを対象にするのか、10人の利用者を対象にするのかで、数える単位は変わります。同じ人が5回現れたイベント列から1件を抽出すれば、その人に結び付く記録は5つあります。人を均等に選びたいなら、イベントをそのまま均等に扱うだけでは目的と合いません。

番号付きのボールに置き換えると、この違いが見えます。同じ文字Aを書いたボールが3個、Bを書いたボールが1個あれば、4個のボールは別々の対象です。ボールごとの確率が同じでも、文字ごとの確率は同じになりません。何を一つと数えるかが、均等という言葉の意味を決めます。

1件だけを保持するリザーバサンプリング
k=1の1ステップを示す例です。過去データはすべて保存しません。 図は横にスクロールできます。
抽出の対象を見分ける番号付きのボール
抽出の対象を見分ける番号付きのボール · Marlon E from USA / CC BY-SA 2.0 · 写真クレジット

1件を残す更新は、1〜nの整数で決める

k=1の基本形では、新項目を採用する条件を一つだけ用意します。n件目で1〜nの整数jを等確率で選び、jが1なら入れ替え、それ以外なら今の項目を残します。

到着した項目整数jの範囲入れ替える条件新項目の採用確率
1件目選択不要最初の項目を保持1
2件目1〜2j=11/2
3件目1〜3j=11/3
5件目1〜5j=11/5
100件目1〜100j=11/100

最初の項目だけはそのまま入れる

項目1が届いた時点では、候補はそれしかありません。枠に項目1を入れ、件数を1にします。ここで半分の確率で空欄を残す必要はありません。1件から1件を選ぶという条件なら、その項目が選ばれる確率は1です。次の項目から、入れ替えるかどうかの処理が始まります。

空の列は別のケースです。何も届かなければ、選ばれた項目もありません。空欄を架空の項目0として集計すると、実在しない候補を加えてしまいます。開始前、1件目の取得後、2件目以降という状態を分けると、最初の処理を無理なく確認できます。

jの一つだけを採用に使う

5件目なら、jの候補は1、2、3、4、5の5つです。そのうち1だけで入れ替えるため、新しい項目の採用確率は1/5です。jが2でも4でも保持する項目は変わりません。jをそのまま過去項目の番号と解釈して、その項目を読み直す処理ではない点が重要です。

たとえば現在の候補が項目2で、n=5、j=4なら、残るのは項目2です。項目4に変わるわけではありません。jは更新の判定に使う値で、保持している項目番号とは役割が違います。画面に二つの数字が並ぶときも、どちらが候補でどちらが判定値なのかを先に確かめます。

等確率という条件を落とさない

jを、それ以前の選択に依存せず1〜5から同じ確率で選ぶなら、1が出る確率は1/5です。ところが、1を出しやすい選び方にすると新項目を入れ替える頻度も変わります。整数の範囲が正しく見えるだけでは十分ではありません。各整数をどういう重みで選んだかまで含めて、更新規則の条件になります。

操作サンプルでは、jを手で指定して分岐を確認します。手入力を何回か試した結果が、等確率の乱数を生成できた証拠になるわけではありません。サンプルは一段階の意味を確認する道具です。均等な抽出の計算は、各段階のjを等確率で選ぶという前提に立っています。

n件目で入れ替えるかを確かめる

到着した項目番号n、現在保持する項目番号、判定値jを指定し、k=1の一段階の更新と採用確率を確認します。

入力値を確かめる準備ができました。

k=1の1ステップを示す例です。過去データはすべて保存しません。

5件の到着を、一回の経路として追う

途中の枠の中身は一つの実現例です。毎段階の採用確率と、実際にその経路で残った項目を分けて並べると、何が変わったのかを見失いません。

到着順n例のj処理処理後の候補
1なし最初の項目を入れる項目1
22そのまま保持項目1
31新項目へ入れ替え項目3
43そのまま保持項目3
51新項目へ入れ替え項目5

残り続ける時間と、最後に選ばれる確率

この経路では項目1が2件目の処理後まで残り、項目3は3件目から4件目まで残ります。項目2と項目4は一度も枠に入りません。それでも、その2件に採用機会がなかったわけではありません。それぞれ到着した時点で、1/2と1/4の採用機会を持っています。

最後に項目5が残ったという一回の経路から、『新しい項目ほど必ず残る』とはいえません。5件目でjが2〜5なら、直前の候補が残ります。実際の枠の中身は一つだけでも、起こり得るjの分岐は複数あります。その分岐全体に割り当てられた確率を考えるのが、抽出の仕組みの確認です。

最後の判定だけを変えてみる

4件目まで項目3が残ったまま、5件目のjだけを変えます。j=1なら項目5へ変わり、j=2、3、4、5なら項目3のままです。この条件の下で、現在の候補が生き残る確率は4/5、新項目が入る確率は1/5です。二つを足すと1になります。

ただし、この4/5は『項目3が最初から最後まで選ばれる確率』ではありません。4件目の処理後に項目3が残っていると分かった条件付きの確率です。全体で項目3が残る確率を求めるには、その前に項目3が候補になっている確率も掛けます。条件付きと全体を分けると、数字の大きさに惑わされません。

途中で止めても、その時点の対象から選べる

列が3件で終われば、そこまでの3項目がそれぞれ1/3で候補になります。5件まで続けば、それぞれ1/5に変わります。最初に最終件数を予約してから選んでいるのではなく、到着済みの全項目に対する均等性を更新し続けているためです。

終わりの通知が来た時点で、現在の候補を取り出せます。ただし、候補の内容を見て都合のよいときだけ停止するような別の規則を加えると、元の抽出条件とは違う問題になります。固定した取得範囲や、データ側の終了条件と、候補に応じた恣意的な停止を混同しないようにします。

抽出の対象を見分ける番号付きのボール
抽出の対象を見分ける番号付きのボール · 写真クレジット

早く来た項目も、最後は1/nになる理由

均等さは、早い項目を不利に扱って調整するような印象ではなく、採用と生存の掛け算で確かめられます。少ない項目から順に計算すると、規則の働きが見えてきます。

2件目では両方が1/2になる

1件目は最初に必ず枠へ入ります。2件目で入れ替えが起こる確率は1/2なので、項目1が残る確率は1−1/2=1/2です。項目2は採用される確率がそのまま1/2になります。どちらを最初に受け取ったとしても、この時点の候補確率は同じです。

ここでは、二つの項目が同時に残ることはありません。枠は一つだけだからです。『両方が1/2』というのは、二つを同時に半分ずつ保存するという意味ではなく、別々の実行を含めて考えたときの選択確率です。一回の処理の中身と、複数の可能性に対する確率を区別します。

3件目で古い項目は2/3の確率で生き残る

2件目までに項目1が残る確率は1/2です。3件目で入れ替えない確率は2/3なので、項目1が3件目の処理後にも残る確率は1/2×2/3=1/3です。項目2も同じ計算になり、新しい項目3の採用確率も1/3です。3つの候補が同じ重みになりました。

一般に、n−1件の時点で古い項目の確率が1/(n−1)なら、n件目での生存確率(n−1)/nを掛けます。結果は1/nです。新項目も1/nで入るため、古い項目と新しい項目の確率がそろいます。この一段階の計算が、件数を増やしても同じ形で続きます。

途中から入る項目でも同じ計算になる

5件目に来た項目5が10件目まで残る確率を考えます。採用される1/5に、その後の5/6、6/7、7/8、8/9、9/10を掛けます。分子と分母の中間部分が約分され、最後は1/10になります。遅く来た分だけ生存の判定が少ないことと、最初の採用確率が小さいことがつり合います。

この計算は、各段階で規則どおりの選択をしていることを使っています。nの数え忘れや、同じ段階での二重更新があると、掛け合わせる値が変わります。手順の形だけを真似るのではなく、到着件数と更新が一対一で対応しているかを確認することが、均等な抽出を保つ条件です。

同じ値の記録と、同じ項目の再送は区別する

抽出の前にどこまで整理するかで、対象の集合が変わります。値が同じという理由だけで削除したり、同じ記録の再送を新規項目として数えたりすると、意図した単位からずれます。

A・A・Bは3件のイベントになり得る

A、A、Bという3つの到着イベントが別々の出来事なら、3件から1件を均等抽出します。Aという表示が残る確率は2/3、Bは1/3です。リザーバサンプリングは、同じ表示を持つ項目を自動的に一つの値へまとめません。各到着項目を一つとして扱った結果です。

値Aと値Bを半分ずつ選びたいなら、まず異なる値の集合を作るなど、別の入力設計が必要です。その設計には、どの値を既に見たかを覚える保存量も必要になります。候補を一つだけ持つ処理と、全ての異なる値を識別する処理のメモリ量は同じとは限りません。

再送を数えるかどうかは、記録の定義で決める

通信の都合で同じイベントIDがもう一度届いた場合、それを同じ出来事の再送と扱う設計があります。出来事から1件を選ぶなら、再送を重複として除いてから件数を増やします。到着メッセージそのものから1件を選ぶなら、再送を含めて別の到着として数えることもできます。

どちらが正しいかは、求めている標本の単位で決まります。大切なのは途中で定義を変えないことです。最初の半分ではイベントIDをまとめ、後半では再送も別件にすると、同じ規則の対象ではなくなります。候補の番号だけでなく、対象の定義を記録しておくと、後から抽出結果を説明できます。

条件で絞った後の均等性を読む

全ての記録から選ぶのではなく、あるゲーム形式の記録だけを対象にする場合、条件に合う項目が届いたときだけ抽出用の件数を増やします。対象外の項目でもnを増やしてしまうと、採用確率の分母だけが大きくなり、意図した対象内の均等抽出から外れます。

絞り込みの条件を変えると、均等に選ぶ範囲も変わります。曜日を限定した標本は、その曜日の記録に対する標本です。期間や形式が違う標本を並べるときは、抽出法が同じかだけでなく、対象範囲がそろっているかも確かめます。抽出処理だけで、入力の偏りが自動的に消えるわけではありません。

抽出の対象を見分ける番号付きのボール
抽出の対象を見分ける番号付きのボール · L.enriquez / CC BY-SA 4.0 · 写真クレジット

全件シャッフルや固定割合の抽出との違い

似たようにランダムな候補を作る方法でも、保存する量や、最終的に何件残るかが違います。どこを一定にしたいかで、使う処理を区別できます。

シャッフルは全体の順番を作る

全件を配列に入れてシャッフルすれば、その後で先頭を1件取り出せます。この方法は全件の並べ替えを持っているため、2件目、3件目という順番も使えます。一方、1件のリザーバだけを残した場合、捨てた項目の次順位は保存されていません。二つの方法が残す情報は違います。

全順序が必要なら、その目的に合う方法を選びます。代表を1件だけ欲しいときに全件を保持する必要があるか、逆に後で複数件を取り出したいのに1件の枠だけでよいかを考えます。処理の名前より、最後に利用する情報の形を先に決めると、無駄や不足を見つけやすくなります。

一定確率で残すと、残る件数は変わる

各項目を1/10の確率で個別に残す方法では、100件から必ず10件が残るわけではありません。平均的な件数と、実際の残る件数は違います。対象の総数が分からなくても処理できますが、残る枠の数を1件に固定するという目的とは異なります。

リザーバサンプリングのk=1では、1件以上届いていれば枠に残る件数は常に1件です。新しい項目を採用するときは、古い候補を入れ替えます。追加だけを続ける処理ではないため、対象が増えても候補の件数が増えません。件数を固定したい場合の違いがここにあります。

k件版では、更新の対象となる枠も選ぶ

k件を残す基本形では、最初のk件を枠に入れます。n件目以降で1〜nの整数jを選び、jがk以下なら、その番号の枠を新項目で置き換えます。新項目がどこかの枠に入る確率はk/nです。1件版の1/nを、枠が複数ある形へ拡張した規則として読めます。

k=2、n=5なら、j=1か2のときに採用され、採用確率は2/5です。ただし、一つの新項目を二つの枠へ同時に複写するわけではありません。選んだ一つの枠だけを置き換えます。複数枠の処理を実装するときも、候補の重複を勝手に増やさないように、枠と項目を区別します。

n・現在の項目・jを変えて、更新を検算する

操作例はk=1の一段階を表示します。nはこれから処理する新項目の番号で、現在保持する項目番号は1〜n−1、jは1〜nの範囲で指定します。

n=5、現在2、j=1から始める

この入力では、5件目が届く前に項目2を保持しています。jが1なので、新しい項目5へ入れ替わります。次にjだけを2へ変えると、項目2をそのまま保持します。現在の番号を3へ変えても、採用確率が1/5であるという条件は変わりません。現在の中身と更新確率は別の情報です。

サンプルに入れる現在の番号は、過去のある経路から残った候補を表しています。番号を直接入力すること自体が、その候補を正しく均等抽出した証明にはなりません。現在の状態を仮定して次の一段階を検算する道具として使うと、表示結果と確率の役割がはっきりします。

小さいnで全てのjを試す

n=3ならjを1、2、3と順に変えられます。新項目を採用するのは1の一つだけで、残り二つは保持です。n=4なら採用1通り、保持3通りになります。整数の候補を一つずつ確かめると、採用1/nと保持(n−1)/nの分子が、そのまま分岐の数であることを確認できます。

この数え上げは、全てのjを同じ重みで考えたときの確認です。jを毎回1に固定すれば、表示上はいつも新項目へ変わります。その結果を見て更新規則が新項目を優遇していると判断するのではなく、入力したjの選び方が前提と違うことに注目します。規則と入力経路を分けて読みます。

範囲外の番号は、処理の矛盾を示す

n=5なのに現在の項目を5とすると、まだ到着していない新項目を既に保持している状態になります。j=6も、1〜5から選ぶという範囲の外です。サンプルではこうした入力を受け付けません。表示の都合ではなく、更新前と更新後の順序を守るための条件です。

nは2〜1000の範囲で試せますが、この上限は操作例を扱いやすくするための設定です。基本の更新規則が1000件で終わるという意味ではありません。大きな列で使う場合は、件数カウンターの表現範囲、乱数の選び方、再開時の状態保存など、実装側で確認する項目が増えます。

抽出の対象を見分ける番号付きのボール
抽出の対象を見分ける番号付きのボール · 写真クレジット

残った1件から分かることと、保存していないこと

抽出結果には、対象から選んだ一つの記録が残ります。対象全体の分布や順序まで残るわけではありません。何に使える標本なのかを、保存している情報から判断します。

1件の標本は全体の頻度表ではない

残った項目がAだったとしても、全体にAが何件あったかは、その一件だけから分かりません。均等に選ぶことと、全体の種類別件数を集計することは別の目的です。頻度を知るためには集計を別に保存するか、目的に合った標本件数を用意する必要があります。

一つの代表記録は、形式の確認や、ある記録を詳しく読む入り口になります。しかし、その記録に見つかった特徴を全件の性質として扱うには情報が足りません。標本の選び方が均等でも、1件しか持っていないことによる情報の少なさは残ります。保存量を減らす利点と、残る情報の量を一緒に読みます。

過去の候補を後から復元する機能ではない

n件目を処理した後に、以前どの項目が候補だったかを知りたければ、その履歴を別に残す必要があります。最終候補一つと件数だけでは、途中で起きた入れ替えの経路は一つに決まりません。同じ最終候補に到達する複数のjの列があり得ます。

再現可能な学習例では、使った入力列と各段階のjを記録すると経路を追えます。これを候補を一つ保持するための最小状態と混同しないようにします。再現や監査のための記録は、抽出に必要な状態とは別に設計する情報です。何を後から確かめたいかで、保存する内容が変わります。

抽出方法とゲームの結果決定を結び付けない

データ列から均等な標本を残す説明は、個別のゲームがこの方法で結果を決めているという主張ではありません。実際の製品の結果決定、記録の抽出、画面への表示は役割が異なります。共通して番号や乱数が出てきても、同じ仕組みとして扱わないことが理解を助けます。

アルゴリズムの説明を読むときは、入力が何か、出力が何件か、どの条件で均等になるかを確かめます。1件を残すリザーバでは、到着順に番号を付け、n件目を1/nで採用することが中心です。そこまでを手で検算できれば、全件を保存しない抽出の仕組みを具体的に読み取れます。

よくある質問

リザーバサンプリングは何のために使う方法ですか?

長さが先に分からないデータ列から、一定件数の項目を均等に残すための抽出方法です。k=1なら候補を一つ保持し、新項目が届くたびに採用するか更新します。

最初に来た項目が有利になりませんか?

規則どおりの更新では、最初の項目もその後の入れ替えで外れる可能性があります。採用と生存の確率を掛けると、n件目の処理後には各項目が残る確率は1/nです。

n件目でjが3なら項目3に入れ替えますか?

k=1の例では入れ替えません。j=1のときだけ新しいn件目へ変え、それ以外は現在の候補を保持します。jは過去項目を直接指定する番号ではありません。

途中で列が終わっても使えますか?

入力が終わった時点で、現在の候補を取り出せます。終了までに届いた各項目が均等に選ばれるよう更新されています。候補を見て都合よく止める別の条件は加えません。

同じ値が何度も出たら一つにまとめますか?

値が同じでも別の到着項目なら別件として扱います。異なる値を均等に選ぶことが目的なら、抽出前に対象の単位や重複の整理方法を決める必要があります。

全件シャッフルと同じ情報が残りますか?

残りません。全件シャッフルは全体の順序を作りますが、1件のリザーバは候補一つだけを残します。捨てた項目の順位や途中経路は別途記録しなければ残りません。

操作例は自動で乱数を生成しますか?

この操作例ではn、現在の項目番号、整数jを自分で指定し、一段階の採用と保持を確認します。手入力の結果は、乱数の均等性や実際の製品の動作を検証するものではありません。

1件の抽出結果から全体の比率が分かりますか?

一件だけでは全体の種類別件数や比率は分かりません。均等に選ぶ規則と、全体を推定するために必要な標本の量や集計情報は別の問題です。