Reservoir Sampling

Un modèle de service client apprend sur des messages qui arrivent l’un après l’autre. Vous voulez en garder quelques-uns pour des révisions ultérieures, mais vous n’avez que quatre places en mémoire. Vous ne savez pas non plus combien de messages arriveront encore : vingt ou deux millions.

Garder les quatre premiers ? La mémoire ne connaît alors que le début. Garder toujours les quatre derniers ? Elle ne connaît alors que la fin. Un tirage équitable de « quatre parmi l’ensemble » obligerait à tout stocker ou à connaître d’avance le nombre de messages. La question est donc : comment, avec un nombre fixe de places et un flux de longueur inconnue, donner la même chance à chaque message ?

Le Reservoir Sampling est une façon de maintenir un échantillon aléatoire de taille fixe en un seul passage sur des données dont on ne connaît pas le nombre à l’avance. Après chaque nouveau message, la mémoire, appelée ici réservoir, contient un échantillon aléatoire équitable de tout ce qui est arrivé jusque-là. La version la plus simple, Algorithm R, est décrite par Vitter, Random Sampling with a Reservoir, §2, qui l’attribue à Alan Waterman.

La recette en deux étapes

1. Les quatre premiers messages entrent en mémoire sans tirage au sort.
2. Le message numéro $t$ (le cinquième, le sixième et chacun des suivants) entre en mémoire avec une chance de $4/t$. S’il y entre, il remplace l’un des quatre messages enregistrés, choisi au hasard.

Le cinquième message entre donc avec une chance de 4/5, le centième avec une chance de 4/100. Les nouveaux messages ont de moins en moins de chances d’entrer, mais les anciens ont déjà été exposés maintes fois au risque d’être éjectés, et ces deux effets se compensent exactement. Vérifions-le après le cinquième message. Il entre avec une chance de 4/5. Le premier message ne sort que si le cinquième est entré (4/5) et est tombé justement à sa place (1/4), soit avec une chance de 1/5. Il reste avec une chance de 4/5 : la même que celle du cinquième. Après $t$ messages, chacun d’eux se trouve en mémoire avec une chance de $4/t$.

Une chance égale n’est pas une garantie

Dans l’expérience, le flux compte 20 messages. Dix-huit concernent la livraison, et deux, le neuvième et le quinzième, concernent les retours. Chaque lancement fait passer un tel flux 2 000 fois et compte à quelle fréquence chaque position est restée en mémoire à la fin. Les tirages sont réels : les résultats diffèrent donc à chaque fois d’une fraction de pour cent.

Avec le Reservoir Sampling, chaque barre atteint environ 20 %, soit 4/20. Dans le même temps, dans la plupart des passages, aucun des deux retours ne reste en mémoire. La valeur exacte est 3060/4845, soit environ 63 % : c’est la part, parmi tous les groupes de quatre choisis dans 20 messages, de ceux qui se composent uniquement des dix-huit messages sur la livraison. La méthode est équitable envers chaque message pris isolément, mais elle ne veille pas à ce que chaque catégorie ait un représentant.

Là où cela compte

Dans l’apprentissage avec révisions, le Reservoir Sampling sert parfois de méthode d’écriture dans le tampon : il n’est pas nécessaire de connaître la longueur du flux ni les frontières entre les tâches. Chaudhry et al., Continual Learning with Tiny Episodic Memories, §2, algorithme 2 l’emploient précisément ainsi. Dans leurs expériences sur des tâches d’images, il donnait de bons résultats, sauf avec de très petites mémoires, où des classes antérieures disparaissaient du tampon ; les stratégies veillant à une représentation égale des classes s’en sortaient alors mieux (§4.4). C’est un résultat pour la classification d’images, pas pour les LLM.

L’algorithme lui-même ne relève pas de l’apprentissage automatique. L’article de Vitter, daté de 1985, décrit le tirage d’enregistrements sur une bande magnétique de longueur inconnue et propose des variantes plus rapides qui, au lieu de tirer au sort à chaque enregistrement, calculent combien d’enregistrements sauter. Les messages de clients et le flux de 20 positions sont un exemple personnel.

• Experience Replay a besoin d’un tampon d’anciens exemples ; le Reservoir Sampling est l’une des façons de décider ce qui y entre.
• Continual Learning suppose un apprentissage à partir d’un flux de données avec une mémoire limitée, c’est-à-dire une situation où l’on ne peut pas tout garder.
• Catastrophic Forgetting [Polski] peut s’aggraver lorsque tous les exemples d’une ancienne catégorie sortent d’une petite mémoire.

Texte et illustration préparés avec l’aide de l’IA. Le flux de messages et la démonstration sont un exemple pédagogique personnel simplifié ; l’illustration est une métaphore, pas un schéma de l’algorithme.