문제 설명
어떤 데이터 $ E_i \, (1 \le i \le N) $ 스트림이 있는데 시점 $t$ 에 $E_t$ 를 볼 수 있고 스트림의 총 길이 $N$ 은 미리 알 수 없다. 각 $E_i$ 에 가중치 $w_i$ 가 주어지고 우리는 가중치에 비례해 데이터를 샘플링 하고 싶다.
즉, 총 가중치 $ W = \sum_{k \le N} w_k $ 로 모든 데이터를 본 시점에 랜덤한 샘플 $ E_j $ 를 $ w_j / W $ 의 확률로 뽑고자 한다.
Weighted Reservoir Sampling
Weighted Reservoir Sampling 알고리즘은 현재 선택된 샘플 $R$ 과 가중치 합 $w_{sum}$ 을 저장하는 Reservoir $\mathcal{R} = \{ R,\,w_{sum} \} $ 를 들어오는 데이터에 대해 순차적으로 업데이트하는 방식으로 동작한다.
알고리즘
Reservoir를 초기화한다.
$\mathcal{R} \leftarrow \{ \emptyset,\, 0 \} $
스트리밍 데이터 $E_i$ 와 해당 가중치 $w_i$를 가지고 다음의 함수를 통해 Reservoir를 업데이트한다.
$\textbf{update}(\,E_i,\,w_i\,):$
$\qquad w_{sum} \leftarrow w_{sum} + w_i $
$\qquad \zeta \leftarrow rand() $ // $\text{uniform random [0…1]}$
$\qquad \textbf{if}\, (\, \zeta < w_i / w_{sum\,} ):$
$\qquad\qquad R \leftarrow E_i $
수학적 증명
위 알고리즘이 원하는대로 동작하는지, 즉 N개의 데이터를 처리했을 때 $ w_j / \sum_{k \le N} $ 의 확률로 $E_j$를 샘플링 한게 맞는지 귀납적으로 증명해보자.
우선 N=1 인 경우 $E_1$을 $w_1/w_1 = 1$ 의 확률로 선택한다. ($w_1$가 0인경우 0의 확률로 선택)
스텝 $i$에서 $E_i$ 를 처리하기 전에 현재 Reservoir가 $E_j$ 를 $w_j / \sum_{k < i} w_k$ 의 확률로 선택하여 $ \{ E_j,\,\sum_{ k < i w_k} \}$ 인 상태라고 가정하자.
위 업데이트 알고리즘에 따라 $E_i$는 다음의 확률로 선택된다.
\[\frac{w_i}{\Sigma_{k < i} w_k + w_i} = \frac{w_i}{\Sigma_{k \le i} w_k}\]반대로 기존의 선택된 샘플 $E_j$는 다음의 확률로 Reservoir에 남는다.
\[1 - \frac{w_i}{\Sigma_{k < i} w_k + w_i} = \frac{(\Sigma_{k \le i} w_k) - w_i}{\Sigma_{k \le i} w_k} = \frac{\Sigma_{k < i} w_k}{\Sigma_{k \le i} w_k}\]$E_j$가 기존에 $w_j / \sum_{k < i} w_k$의 확률로 선택되어 있었고 스탭 $i$가 처리되면 $E_j$는 최종적으로 다음과 같은 확률로 선택된다.
\[\Big( \frac{w_j}{\Sigma_{k < i} w_k} \Big) \Big( \frac{\Sigma_{k < i} w_k}{\Sigma_{k \le i} w_k} \Big) = \frac{w_j}{\Sigma_{k \le i} w_k}\]결과적으로 $E_i$ 또는 $E_j$가 정확한 확률로 선택되게 된다.
Reservoir 합치기
Reservoir $ \mathcal{R_1} $ 이 $ \{ E_i,\, \Sigma_{k \le n} w_k \} $ 인 상태이고 $ \mathcal{R_2} $ 가 $ \{ E_j,\, \Sigma_{k \le m} w_k \} $ 인 상태를 생각해보자. 두 Reservoir는 각각 $E_i,\, E_j$ 를 $ w_i / \Sigma_{k \le n} w_k $, $ w_j / \Sigma_{k \le m} w_k $ 의 확률로 샘플링한 정상적인 상태다.
Reservoir $ \mathcal{R_1} $ 에 대해 $ \mathcal{R_2}.R $ 과 $\mathcal{R_2}.w_{sum}$ 으로 업데이트 함수를 호출하면 어떻게 될까 ?
$ \mathcal{R_2} $ 의 샘플 $E_j$ 가 다음의 확률로 선택되거나
\[\Big( \frac{w_j}{\Sigma_{k \le m} w_k} \Big) \Big( \frac{\Sigma_{k \le m} w_k}{\Sigma_{k \le n} w_k + \Sigma_{k \le m} w_k} \Big) = \frac{w_j}{\Sigma_{k \le n} w_k + \Sigma_{k \le m} w_k}\]$ \mathcal{R_1} $ 의 샘플 $E_i$ 가 다음의 확률로 선택된다.
\[\Big( \frac{w_i}{\Sigma_{k \le n} w_k} \Big) \Big(1 - \frac{\Sigma_{k \le m} w_k}{\Sigma_{k \le n} w_k + \Sigma_{k \le m} w_k} \Big) = \Big( \frac{w_i}{\Sigma_{k \le n} w_k} \Big) \Big( \frac{\Sigma_{k \le n} w_k}{\Sigma_{k \le n} w_k + \Sigma_{k \le m} w_k} \Big) = \frac{w_i}{\Sigma_{k \le n} w_k + \Sigma_{k \le m} w_k}\]결과적으로 어떤 Reservoir의 결과 샘플과 가중치의 합으로 다른 Reservoir를 업데이트하는 과정은 독립적인 두 스트리밍 데이터를 모두 보고 샘플링한 결과와 동일하다. 샘플 $\{ E, w \}$ 을 데이터 1개를 처리한 Reservoir로 취급할 수 있다.
결론
- Weighted Reservoir Sampling은 길이를 알 수 없는 스트리밍 데이터에 대해 공간 복잡도 O(1)으로 가중치 샘플링을 할 수 있다.
- 각 데이터를 처리하는 과정은 시간복잡도 O(1)이다.
- 독립적으로 진행된 두 샘플링 결과를 쉽게 합칠수 있다. (분할 정복)
참조
http://cwyman.org/papers/rtg2-chapter22-preprint.pdf
https://agraphicsguynotes.com/posts/understanding_the_math_behind_restir_di/#weighted-reservoir-sampling-wrs