Comptage approximatif

Les structures de données probabilistes sont l’un des sujets les plus négligés en informatique : les bloom filters, les compteurs HyperLogLog, les voisins les plus proches approximatifs, les projections aléatoires doivent être connues des programmeurs aussi bien que le sont les algorithmes de tri, les tables de hachage ou les tas. C’est un domaine qui peut vraiment faire la différence, dans de nombreux cas, en termes de performance et d’économie de ressources.

Peut-être que la partie « probabilité » effraie les programmeurs qui sont souvent bons en logique, mais pas tellement en mathématiques. Vous ne devriez pas avoir peur de ces algorithmes, ils ne sont pas si difficiles à comprendre, et une bonne intuition peut beaucoup aider : une bonne compréhension de la génération de nombres aléatoires, du hachage et des collisions est utile.

Dans cet article, je vais aborder la façon de compter les événements avec un grand nombre de type différents, c’est-à-dire comment stocker beaucoup de nombres (et les mettre à jour). En commençant par les Count-Min sketch, l’une des premières structures probabilistes, puis le comptage logarithmique connu sous le nom de compteurs de Morris, et enfin d’autres approches qui nous ont finalement conduits à notre proposition des Count-Min Tree sketch.

Table of Contents

La manière directe de compter

Tout d’abord, un peu de vulgarisation scientifique : en informatique, quelle est la voie à suivre si vous souhaitez stocker des nombres associés à des éléments ? Par exemple, si vous voulez savoir combien de fois les messages ont été aimés ou combien de fois les hashtags ont été twittés au cours d’une journée ?

La structure que l’on utiliserait normalement est une collection (clé, valeur) aussi appelé tableau associatif, où la clé contient l’étiquette de la chose comptée, et la valeur contient le nombre lui-même. Pour pouvoir compter réellement, vous avez besoin d’une collection modifiable, avec la possibilité d’accéder à la valeur en temps constant ou logarithmique. Pour ce faire, vous devez utiliser une table de hachage ou une structure d’arbre.

Compter approximativement avec des Count-Min sketch

En 2005, un article de Cormode & Muthukrishnan a décrit le Count-Min Sketch (CMS), une structure de données probabiliste, inspirée du Bloom Filter (et de leur variante pour le comptage), qui peut stocker très efficacement les comptes associés à des items (mais sans stocker l’item). La principale différence entre l’approche Bloom et l’approche CMS est que le CMS sépare la mémoire en plusieurs couches et utilise des hachages différents pour chaque couche, tandis que l’approche Bloom utilise différents hachages dans un seul segment de mémoire.

Deux opérations sont associées à un CMS :

Update(item,value) et
Requête(item).

Update() ajoute une valeur aux comptes stockés pour les éléments, tandis que Query() renvoie l’estimation du nombre pour l’élément.

L’idée géniale derrière le CMS est que, même s’il y a des collisions (et il y en aura nécessairement), on peut minimiser l’erreur d’estimation en ne gardant que la valeur MIN stockée dans les cellules correspondant à un élément. En effet, toutes les autres cellules surestiment nécessairement le décompte réel.

L’illustration ci-dessus montre un CMS avec 3 couches de 20 cellules. Il a été mis à jour en comptant deux éléments : X et Y. X a été vu 2 fois, Y 3 fois. Étant donné que le hachage de X et Y est le même pour la couche 0, il y a une collision, et donc, la cellule contient la somme des comptes X et Y. Lors de l’interrogation du CMS pour le nombre de X, les valeurs extraites pour X sont (5,2,2). Grâce à la règle MIN, le CMS ne renvoie que la valeur minimale, et par conséquent, 2 est correctement renvoyée.

Le CMS peut prendre en charge les mises à jour positives et négatives. Si nous ajoutons la contrainte des mises à jour positives uniquement, nous pouvons utiliser la variante Conservative Update. Dans cette variante, seules les cellules qui sont déjà à la valeur minimale vont être incrémentées (du moins si nous ne faisons que des incréments simples, sinon la règle est légèrement plus compliquée).

Évaluation

