Recherche de similarité, Partie 2 Quantification de Produit

Similarity Search, Part 2 Product Quantification

Découvrez une technique puissante pour compresser efficacement de grandes quantités de données

La recherche de similarité est un problème où, étant donné une requête, l’objectif est de trouver les documents les plus similaires parmi tous les documents de la base de données.

Introduction

En science des données, la recherche de similarité apparaît souvent dans le domaine du traitement du langage naturel, des moteurs de recherche ou des systèmes de recommandation où les documents ou les éléments les plus pertinents doivent être récupérés pour une requête. Normalement, les documents ou les éléments sont représentés sous forme de textes ou d’images. Cependant, les algorithmes d’apprentissage automatique ne peuvent pas travailler directement avec des textes ou des images brutes, c’est pourquoi les documents et les éléments sont généralement prétraités et stockés sous forme de vecteurs de nombres.

Parfois, chaque composant d’un vecteur peut stocker une signification sémantique. Dans ce cas, ces représentations sont également appelées incorporations. De telles incorporations peuvent avoir des centaines de dimensions et leur quantité peut atteindre des millions ! En raison de ces nombres énormes, tout système de recherche d’informations doit être capable de détecter rapidement les documents pertinents.

• Suppression et distillation architecturales une voie vers une compression efficace dans les modèles de diffusion texte-image d’IA
• Google AI dévoile Imagen Editor et EditBench pour améliorer et évaluer l’Inpainting d’image guidée par le texte.
• Forged in Flames Une start-up fusionne l’IA générative et la vision par ordinateur pour lutter contre les incendies de forêt.

En apprentissage automatique, un vecteur est également appelé un objet ou un point.

Index

Pour accélérer les performances de recherche, une structure de données spéciale est construite sur les incorporations de l’ensemble de données. Une telle structure de données est appelée index. Il y a eu beaucoup de recherches dans ce domaine et de nombreux types d’index ont évolué. Avant de choisir un index à appliquer pour une tâche spécifique, il est nécessaire de comprendre comment il fonctionne sous le capot, car chaque index sert un but différent et vient avec ses propres avantages et inconvénients.

Dans la première partie de cette série d’articles, nous avons examiné la structure d’index de kNN et de fichier inversé pour effectuer une recherche de similarité. Les deux méthodes n’utilisent pas de techniques de compression de données, ce qui peut entraîner des problèmes de mémoire, en particulier dans les cas de grands ensembles de données et de RAM limitée. Dans cet article, nous essaierons de résoudre ce problème en examinant une autre méthode appelée Quantification de Produit.

Recherche de similarité, Partie 1 : kNN & Index de Fichier Inversé

La recherche de similarité est un problème courant où, étant donné une requête Q, nous devons trouver les documents les plus similaires parmi tous les…

towardsdatascience.com

Définition

La quantification de produit est le processus où chaque vecteur de données est converti en une représentation courte et efficace en mémoire (appelée code PQ). Au lieu de conserver entièrement tous les vecteurs, leurs représentations courtes sont stockées. En même temps, la quantification de produit est une méthode de compression avec perte qui entraîne une précision de prédiction plus faible mais qui fonctionne très bien en pratique.

En général, la quantification est le processus de mappage de valeurs infinies en valeurs discrètes.

Entraînement

Tout d’abord, l’algorithme divise chaque vecteur en plusieurs parties égales – les sous-vecteurs. Chacune des parties respectives de tous les vecteurs de l’ensemble de données forme des sous-espaces indépendants et est traitée séparément. Ensuite, un algorithme de regroupement est exécuté pour chaque sous-espace de vecteurs. Ainsi, plusieurs centroïdes sont créés dans chaque sous-espace. Chaque sous-vecteur est encodé avec l’ID du centroïde auquel il appartient. De plus, les coordonnées de tous les centroïdes sont stockées pour une utilisation ultérieure.

Les centroïdes de sous-espace sont également appelés vecteurs quantifiés.

Dans la quantification de produit, un ID de cluster est souvent appelé une valeur de reproduction.

Remarque. Dans les figures ci-dessous, un rectangle représente un vecteur contenant plusieurs valeurs, tandis qu’un carré indique un seul nombre.

En conséquence, si un vecteur d’origine est divisé en n parties, il peut être encodé par n nombres – les ID des centroïdes respectifs pour chacun de ses sous-vecteurs. En général, le nombre de centroïdes créés k est choisi comme une puissance de 2 pour une utilisation plus efficace de la mémoire. De cette façon, la mémoire requise pour stocker un vecteur encodé est de n * log(k) bits.

L’ensemble de tous les centroids à l’intérieur d’un sous-espace est appelé un dictionnaire de codes. L’exécution de n algorithmes de clustering pour tous les sous-espaces produit n dictionnaires de codes distincts.

Exemple de compression

