Échantillonnage par réservoir : une méthode de tirage aléatoire équitable dans des données de taille inconnue
(samwho.dev)- L’échantillonnage par réservoir est une technique d’extraction qui, même dans un flux de données dont on ne connaît pas la taille totale, ne conserve en mémoire qu’un nombre fixé d’éléments tout en donnant à chacun la même chance d’être sélectionné
- Pour un tableau de taille connue, mélanger les éléments ou choisir des indices aléatoires suffit, mais dans un flux où l’on ne peut pas revenir aux éléments déjà passés, une autre approche est nécessaire
- Pour sélectionner un seul élément, on adopte le n-ième élément avec une probabilité de 1/n, afin d’équilibrer la probabilité de sélection du nouvel élément et la probabilité de survie des éléments existants
- Pour tirer plusieurs éléments, on adopte un nouvel élément avec une probabilité de k/n, où k est le nombre d’éléments conservés, puis on remplace au besoin l’un des éléments actuellement conservés, choisi au hasard
- Appliqué à la collecte de logs, cela permet de ne pas dépasser une limite de traitement, par exemple 5 éléments par seconde, tout en réduisant à la fois la perte de logs pendant les périodes calmes et l’utilisation mémoire
Échantillonner dans un ensemble de taille connue
- Si l’on veut tirer au hasard 3 cartes parmi 10, il suffit de mélanger l’ensemble puis de prendre les 3 premières cartes pour donner à chaque carte la même probabilité d’être choisie
- Si le nombre de cartes passe à 1 million, les mélanger directement devient difficile, mais dans une structure accessible par indice, comme un tableau, choisir 3 indices aléatoires permet d’atteindre le même objectif
- Dans un tableau en mémoire, accéder à un indice précis est simple, mais compter jusqu’à la 436 234e carte dans un paquet prendrait en pratique beaucoup de temps
Contraintes d’un flux de taille inconnue
- Si l’on ne voit qu’une carte à la fois, que l’on ne peut en tenir qu’une seule à la fois et que l’on ne peut pas revenir aux cartes déjà passées, il faut choisir une carte finale sans connaître le nombre total
- Un service de collecte de logs rencontre un problème de forme similaire
- Il reçoit des messages de log provenant d’autres services et les stocke au même endroit
- En cas de mauvaise release ou de forte hausse du trafic, un afflux de logs peut submerger le service de collecte
- Dans l’exemple, le service de collecte de logs a un seuil lui permettant de traiter 5 logs par seconde
- Une approche consistant à n’envoyer que 10 % des logs permet de ne pas dépasser le seuil pendant les pics, mais jette inutilement 90 % des logs même pendant les périodes calmes
- Le comportement souhaité est d’envoyer tous les logs pendant les périodes calmes, et au maximum 5 par seconde pendant les pics
- Si l’on envoie seulement les 5 premiers logs vus chaque seconde, les logs arrivant ensuite n’ont aucune chance d’être sélectionnés, ce qui n’est pas équitable
Échantillonnage par réservoir d’un seul élément
- L’échantillonnage par réservoir maintient un échantillon équitable parmi les éléments vus jusqu’à présent, même sans connaître leur nombre total
- On pourrait aussi stocker tous les messages en mémoire puis choisir plus tard, mais si l’on ne connaît pas l’ampleur du pic, il est difficile de prévoir la quantité de mémoire nécessaire
- Cette méthode résout le même problème sans utiliser plus de mémoire que le nombre d’échantillons demandé
- La règle pour choisir une seule carte est simple
- La première carte est toujours conservée
- La n-ième nouvelle carte est conservée avec une probabilité de 1/n
- Si l’on décide de conserver la nouvelle carte, la carte déjà conservée est supprimée
- Remplacer avec une probabilité de 50 % à chaque carte favoriserait les cartes situées vers la fin et ne serait pas équitable
- Pour que la première carte reste après la 10e, elle doit survivre à plusieurs occasions de remplacement
- La dernière carte, elle, n’a besoin d’être sélectionnée qu’une seule fois pour rester en main
- La règle 1/n ajuste non seulement la probabilité de sélection de la nouvelle carte, mais aussi la probabilité de survie de la carte existante
- La première carte est conservée avec une probabilité de 1/1, c’est-à-dire 100 %
- À la deuxième carte, la nouvelle carte est sélectionnée avec une probabilité de 1/2, et la première carte reste aussi avec une probabilité de 1/2
- À la troisième carte, la nouvelle carte est sélectionnée avec une probabilité de 1/3, et la carte déjà conservée a également une probabilité de 50 % × 2/3, soit 1/3
- En général, à l’étape n, la probabilité qu’une carte existante reste est
1/(n-1) * (1-(1/n)), et la probabilité que la nouvelle carte soit sélectionnée est1/n, ce qui les rend égales
Extension à plusieurs éléments
- La sélection d’un seul élément peut être étendue à la sélection de plusieurs éléments
- Pour sélectionner k éléments, deux règles changent
- Le nouvel élément est sélectionné non pas avec une probabilité de
1/n, mais avec une probabilité de k/n - Si un remplacement est nécessaire, on choisit au hasard l’un des k éléments actuellement conservés et on le remplace par le nouvel élément
- Le nouvel élément est sélectionné non pas avec une probabilité de
- La probabilité de sélection d’un élément existant s’exprime par
k/(n-1), et l’équité est maintenue en la multipliant par la probabilité de ne pas être remplacé par le nouvel élément - Comme tous les éléments conservés ont la même probabilité d’être choisis pour le remplacement, la probabilité que chaque élément reste à chaque étape demeure elle aussi identique
- L’implémentation se résume à utiliser un tableau de taille k
- Pour chaque nouvel élément, on génère un nombre aléatoire entre 0 et n
- Si ce nombre aléatoire est inférieur à k, on remplace l’élément à l’indice correspondant par le nouvel élément
- Sinon, on rejette le nouvel élément
Application à un service de collecte de logs
- Dans l’exemple de collecte de logs, on définit
k=5, afin de ne conserver au maximum que 5 messages de log à la fois - Chaque seconde, on envoie les logs sélectionnés au service de collecte, puis on vide le tableau de taille 5 avant de recommencer
- Cette approche crée un schéma par paquets, où des lots de logs sont envoyés à intervalles réguliers plutôt qu’un flux de logs en temps réel
- En contrepartie, le nombre de logs transmis ne dépasse pas le seuil, et pendant les périodes calmes, le nombre total de logs et le nombre de logs transmis évoluent presque ensemble
- Pendant les périodes calmes, on ne perd pas de logs ; pendant les pics, on n’envoie pas plus de logs par seconde que le seuil, et l’espace de stockage ne dépasse pas
k=5logs
Quand des pondérations sont nécessaires
- Certains logs peuvent avoir plus de valeur que d’autres
- Par exemple, on peut vouloir conserver tous les logs d’erreur
- Dans ce cas, on peut utiliser une variante d’échantillonnage par réservoir pondéré
- L’échantillonnage par réservoir est un algorithme qui permet de résoudre avec peu de mémoire un problème d’échantillonnage de flux qui semble d’abord impossible
1 commentaires
Avis de Hacker News
Quand j’étais enfant, je vivais à la campagne, et j’ai entendu dire qu’un ami de mon père devait, dans le cadre de son travail, compter chaque année le nombre de lagopèdes alpins dans les montagnes.
Il suivait un itinéraire défini, faisait s’envoler les oiseaux à intervalles réguliers pour les compter, puis transmettait le total à l’administration, qui l’utilisait pour estimer la population totale.
Une année, il a dû partir à l’étranger pendant la période de comptage, alors il a expliqué en détail la méthode à un ami et lui a demandé de le remplacer. Mais cet ami a oublié le jour venu et, comme c’était fastidieux, il a simplement envoyé un chiffre à peu près plausible.
L’année suivante, la une du journal local titrait sur une hausse record de la population de lagopèdes alpins : l’ami n’avait pas pensé que cette estimation servait à fixer les quotas de chasse.
https://en.wikipedia.org/wiki/Rock_ptarmigan
Il y a quelque temps, j’ai développé les systèmes de réservation de stations de ski assez importantes. Le planning avait pris du retard et, pendant qu’on travaillait toute la nuit, l’une des dernières choses à terminer était un rapport de statistiques officielles pour le gouvernement, du genre nombre de nuitées.
Disons simplement que les statistiques de cette année-là avaient très peu de rapport avec la réalité.
Je suis l’auteur de l’article. Je peux répondre aux questions, et les retours sont les bienvenus.
Tout le code des articles se trouve sur https://github.com/samwho/visualisations et est sous licence MIT, donc vous pouvez l’utiliser librement.
Une extension plus intéressante de l’échantillonnage par réservoir consiste, au lieu de tirer un nombre aléatoire pour chaque élément afin de décider s’il faut remplacer et quoi remplacer, à tirer une valeur dans une loi géométrique pour déterminer combien d’éléments on peut sauter sans risque avant le prochain remplacement.
C’est particulièrement utile quand on peut sauter beaucoup d’éléments à faible coût, par exemple si l’on peut avancer rapidement une bande sans en connaître la longueur totale, ou si l’on peut mettre la majeure partie du système en veille pendant les sauts.
Pour choisir k éléments parmi n, cette méthode effectue environ O(k * log (n/k)) opérations d’échantillonnage et de saut.
Conceptuellement, je préfère une version de l’échantillonnage par réservoir où chaque carte reçoit, à son arrivée, une priorité aléatoire fixe, et où l’on ne conserve que les k plus hautes priorités.
Le problème qui en découle est de sélectionner les k plus grands éléments dans un flux de longueur inconnue en temps O(n) et en espace O(k). En maintenant simplement un tas min, on obtient bien O(k) en espace, mais O(n log k) en temps.
À la place, on peut utiliser un tampon non ordonné d’une capacité maximale de 2k, y ajouter des éléments, puis, lorsqu’il est plein, ne conserver que les k meilleurs en O(k) avec un quickselect aléatoire ou median-of-medians. Sur l’ensemble des n éléments, on fait O(2k) de travail tous les k éléments, ce qui donne un temps d’exécution O(n).
Un sujet lié est le rendezvous hashing : https://en.wikipedia.org/wiki/Rendezvous_hashing
À côté de ça, il existe aussi un bon article sur la méthode des alias pour échantillonner dans une distribution de probabilité discrète : https://www.keithschwarz.com/darts-dice-coins/
En revanche, au début il était question de choisir 3 cartes au hasard dans un paquet de 10 cartes ou de 436 234 cartes, puis on passe soudain à une seule carte, ce qui m’a brièvement dérouté.
Ce serait plus clair s’il y avait, avant “Now let me throw you a curveball...”, un titre de section du genre : « À partir de maintenant, on passe à une hypothèse simplifiée où l’on ne garde plus 3 cartes mais une seule, et où l’on ne connaît pas non plus la taille du paquet ».
Cela dit, je ne suis pas sûr d’avoir bien compris la validité statistique de cette approche. Je comprends que tous les logs d’une période donnée aient la même probabilité d’être inclus, mais dans ce cas, les logs générés pendant les « périodes calmes » ne sont-ils pas surreprésentés dans les métriques globales ?
Par exemple, si l’on veut savoir quel endpoint consomme le plus de temps afin de réduire le coût total de toute la flotte (secondes CPU, etc.), un endpoint recevant du trafic en rafales pourrait être sous-représenté par rapport à un endpoint au trafic régulier, donc cette méthode me semble inadaptée.
On pourrait alors perdre du temps à optimiser un endpoint qui, en réalité, ne reçoit pas beaucoup de trafic.
Pour la planification de capacité par service, je me demande aussi s’il est normal qu’un service recevant du trafic en rafales soit sous-représenté.
J’aimerais savoir à quels cas d’usage l’échantillonnage par réservoir convient, et quelles analyses statistiques on peut effectuer avec les données renvoyées.
L’article et les explications sont excellents
D’un point de vue pratique, je pense malgré tout que ce serait la toute dernière approche que j’utiliserais pour la collecte de logs. Je comprends qu’en cas de pic, il faut bien jeter quelque chose, mais l’essentiel est de savoir quoi jeter
Décider « équitablement » quoi jeter ne me semble pas avoir beaucoup de sens
Il vaut mieux commencer par supprimer les logs de faible priorité ; s’il existe des niveaux de logs comme debug/info/warning/error, on peut privilégier les événements les plus graves et jeter d’abord les logs debug verbeux
On peut aussi regrouper des séquences de logs comme faisant partie d’une même activité : pour les activités réussies, ne consigner que le début et la fin, ou les changements d’état clés, et omettre les logs intermédiaires répétitifs
En cas de pic, plutôt que de stocker chaque ligne de log, agréger et résumer les messages similaires ou dupliqués réduit aussi le volume et fait mieux apparaître les tendances
Et on veut aussi limiter le nombre total de lignes de logs collectées, avec un budget plus large. L’échantillonnage par réservoir peut gérer tout cela
Un échantillonnage par réservoir équitable peut aussi être rendu inéquitable de façon contrôlée. Par exemple, on peut augmenter la probabilité de conserver les éléments dont le contenu est particulièrement intéressant
En dernier recours, c’est une technique en concurrence avec une sélection aléatoire biaisée moins principielle, ou avec des algorithmes de sélection qui ne sont même pas aléatoires
Article vraiment bien écrit et bien visualisé
Parmi les extensions avancées, il existe des algorithmes qui calculent le nombre d’enregistrements à sauter au lieu de faire un tirage pour chaque enregistrement. Un bon article à ce sujet se trouve ici : https://richardstartin.github.io/posts/reservoir-sampling
Une variante de l’échantillonnage par réservoir pondéré est utilisée dans ReSTIR (rééchantillonnage spatio-temporel par réservoir pour le lancer de rayons en temps réel). C’est un estimateur de transport lumineux probabiliste avec débruitage spatio-temporel intégré
Un estimateur de transport lumineux cherche à calculer la quantité de lumière traversant une scène (https://en.wikipedia.org/wiki/Radiance). Pour cela, il faut intégrer la radiance de tous les chemins que la lumière peut emprunter, tout en respectant la conservation de l’énergie (https://en.wikipedia.org/wiki/Rendering_equation)
Sauf dans des cas très simples, cette intégrale de l’équation du rendu n’a pas de solution fermée facilement manipulable et doit donc être résolue de façon probabiliste
L’idée de base est la méthode de Monte-Carlo (https://en.wikipedia.org/wiki/Monte_Carlo_method) : échantillonner aléatoirement un grand nombre de chemins possibles et en faire la moyenne
Au fil des décennies suivantes, des stratégies plus sophistiquées ont été développées, comme l’échantillonnage d’importance (IS), l’échantillonnage d’importance multiple (MIS), le rééchantillonnage par importance des échantillons (SIR), l’échantillonnage d’importance avec rééchantillonnage (RIS), l’échantillonnage par réservoir pondéré (WRS), puis ReSTIR, qui combine RIS et WRS
Un article détaillé se trouve ici : https://agraphicsguynotes.com/posts/understanding_the_math_b...
Cela me fait penser qu’il faudrait que je réfléchisse davantage à l’algorithme par lequel les Alliés ont estimé le nombre de chars allemands à partir de leurs numéros de série
Les estimations de terrain étaient environ cinq fois supérieures à la production réelle, tandis que la technique fondée sur les numéros de série était exacte à plus de 90 %
Bon article, avec d’excellentes explications. Il semble traiter de l’Algorithm R, probablement décrit pour la première fois par Vitter : https://www.cs.umd.edu/~samir/498/vitter.pdf
L’article précédent de Vitter https://dl.acm.org/doi/10.1145/358105.893 cite le volume 2 de TAOCP de Knuth, et Knuth ne cite à son tour aucune source
Du point de vue de la data science, le volume de données lui-même porte aussi une information très importante ; il est donc utile de consigner aussi combien d’éléments chaque point de données représente
Par exemple, si le taux d’échantillonnage est de 10 %, on peut ajouter un champ contenant 10, ce qui permet de reconstruire et d’estimer la plupart des statistiques comme count, sum ou average
La structure est bonne et les explications sont claires. Si la version pondérée vous intéresse, j’en avais donné quelques explications ici : https://gregable.com/2007/10/reservoir-sampling.html
Il existe aussi une version distribuée facile à réaliser avec MapReduce
Un algorithme très simple consiste aussi à associer une paire aléatoire à chaque élément du flux, puis à conserver les N premiers selon cette valeur aléatoire
D’abord, l’implémentation intuitive qui classe avec
POW(RANDOM(), 1.0 / weight)puis choisit les N premiers présente des problèmes de stabilité numérique lorsque les poids sont très grands ou très petitsEnsuite, l’échantillon obtenu n’a pas la même distribution que la population d’origine, même en valeur attendue. C’est particulièrement vrai lorsque le poids total est concentré sur un petit nombre d’éléments de la population, mais dans beaucoup de cas cela reste une approximation utilisable
Ces problèmes sont traités plus en détail ici : https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....
Excellent article, très accessible, avec de très bonnes visualisations
Chez $WORK, nous utilisons une variante similaire pour résoudre un problème connexe : estimer certains percentiles dans un flux en cours d’exécution
Le percentile que l’on veut sélectionner change de temps à autre, mais il reste généralement fixe pendant plus de 1 000 milliards d’itérations, et les données sous-jacentes sont quasi stationnaires
En s’appuyant sur un arbre splay, ce processus permet une estimation des percentiles en O(1) amorti. À quantité de RAM égale, la marge d’erreur est plus grande qu’avec plusieurs autres techniques, mais c’est très rapide
On peut aussi ajuster la probabilité de remplacement afin d’introduire une « demi-vie des données » fondée sur le temps ou sur le nombre d’éléments, et ainsi biaiser l’estimation vers les événements récents ; pour certains problèmes, c’est plus adapté