Reservoir Sampling

Model obsługi klienta uczy się na wiadomościach, które przychodzą jedna po drugiej. Chcesz zachować kilka z nich do późniejszych powtórek, ale masz tylko cztery miejsca w pamięci. Nie wiesz też, ile wiadomości jeszcze przyjdzie: dwadzieścia czy dwa miliony.

Zostawić pierwsze cztery? Wtedy pamięć zna tylko początek. Trzymać zawsze cztery ostatnie? Wtedy zna tylko koniec. Uczciwe losowanie „czterech z całości” wymagałoby przechowania wszystkiego albo znajomości liczby wiadomości z góry. Pytanie brzmi: jak przy stałej liczbie miejsc i nieznanej długości strumienia dać każdej wiadomości tę samą szansę?

Reservoir Sampling to sposób utrzymywania losowej próbki o stałej wielkości podczas jednego przejścia przez dane, których liczby nie znamy z góry. Po każdej kolejnej wiadomości pamięć, nazywana tu rezerwuarem, zawiera uczciwą losową próbkę wszystkiego, co do tej pory przyszło. Najprostszą wersję, Algorithm R, opisuje Vitter, Random Sampling with a Reservoir, §2, przypisując ją Alanowi Watermanowi.

Przepis w dwóch krokach

1. Pierwsze cztery wiadomości trafiają do pamięci bez losowania.
2. Wiadomość numer $t$ (piąta, szósta i każda następna) dostaje się do pamięci z szansą $4/t$. Jeśli się dostała, zastępuje jedną z czterech zapisanych, wybraną losowo.

Piąta wiadomość wchodzi więc z szansą 4/5, setna z szansą 4/100. Nowe wiadomości mają coraz mniejszą szansę wejścia, ale stare były już wielokrotnie narażone na wyrzucenie, i te dwa efekty dokładnie się równoważą. Sprawdźmy to po piątej wiadomości. Wchodzi z szansą 4/5. Pierwsza wiadomość wypada tylko wtedy, gdy piąta weszła (4/5) i trafiła akurat na jej miejsce (1/4), czyli z szansą 1/5. Zostaje z szansą 4/5: taką samą, jaką ma piąta. Po $t$ wiadomościach każda z nich jest w pamięci z szansą $4/t$.

Równa szansa to nie gwarancja

W eksperymencie strumień ma 20 wiadomości. Osiemnaście dotyczy dostawy, a dwie, dziewiąta i piętnasta, dotyczą zwrotów. Każde uruchomienie przepuszcza taki strumień 2000 razy i liczy, jak często dana pozycja została w pamięci na końcu. Losowania są prawdziwe, więc wyniki za każdym razem różnią się o ułamek procenta.

Przy Reservoir Sampling każdy słupek ma około 20%, czyli 4/20. Jednocześnie w większości przebiegów żaden z dwóch zwrotów nie zostaje w pamięci. Dokładna wartość to 3060/4845, czyli około 63%: tyle spośród wszystkich czwórek wybranych z 20 wiadomości składa się wyłącznie z osiemnastu wiadomości o dostawie. Metoda jest uczciwa wobec pojedynczych wiadomości, ale nie pilnuje, żeby każda kategoria miała przedstawiciela.

Gdzie to ma znaczenie

W uczeniu z powtórkami Reservoir Sampling bywa sposobem zapisu do bufora: nie trzeba znać długości strumienia ani granic między zadaniami. Chaudhry et al., Continual Learning with Tiny Episodic Memories, §2, algorytm 2 używają go właśnie tak. W ich eksperymentach na zadaniach obrazowych sprawdzał się dobrze, z wyjątkiem bardzo małych pamięci, gdzie z bufora znikały wcześniejsze klasy; lepiej wypadały wtedy strategie dbające o równą reprezentację klas (§4.4). To wynik dla klasyfikacji obrazów, nie dla LLM.

Sam algorytm nie dotyczy uczenia maszynowego. Praca Vittera z 1985 roku opisuje losowanie rekordów z taśmy magnetycznej o nieznanej długości i proponuje szybsze warianty, które zamiast losować przy każdym rekordzie wyliczają, ile rekordów pominąć. Wiadomości od klientów i strumień 20 pozycji są własnym przykładem.

• Experience Replay potrzebuje bufora z dawnymi przykładami; Reservoir Sampling jest jednym ze sposobów decydowania, co do niego trafia.
• Continual Learning zakłada naukę ze strumienia danych przy ograniczonej pamięci, czyli sytuację, w której nie da się zachować wszystkiego.
• Catastrophic Forgetting może się nasilić, gdy z małej pamięci wypadną wszystkie przykłady dawnej kategorii.

Tekst i ilustrację przygotowano z pomocą AI. Strumień wiadomości i demonstracja są własnym uproszczonym przykładem edukacyjnym; ilustracja jest metaforą, nie schematem algorytmu.