Reservoir Sampling

Un modelo de atención al cliente aprende de mensajes que llegan uno tras otro. Quieres conservar algunos para repasarlos más adelante, pero solo tienes cuatro espacios en la memoria. Tampoco sabes cuántos mensajes llegarán todavía: veinte o dos millones.

¿Quedarte con los cuatro primeros? Entonces la memoria solo conoce el principio. ¿Guardar siempre los cuatro últimos? Entonces solo conoce el final. Un sorteo justo de «cuatro de entre todos» exigiría guardarlo todo o conocer de antemano el número de mensajes. La pregunta es: ¿cómo dar a cada mensaje la misma probabilidad con un número fijo de espacios y un flujo de longitud desconocida?

Reservoir Sampling es una forma de mantener una muestra aleatoria de tamaño fijo durante una sola pasada por unos datos cuya cantidad no conocemos de antemano. Después de cada nuevo mensaje, la memoria, llamada aquí reservorio, contiene una muestra aleatoria justa de todo lo que ha llegado hasta ese momento. La versión más sencilla, Algorithm R, la describe Vitter, Random Sampling with a Reservoir, §2, que la atribuye a Alan Waterman.

La receta en dos pasos

1. Los cuatro primeros mensajes entran en la memoria sin sorteo.
2. El mensaje número $t$ (el quinto, el sexto y cada uno de los siguientes) entra en la memoria con probabilidad $4/t$. Si entra, sustituye a uno de los cuatro guardados, elegido al azar.

Así, el quinto mensaje entra con probabilidad 4/5 y el centésimo con probabilidad 4/100. Los mensajes nuevos tienen cada vez menos probabilidad de entrar, pero los antiguos ya han estado expuestos muchas veces a ser expulsados, y estos dos efectos se compensan exactamente. Comprobémoslo después del quinto mensaje. Entra con probabilidad 4/5. El primer mensaje sale solo si el quinto entró (4/5) y cayó justo en su lugar (1/4), es decir, con probabilidad 1/5. Se queda con probabilidad 4/5: la misma que tiene el quinto. Después de $t$ mensajes, cada uno de ellos está en la memoria con probabilidad $4/t$.

La misma probabilidad no es una garantía

En el experimento, el flujo tiene 20 mensajes. Dieciocho tratan de entrega y dos, el noveno y el decimoquinto, tratan de devoluciones. Cada ejecución hace pasar ese flujo 2000 veces y cuenta con qué frecuencia cada posición quedó en la memoria al final. Los sorteos son reales, así que los resultados varían cada vez en una fracción de punto porcentual.

Con Reservoir Sampling, cada barra ronda el 20%, es decir, 4/20. Al mismo tiempo, en la mayoría de las ejecuciones ninguna de las dos devoluciones queda en la memoria. El valor exacto es 3060/4845, es decir, alrededor del 63%: esa es la parte de todos los grupos de cuatro elegidos entre 20 mensajes que se compone únicamente de los dieciocho mensajes sobre entrega. El método es justo con cada mensaje por separado, pero no se ocupa de que cada categoría tenga un representante.

Dónde importa

En el entrenamiento con repaso, Reservoir Sampling se usa a veces como forma de guardar en el búfer: no hace falta conocer la longitud del flujo ni los límites entre tareas. Chaudhry et al., Continual Learning with Tiny Episodic Memories, §2, algoritmo 2 lo usan precisamente así. En sus experimentos con tareas de imágenes funcionó bien, salvo con memorias muy pequeñas, donde las clases anteriores desaparecían del búfer; en ese caso daban mejor resultado las estrategias que cuidan una representación igual de las clases (§4.4). Es un resultado para clasificación de imágenes, no para LLM.

El algoritmo en sí no trata de aprendizaje automático. El trabajo de Vitter de 1985 describe el muestreo de registros de una cinta magnética de longitud desconocida y propone variantes más rápidas que, en lugar de sortear en cada registro, calculan cuántos registros saltarse. Los mensajes de clientes y el flujo de 20 posiciones son un ejemplo propio.

• Experience Replay necesita un búfer con ejemplos anteriores; Reservoir Sampling es una de las formas de decidir qué entra en él.
• Continual Learning supone aprender de un flujo de datos con memoria limitada, es decir, una situación en la que no se puede conservar todo.
• Catastrophic Forgetting [Polski] puede agravarse cuando de una memoria pequeña salen todos los ejemplos de una categoría anterior.

El texto y la ilustración se prepararon con ayuda de IA. El flujo de mensajes y la demostración son un ejemplo educativo propio y simplificado; la ilustración es una metáfora, no un esquema del algoritmo.