Reservoir Sampling Algorithm - 순차적으로 한 번에 하나의 샘플만 볼 수 있고 전체 샘플 개수를 모르는 상황에서 무작위 추출을 하는 방법

Reservoir sampling을 알려준 연습 문제 (출처: Mitzenmacher, M., & Upfal, E. (2017).  Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis . Cambridge university press.)

왜 이런 설정에서 무작위 추출을 할 수 있는 것이 중요할까? 

오늘은 확률 기법 수업의 숙제로 받은 연습문제를 풀다가 재미있는 알고리즘을 알게 되어 글을 쓰게 되었습니다. 보통 random sampling(무작위 추출)과 관련된 문제를 풀 때면 우리는 주머니에 들은 여러 개의 공 중에 하나의 공을 뽑는 것처럼 모든 샘플을 모아 두고 거기서 하나를 공평하게 뽑는 상상을 합니다. 하지만 항상 모든 샘플에 대한 접근이 가능한 것도 아니고 샘플의 개수가 총 몇 개인지도 모르는 경우도 있습니다. 예를 들어, 메모리가 제한적인 기기를 생각해보지요. 모든 샘플을 다 저장해둔 후 총샘플의 개수를 알고 각각의 샘플을 1/(샘플의 총 개수)의 확률로 무작위 추출을 하려면 샘플의 개수만큼 많은 메모리가 필요합니다. 하지만 메모리는 비싸지요. (왜 제가 32기가짜리 아이패드를 샀겠습니까. 😞) 단 하나의 샘플을 저장할 수 있는 메모리로 무작위 추출을 할 수 있다면 얼마나 좋을까요. 

무료 버블티 당첨자 뽑기 예시 

순차적으로 각 샘플에 접근할 수 있고 메모리가 한 샘플만 저장할 수 있는 예를 생각해봅시다. 예를 들어, 우리가 버블티 가게를 운영하고 있고 하루에 단 한 명에게만 ⭐️타피오카 펄이 들어간 얼그레이 밀크티 라지 사이즈⭐️를 한 잔 무료로 주는 이벤트를 한다고 생각해봅시다. 그리고 그 한 명은 공평하게 1/(응모한 사람 수)의 확률로 뽑혀야 합니다. 안 그러면 주작으로 별점 테러를 받고 망하겠지요. 그런데 응모하는 사람의 응모권을 넣을 수 있는 상자가 아주 작아서 종이가 딱 한 장밖에 안 들어가는 것입니다. 상자가 충분히 컸다면 모든 사람의 응모권을 한데 모으고 와랄랄라 섞은 다음에 한 장 뽑았겠지만, 이 상자에는 단 한 장밖에 들어가지 않는 것입니다. 아쉽지만 상자에 들어가지 못한 응모권은 자리가 없어서 바로 불태워야겠습니다. 이 한 장만 넣을 수 있는 상자로 과연 공평하게 당첨자를 정할 수 있을까요? 그걸 가능하게 해주는 방법이 바로 Reservoir Sampling Algorithm입니다.  

문제의 수학적 표현

이 문제를 수학적으로 표현하고 풀어봅시다. 총 $N$개의 샘플이 있고 그것들을 $S_1, S_2, \ldots, S_N$ 이라고 각각 이름을 붙이기로 하지요. 그리고 각 단계에서 메모리에 저장된 값을 $X_1, X_2, \ldots, X_N$이라고 부릅시다. 응모한 사람의 수가 총 N명이고 각각의 응모권에 $S_1, S_2, \ldots , S_N$라는 이름을 붙인 것입니다. 그리고 응모권이 제출될 때마다 상자에 들어있는 샘플의 값을 $X_1, X_2, \ldots, X_N$라고 부른 것이지요. $N$개의 샘플($N$개의 응모권) 중 하나를 $1/N$확률로 고르고 싶고, 샘플은 순차적으로 접근(줄 서서 한 명씩 응모)할 수 있으며 여태까지 관찰한 샘플(응모권) 중에 단 하나만 메모리(작은 상자)에 저장될 수 있습니다. 맨 처음에는 첫 샘플인 $S_1$을 관찰합니다. 어차피 아직까지는 하나 밖에 샘플이 없으니 $S_1$을 일단 메모리에 넣도록 하지요. 그다음에는 $S_2$를 관찰하고 메모리에 $S_2$를 저장할지 아니면 기존 값인 $S_1$을 유지할지 결정합니다. 그다음에도 마찬가지로 $S_3$을 관찰하고 메모리에 $S_3$을 저장할지 아니면 기존 값을 유지할지 결정하는 것입니다. 같은 방식으로 $S_4, \ldots, S_N$에 대해서도 관찰하고 저장할지 말지 결정하는 것입니다. 이때 마지막에 메모리에 남아있는 샘플이 $1/N$의 확률로 $N$개의 샘플 중 무작위로 뽑힌 결과가 되도록 하려면 각 단계에서 새로운 샘플과 기존에 메모리에 들어있던 값 중에 무엇을 어떻게 선택해야 할까요? 즉, $X_N$이 $S_i$가 될 확률이 아래처럼 항상 $1/N$인 균등 분포를 따랐으면 하는 것이지요.  

 

