[번역] Reservoir Sampling

개인 공부용으로 번역한 거라 잘못 번역된 내용이 있을 수 있습니다.
또한 원작자의 동의 없이 올려서 언제든 글이 내려갈 수 있습니다.

 

이 글은 Reservoir Sampling 에 대한 2개의 글을 동시에 담고 있습니다. (출처1은 이론, 출처2는 실제 코드에 대해 설명)

출처1 : https://florian.github.io/reservoir-sampling/#proof

출처2 : https://www.geeksforgeeks.org/reservoir-sampling/

 

---

Reservoir Sampling

November 30, 2019

출처1 : https://florian.github.io/reservoir-sampling/#proof

 

내가 가장 좋아하는 알고리즘 중 하나는 reservoir sampling 으로 불리는 기술 그룹 중 하나 입니다. 나는 알고리즘이 복잡하지도 멋진 수학이 필요하지도 않지만 아주 우아하게 문제를 해결하는 것을 좋아합니다. 그건 그렇고, 인기 있는 인터뷰 질문의 해결법이기도 합니다.

문제는 다음과 같습니다: 요소들의 steam 이 주어졌을 때, 우리는 k 개를 uniform 확률을 사용하여 without replancement 방식으로 무작위로 샘플링 하고싶습니다.  (역주: replacement 방식은 중복허용, without replacement 는 중복 허용 안함. 이 링크 참고). stream 의 총 요소의 수는 모릅니다. 언제든지, stream 을 중단 할 수 있고, k 개의 랜덤 요소를 반환해야만 합니다. 이 블로그 글은 단순한 해결법을 먼저 살펴봅니다, 이어서 실제로 확장하고, 내가 찾은 우아한 알고리즘으로 갑니다.

 

Naive Approach

우리가 문제를 해결법은 모른다면, 우리가 알고 있는 해결법으로 문제를 줄여볼 수 있을 것입니다. 이를 위해, 우리는 모든 stream 요소들을 배열에 저장할 수 있습니다. 문제는 각각의 요소가 반환되는 k 개의 랜덤 인덱스를 샘플링하는 것으로 축소됩니다.

명백하게, 이 방법은 확장되지 않습니다. stream 은 수십억 개의 요소들이 있고, 우리는 그들을 메모리에 보관하고 싶지 않고 종종 그럴 수 없습니다. 게다가, 우리는 근본적으로 분리된 두 단계로 문제를 해결합니다. 첫 번째는 요소들의 배열을 만듭니다, 그런 뒤 우리는 무작위로 하나를 선택합니다. 이것은 streaming 같은 문제에 대해서 자연스러운 해결책이 아닌 것 같이 보입니다. 

Random Tags

Sorting

그래도 당분간 이 아이디를 생각해 봅시다. stream 의 모든 요소가 이미 저장되었다면, 우리는 랜덤 하게 정렬할 수도 있을 것입니다. 이렇게 하기 위해, 각 요소에 random tag 를 할당합니다, 이 태그는 0 과 1 사이의 랜덤 수입니다. 그 뒤 우리는 random tag 로 정렬하고 k 개의 가장 작은 아이템을 유지합니다.

물론, 이것은 더 이상 확장되지 않습니다. 또한 공간 요구사항도 전혀 개선되지 않습니다. 우리는 근본적으로 그것을 정렬하기 위해서 stream 을 복제합니다.

 

Reservoir

그러나, 위의 해결법에는 명백한 병목이 있습니다. 우리는 전체 stream 을 정렬합니다, 실제로는 오직 k 요소에만 관심이 있더라도 말이죠. 수많은 경우, k 는 stream 의 총요소의 수 보다 크게 작을 것입니다, 그래서 우리는 많은 불필요한 작업을 하고 있습니다.
이것을 향상시키기 위해서, k=1 일 때를 생각해 봅시다. 우리가 오직 한 개의 랜덤 요소만 다룬다면, 우리는 가장 작은 tag 만으로 요소를 추적해야 합니다. stream 을 반복하면서 다른 요소들은 버려질 수 있습니다.
임의의 k 개 대해서는, 우리는 가장 작은 tag 를 가진 k 개의 reservoir 를 추적해야 합니다. 단순히, 우리는 현재 요소의 random tag 와 reservoir 에 있는 요소의 random tag 를 비교할 수 있습니다. 만약 필요한 경우, 가장 큰 tag 를 가진 요소가 교체됩니다.