Les graphiques suivants montrent l’erreur d’estimation pour le CMS d’origine et le CMS avec mise à jour conservatrice (CMS-CU) tous deux avec 3 couches, avec une taille variant de 12,5 % à 800 % de la taille parfaite (la taille d’un tableau contenant uniquement les comptes, ce qui serait faisable avec une fonction de hachage parfaite).

Le premier graphique montre l’erreur absolue (RMSE), après avoir compté un million de mots d’un dump de Wikipédia, plus les bigrammes (c’est-à-dire, pour la phrase « le petit chat », on compte en fait « le », « petit », « chat » et « le petit » et « le petit chat »). Ces millions de mots finissent par créer une table de hachage avec 523563 entrées (30 Mo selon notre estimation). La taille parfaite est calculée sur des compteurs de 32 bits, soit un total de 2 Mo. Par conséquent, le stockage requis pour cette table de hachage est de 1500 % la taille parfaite.

Dans ce graphique, les lignes verticales du milieu montrent la taille parfaite. Mesurer l’erreur absolue n’est pas un choix neutre, car la plupart des valeurs lors du comptage des unigrammes et des bigrammes sont à un (1), car beaucoup de bigrammes ne sont vus qu’une seule fois. Lorsque vous mesurez l’erreur absolue, estimer 101 au lieu de 1 est la même chose qu’estimer 100100 au lieu de 100000 (et vous conviendrez peut-être que ce n’est en fait pas la même gravité).

Nous devons donc également mesurer l’erreur relative moyenne (Average Relative Error):

C’est proche du premier graphique, mais ça ne veut pas dire la même chose du tout ! À la taille parfaite, un CMS a une erreur relative moyenne de 1 (100 %), ce qui signifie qu’en moyenne, au lieu de 1, il en estimera 2, au lieu de 100, il en estimera 200, etc. Pour une erreur relative de 1 % (c’est-à-dire probablement correcte pour n’importe quel usage pratique), vous avez besoin de 800 % de la taille parfaite. C’est la moitié de la mémoire requise d’une table de hachage, ce qui est intéressant. Mais est-ce suffisant ?

En 2014, nous avons commencé à travailler sur une version en streaming de notre outil de fouille de texte, eXenGine. Par conséquent, nous avons commencé à nous intéresser au Count-Min Sketch, mais nous avons été déçus par le gain de taille : un Count-Min Sketch peut approximer des valeurs avec une erreur relative de 1 %, à la moitié de la taille d’une table de hachage, ce qui est intéressant, mais ne change pas la donne.

Compter approximativement

Ce n’était pas assez bon pour nous. Compte tenu du nombre d’éléments que nous voulions compter, réduire de moitié les besoins en mémoire n’était pas un objectif suffisant. Nous avons donc commencé à réfléchir à de meilleurs systèmes, avec deux objectifs en tête :

la mesure de l’erreur devrait être l’erreur relative moyenne, car on peut utiliser l’estimation soit pour le cutoff (pour ignorer les événements très rares), soit pour calculer l’ information mutuelle ponctuelle ou le TF-IDF, qui prennent tous deux un logarithme des comptes à un moment donné.
la distribution des valeurs est très asymétrique (les données textuelles suivent généralement la loi de Zipf), donc le stockage de petites valeurs devrait être super efficace.

Dans un premier temps (en 2014), nous avons eu l’idée d’utiliser des compteurs approximatifs (également appelés compteurs de Morris, analysés par le grand Flajolet, le même scientifique qui nous a donné HyperLogLog). Il m’a semblé vraiment étrange à l’époque que personne n’ait appliqué cette idée auparavant. Il s’avère (comme souvent) que je n’ai pas assez cherché : David Talbot avait déjà eu l’idée en 2009. Sans le savoir, nous avons publié un article (Guillaume Pitel et Geoffroy Fouquier) sur l’idée. Au moins, cela a inspiré Seif Lotfy à travailler sur diverses implémentations de CMS. Notre méthode est significativement différente de celle de Talbot et d’Osborne, puisqu’elles stockent essentiellement une chaîne unaire approximant le nombre de logarithmes à l’aide d’un Bloom Fiter (voir ci-dessous). Nous n’avons pas essayé leur méthode car elle me semblait trop pénalisante en termes d’accès à la mémoire.

