貯留層サンプリング

リザーバ サンプリングは、未知のサイズnの母集団からk 個のアイテムを1 回のパスで非置換の単純ランダム サンプルとして選択するランダム化アルゴリズムのファミリです。母集団nのサイズはアルゴリズムにはわかりません。通常、 n個のアイテムすべてをメイン メモリに収めるには大きすぎます。母集団は時間の経過とともにアルゴリズムに公開され、アルゴリズムは以前のアイテムをさかのぼることはできません。どの時点でも、アルゴリズムの現在の状態は、これまでに確認された母集団の一部からサイズkの非置換の単純ランダム サンプルを抽出できる必要があります。

アイテムのシーケンスを 1 つずつ見ているとします。メモリに 10 個のアイテムを保持し、シーケンスからランダムに選択するとします。アイテムの総数nがわかっていて、アイテムに任意にアクセスできる場合、解決方法は簡単です。1からnまでの間の 10 個の異なるインデックスi を等確率で選択し、i番目の要素を保持します。問題は、正確なn が常に事前にわかっているわけではないことです。

シンプルで人気があるが遅いアルゴリズムであるアルゴリズムRは、ジェフリー・ヴィッターによって作成されました。^[1]

入力の最初のk項目を含む、から までのインデックスを持つ配列を初期化します。これがリザーバです。 ${\displaystyle R}$${\displaystyle 1}$${\displaystyle k}$${\displaystyle x_{1},...,x_{k}}$

それぞれの新しい入力 に対して、内で一様に乱数j を生成します。 の場合、 を設定します。それ以外の場合は を破棄します。 ${\displaystyle x_{i}}$${\displaystyle \{1,...,i\}}$${\displaystyle j\in \{1,...,k\}}$${\displaystyle R[j]:=x_{i}.}$${\displaystyle x_{i}}$

すべての入力が処理された後に戻ります。${\displaystyle R}$

このアルゴリズムは 上の帰納法によって機能します。 ${\displaystyle i\geq k}$

このアルゴリズムは概念的には単純で理解しやすいですが、破棄される項目も含め、入力の各項目に対して乱数を生成する必要があります。したがって、アルゴリズムの漸近的実行時間は です。この程度の乱数と線形実行時間を生成すると、入力母集団が大きい場合にアルゴリズムが不必要に遅くなります。 ${\displaystyle O(n)}$

これはアルゴリズム R であり、次のように実装されています。

(* S にはサンプリングする項目があり、R にはその結果が含まれます *) 
ReservoirSample ( S [ 1 .. n ] , R [ 1 .. k ]) // リザーバー配列を埋めるfor i := 1 to k R [ i ] := S [ i ] end 
  
       
        
  

  // 徐々に確率が下がる要素を置き換えます。
for i := k + 1 to n (* randomInteger(a, b) は、{a, ..., b} を含む範囲から均一な整数を生成します。 *) j := randomInteger ( 1 , i ) if j <= k R [ j ] := S [ i ] end end end       
    
       
       
          
    
  

乱数を独立に生成すると、そのうちの最小の乱数のインデックスはの k 部分集合の均一なサンプルになります。 ${\displaystyle n}$${\displaystyle u_{1},...,u_{n}\sim U[0,1]}$${\displaystyle k}$${\displaystyle \{1,...,n\}}$

このプロセスは、次のことを知らなくても実行できます。${\displaystyle n}$

これまでに見たの最小値と、それらの最大値のインデックス を保持します。新しい ごとに、それを と比較します。 の場合、 を破棄し、 を保存して、 をそれらの最大値のインデックス に設定します。それ以外の場合は、 を破棄してを設定します。${\displaystyle k}$${\displaystyle u_{1},...,u_{i}}$${\displaystyle w_{i}}$${\displaystyle u_{i+1}}$${\displaystyle u_{w_{i}}}$${\displaystyle u_{i+1}<u_{w_{i}}}$${\displaystyle u_{w_{i}}}$${\displaystyle u_{i+1}}$${\displaystyle w_{i+1}}$${\displaystyle u_{i+1}}$${\displaystyle w_{i+1}=w_{i}}$

これを入力のストリームと組み合わせます。 一部が受け入れられるたびに、対応する を保存します。 一部が破棄されるたびに、対応する を破棄します。 ${\displaystyle x_{1},...,x_{n}}$${\displaystyle u_{i}}$${\displaystyle x_{i}}$${\displaystyle u_{i}}$${\displaystyle x_{i}}$

このアルゴリズムでは依然として乱数が必要なので時間がかかります。しかし、簡略化することは可能です。 ${\displaystyle O(n)}$${\displaystyle O(n)}$