Imaginons un vecteur original de taille 1024 qui stocke des nombres flottants (32 bits) divisé en n = 8 sous-vecteurs où chaque sous-vecteur est encodé par l’un des k = 256 clusters. Par conséquent, l’encodage de l’ID d’un seul cluster nécessiterait log(256) = 8 bits. Comparons les tailles de mémoire pour la représentation des vecteurs dans les deux cas :

• Vecteur original : 1024 * 32 bits = 4096 octets.
• Vecteur encodé : 8 * 8 bits = 8 octets.

La compression finale est de 512 fois ! C’est le véritable pouvoir de la quantification de produit.

Voici quelques notes importantes :

• L’algorithme peut être entraîné sur un sous-ensemble de vecteurs (par exemple, pour créer des clusters) et être utilisé pour un autre : une fois que l’algorithme est entraîné, un autre ensemble de données de vecteurs est passé où de nouveaux vecteurs sont encodés en utilisant les centroids déjà construits pour chaque sous-espace.
• Typiquement, k-means est choisi comme algorithme de clustering. L’un de ses avantages est que le nombre de clusters k est un hyperparamètre qui peut être défini manuellement, selon les exigences d’utilisation de la mémoire.

Inférence

Pour mieux comprendre, examinons d’abord plusieurs approches naïves et découvrons leurs inconvénients. Cela nous aidera également à réaliser pourquoi elles ne devraient normalement pas être utilisées.

Approches naïves

La première approche naïve consiste à décompresser tous les vecteurs en concaténant les centroids correspondants de chaque vecteur. Après cela, la distance L2 (ou une autre métrique) peut être calculée à partir d’un vecteur de requête vers tous les vecteurs de l’ensemble de données. Évidemment, cette méthode fonctionne mais elle est très chronophage car la recherche par force brute est effectuée et le calcul de distance est effectué sur des vecteurs décompressés à haute dimension.

Une autre façon possible est de diviser un vecteur de requête en sous-vecteurs et de calculer une somme de distances de chaque sous-vecteur de requête aux vecteurs quantifiés respectifs d’un vecteur de base, en fonction de son code PQ. En conséquence, la technique de recherche par force brute est utilisée à nouveau et le calcul de distance ici nécessite toujours un temps linéaire de la dimensionnalité des vecteurs d’origine, comme dans le cas précédent.

Une autre méthode possible consiste à encoder le vecteur de requête dans un code PQ. Ensuite, ce code PQ est directement utilisé pour calculer des distances à tous les autres codes PQ. Le vecteur de l’ensemble de données avec le code PQ correspondant qui a la plus courte distance est alors considéré comme le voisin le plus proche de la requête. Cette approche est plus rapide que les deux premières car la distance est toujours calculée entre des codes PQ de faible dimension. Cependant, les codes PQ sont composés d’IDs de cluster qui n’ont pas beaucoup de sens sémantique et peuvent être considérés comme une variable catégorielle utilisée explicitement comme une variable réelle. Clairement, c’est une mauvaise pratique et cette méthode peut conduire à une mauvaise qualité de prédiction.

Approche optimisée

Un vecteur de requête est divisé en sous-vecteurs. Pour chacun de ses sous-vecteurs, les distances à tous les centroids de l’espace correspondant sont calculées. En fin de compte, cette information est stockée dans la table d.

Les distances partielles calculées entre les sous-vecteurs et les centroids sont souvent appelées distances partielles.

En utilisant cette table de distance entre sous-vecteurs et centroïdes d, la distance approximative entre la requête et tout vecteur de la base de données peut être facilement obtenue par ses codes PQ:

1. Pour chacun des sous-vecteurs d’un vecteur de la base de données, le centroïde le plus proche j est trouvé (en utilisant les valeurs de mappage des codes PQ) et la distance partielle d[i][j] de ce centroïde au sous-vecteur i de la requête (en utilisant la matrice calculée d) est prise.
2. Toutes les distances partielles sont au carré et additionnées. En prenant la racine carrée de cette valeur, la distance euclidienne approximative est obtenue. Si vous souhaitez savoir comment obtenir des résultats approximatifs pour d’autres métriques également, accédez à la section ci-dessous “Approximation des autres métriques de distance”.

L’utilisation de cette méthode de calcul de distances approximatives suppose que les distances partielles d sont très proches des distances réelles a entre les sous-vecteurs de la requête et de la base de données.

Néanmoins, cette condition peut ne pas être satisfaite, surtout lorsque la distance c entre le sous-vecteur de la base de données et son centroïde est grande. Dans de tels cas, les calculs donnent une précision moindre.

Après avoir obtenu des distances approximatives pour toutes les lignes de la base de données, nous recherchons les vecteurs ayant les plus petites valeurs. Ces vecteurs seront les voisins les plus proches de la requête.

Approximation des autres métriques de distance