Heaps

이것은 작동합니다, 그러나 이 단계에서 문제는 더 나은 복잡도를 위해서 heap 을 사용해야 합니다. Heap 은 효율적인 방법으로 k 개의 가장 작은 요소들을 유지하는 문제를 정확하게 해결합니다. 이 해결법은 더 낫습니다:우리는 추가 공간이 필요 없고, 새 요소를 처리할 때, 우리는 기껏해야 O(logk) 작업을 수행해야 합니다.

 

새로운 해결법의 추가적인 장점은 stream 의 각 단계 이후에 사용가능한 유효한 샘플들을 가진다는 것입니다. 이것은 stream 이 무한정 계속되는 어플리케이션에서 샘플링 기술을 사용하는 것을 가능하게 해 줍니다. 예를 들어, web server 를 생각해 봅시다. 이 web server 는 요청을 받고 언제든지 이 요청의 샘플을 제공해야 합니다. 유저가 서버로 데이터를 더 보내면, 샘플은 변합니다. 그러나 언제든지 서버는 임의의 샘플을 제공할 수 있습니다, 모든 요청을 추적하지 않고서도요.

 

Adapting Probabilities

우리가 도달한 해결법은 좋습니다, 그러나 우리는 더 잘할 수 있습니다. 로그 인자(logrithmic factor) 를 상수로 줄일 수 있습니다. 이제 random tag 아이디어를 버립니다만 여전히 k 요소의 reservoir 를 사용합니다.

reservoir 를 특정 방법으로 구성하는 대신에, 즉, heap 을 사용하는 식으로, 우리는 Array 를 사용하려 합니다. stream 을 처리할 때, reservoir 에 있는 아이템을 특정 확률로 교체합니다. 이 확률은 stream 을 반복하면서 계속해서 조정됩니다[1].

기본 케이스 k=1 으로 다시 가봅시다. 이 요소를 샘플링하기 위한 최종 알고리즘은 다음과 같이 작동합니다:

• 첫 번째 요소를 reservoir 의 요소로 저장합니다.
• i 번째 요소에 대해서, 1/i 를 reservoir 요소로 합니다.

내가 찾은 아주 우아한 알고리즘입니다. 이것은 놀라울 정도로 간단하고, 완벽한 복잡도를 가지지만, 그것이 작동하는 것은 약간 마법처럼 보입니다. 몇 가지 예제를 생각해 보면, 이 처럼 확률을 조정하는 것이 잘 되는 것 같습니다. 예를 들어, 아래처럼 3 개의 요소로 된 stream 을 처리한다면:

1. 첫 번째 요소를 저장합니다.
2. 두 번째 요소를 1/2 확률로 저장합니다. 이제 두 요소는 reservoir 내에서 동일한 확률을 가집니다.
3. 세 번째 요소를 1/3 확률로 저장합니다. 이전 2개 요소 또한 선택되는 최종 확률로 (1/2)*(2/3)=1/3 를 가집니다.

아래의 시각화는 이것을 보여줍니다. 원은 stream 의 요소를 나타냅니다.

조정 확률 알고리즘의 시각화

 

Proof

유도에 의해서 이것이 임의의 요소 개수에도 작동한다는 것이 밝혀졌습니다.

Base case: 이 알고리즘은 n=1 에서 쉽게 작동합니다.

Induction assumption: n 개의 stream 에 대해서, 모든 요소들은 최종적으로 1/n 확률로 선택됩니다.

Inductive step: n→n+1. 우리는 n+1 요소의 stream 에 대해 보여주고 싶습니다, 모든 요소는 여전히 동일하게 1/(n+1) 의 확률로 샘플링됩니다.

알고리즘은 1/(n+1) 의 확률로 stream 의 다음 요소를 선택하라고 합니다. 유도 가정(induction assumption)에 의해서 모든 다른 요소들은 1/n 의 확률로 현재 reservoir 요소일 수 있습니다.