$X_N = S_i$ with probability of $1/N$    $\forall i=1,2,\ldots, N$.

 

답이 궁금하신 분은 아래 섹션을 생략하고 그다음 섹션인 "Reservoir Sampling 알고리즘이 무작위 추출을 한다는 증명"으로 바로 넘어가시면 됩니다.

Naïve Approach for Intuition 직관을 위한 순진한 접근법 

가장 간단한 예시로 이미 메모리에 들어있던 샘플을 $1/2$의 확률로 유지하고, 나머지 $1/2$의 확률로 새 샘플로 기존 샘플을 대체한다고 해봅시다. 그럼 첫 번째로 들어온 샘플인 $S_1$이 최종적으로 추출된 샘플이 되려면 그 이후에 $N-1$개의 샘플 $S_2, S_3, \ldots, S_N$이 들어올 때마다 $1/2$의 확률로 경쟁에서 살아남아야 합니다. 첫 샘플이 마지막까지 메모리에 남아있을 확률은 $(1/2)^{N-1}$이 되겠지요. 반대로 마지막 샘플인 $S_N$을 비교해볼까요? 마지막 샘플은 $N$번째 단계에서 $1/2$의 확률로 메모리에 들어갈지 아닐지 결정이 됩니다. 그럼 최종적으로 메모리에 남아있을 확률도 $1/2$이 됩니다. 좀 더 일반적으로 $1/2$이 아니고 $p$의 확률로 기존 샘플을 유지한다고 하면 어떨까요? 첫 번째 샘플 $S_1$이 최종적으로 추출될 확률은 $p^{N-1}$이 되고 마지막 샘플이 최종적으로 추출될 확률은 $p$로, 더 나중 단계에 관찰된 샘플이 더 추출될 확률이 높아집니다. 응모권을 마지막에 낸 사람이 가장 당첨확률이 높아지는 식인 것이지요. 그럼 더 나중 단계에 관찰되는 샘플일수록 기존 샘플을 대체하고 메모리에 들어갈 확률을 점점 낮추어서 페널티를 주어야겠지요? 즉, $i$번째 단계에서 $i$번째 샘플이 메모리에 들어갈 확률을 $p(i)$라고 정의하면, $p(i)$는 $i$에 대해 감소 함수가 되어야 합니다. 여러 가지 감소 함수 중에 무엇을 $p(i)$로 사용해야 모든 샘플이 최종적으로 추출될 확률이 같아질까요?

Reservoir Sampling 알고리즘이 무작위 추출을 한다는 증명

Reservoir Sampling 알고리즘은 $i$ 번째 단계에서 $1/i$의 확률로 새 샘플인 $S_i$를 메모리에 저장하고, $(i-1)/i$의 확률로 기존에 저장되어 있던 값($i-1$번째 단계에서 뽑힌 값)을 유지하라고 말합니다. 그럼 이런 방식이 왜 결국 무작위 추출과 같은 결과를 만드는지 증명해볼까요? 

 

수식으로 보는 것이 편하신 분들은 아래 이미지를 참조하시면 될 것 같습니다. 

 

Reservoir Sampling이 무작위 추출을 한다는 증명

