FARGO : Recherche rapide du produit scalaire maximal via multi-sondage global

01/01/2023

Comprendre la recherche du produit scalaire maximal : de la théorie à la pratique

À mesure que l’apprentissage automatique et l’intelligence artificielle continuent de progresser, la capacité à effectuer efficacement des recherches dans des espaces vectoriels de grande dimension est devenue de plus en plus cruciale. Un défi fondamental dans ce domaine est le problème de la recherche du produit scalaire maximal (Maximum Inner Product Search, MIPS), qui consiste à trouver, dans un jeu de données, les vecteurs qui maximisent leur produit scalaire avec un vecteur de requête donné. Cette opération est au cœur de nombreuses applications, notamment les systèmes de recommandation, la prédiction d’étiquettes multi-classes, la récupération d’éléments similaires, les SVM structuraux et l’apprentissage profond.

Les approches traditionnelles du MIPS utilisant des arbres de partitionnement de l’espace deviennent exponentiellement plus lentes à mesure que la dimensionnalité augmente, ce qui les rend impraticables pour les applications modernes qui traitent souvent des centaines ou des milliers de dimensions. Bien que le hachage sensible à la localité (Locality-Sensitive Hashing, LSH) se soit révélé efficace pour la recherche approximative des plus proches voisins, il ne peut pas être appliqué directement au MIPS en raison des propriétés uniques de la similarité par produit scalaire. Le besoin d’une solution efficace et évolutive au MIPS n’a jamais été aussi pressant, alors que les organisations traitent des jeux de données de plus en plus volumineux, à grande échelle et de grande dimension.

Cet article présente FARGO, un nouveau cadre qui révolutionne notre manière d’aborder le problème du MIPS. Nous présentons une analyse complète des solutions MIPS actuelles, de leurs limites et de la façon dont FARGO surmonte ces défis grâce à des techniques innovantes, notamment le multi-sondage global et la transformation XBOX aléatoire. Notre cadre atteint non seulement une précision et une efficacité supérieures par rapport aux méthodes existantes, mais fournit également des solutions pratiques pour les applications réelles traitant des données de grande dimension à grande échelle.

Obtenir le livre blanc