현재 reservoir 요소는 유지되기 위해 1−1/(n+1)=n/(n+1) 의 확률을 가집니다. 이것은 모든 이전 요소들은 이 단계 이후에 reservoir 요소가 되기 위해 최종 확률로 (1/n)∗(n/(n+1))=1/(n+1) 를 가진다는 의미입니다. 그래서, 모든 요소들은 reservoir 요소로 선택되기 위해 여전히 동일한 확률을 가집니다.

 

Sampling k Elements

만약 우리가 이 기술을 써서 k 개의 랜덤 요소를 선택하고 싶다면, 우리는 알고리즘을 살짝 조정해야 합니다. 다시 우리는 k 요소의 reservoir 를 유지합니다. 이 reservoir 는 stream 의 첫 번째 k 개의 요소로 초기화됩니다.

i > k 에 대해서, i 번째 요소를 처리할 때, 우리는 k/i 확률로 reservoir 에 그 요소를 추가합니다. 만약 우리가 그것을 추가하면, reservoir 중 랜덤 하게 하나와 교체됩니다. 다시 말해, 이 경우 reservoir 의 각 요소는 교체될 확률이 1/k 의 확률을 가집니다. k/i 의 값은 k 개의 아이템을 선택하려는 경우, 주어진 임의의 요소가 균일분포(uniform distribution)으로 부터 샘플링되는 확률이라는 사실에서 유도됩니다.

Full algorithm:

• 첫 k 개의 요소들을 reservoir 요소로 저장합니다.
• i 번째 요소에 대해, 그것을 k/i 확률로 reservoir 에 추가합니다. 이것은 reservoir 에서 랜덤 하게 선택된 요소로 교체됩니다.

알고리즘은 증명은 다시 유도에 의해 나옵니다. k≠1 인 경우 산술이 조금 더 까다로워지기 때문에, 나는 전체 증명을 부록에 이글의 맨 아래 추가하였습니다.

 

Applications

Sampling From Streams

일반적으로, reservoir sampling 은 stream 을 샘플링할 때나 요소의 수가 얼마나 되는지 모를 때 항상 유용합니다, 이것은 임의의 반복가능한 것으로부터의 샘플링으로 번역됩니다.

Spark 의 작업은 이것을 서명하기에 아주 좋은 예제입니다: 데이터의 stream 에 필터를 적용하고 결과에서 샘플링한다고 해봅시다. 단순한 해결법은 먼저 필터를 실행하고, 그 뒤 요소의 수를 세고, 마지막으로 그 결과를 샘플링하는 데 사용합니다.

그러나, reservoir sampling 을 사용한다면, query optimizer 는 이 모든 것을 하나의 단계로 압축할 수 있습니다. 아이템이 처리될 때, 필터 함수가 먼저 적용됩니다, 그리고 필요한 경우 요소를 reservoir 에 저장할지 여부는 나중에 결정됩니다.

만약 요소들이 디스크로부터 읽혀지고 직접 샘플링된다면, deserialization 과정을 최적화할 수 있을 것입니다. reservoir sampling 선택한 요소만 deserialized 될 필요가 있을 것입니다. Reservoir sampling 은 stream 이 얼마나 많은 요소를 가지는 모르기 때문에 두 어플리케이션 모두에 잘 맞습니다.

 

Database Query Planning

데이터베이스 엔진은 쿼리 실행 방법을 계획합니다. 이것을 하기 위해, 쿼리는 최적화되고 여러 다른 실행 전력이 고려됩니다. 하나를 결정하기 위해서, 우리는 데이터의 하위집합에서 그들을 실행하여 시뮬레이션을 작동시킬 수 있습니다[2].

Reservoir sampling 은 하위집합 같은 것을 샘플링하는 데 사용될 수 있습니다. 데이터가 읽히는 방법에 따라서, 우리는 총데이터가 얼마나 많은지 사전에 알 수 없습니다. 게다가, reservor sampling 은 쿼리의 특정 파트에 대해서만 샘플링 프로세스를 쉽게 추가하는 것도 가능합니다.

Summary