Ce que nous avons proposé (et ce que David Talbot a proposé avant nous), c’était d’utiliser des compteurs plus petits (disons 8 bits au lieu de 32) qui se rapprocheraient de la valeur réelle. Pour ce faire, la clé est d’autoriser un incrément probabiliste. Par exemple, pour compter approximativement en base 2, vous auriez 50 % de chances d’augmenter de 1 à 2, 25 % d’augmenter de 2 à 3, etc. Avec cette règle, la valeur approchée est (presque) 2^x, donc compter jusqu’à 2³² avec un compteur approximatif en base 2 ne nécessite que 5 bits (car vous pouvez compter jusqu’à 32 avec 5 bits). Nous lui avons donné le nom de « Count-Min Log » car il utilise des compteurs logarithmiques.

Evidemment, avec un compteur en base 2, l’erreur due au comptage approximatif est assez importante. Avec des compteurs 8 bits, cependant, les choses deviennent assez bonnes pour être utilisables.

Il suffit de jeter un coup d’œil au graphique ci-dessous, il montre l’erreur relative moyenne du CMS, du Count-Min Log avec 8 bits (CMLS8) et du Count-Min Log avec 16 bits (CMLS16), le tout avec la règle de mise à jour conservatrice. Il est notable que CMLS8 cesse de s’améliorer à un moment donné. C’est dû à la limite de précision des compteurs approximatifs de 8 bits. CMLS16 cesse également de s’améliorer à un moment donné, mais ce n’est pas visible sur le graphique.

Cela devrait nous faire plaisir, nous avons réduit de moitié les besoins en mémoire du CMS. Mais ne vous précipitez pas pour utiliser le Count-Min Log Sketch maintenant, jetons un coup d’œil à la RMSE :

C’est un désastre ! En raison des erreurs sur les valeurs les plus élevées, l’erreur absolue moyenne est énorme et ne s’améliore pas avec la taille du Sketch. Cependant, il y a une raison pour laquelle nous nous intéressons surtout à l’ARE : dans l’exploration de texte, nous utilisons principalement le logarithme des comptes, donc nous ne nous soucions pas vraiment de la RMSE. Jetons plutôt un coup d’œil à l’erreur d’estimation sur l’indice PMI ; pour chaque bigramme du corpus, calculons le PMI et l’erreur absolue avec le PMI réel :

Pour vous donner une bonne idée de la signification du PMI, voici les histogrammes du PMI estimés sur un corpus plus restreint avec la référence, le CMS, et le CMLS8 :

Comme vous pouvez le voir, la PMI se situe généralement entre 0 et 10, et est centrée autour de 4 ou 5. Donc une erreur de 0,1 sur la PMI est acceptable, on reste proche de la valeur réelle.

L’utilisation de compteurs logarithmiques nous a permis d’améliorer considérablement notre objectif, mais nous nous sentions toujours insatisfaits car nous ne pouvions pas prendre en compte l’asymétrie particulièrement élevée de nos données : chaque compteur utilisait le même nombre de bits.

Du Count-Min Sketch au Count-Min Tree Sketch

Nous avons vu précédemment que l’utilisation de compteurs approximatifs (logarithmiques) améliore l’erreur relative du CMS et l’erreur absolue de l’information mutuelle ponctuelle. Pourquoi? Principalement parce que nous échangeons la précision (dont nous ne nous soucions pas beaucoup) contre la taille, de sorte que sans perdre beaucoup sur l’erreur, nous pouvons doubler ou quadrupler le nombre de cellules dans les couches de stockage.

Pourquoi pouvons-nous faire cela ? Est-ce vraiment parce que nos comptes suivent une loi de Zipf ? La réponse est à la fois oui et non. La vraie réponse est que nous pouvons échanger une précision relative (c’est-à-dire une bonne précision pour les petites valeurs et une faible précision pour les valeurs élevées) parce que nous nous soucions de la PMI, qui prend le logarithme de la fréquence. Ceci, à son tour, est directement causé par le fait que le nombre de mots suit la loi de Zipf.