最初の簡略化:次の承認が で発生する確率は 、つまり承認の間隔は幾何分布 に従うため、新しいものを 1 つずつテストする必要はありません。 ${\displaystyle u_{i+1},u_{i+2},...}$${\displaystyle u_{i+l}}$${\displaystyle (1-u_{w_{i}})^{l-1}\,u_{w_{i}}=(1-u_{w_{i}})^{l-1}-(1-u_{w_{i}})^{l}}$${\displaystyle l}$

2 つ目の簡略化:これまでに見た の最小の配列全体を覚える必要はなく、その中で最大の だけを覚えればよい。これは次の 3 つの観察に基づいています。 ${\displaystyle k}$${\displaystyle u_{1},...,u_{i}}$${\displaystyle w}$

• ストレージに入力する新しいエントリが選択されるたびに、ストレージ内の均一にランダムなエントリが破棄されます。${\displaystyle x_{i+1}}$
• ${\displaystyle u_{i+1}\sim U[0,w]}$
• ${\displaystyle w_{i+1}}$は と同じ分布を持ち、すべては独立しています。これは、まず をサンプリングし、次に を取ることでサンプリングできます。${\displaystyle \max\{u_{1},...,u_{k}\}}$${\displaystyle u_{1},...,u_{k}\sim U[0,w]}$${\displaystyle u\sim U[0,1]}$${\displaystyle w\cdot u^{\frac {1}{k}}}$

これはアルゴリズムL ^[2]であり、以下のように実装される。

(* S にはサンプリングする項目があり、R にはその結果が含まれます *) 
ReservoirSample ( S [ 1 .. n ] , R [ 1 .. k ]) // リザーバー配列を埋めるfor i = 1 to k R [ i ] := S [ i ] end 
  
       
        
  

  (* random() は均一な (0,1) 乱数を生成します *) 
W := exp ( log ( random ()) / k )    

  i <= nの場合i := i + floor ( log ( random ()) / log ( 1 - W )) + 1 if i <= n (* リザーバーのランダムなアイテムをアイテム i に置き換えます *) R [ randomInteger ( 1 , k )] := S [ i ] // 1 から k までの範囲のランダムなインデックスW := W * exp ( log ( random ()) / k ) end end end   
            
         
          
              
              
      
  

このアルゴリズムは、リザーバの一部となるアイテムごとに3つの乱数を計算し、リザーバの一部とならないアイテムには時間を費やしません。したがって、予想される実行時間は[ ^2]であり、最適です。^[1] 同時に、効率的に実装するのは簡単で、エキゾチックな分布や計算が難しい分布からのランダムな偏差に依存しません。 ${\displaystyle O(k(1+\log(n/k)))}$

入力の各項目に均一に生成された乱数を関連付けると、関連付けられた値が最大（または最小）のk項目が単純ランダムサンプルを形成します。 ^[3] 単純なリザーバサンプリングでは、現在関連付けられている値が最大であるk項目が優先キューに保持されます。

(* 
  S はサンプルするアイテムのストリームです。
  S.Current はストリーム内の現在のアイテムを返します。
  S.Next はストリームを次の位置に進めます。
  min-priority-queue は以下をサポートします: 
    Count -> 優先キュー内のアイテム数
    Minimum -> 全アイテムの最小キー値を返します
    Extract-Min() -> 最小キーを持つアイテムを削除します
    Insert(key, Item) -> 指定されたキーを持つアイテムを追加します
* ) 
ReservoirSample ( S [ 1 .. ? ] ) 
H := new min - priority - queue while S has data r := random ( ) // 0 から 1 の間の均一ランダム (排他的) if H.Count < k H.Insert ( r , S.Current ) else //最大の関連キーを持つ k 個のアイテムを保持if r > H.Minimum H.Extract - Min ( ) H.Insert ( r , S.Current ) end S.Next end H内のアイテムを返しますend     
     
         
       
       
    
      
         
        
         
    
    
  
     

このアルゴリズムの予想される実行時間は、重みのあるアイテムに簡単に拡張できるため、主に重要です。 ${\displaystyle O(n+k\log k\log(n/k))}$

前のセクションで紹介した方法では、事前に固定された包含確率を得ることはできません。一部のアプリケーションでは、アイテムのサンプリング確率が各アイテムに関連付けられた重みに応じている必要があります。たとえば、検索エンジンでクエリを重みを実行回数としてサンプリングして、サンプルのユーザーエクスペリエンスへの全体的な影響を分析する必要がある場合があります。アイテムiの重みを、すべての重みの合計をWとします。セット内の各アイテムに割り当てられた重みを解釈する方法は 2 つあります。^[4]${\displaystyle w_{i}}$