Reservoir sampling 은 요소가 얼마나 많은지 예측하지 못하는 상황에서 우리가 stream 에서 요소들을 샘플링하는 것을 하게 해 줍니다. 최종 해결법은 극도로 간단하면서도 우아합니다. 그것은 멋진 데이터 구조나 복잡한 수학을 요구하지 않고 확률을 조정하는 직관적인 방법을 요구합니다. 그것이 동작하는 것을 증명도 유도에 대해서 배우기에 좋은 예제로 보입니다.

확률 조정의 해결법은 여기에 설명한 문제에 최적입니다. 그러나, 다른 사용 케이스에 대한 다양한 확장이 있습니다. random tag 알고리즘은 그것이 weighted distribution 으로 부터 샘플링 가능하도록 확장될 수 있습니다. 추가적으로 만약 반복적인 인터페이스가 특정 수의 아이템을 건너뛰는 걸 허용한다면, 확률 조정 알고리즘은 더 향상될 수 있습니다. 최종 복잡도는 stream 에 얼마나 많은 요소가 있는지가 아니라 우리가 얼마나 많은 샘플을 원하는가에 따라 달라집니다.

 

References

1. Vitter, J. S. (1985). Random sampling with a reservoir. ACM Transactions on Mathematical Software (TOMS), 11(1), 37-57.
2. Cormode, G. (2017). What is Data Sketching, and Why Should I Care?. Communications of the ACM (CACM), 60(9), 48-55.

 

Appendix

Proof for sampling k elements

 

Base case: 이 알고리즘은 n = k 에 대해서 쉽게 작동합니다.

 

Induction assumption: n 개의 요소를 가진 stream 에서, 그리고 k <= n 임, 모든 요소들은 동일하게 최종 확률 k/n 으로 선택됩니다.

Inductive step:  n→n+1
이전과 동일하게, 알고리즘은 k/(n+1) 의 확률로 stream 의 다음 요소를 선택하라고 합니다. 모든 다른 요소들은 유도과정(induction assumption)에 의해서 k/n 의 확률로 현재 reservoir 요소가 됩니다.

한 요소가 Reservoir 에 있게 될 확률을 계산하기 위해서, 우리는 2 가지 경우를 고려해야 합니다:

1. stream 의 현재 요소가 reservoir 에 전혀 추가되지 않는다.
   1−(k/(n+1))=(n+1−k)/(n+1)
   (역주 : n+1 개의 요소들 중 k 개를 뽑는데, 선택되지 않을 확률이니 1 - (k/(n+1)) 이 됨)
2. (a) 추가되었지만 (b) reservoir 에 있던 요소와 교체되지 않았다.
   (a): k/(n+1)
   (b): 1−(1/k)=(k−1)/k
   (역주 : n+1 의 stream 에서 뽑혔다고 가정하므로 k/(n+1)이고, 이렇게 뽑혔을 때 기존 reservoir 에 들어있는 k 개의 요소들 중 하나로 선택되지 않은 경우를 나타내기 위해서 1-(1/k) 로 둠. 이 두 가지 경우는 연속적으로 일어나기 때문에 곱하여서 확률을 계산함)
3. Joint probability: (k/(n+1))∗((k−1)/k)=(k−1)/(n+1)
   (a) 와 (b) 의 곱한 결과임

이 두 경우를 더 합니다. 이 둘은 서로 개별적인 케이스기 때문입니다:
(n+1−k)/(n+1)+(k−1)/(n+1)=n/(n+1)

이것이 reservoir 에 남아있는 요소들의 확률입니다. 마지막으로, 각 이전 요소들은 k/n 확률로 처음부터 reservoir 에 있었습니다(역주 : Induction assumption 참고). 이전 단계는 현재 단계와는 독립적입니다, 그래서 우리는 두 개의 확률을 곱해야 합니다:
(n/(n+1))∗(k/n)=k/(n+1)

이것이 바로 우리가 도달하고 싶었던 곳입니다. 모든 요소들은 reservoir 에서 여전히 동일한 최종 확률을 가집니다.

 

---

Reservoir Sampling

Difficulty Level : Hard, Last Updated : 21 Oct, 2021