Mais fondamentalement, avec les compteurs logarithmiques, nous ne tirions pas directement parti de la distribution des comptes, en allouant moins de bits aux valeurs faibles. Nous allouions toujours le même nombre de bits pour chaque événement, ces bits étaient simplement utilisés d’une manière différente.

Huffman? Pas vraiment

Certains d’entre vous, lecteurs, ont probablement pensé au codage Huffman, mais en réalité, c’est le contraire. Dans le codage de Huffman, un code très fréquent, par exemple la séquence de bits 0b01100100 (code ascii pour « e ») peut être codé avec 3 bits, car il apparaît fréquemment, tandis que 0b0101101010 (« Z ») peut être codé avec 10 bits, car il est beaucoup moins fréquent.

Cependant, nous ne compressons pas des flux binaires : à la place, nous comptons les occurrences. Par conséquent, les événements les plus fréquents auront besoin de beaucoup de bits pour être comptés, tandis que de nombreux éléments à basse fréquence n’auront besoin que de quelques bits.

Talbot et Osborne

Revenons d’abord sur l’idée de Talbot & Osborne. Il consiste essentiellement à stocker une chaîne de uns qui représentera le log-count d’un élément est une représentation en base 1.

Disons que vous voulez compter l’élément « the ». Vous disposez d’une famille de fonctions de hachage indépendantes h_i(x) qui vous donne une position dans un tableau de bits. Vous recherchez d’abord le bit à h_1(‘the’), s’il s’agit d’un, vous recherchez la valeur à h_2(‘the’) et ainsi de suite, jusqu’à ce que vous rencontriez un 0. Enfin, le dernier i vous donne la valeur logarithmique de votre compteur Morris.

Afin d’éviter les faux positifs, on pourrait également utiliser plusieurs fonctions de hachage pour chaque i, en échange d’une augmentation de l’utilisation de la mémoire.

Un inconvénient de la méthode : supposons que vous encodiez les compteurs Morris avec 16 bits. Par conséquent, la lecture de cette valeur nécessitera jusqu’à seize accès en mémoire. C’est un coût énorme, du moins si vous considérez cette solution pour le comptage en ligne (c’est-à-dire pas seulement le stockage des valeurs), car elle affectera particulièrement les articles à haute fréquence.

La solution proposée par Talbot pour éviter cela consiste à sonder de manière probabiliste la chaîne unaire des bits. Fondamentalement, l’idée est que vous n’avez pas à continuer à chercher le prochain morceau si vous avez déjà abandonné l’idée de faire l’incrément. Et le fait est que plus votre chaîne de bits est longue, moins vous risquez de l’allonger. La limite qu’ils proposent pour cette solution n’est cependant pas si intéressante.

Compteurs TOMB : Van Durme & Lall

Les compteurs TOMB combinent l’idée de Talbot & Osborne, les compteurs Morris et l’approche du compteur Bloom.

Au lieu de stocker la valeur dans une représentation en base 1 (c’est-à-dire une chaîne de uns terminée par un zéro), il utilise plusieurs niveaux de stockage, chacun ayant un petit compteur de Morris.

L’idée est de commencer par mettre à jour l’une des cellules de la colonne de comptage Morris au niveau de la couche inférieure. Lorsque la cellule est à la valeur maximale, vous passez à la couche suivante. Le calcul de la valeur stockée d’un élément consiste à additionner les valeurs de chaque couche jusqu’à la première couche avec une valeur non maximale. Bien que cela s’améliore considérablement à bien des égards par rapport à l’idée de Talbot et Osborne, il y a plusieurs améliorations possibles à apporter : la « longueur » de la valeur est codée de manière sous-optimale.

Count-Min Tree Sketches

