Jak wylosować uczciwą próbkę ze strumienia, którego końca nie znamy
Reservoir sampling pozwala wybrać równomierną losową próbkę k elementów ze strumienia, nawet gdy z góry nie wiadomo, ile elementów ostatecznie nadejdzie i nie można zapisać ich wszystkich. Najprostsza wersja przechowuje pierwsze k rekordów. Gdy pojawia się element numer j, losuje liczbę od 1 do j i zastępuje jeden z elementów rezerwuaru tylko wtedy, gdy wypadnie wartość z pierwszych k pozycji. Mimo że późne rekordy mają coraz mniejszą szansę wejścia do próbki, wcześniejsze mogą być stopniowo wypierane. Po przetworzeniu dowolnej liczby N rekordów każdy z nich ma dokładnie taką samą szansę k/N na obecność w próbce.
Problem bez drugiego przebiegu
Jeżeli znamy rozmiar zbioru i możemy swobodnie do niego wracać, losowanie próbki jest stosunkowo proste. W strumieniu sytuacja wygląda inaczej. Rekordy przychodzą jeden po drugim, liczba N może nie być znana do samego końca, a pamięć może pomieścić tylko k reprezentantów. Nie da się najpierw policzyć wszystkich rekordów, a potem wrócić i wylosować odpowiednich pozycji, jeśli źródło jest jednoprzebiegowe albo ponowne odczytanie byłoby zbyt drogie.
Reservoir sampling rozwiązuje właśnie ten wariant. NIST opisuje podstawowy algorytm: zachowaj pierwsze k elementów; dla elementu o numerze j>k wylosuj równomiernie M z zakresu 1..j; jeśli M≤k, zastąp element na pozycji M w rezerwuarze. Pamięć potrzebna na próbkę nie rośnie wraz z długością strumienia.
Dlaczego ostatni rekord nie jest pokrzywdzony
Na pierwszy rzut oka metoda wygląda niesprawiedliwie. Pierwszych k elementów wchodzi do próbki automatycznie, podczas gdy element numer milion dostaje szansę tylko k/1 000 000. Sekret polega na tym, że wczesne elementy muszą przetrwać wszystkie późniejsze okazje do zastąpienia.
Dla pojedynczego miejsca w próbce można prześledzić prawdopodobieństwa krok po kroku, a ogólny wynik jest elegancki: po przetworzeniu j elementów każdy z nich ma prawdopodobieństwo k/j, że znajduje się w rezerwuarze. Gdy nadchodzi element j+1, nowy rekord wchodzi z prawdopodobieństwem k/(j+1). Każdy wcześniejszy rekord pozostaje z prawdopodobieństwem k/j pomnożonym przez j/(j+1), co również daje k/(j+1). Po każdym kroku symetria zostaje więc odtworzona.
Nie trzeba nawet podejmować decyzji przy każdym rekordzie
Klasyczny schemat jest prosty, lecz dla gigantycznych strumieni wykonuje losowanie przy każdym kolejnym elemencie. Jeffrey Scott Vitter w pracy z 1985 roku analizował szybsze warianty reservoir sampling. Jego Algorithm Z wybiera, ile rekordów można od razu pominąć, zamiast za każdym razem losować decyzję „wejdzie czy nie wejdzie”. Praca dotyczy właśnie sytuacji, gdy całkowity rozmiar N nie jest wcześniej znany, i pokazuje algorytmy działające w jednym przebiegu przy stałej pamięci zależnej od rozmiaru próbki.
To ważne przypomnienie, że nazwa jednego pomysłu może obejmować rodzinę algorytmów. Najprostsza wersja świetnie tłumaczy zasadę probabilistyczną, a bardziej zaawansowane warianty redukują narzut, gdy przetwarzanych jest bardzo dużo danych.
Gdzie kryje się prawdziwa korzyść
Reservoir sampling nie kompresuje całego zbioru i nie pozwala później odzyskać utraconych rekordów. Rozwiązuje dokładnie określony problem: utrzymuje losową próbkę bez znajomości końcowego N i bez przechowywania całości. To pasuje do logów, telemetrii, potoków zdarzeń i innych sytuacji, w których dane są potencjalnie ogromne lub przychodzą bez końca.
Algorytm pokazuje też szerszą ideę systemów strumieniowych. Czasem nie próbujemy przechować wszystkich informacji, lecz projektujemy stan o stałym rozmiarze, który zachowuje dokładnie tę własność statystyczną, której potrzebujemy. W tym przypadku tą własnością jest równy udział każdego rekordu w losowaniu końcowej próbki.
Ta sama zasada działa dla próbki większej niż jeden element
Reservoir sampling nie ogranicza się do wylosowania pojedynczego rekordu. Dla rezerwuaru o rozmiarze k pierwsze k elementów trafia do pamięci. Gdy pojawia się i-ty element, losujemy pozycję spośród i dotychczas widzianych możliwości; jeśli wybór wskazuje jedną z k pozycji rezerwuaru, nowy element zastępuje dotychczasowy. Po przetworzeniu i rekordów każdy z nich ma takie samo prawdopodobieństwo k/i znalezienia się w próbce. Dzięki temu pamięć zależy od żądanego rozmiaru próby, a nie od długości całego strumienia. To szczególnie użyteczne, gdy dane są generowane na bieżąco albo ich pełne zapisanie byłoby zbyt kosztowne.
Jednoprzebiegowość jest ważniejsza niż samo oszczędzanie pamięci
Gdybyśmy znali długość N i mogli swobodnie wykonać drugi przebieg, problem losowej próbki byłby znacznie prostszy: można wylosować indeksy albo najpierw policzyć elementy, a potem wrócić do danych. Strumień może jednak pochodzić z sieci, czujnika lub logu, którego nie da się przewinąć. Reservoir sampling podejmuje decyzję w momencie pojawienia się rekordu i nigdy nie wymaga ponownego odczytu wcześniejszej części strumienia. To sprawia, że jego ograniczenie pamięciowe ma praktyczne znaczenie: O(k) pamięci idzie w parze z jednym przejściem po danych. Koszt obliczeniowy pozostaje związany z liczbą obserwacji, ale magazyn nie rośnie wraz z N. Algorytm rozdziela więc dwa zasoby, które w naiwnym rozwiązaniu byłyby powiązane: możemy zobaczyć dowolnie długi strumień, zachowując tylko stałej wielkości reprezentatywną próbkę.