위 증명을 한국어로 조금 풀어 설명해봅시다. Reservoir sampling 알고리즘을 식으로 표현하면, 모든 $i=2,3,\ldots, N$에 대해 새로 관찰된 확률이 메모리에 들어가질 확률은 $\Pr [X_i=S_i]=1/i$입니다. 자연스레 이전에 메모리에 들어있던 값이 유지될 확률은 $\Pr [X_i=S_{i-1}]=1-1/i={i-1}/i$이 되겠지요. 첫 샘플인 $S_1$은 무조건 선택되므로 $X_1=S_1$이라는 초기 조건이 있습니다. 그럼 임의의 $j$번째 샘플 $S_j$가 마지막에 추출될 확률 $\Pr [X_N=S_j]$을 구해봅시다. $j$번째 샘플이 마지막인 $N$단계까지 남아있다는 것은 $j$번째 단계부터 $j+1, j+2, \ldots, N-1, N$번째에서도 계속 선택된 것이겠지요. 따라서, 구하고자 하는 확률은 $\Pr [X_N=S_j]=\Pr [X_j = X_{j+1} = \ldots = X_N=S_j]$로 풀어쓸 수 있습니다. 직관적으로 생각해보면 $j$번째 단계에서 선택될 확률은 $\frac {1}{j}$이고, 그 이후 $i$번째 단계$(j <i\leq N)$에서는 $\frac {i-1}{i}$의 확률로 $S_j$가 선택됩니다. 따라서 $\frac {1}{j}\frac {j}{j+1}\frac {j+1}{j+2}\ldots\frac {N-1}{N}=\frac {1}{N}$이 됩니다. 즉 임의의 샘플 $S_j$에 대해 샘플이 추출될 확률이 모두 $1/N$으로 같으니 무작위 추출을 하는 것과 같은 결과가 나오게 됩니다.

 

조금 더 수학적으로 엄격하게 표현해보자면 Law of Total Probability(전체 확률의 정리)에 의해 아래와 같이 풀어쓸 수 있습니다. $$ \Pr [X_N=S_j] = \Pr[\{X_N=S_j\} \cap \{X_j=S_j\}] + \Pr [\{X_N=S_j\} \cap \{X_j\neq S_j\}]$$ $$= \Pr [X_j=S_j]\Pr [X_N=S_j|X_j=S_j] + \Pr [X_j\neq S_j]\Pr [X_N=S_j|X_j\neq S_j]$$ $j$번째 단계에서 $S_j$가 선택되지 않을 경우 $X_N$은 $S_j$가 될 수 없으므로 $\Pr [X_N=S_j|X_j\neq S_j]=0$이 되고, 위 식은 아래와 같이 정리됩니다. $$\Pr [X_N=S_j]=\Pr [X_j=S_j]\Pr [X_N=S_j|X_j=S_j]=\frac {1}{j}\Pr [X_N=S_j|X_j=S_j]$$ 같은 방법으로 $j+1$번째 단계에 대해서도 아래와 같이 전개해볼 수 있습니다. $$\Pr [X_N=S_j|X_j=S_j] = \frac {1}{j}\Pr [X_N=S_j|X_j=S_j] $$ $$= \frac {1}{j}\Pr [X_{j+1}=S_j]\Pr [X_N=S_j|X_j=S_j, X_{j+1}=S_j] $$ $$+ \frac {1}{j}\Pr [X_{j+1}\neq S_j]\Pr [X_N=S_j|X_j=S_j, X_{j+1}\neq S_j]$$ $$= \frac {1}{j}\frac {j}{j+1}\Pr [X_N=S_j|X_j=X_{j+1}=S_j]$$ 이 과정을 $N$번째 단계까지 계속 반복하면 $\Pr [X_N=S_j]=\frac {1}{j}\frac {j}{j+1}\frac {j+1}{j+2}\ldots\frac {N-1}{N}=\frac {1}{N}$이라는 결과를 얻게 됩니다.

 

이 문제에 대해서는 직관적인 풀이로 쉽게 증명을 할 수 있지만 조금 문제가 복잡해지고 직관을 적용할 수 없는 경우에는 전체 확률의 정리를 이용해 문제를 우리가 아는 용어로 해체하는 것이 중요해집니다. 그래서 조금 번거롭지만 자세한 설명을 덧붙이고 글이 길어지게 되었네요. 

꼬리글

이번 포스팅에서는 메모리가 제한된 순차적으로 입력되는 샘플에 대해 무작위 추출을 할 수 있는 Reservoir sampling 알고리즘을 알아보고 증명을 해보았습니다. 증명 중에 사용된 전체 확률의 정리는 여러 확률 변수가 개입된 Joint Distribution(결합 확률분포)를 매개변수에 대한 간단한 식으로 전개하는데 아주 중요한 정리입니다.