En 2016, nous (Guillaume Pitel, Geoffroy Fouquier, Emmanuel Marchand et Abdul Muhamadsultane) avons conçu et mis en œuvre le Count-Min Tree Sketch (CMTS), une structure arborescente mélangeant des bits de comptage et des bits barrière. L’objectif qui a motivé ce travail était de disposer d’un moyen très efficace de compter les données avec une distribution de Zipf, où les éléments à basse fréquence sont largement plus nombreux que les éléments à haute fréquence. Les principales caractéristiques du CMTS sont les suivantes :

Les bits codant la longueur d’un compteur sont séparés des bits du compteur
La longueur d’un compteur est encodée en base-1
Le stockage en longueur et le stockage en compteur sont « partagés »

En résumé, nous avons deux types de bits : les bits de comptage et les bits barrières pour coder la longueur.

Un exemple de CMTS avec 4 couches et une flèche.

Comme illustré dans la figure ci-dessus, un compteur commence par le bas avec un bit de comptage, si son premier bit de barrière est égal à un, alors le bit de comptage suivant est également pris en compte, sinon le compteur n’utilise qu’un seul bit de comptage. Le compteur s’arrête au bit juste après la dernière barrière activée de manière contiguë. Un bit barrière, une fois réglé sur 1, ne peut plus jamais être changé. Tout en haut, après le dernier bit de barrière, une flèche (spire) contient les bits de comptage restants, principalement pour des raisons de performance puisque notre objectif était de stocker une « super-cellule » dans une ligne de cache CPU typique de 64 octets (512 bits), permettant une base de 128 bits. Idéalement, une super-cellule prend 2*128+2*64+… = 510 bits avec seulement 8 niveaux, permettant de stocker une valeur dans l’arbre de base lui-même jusqu’à 765. La flèche est stockée dans un autre segment de mémoire pour coder les valeurs supérieures à ce seuil. Avec ce paramètre, on obtient 128 compteurs pour 512+32 bits, soit 4,25 bits par compteur en moyenne pour une seule couche.

L’algorithme général de mise à jour et d’interrogation d’un croquis est inchangé par rapport à un croquis classique. Cependant, étant donné la complexité de la structure des bits partagés, les algorithmes permettant d’obtenir la valeur, d’incrémenter ou de fusionner les compteurs dans le cas de l’informatique distribuée sont plus complexes qu’un Count-Min sketch. L’obtention d’une mise en œuvre performante a été un défi majeur.

Obtenir la valeur des pions dans un CMTS à 4 couches et une flèche de 4 bits.

Le principe d’obtention de la valeur d’un compteur CMTS est le suivant, et est illustré dans la figure ci-dessus :

Les valeurs binaires de la barrière sont collectées à partir de la cellule inférieure du compteur, jusqu’à la première barrière à zéro. S’il y a 2 bits de barrière définis de manière contiguë (comme le compteur 0 sur la figure 2), alors b= 2.
(b + 1) bits de valeur sont rassemblés dans le compteur c. Si le bit de valeur inférieure est 0 et que les deux autres sont 1, alors le compteur est c = 110b = 6
La valeur réelle peut enfin être calculée : v = c+2×=12

L’incrémentation peut être mise en œuvre en obtenant la valeur réelle, en l’incrémentant, puis en remettant le résultat dans le CMTS, en définissant la barrière correcte et en comptant les bits.

Le principe de réglage de la valeur d’un compteur CMTS est le suivant :

La nouvelle barrière nb est calculée à partir de la valeur d’incrément de post-incrément nv à l’aide de la formule suivante :
nb=min(nblayers, lsb((nv+2)/4)))où lsb(x) donne la longueur de bit de x, c’est-à-dire la position du premier bit à un. Dans l’exemple précédent, la nouvelle valeur du compteur 0 est 13, nblayer est 4 et lsb((13+2)/4)=2. Par conséquent, nb = 2
Le nouveau bit de comptage est alors calculé comme suit : nc = nv − 2 × (2^nb − 1). Ici nc = 7, c’est-à-dire 111b
Enfin, la nouvelle barrière et la nouvelle valeur sont définies : nb bits sont définis à un pour la barrière, et nb + 1 bits sont définis pour la valeur à l’aide du nouveau bit de comptage. Dans notre exemple, le nombre de bits de barrière défini à un reste le même (2), et nb + 1 = 3 bits sont définis pour la valeur à l’aide du nouveau bit de comptage nc = 111b, donc les trois premiers compteurs sont définis à 1. Dans ce cas, seul le premier change (de 0 à 1).