1. 各ラウンドで、選択されていないすべてのアイテムがそのラウンドで選択される確率は、選択されていないすべてのアイテムの重みに対するそのアイテムの重みに比例します。X が現在のサンプルの場合、現在のラウンドでアイテムが選択される確率は です。${\displaystyle i\notin X}$${\displaystyle \textstyle w_{i}/(W-\sum _{j\in X}{w_{j}})}$
2. ランダムサンプルに含まれる各項目の確率は、その相対的な重みに比例します。つまり、 です。ただし、この解釈は、たとえば などの場合には実現できない可能性があることに注意してください。${\displaystyle w_{i}/W}$${\displaystyle k=n}$

エフライミディスとスピラキスは、解釈1を用いた次のアルゴリズムを提示した。^[5]

(* 
  S はサンプリングする項目のストリームです。
  S.Current はストリーム内の現在の項目を返します。
  S.Weight はストリーム内の現在の項目の重みを返します。
  S.Next はストリームを次の位置へ進めます。
  累乗演算子は ^ で表されます。
  min-priority-queue は以下をサポートします: 
    Count -> 優先キュー内の項目数
    Minimum() -> 全項目の最小キー値を返します
    Extract-Min() -> 最小キーを持つ項目を削除します
    Insert(key, Item) -> 指定されたキーを持つ項目を追加します
*) 
ReservoirSample ( S [ 1 .. ? ]) 
H := new min - priority - queue while Sにデータがありますr := random () ^ ( 1 / S . Weight ) // random() は (0,1) の範囲で一様に乱数を生成します。if H . Count < k H . Insert ( r , S . Current ) else // 最大の関連キーを持つ k 個の項目を保持します。 if r > H . Minimum H . Extract - Min () H . Insert ( r , S . Current ) end end S .次の終了H終了の項目を返す     
     
           
       
       
    
      
         
        
         
      
    
    
  
     

このアルゴリズムは、アイテムのキーの生成を除いて、ランダムソートによるリザーバサンプリングで示されたアルゴリズムと同一です。このアルゴリズムは、各アイテムにキーを割り当て、rを乱数として、最大のキーを持つk個のアイテムを選択することと同等です。同様に、このアルゴリズムのより数値的に安定した定式化では、キーを次のように計算し、最小のキーを持つk個のアイテムを選択します。^{[6] [検証失敗]}${\displaystyle r^{1/w_{i}}}$${\displaystyle -\ln(r)/w_{i}}$

以下のアルゴリズムはA-Resのより効率的なバージョンであり、これもエフライミディスとスピラキスによって提案されたものである。^[5]

(* 
  S はサンプリングする項目のストリームです。
  S.Current はストリーム内の現在の項目を返します。
  S.Weight はストリーム内の現在の項目の重みを返します。
  S.Next はストリームを次の位置へ進めます。
  べき乗演算子は ^ で表されます。
  min-priority-queue は以下をサポートします: 
    Count -> 優先キュー内の項目数
    Minimum -> 優先キュー内の任意の項目の最小キー
    Extract-Min() -> 最小キーを持つ項目を削除
    Insert(Key, Item) -> 指定されたキーを持つ項目を追加します
*) 
ReservoirSampleWithJumps ( S [ 1 .. ? ]) 
H := new min - priority - queue while Sにデータがあり、H . Count < k r := random () ^ ( 1 / S . Weight ) // random() は (0,1) 内の一様乱数を生成します。 H . Insert ( r , S . Current ) S .次へend X := log ( random ()) / log ( H . Minimum ) // これは、 Sにデータがある間に飛び越える必要がある重みの量です。 X := X - S . Weight if X <= 0 t := H . Minimum ^ S . Weight r := random ( t , 1 ) ^ ( 1 / S . Weight ) // random(x, y) は、(x, y) で均一な乱数を生成します。H . Extract - Min () H . Insert ( r , S . Current )     
         
           
     
    
  
       
     
        
       
          
            
    
      
       

      X := log ( random ()) / log ( H . Minimum ) end S . Next end H内の項目を返すend    
    
    
  
     

このアルゴリズムは、A-Res で使用されるのと同じ数学的特性に従いますが、各アイテムのキーを計算してそのアイテムを挿入するかどうかをチェックする代わりに、挿入される次のアイテムへの指数関数的なジャンプを計算します。これにより、コストがかかる可能性がある各アイテムのランダム変数を作成する必要がなくなります。必要なランダム変数の数は、期待値で から に削減されます。ここではリザーバのサイズ、 はストリーム内のアイテム数です。^[5]${\displaystyle O(n)}$${\displaystyle O(k\log(n/k))}$${\displaystyle k}$${\displaystyle n}$

警告: 以下の説明は間違っています。Chao の元の論文とここでの議論を参照してください。

以下のアルゴリズムはMT Chaoによって解釈2で示されました: ^[7]およびTillé (2006)。^[8]

