Recherche approximative des plus proches voisins dans les systèmes de recommandation
Introduction
En février 2024, nous avons entendu Yury Malkov au SF Unstructured Data Meetup parler de l’Approximate Nearest Neighbor (ANN) et de son rôle clé dans les systèmes de recommandation. La recherche ANN est déjà intégrée dans les stacks de production des outils les plus populaires au monde. Yury nous aide à comprendre les concepts clés et le contexte qui ont favorisé l’adoption de l’ANN dans les systèmes de recommandation à grande échelle.
Lien vers le replay YouTube de la conférence de Yury Malkov : Regarder la conférence sur YouTube
Pourquoi devriez-vous vous intéresser à l’ANN ?
Yuri Malkov est littéralement un génie. Si vous ne me croyez pas, consultez sa page Google Scholar https://scholar.google.com/citations?user=KvAyakQAAAAJ&hl=en. Physicien, chercheur en lasers, et inventeur de HNSW - un algorithme d’indexation basé sur les graphes désormais intégré par défaut dans toutes les principales bases de données vectorielles. Il travaille désormais chez OpenAI en tant que Research Scientist. Dites-moi que cela ne ressemble pas à une biographie plausible de Tony Stark en 2024.
Sur ce, plongeons dans la conférence de Yuri sur “Approximate Nearest Neighbor Search in Recommender Systems.”
Qu’est-ce que la recherche ANN ?
Nous resterons brefs, car nous avons déjà couvert les bases de la recherche ANN en résumé et en détail.
Les recherches de plus proches voisins sont un ensemble de techniques statistiques que nous pouvons utiliser pour effectuer des recherches de similarité dans des applications de machine learning ou de data science. Contrairement à leur cousin aromatisé K, le KNN, qui compare chaque point de données d’un système à tous les autres lors de la recherche, les algorithmes de recherche ANN utilisent diverses techniques d’indexation pour renvoyer des plus proches voisins approximatifs. Les recherches ANN sont devenues centrales pour de nombreuses applications et technologies destinées aux clients aujourd’hui. Des moteurs de recherche (comme Google, pas la recherche vectorielle) aux sites de réseaux sociaux, l’ANN et les systèmes de recommandation sont déjà intégrés dans toute la stack, en production.
L’ANN n’était pas la seule solution pour les systèmes de recommandation. Alors, comment en sommes-nous arrivés là ? Nous passerons en revue les solutions ANN matures disponibles sur le marché aujourd’hui, ce qui fait des systèmes de recommandation un problème difficile pour les algos de plus proches voisins, comment les développeurs ont structuré les systèmes de recommandation, et comment les chercheurs utilisent l’ANN pour réécrire la stack des systèmes de recommandation. Yuri note dans sa conférence qu’il existe de nombreuses solutions ANN matures. Beaucoup de ces sujets sont traités en profondeur dans notre Guide visuel pour choisir un index vectoriel, mais j’ai préparé un tableau des outils listés dans la présentation de Yuri.
Tableau des index ANN mentionnés
| Indice ANN | Classification | Scénario |
|---|---|---|
| LSH | Index basé sur un graphe | - Grands jeux de données multidimensionnels très complexes - Utilise la distance euclidienne pour regrouper les points de données en compartiments - Ne renvoie que les résultats les plus proches |
| HNSW | Index basé sur un graphe | - Requête à très grande vitesse - Nécessite un taux de rappel aussi élevé que possible - Grandes ressources mémoire |
| SCANN | Index basé sur la quantification | - Requête à très grande vitesse - Nécessite un taux de rappel aussi élevé que possible - Grandes ressources mémoire |
| IVF_PQ | Index basé sur la quantification (inversé) | - Index inversé - Requête à très grande vitesse - Ressources mémoire limitées - Accepte un compromis substantiel sur le taux de rappel |
| IVF_HSNW | Index basé sur un graphe (inversé) | - Index inversé - Basé sur HSNW - Nécessite un taux de rappel aussi élevé que possible - Grandes ressources mémoire |
| DiskANN | Plusieurs indices de plus proches voisins | - Modifications ANN et boîte à outils pour les recherches ANN |
| ANNOY | Plusieurs indices de plus proches voisins | - Implémentations LSH ou KDtrees - Recherche économe en mémoire et rapide dans les espaces de grande dimension |
| Beaucoup d’autres | - | - FAISS, cuHNSW, ngt, song |
À propos des benchmarks ANN
Yuri parcourt les benchmarks ANN à toute vitesse - en pointant vers ANNBenchmarks avec une mise en garde : benchmarker des algorithmes ANN inverses peut devenir délicat. Ralentissons un peu :
Qu’est-ce qu’ANN-Benchmarks ?
ANN-Benchmarks est un environnement de benchmark qui évalue divers algorithmes de recherche approximative des plus proches voisins, en fournissant sur leur site web des résultats ventilés par mesure de distance et par jeu de données. Les benchmarks affichent des métriques de performance comme le taux de rappel et les requêtes par seconde, et les utilisateurs peuvent contribuer en soumettant leur code via des pull requests GitHub .
Bien que vous puissiez trouver des données de benchmark d’algorithmes ANN à de nombreux endroits (github, ANN-Benchmarks, même dans la documentation produit), vous verrez toujours des graphiques traçant les QPS - requêtes par seconde. Plus de QPS, c’est mieux ! Vroum vroum !
Une note sur le choix des algorithmes ANN (et autres algorithmes de recherche vectorielle)
Si regarder les benchmarks d’algorithmes vous donne des saignements de nez, vous n’êtes pas seul. C’est pourquoi l’équipe Milvus a créé Knowhere. Knowhere est le moteur d’exécution vectorielle open source central de Milvus, qui intègre plusieurs bibliothèques de recherche de similarité vectorielle, notamment Faiss, Hnswlib et Annoy. Knowhere contrôle sur quel matériel (CPU ou GPU) exécuter la construction d’index et les requêtes de recherche. C’est ainsi que Knowhere tire son nom : savoir où exécuter les opérations. D’autres types de matériel, notamment les DPU et les TPU, seront pris en charge dans les prochaines versions.
S’appuyant sur Knowhere, l’équipe de Zilliz Cloud a lancé Cardinal, qui est le moteur de recherche vectorielle central de Zilliz. Ce moteur de recherche a déjà démontré une multiplication par trois des performances par rapport à la version précédente, offrant une performance de recherche (QPS) atteignant dix fois celle de Milvus. La recherche ANN est intégrée depuis longtemps aux systèmes de recommandation. Pour comprendre pourquoi les algorithmes de recherche ANN sont devenus si populaires dans les systèmes de recommandation en production, nous devons prendre du recul et examiner les motivations, l’architecture et les solutions novatrices que l’ANN a surpassées.
Applications des systèmes de recommandation à grande échelle : motivations et défis
Objectif : L’objectif fondamental de tous les systèmes de recommandation est de renvoyer un élément (vidéo, produit, document, message) à une requête (utilisateur, application, contexte). Gardez à l’esprit cette relation élément-requête : elle est importante pour comprendre les algorithmes de recherche (recommandation).
Marché : Les technologies de recommandation ont représenté et représentent un vaste marché, compte tenu de leur capacité à générer des comportements de consommation.
Défis typiques à grande échelle :
Généralisabilité :
- Traditionnellement, les systèmes de recommandation ont eu une faible généralisabilité, en grande partie en raison de leur dépendance aux données, modèles et infrastructures internes.
Corpus énormes :
Les grands ensembles de données (de millions à des milliers de milliards d’éléments, de requêtes) génèrent des coûts d’inférence élevés.
L’efficacité et la limitation des coûts d’inférence sont très importantes.
Le traitement intensif de vidéos et d’images a nécessité des ingénieurs dédiés pour maintenir l’infrastructure.
Solutions, maturité :
Les solutions/infrastructures internes sont généralement développées en interne (par ex. Google, Meta, X,)
Généralement, un entonnoir de recommandation en plusieurs étapes (voir ci-dessous) est utilisé pour réduire les coûts d’inférence
Les outils prêts à l’emploi gagnent en popularité et en traction avec l’essor des bases de données vectorielles et des LLM.
Entonnoir typique en plusieurs étapes
Yuri examine un schéma d’un système de recommandation typique en production. Dans l’exemple ci-dessous pour la recommandation vidéo, une application reçoit des éléments et une requête et doit renvoyer une épingle de recommandation vidéo. Ces applications sont des entonnoirs en plusieurs étapes où des candidats éléments sont générés puis passés dans des modèles de classement successifs afin d’affiner les résultats de recherche.
Étape 1 : Génération de candidats - ANN + Modèle léger
Dans cette étape initiale, le système utilise les plus proches voisins approximatifs pour parcourir rapidement la vaste base de données vidéo et identifier une liste préliminaire de vidéos candidates pertinentes par rapport à la requête de l’utilisateur. Ce processus est conçu pour être rapide et efficace, en traitant potentiellement des millions d’éléments en se concentrant sur ceux qui sont les plus susceptibles de correspondre aux caractéristiques de la requête. Le « Modèle léger » utilisé à cette étape est généralement un modèle plus simple, moins intensif en calcul, qui aide à réduire le vivier de candidats à ceux qui correspondent le mieux aux intérêts ou aux termes de recherche de l’utilisateur.
Étape 2 : Classement léger - Force brute + Modèle intermédiaire
Une fois qu’un ensemble de candidats est généré, l’étape suivante implique un examen plus détaillé de ces candidats. Cela se fait à l’aide d’une approche de « Force brute », où chaque candidat est évalué plus en profondeur au moyen d’un « Modèle intermédiaire », plus complexe que le Modèle léger utilisé lors de la première étape. Ce modèle prend en compte des caractéristiques supplémentaires, telles que les métriques d’engagement des utilisateurs, la pertinence contextuelle et la qualité du contenu, afin de classer les candidats de manière à faire remonter les vidéos les plus pertinentes vers le haut de la liste de recommandations. Cette étape établit un équilibre entre performance et précision, en affinant la sélection en se concentrant davantage sur la qualité et la pertinence.
Étape 3 : Classement complet - Force brute + Modèle lourd
La dernière étape du processus de recommandation est l’étape de classement complet, qui emploie un « Heavy Model » — le plus sophistiqué et le plus gourmand en ressources parmi les modèles utilisés. Ce modèle intègre un large éventail de signaux et de points de données, notamment une analyse plus approfondie du profil utilisateur, les préférences à long terme, une analyse détaillée du contenu et éventuellement des données en temps réel comme les tendances de visionnage actuelles. La méthode Brute Force appliquée ici garantit que chaque vidéo est notée et classée de manière exhaustive, assurant ainsi que les recommandations finales sont hautement personnalisées et pertinentes. Cette étape garantit des recommandations de la plus haute qualité, mais nécessite davantage de puissance de traitement et de temps, ce qui la rend adaptée à l’affinement final de la liste de recommandations.
Pourquoi HSNW échoue pour les systèmes de recommandation traditionnels et solutions (imparfaites) Sachant que les systèmes de recommandation de production à grande échelle sont contraints par de vastes ensembles de données et les coûts associés, Yuri affirme que les éléments et les requêtes se situent sur deux - plans incompatibles. Lorsque les requêtes et les éléments résident dans des espaces différents et incompatibles, les algorithmes traditionnels de recherche par similarité comme Hierarchical Navigable Small World (HNSW) rencontrent des difficultés, car ces algorithmes dépendent d’une relation mesurable ou d’une fonction de distance directement entre la requête et les éléments. Sans métrique claire pour évaluer la proximité, HNSW ne peut pas remplir efficacement sa fonction, qui consiste à naviguer dans un graphe d’éléments pour trouver les correspondances les plus proches d’une requête.****
Revue de solutions nouvelles à l’incompatibilité élément-requête
Distance L2 sur les vecteurs de données
Fonctionnement : Utilise la distance L2 entre des entrées de données vectorisées pour créer une structure de graphe de substitution pour les systèmes de recommandation.
Avantages : Simplifie le processus en utilisant un calcul de distance direct, offrant un avantage de vitesse lors des phases de génération de candidats et de reclassement.
Inconvénients : Peut ne pas capturer les relations complexes ou les nuances entre les éléments et les requêtes aussi efficacement que des modèles plus sophistiqués, ce qui peut conduire à des recommandations moins personnalisées.
Classement par graphe biparti
Fonctionnement : Projette les éléments et les requêtes dans un graphe biparti où les éléments sont liés à leurs utilisateurs ou requêtes les plus proches, ce qui permet de générer des arêtes sur la base de ces relations.
Avantages : Efficace pour structurer les données relationnelles entre utilisateurs et éléments, bien que les comparaisons directes avec d’autres méthodes soient limitées.
Inconvénients : La construction et la maintenance du graphe biparti peuvent être gourmandes en ressources, et l’efficacité peut varier considérablement selon la densité et la qualité des connexions du graphe.
Source de l’image : https://www.vldb.org/pvldb/vol15/p794-tan.pdf
Reclassement par graphe (axé sur le texte)
Fonctionnement : Utilise un graphe créé à partir de vecteurs pour la génération de candidats, en appliquant directement un ranker lourd au graphe pour la récupération de texte, ce qui améliore la qualité des résultats.
Avantages : Élimine l’entonnoir traditionnel à plusieurs étapes, permettant de corriger les erreurs commises lors des étapes antérieures de filtrage des candidats.
Inconvénients : Principalement efficace pour la récupération fondée sur le texte ; peut ne pas être aussi efficace dans d’autres contextes où les caractéristiques non textuelles dominent, ce qui limite son applicabilité.
Source de l’image : https://arxiv.org/pdf/2208.08942
Recherche en graphe en cascade
Comment ça fonctionne : Commence par une fonction de distance légère pour la recherche initiale et passe de manière fluide à une fonction de distance plus lourde au cours du processus de recherche.
Avantages : Offre de la flexibilité en adaptant la fonction de distance en temps réel, optimisant à la fois la vitesse et la précision tout au long du processus de recherche.
Inconvénients : La complexité de la gestion et de l’optimisation de deux fonctions de distance peut augmenter la surcharge computationnelle et la complexité du système, ce qui peut potentiellement impacter la scalabilité.
Source de l’image : https://arxiv.org/pdf/2202.10226
Pourquoi la recherche ANN est-elle si populaire ?
En mettant tout cela bout à bout, Yuri a bien illustré pourquoi les algorithmes ANN ont été si largement mis en œuvre, en particulier dans les applications (comme les systèmes de recommandation à grande échelle) qui travaillent avec des jeux de données de très grande dimension.
Correspondance suffisamment bonne (ou meilleure) - Si vous n’avez pas besoin d’une correspondance parfaite, une variante ANN est presque toujours une meilleure solution que les autres algorithmes NN.
Flexibilité - avec un large éventail d’implémentations, un développeur peut choisir le coût
Maturité - Les ANN ont été implémentés dans tous les principaux langages de programmation, et il existe plusieurs frameworks populaires pour sélectionner et exécuter des recherches ANN.
Ressources complémentaires
https://zilliz.com/learn/Local-Sensitivity-Hashing-A-Comprehensive-Guide
https://zilliz.com/learn/how-to-pick-a-vector-index-in-milvus-visual-guide
Lien vers la rediffusion YouTube de la conférence de Yury Malkov : Regarder la conférence sur YouTube
Continuer à lire
Why We Built Vector Lakebase: Rethinking Unstructured Data Architecture for AI
Vector Lakebase: a unified, lake-native data foundation for AI workloads — and an answer to what happens after vector databases succeed.
Why I’m Against Claude Code’s Grep-Only Retrieval? It Just Burns Too Many Tokens
Learn how vector-based code retrieval cuts Claude Code token consumption by 40%. Open-source solution with easy MCP integration. Try claude-context today.
Similarity Metrics for Vector Search
Exploring five similarity metrics for vector search: L2 or Euclidean distance, cosine distance, inner product, and hamming distance.