Reservoir Sampling

Ein Kundenservice-Modell lernt anhand von Nachrichten, die eine nach der anderen eintreffen. Du möchtest einige davon für spätere Wiederholungen aufbewahren, hast aber nur vier Speicherplätze. Du weißt auch nicht, wie viele Nachrichten noch kommen: zwanzig oder zwei Millionen.

Die ersten vier behalten? Dann kennt der Speicher nur den Anfang. Immer die letzten vier behalten? Dann kennt er nur das Ende. Eine faire Auslosung „vier aus allen“ würde verlangen, alles zu speichern oder die Zahl der Nachrichten im Voraus zu kennen. Die Frage lautet: Wie gibt man bei fester Zahl von Plätzen und unbekannter Länge des Stroms jeder Nachricht dieselbe Chance?

Reservoir Sampling ist ein Verfahren, mit dem man während eines einzigen Durchgangs durch Daten, deren Anzahl wir nicht im Voraus kennen, eine Zufallsstichprobe fester Größe führt. Nach jeder weiteren Nachricht enthält der Speicher, hier Reservoir genannt, eine faire Zufallsstichprobe von allem, was bis dahin eingetroffen ist. Die einfachste Version, Algorithm R, beschreibt Vitter, Random Sampling with a Reservoir, §2 und schreibt sie Alan Waterman zu.

Das Rezept in zwei Schritten

1. Die ersten vier Nachrichten kommen ohne Auslosung in den Speicher.
2. Die Nachricht Nummer $t$ (die fünfte, die sechste und jede weitere) gelangt mit der Chance $4/t$ in den Speicher. Gelangt sie hinein, ersetzt sie eine der vier gespeicherten, die zufällig ausgewählt wird.

Die fünfte Nachricht kommt also mit der Chance 4/5 hinein, die hundertste mit der Chance 4/100. Neue Nachrichten haben eine immer kleinere Chance hineinzukommen, aber die alten waren schon viele Male der Gefahr ausgesetzt, hinausgeworfen zu werden, und diese beiden Effekte gleichen sich genau aus. Prüfen wir das nach der fünften Nachricht. Sie kommt mit der Chance 4/5 hinein. Die erste Nachricht fällt nur dann heraus, wenn die fünfte hineingekommen ist (4/5) und ausgerechnet ihren Platz getroffen hat (1/4), also mit der Chance 1/5. Sie bleibt mit der Chance 4/5: derselben, die auch die fünfte hat. Nach $t$ Nachrichten ist jede von ihnen mit der Chance $4/t$ im Speicher.

Gleiche Chance ist keine Garantie

Im Experiment hat der Strom 20 Nachrichten. Achtzehn betreffen die Lieferung, und zwei, die neunte und die fünfzehnte, betreffen Rücksendungen. Jeder Start lässt einen solchen Strom 2000-mal durchlaufen und zählt, wie oft eine Position am Ende im Speicher geblieben ist. Die Auslosungen sind echt, daher weichen die Ergebnisse jedes Mal um den Bruchteil eines Prozents voneinander ab.

Bei Reservoir Sampling liegt jeder Balken bei etwa 20%, also 4/20. Zugleich bleibt in den meisten Durchläufen keine der beiden Rücksendungen im Speicher. Der genaue Wert ist 3060/4845, also etwa 63%: So viele von allen Vierergruppen, die sich aus 20 Nachrichten auswählen lassen, bestehen ausschließlich aus den achtzehn Nachrichten zur Lieferung. Das Verfahren ist fair gegenüber einzelnen Nachrichten, achtet aber nicht darauf, dass jede Kategorie einen Vertreter hat.

Wo das eine Rolle spielt

Beim Lernen mit Wiederholungen dient Reservoir Sampling mitunter als Verfahren zum Schreiben in den Puffer: Man muss weder die Länge des Stroms noch die Grenzen zwischen den Aufgaben kennen. Chaudhry et al., Continual Learning with Tiny Episodic Memories, §2, Algorithmus 2 verwenden es genau so. In ihren Experimenten mit Bildaufgaben bewährte es sich gut, außer bei sehr kleinen Speichern, bei denen frühere Klassen aus dem Puffer verschwanden; besser schnitten dann Strategien ab, die auf eine gleichmäßige Vertretung der Klassen achten (§4.4). Das ist ein Ergebnis für die Bildklassifikation, nicht für LLMs.

Der Algorithmus selbst betrifft nicht das maschinelle Lernen. Vitters Arbeit von 1985 beschreibt das zufällige Auswählen von Datensätzen von einem Magnetband unbekannter Länge und schlägt schnellere Varianten vor, die nicht bei jedem Datensatz losen, sondern berechnen, wie viele Datensätze zu überspringen sind. Die Kundennachrichten und der Strom mit 20 Positionen sind ein eigenes Beispiel.

• Experience Replay braucht einen Puffer mit früheren Beispielen; Reservoir Sampling ist eine der Möglichkeiten zu entscheiden, was hineinkommt.
• Continual Learning geht vom Lernen aus einem Datenstrom bei begrenztem Speicher aus, also von einer Situation, in der sich nicht alles aufbewahren lässt.
• Catastrophic Forgetting [Polski] kann sich verstärken, wenn aus einem kleinen Speicher alle Beispiele einer früheren Kategorie herausfallen.

Text und Illustration wurden mit KI-Unterstützung erstellt. Der Nachrichtenstrom und die Demonstration sind ein eigenes vereinfachtes Lernbeispiel; die Illustration ist eine Metapher, kein Schema des Algorithmus.