Jusqu’à présent, nous avons examiné comment approximer la distance euclidienne en utilisant des distances partielles. Généralisons maintenant la règle pour d’autres métriques également.

Imaginons que nous voulions calculer une métrique de distance entre une paire de vecteurs. Si nous connaissons la formule de la métrique, nous pouvons l’appliquer directement pour obtenir le résultat. Mais parfois, nous pouvons le faire par parties de la manière suivante:

• Les deux vecteurs sont divisés en n sous-vecteurs.
• Pour chaque paire de sous-vecteurs respectifs, la métrique de distance est calculée.
• Les métriques n calculées sont ensuite combinées pour produire la distance réelle entre les vecteurs d’origine.

La distance euclidienne est un exemple de métrique qui peut être calculée par parties. En se basant sur la figure ci-dessus, nous pouvons choisir les fonctions d’agrégation d’être h(z) = z², g(z₀, z₁, …, zₙ) = sum(z₀, z₁, …, zₙ) et f(z) = √z.

Le produit intérieur est un autre exemple de métrique avec des fonctions d’agrégation h(z) = z, g(z₀, z₁, …, zₙ) = somme(z₀, z₁, …, zₙ) et f(z) = z.

Dans le contexte de la quantification de produit, il s’agit d’une propriété très importante car lors de l’inférence, l’algorithme calcule les distances par parties. Cela signifie qu’il serait beaucoup plus problématique d’utiliser des métriques pour la quantification de produit qui n’ont pas cette propriété. La distance cosinus est un exemple de telle métrique.

S’il est encore nécessaire d’utiliser une métrique sans cette propriété, des heuristiques supplémentaires doivent être appliquées pour agréger les distances partielles avec une certaine erreur.

Performance

Le principal avantage de la quantification de produit est une compression massive des vecteurs de base de données qui sont stockés sous forme de codes PQ courts. Pour certaines applications, ce taux de compression peut être encore plus élevé que 95%! Cependant, en plus des codes PQ, la matrice d de taille k x n contenant des vecteurs quantifiés de chaque sous-espace doit être stockée.

La quantification de produit est une méthode de compression avec perte, plus la compression est élevée, plus il est probable que la précision de la prédiction diminuera.

La construction d’un système de représentation efficace nécessite la formation de plusieurs algorithmes de regroupement. En plus de cela, lors de l’inférence, k * n distances partielles doivent être calculées de manière brute et ajoutées pour chacun des vecteurs de base de données, ce qui peut prendre du temps.

Implémentation de Faiss

Faiss (Facebook AI Search Similarity) est une bibliothèque Python écrite en C++ utilisée pour une recherche de similarité optimisée. Cette bibliothèque présente différents types d’index qui sont des structures de données utilisées pour stocker efficacement les données et effectuer des requêtes.

Sur la base des informations de la documentation de Faiss, nous verrons comment la quantification de produit est utilisée.

La quantification de produit est implémentée dans la classe IndexPQ. Pour l’initialisation, nous devons lui fournir 3 paramètres:

• d : nombre de dimensions dans les données.
• M : nombre de divisions pour chaque vecteur (le même paramètre que n utilisé ci-dessus).
• nbits : nombre de bits nécessaires pour coder un seul ID de cluster. Cela signifie que le nombre total de clusters dans un seul sous-espace sera égal à k = 2^nbits.

Pour une division de dimensions d’espace égales, le paramètre dim doit être divisible par M.

Le nombre total d’octets requis pour stocker un seul vecteur est égal à:

Comme nous pouvons le voir dans la formule ci-dessus, pour une utilisation plus efficace de la mémoire, la valeur de M * nbits doit être divisible par 8.

Conclusion

Nous avons examiné un algorithme très populaire dans les systèmes de récupération d’informations qui compresse efficacement de grands volumes de données. Son principal inconvénient est une vitesse d’inférence lente. Malgré ce fait, l’algorithme est largement utilisé dans les applications modernes de Big data, en particulier en combinaison avec d’autres techniques de recherche de similarité.

Dans la première partie de la série d’articles, nous avons décrit le flux de travail de l’index de fichier inversé. En fait, nous pouvons fusionner ces deux algorithmes en un seul plus efficace qui possédera les avantages des deux! C’est exactement ce que nous allons faire dans la prochaine partie de cette série.

Recherche de similarité, partie 3: Fusion de l’index de fichier inversé et de la quantification de produit

Dans les deux premières parties de cette série, nous avons discuté de deux algorithmes fondamentaux dans la récupération d’informations: l’inversion …

IPGirl.com

Ressources

• Quantification de produits pour la recherche des plus proches voisins
• Documentation de Faiss
• Dépôt de Faiss
• Résumé des index Faiss

Toutes les images, sauf indication contraire, sont de l’auteur.

We will continue to update IPGirl; if you have any questions or suggestions, please contact us!