(* 
  S にはサンプリングするアイテムがあり、R には結果が含まれます
  S[i].Weight には各アイテムの重みが含まれます
*) 
WeightedReservoir - Chao ( S [ 1 .. n ] 、R [ 1 .. k ]) WSum := 0 // リザーバー配列を埋めるfor i := 1 to k R [ i ] := S [ i ] WSum := WSum + S [ i ] . Weight end for i := k + 1 to n WSum := WSum + S [ i ] . Weight p := S [ i ] . Weight / WSum // このアイテムの確率j := random () ; // 0 から 1 の間で均一にランダムif j <= p // 確率に従ってアイテムを選択R [ randomInteger ( 1 , k )] := S [ i ] // 置換用のリザーバー内の均一な選択end end end 
    
  
       
        
          
  
       
        
         
                
                      
            
    
  

各アイテムの相対的な重みが計算され、そのアイテムをリザーバーに追加するかどうかをランダムに決定するために使用されます。アイテムが選択されると、リザーバーの既存のアイテムの 1 つが均一に選択され、新しいアイテムに置き換えられます。ここでの秘訣は、リザーバー内のすべてのアイテムの確率がすでに重みに比例している場合、どのアイテムを置き換えるかを均一に選択することで、置き換え後もすべてのアイテムの確率が重みに比例したままになるということです。

Chao は最初のk個の要素をサンプリングする方法を指定していないことに注意してください。彼は、重みに比例して要素を選択する別の方法があると単純に想定しています。Chao: 「時刻AにおけるS_kに関する固定サイズのサンプリング プランがあり、そのX_tの 1 次包含確率がπ(k; i)であると仮定します」。

j他のアルゴリズムと同様に、ランダムな重みを計算し、アイテムの確率質量値を減算してスキップすることでj > 0、生成しなければならない乱数の数を減らすことができます。 ^[4]

(* 
  S にはサンプリングする項目があり、R には結果
  S[i] が含まれます。Weight には各項目の重みが含まれます
*) 
WeightedReservoir - Chao ( S [ 1 .. n ] 、R [ 1 .. k ]) WSum := 0 // リザーバー配列を埋めますfor i := 1 to k R [ i ] := S [ i ] WSum := WSum + S [ i ] . Weight end j := random () // 0 から 1 の間の均一ランダムpNone := 1 // これまで (このジャンプで) 項目が選択されていない確率for i := k + 1 to n WSum := WSum + S [ i ] . Weight p := S [ i ] . Weight / WSum // このアイテムの確率j -= p * pNone pNone := pNone * ( 1 - p ) if j <= 0 R [ randomInteger ( 1 , k )] := S [ i ] // 置換のためのリザーバー内の均一選択j = random () pNone := 1 end end end 
    
  
       
        
          
  
     
     
       
        
         
        
          
       
            
          
          
    
  

トランプのデッキからランダムにk枚のカードを取りたいとします。自然な方法は、デッキをシャッフルして、上からk枚のカードを取ることです。一般的なケースでは、デッキのカードの枚数が事前にわからなくてもシャッフルが機能する必要がありますが、この条件はフィッシャー・イェーツ・シャッフルの裏返しバージョンによって満たされます。^[9]

(* S には入力があり、R には出力順列が含まれます *) 
Shuffle ( S [ 1 .. n ] , R [ 1 .. n ]) R [ 1 ] := S [ 1 ] for i from 2 to n do j := randomInteger ( 1 , i ) // 包含範囲R [ i ] := R [ j ] R [ j ] := S [ i ] end end 
    
        
           
        
        
  

残りのカードはシャッフルされますが、現在のコンテキストでは最初のk 枚だけが重要であることに注意してください。したがって、配列R はシャッフルの実行中に最初のk位置のカードを追跡するだけでよく、必要なメモリの量を削減できます。R を長さkに切り捨てると、アルゴリズムはそれに応じて変更されます。

(* S にはサンプリングする項目があり、R にはその結果が含まれます *) 
ReservoirSample ( S [ 1 .. n ] , R [ 1 .. k ]) R [ 1 ] := S [ 1 ] for i from 2 to k do j := randomInteger ( 1 , i ) // 包含範囲R [ i ] := R [ j ] R [ j ] := S [ i ] end for i from k + 1 to n do j := randomInteger ( 1 , i ) // 包含範囲if ( j <= k ) R [ j ] := S [ i ] end end end 
    
        
           
        
        
  
          
           
         
            
      
  

最初のk枚のカードの順序は重要ではないため、最初のループを削除し、R を入力の最初のk個の項目に初期化することができます。これにより、アルゴリズム R が生成されます。

リザーバサンプリングでは、目的のサンプルがメインメモリに収まるという仮定が立てられ、 kはnに依存しない定数であることがしばしば示唆されます。入力リストの大きなサブセット（たとえば3分の1）を選択したいアプリケーションでは、他の方法を採用する必要があります。この問題に対する分散実装が提案されています。^[10]${\displaystyle k=n/3}$