Les mêmes algorithmes de base get et set peuvent être utilisés pour fusionner les compteurs, même si de nombreuses erreurs peuvent être évitées en prenant en compte les éventuels débordements qui peuvent se produire en raison des conflits dans l’arborescence.

Évaluation

Nous avons vérifié notre hypothèse empiriquement dans le cadre suivant : nous comptons les unigrammes et les bigrammes de 140 millions de mots du corpus Wikipédia en anglais. Le petit corpus analysé contient 14,7 millions de tokens distincts.

Dans ce qui suit, la taille de stockage idéale du comptage parfait correspond, pour un nombre donné d’éléments, à la quantité minimale de mémoire pour les stocker parfaitement, dans un cadre idéal. Un réglage haute pression correspond à un paramètre où l’empreinte mémoire est inférieure à la taille de stockage idéale pour le même nombre d’éléments. Pour notre expérience, cette taille est de 59 mégaoctets (Mio).

Il est à noter que tous les sketches testés utilisent une implémentation qui est plus rapide qu’une structure de dictionnaire natif (nous utilisons l’implémentation STL C++ native d’une UnorderedMap). L’empreinte mémoire de cette structure est d’environ 815 Mio, soit 1380 % de la taille de stockage idéale pour un comptage parfait.

Nous comparons les estimations de quatre sketches (tous utilisent le mode de mise à jour conservateur) :

CMS-CU est le Count-Min Sketch classique.
CMLS16-CU est le Count-Min Log Sketch utilisant une base logarithmique de 1,00025 et des compteurs de 16 bits.
CMLS8-CU est le Count-Min Log Sketch utilisant une base logarithmique de compteurs de 1,08 et 8 bits.
CMTS-CU est le Count-Min Tree Sketch. Les paramètres sont : 128 bits de base, 32 bits de flèche.

Tout d’abord, nous comparons l’erreur relative moyenne :

Ensuite, nous comparons le RMSE sur Pointwise Mutual Information : nous utilisons la même valeur stockée, c’est-à-dire les nombres d’unigrammes et de bigrammes, et calculons le PMI d’un bigramme qui utilise trois valeurs : count(x), count(y) et count(x_y).

On peut voir qu’avec une taille « raisonnable » autour de la taille parfaite, CMTS surpasse largement les autres croquis. Il y a cependant une tendance de l’erreur à croître plus vite que les autres croquis sous très forte « pression », mais comme nous ne nous intéressons qu’aux paramètres où l’ARE est inférieur à 1 %, l’erreur n’est de toute façon pas acceptable.

Quelle est la prochaine étape ?

Une différence importante entre les Count-Min sketch et les structures de données normales est que vous devez définir votre taille une fois pour toutes. Si vous vous trompez dans la taille du vocabulaire cible, vous pouvez avoir de sérieux problèmes car les taux d’erreur augmentent avec la pression.

Nous avons généralement un bon prédicteur du vocabulaire en fonction de la taille du corpus que nous comptons, donc pour notre cas d’utilisation, ce n’est pas vraiment un problème. Mais nous aimerions un jour publier une version super robuste du CMTS qui adapterait automatiquement la structure des données au fur et à mesure que davantage de données sont ingérées.

Nous avons déjà exploré deux directions principales :

Sous-échantillonnage adaptatif : lorsqu’une cellule ou un croquis est sous pression, diviser les comptages par deux et commencer à compter uniquement à la moitié de la fréquence (puis à la fréquence 1/4 et ainsi de suite). La division des comptes est cependant difficile.
Croissance adaptative : lorsqu’un croquis est sous pression, créer un croquis deux fois plus grand et, lors des mises à jour suivantes, lancez les comptes dans le nouveau croquis la première fois que vous mettez à jour un élément.

Espérons que nous trouverons un peu de temps pour cela.