저수지 샘플링 Reservoir Sampling

레저보어 샘플링

---

이 알고리즘은 아래와 같은 문제상황에서 사용된다.

 

Data Stream이 있는데 나에게는 한정적인 Memory 가 있고 Data Stream의 크기는 미리 알지못하지만

나는 공평하게 Random Sampling을 전체 Data Stream에서 하고 싶을때 어떻게 할까?

 

정답 부터 말하자면

---

1. 스트림에서 항목을 하나씩 가져옵니다
2. 첫 번째 항목을 선택하여 저장합니다
3. k번째 항목을 선택할 때 1/k의 확률로 선택하고 기존 선택을 대체합니다
   ↔ 모든 데이터에 대해 일정한 확률을 사용하면 마지막 데이터가 데이터셋에 포함될 가능성이 첫 번째 데이터보다 훨씬 더 높아집니다. 첫 번째 데이터는 더 많은 선택 과정을 견뎌야 하기 때문입니다.

---

밑에 수학적인 증명을 보여주기 전에 더 와닫게 예시를 들어보면

 

죄수들이 한줄로 한명씩 문을 통과하는 상황이라 하자

 

오늘은 기분이 좋아 이벤트로 N명의 죄수들이 식사를 하고 식당을 한줄로 나오면서 

식당 출구에 있는 기계가 1명의 죄수들가 지나갈때 마다 어떤 확률로 경고음을 내면 

출구에 있는 철창에 들어가게 된다 -> 기계에 의해 선택받음

 

철창은 1명 크기라서 새로운 죄수가 기계에 의해 선택 받으면 원래 있던 죄수는 철창에서 나와야한다

 

N명의 죄수들이 모두 식사를 마치고 출구를 통과한뒤 마지막으로 철창안에 남아있는 죄수는

감옥에서 풀려나게 된다

반응형

그래서 공평하게 기계가 경고음을 낼 확률을 정하려하는데

50% 확률 1/2라고 해보자

공평할까?

 

식사를 빨리 마친 죄수는 첫번째로 기계를 통과해 철창안에 들어가게 된다

그 후 N-1명의 죄수들이 지나갈텐데

식사를 마지막으로 마친 죄수가 지나갈때 1/2확률로 기계가 선택하면

첫번째로 식사를 마친 죄수보다 너무나 유리하다!

 

그럼 어떻게 해야하냐?

 

첫번째 죄수는 무조건 들어가고

두번째는 1/2 확률로 선택하고

세번째는 1/3 확률로

마지막 죄수는 1/N 확률로 선택되면 된다

그럼 이게 진짜 모든 죄수들이 석방될 확률을 1/N로 공평하게 보장하는가?

 

증명

---

N개 항목의 스트림에서 1개 항목을 선택한다고 가정해 봅시다
k번째 항목이 선택될 확률을 다음과 같이 설정합니다

그리고 임의의 m번째 항목이 들어올 때
현재 선택된 항목이 남을 확률은

따라서 N개의 모든 항목이 보여졌을 때
k번째 항목이 선택될 확률은
P(k=선택됨)=P(k=선택)P(k=N번째까지 생존)=P(k=선택)P(k=k+1 생존)P(k=k+2 생존)...P(k=N번째 생존)

728x90

귀납법에 의한 증명

n 라운드 수에 대한 귀납법

---

귀납법의 Base:
n=k일 때, k번째 항목이 선택될 확률은 처음 보았을 때 선택될 확률과 같습니다:

귀납적 가설:
n=m일 때 가설이 참이라고 가정합니다. 여기서 m≥kk번째 항목이 m 라운드에서 선택될 확률은

 

귀납 단계:
k번째 항목이 n=m+1 라운드에서도 여전히 선택될 확률은
P(k=m 라운드에서 선택)P(k=m+1에서 생존)