출처2 : https://www.geeksforgeeks.org/reservoir-sampling/

Reservoir sampling 은 n개의 아이템 리스트에서 k 개를 무작위로 선택하기 위한 랜덤 알고리즘의 한 종류입니다. 일반적으로 n 은 메인 메모리에 들어가지 못할 정도로 충분히 큰 개수 입니다. 예를들면, 구글과 페이스북의 검색 질의 목록입니다. 우리는 큰 수의 배열(또는 stream)가 주어집니다, 그리고 1 <= k <= n 에서 k 개의 숫자를 무작위로 선택하는 효율적인 함수를 작성해야 합니다. 입력 배열을 stream[] 라 둡시다.

 

간단한 해결법은 최대 k 크기의 reservoir[] 배열을 만드는 것입니다. stream[0..n-1] 에서 무작위로 아이템을 하나씩 선택합니다. 만약 선택된 아이템이 이전에 선택된 것이 아니라면, reservoir[] 에 넣습니다. 아이템이 이전에 선택되었나 안되었나 확인하기 위해서, 우리는 reservoir[] 을 검색해야합니다. 이 알고리즘의 시간 복잡도는 O(k^2) 일 것입니다. 이것은 k 가 크다면 비쌀 것입니다. 또한, 입력이 stream 형태인 경우에 효율적이지 않습니다.

 

O(n) 시간에 완료할 수 있습니다. 이 해결법은 stream 형태의 입력에 대해서도 잘 맞습니다. 아이디어는 이 글과 유사합니다. 다음은 알고리즘의 스텝입니다.
1). reservoir[0..k-1] 을 만들고 첫번째 k 을 stream[] 에 복사합니다.
2). 이제 (k+1) 번째 아이템 부터 n 번째 아이템까지 모든 아이템을 하나씩 고려합니다.
   a). 0 에서 i 까지의 랜덤 수를 생성합니다. 여기서 i 는 stream[] 에서 현재 아이템의 인덱스 입니다. 이제 랜덤 수 j 를 생성해봅시다.
   b). 만약 j 가 0~k-1 범위안에 있으면, reservoir[k] 를 stream[i] 로 교체합니다.

아래는 위의 알고리즘의 구현입니다.

// 아이템 stream 으로 부터 k 개의 아이템을 무작위로 선택하기 위한 효율적인 프로그램 
#include <bits/stdc++.h> 
#include <time.h> 
using namespace std; 
// 배열을 출력하기 위한 유틸리티 함수 
void printArray(int stream[], int n) 
{ 
	for (int i = 0; i < n; i++) 
		cout << stream[i] << " "; 
	cout << endl; 
} 
// stream[0..n-1] 에서 k 개의 아이템을 무작위로 선택하는 함수
void selectKItems(int stream[], int n, int k) 
{ 
  int i; // stream[] 의 요소에 대한 인덱스
  // reservoir[] 는 출력 배열입니다. stream[] 의 맨앞쪽 k 개 요소들로 초기화 합니다.
  int reservoir[k]; 
  for (i = 0; i < k; i++) 
    reservoir[i] = stream[i]; 
  // 우리가 프로그램을 실행시킬 때 마다 동일한 결과를 얻지 않게 하기 위해서 다른 seed 를 사용함
  srand(time(NULL)); 
  // (k+1) 번째 요소에서 n 번째 요소까지 반복합니다.
  for (; i < n; i++) 
  { 
    // 0~i 사이의 랜던 인덱스를 선택합니다.
    int j = rand() % (i + 1); 
    // 만약 무작위로 선택한 인덱스가 k 보다 작다면, 
    // 그 인덱스에 있는 요소를 stream 에 있는 새로운 요소로 교체합니다.
    if (j < k) 
      reservoir[j] = stream[i]; 
  } 
  cout << "Following are k randomly selected items \n"; 
  printArray(reservoir, k); 
} 
// Driver Code 
int main() 
{ 
  int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; 
  int n = sizeof(stream)/sizeof(stream[0]); 
  int k = 5; 
  selectKItems(stream, n, k); 
  return 0; 
} 
// This is code is contributed by rathbhupendra