Introduction à la recherche de similarité vectorielle
Dans les tutoriels précédents, nous avons examiné les données non structurées, les bases de données vectorielles et Milvus - la base de données vectorielle open source la plus populaire au monde, utilisée pour la recherche par similarité. Nous avons également abordé brièvement l’idée des embeddings, des vecteurs de grande dimension qui servent d’excellentes représentations sémantiques des données non structurées. Un point essentiel à retenir : les embeddings et les représentations vectorielles qui sont « proches » les uns des autres représentent des éléments de données sémantiquement similaires.
Dans cette introduction à la recherche vectorielle (alias recherche par similarité), nous définirons ce qu’elle est et répondrons à quelques questions fondamentales à son sujet. Ensuite, nous nous appuierons sur ces connaissances en examinant un exemple d’embedding de mots et en voyant comment des éléments de données non structurées sémantiquement similaires sont « proches » les uns des autres, tandis que des éléments de données non structurées dissemblables sont « éloignés » les uns des autres. Cela mènera à une vue d’ensemble de haut niveau de la recherche du plus proche voisin, un problème informatique qui consiste à trouver le ou les vecteurs les plus proches d’un vecteur de requête sur la base d’une métrique de distance unifiée. Nous passerons en revue quelques méthodes bien connues (algorithmes de recherche de similarité vectorielle) pour la recherche du plus proche voisin (y compris ma préférée - ANNOY), ainsi que des métriques de distance couramment utilisées.
Plongeons-nous dedans.
Qu’est-ce que la recherche vectorielle ou la recherche de similarité vectorielle ?
La recherche vectorielle, également connue sous le nom de recherche de similarité vectorielle, de recherche du plus proche voisin ou de recherche sémantique, est une technique utilisée dans les systèmes de récupération de données et de recherche d’information pour trouver des éléments ou des points de données similaires ou étroitement liés à un vecteur de requête donné. Contrairement à la recherche traditionnelle par mots-clés, qui fait correspondre des mots ou des expressions exacts, la recherche sémantique comprend l’intention et le sens contextuel d’une requête, ce qui lui permet de renvoyer des résultats plus pertinents même lorsque les mots-clés exacts ne sont pas présents dans le contenu. Dans la recherche vectorielle, nous représentons les points de données, tels que les images, les textes et l’audio, sous forme de vecteurs dans un espace de grande dimension. L’objectif de la recherche vectorielle est de rechercher et de récupérer efficacement les vecteurs les plus pertinents qui sont similaires ou les plus proches d’un vecteur de requête.
En général, des métriques de distance telles que la distance euclidienne ou la similarité cosinus mesurent la similarité entre les vecteurs. La proximité du vecteur dans l’espace vectoriel détermine à quel point il est similaire. Pour organiser et afficher efficacement les résultats de recherche pour les vecteurs, les algorithmes de recherche vectorielle utilisent des structures d’indexation telles que des structures arborescentes ou des techniques de hachage.
La recherche vectorielle est au cœur des bases de données vectorielles et possède diverses applications, notamment les systèmes de recommandation, la récupération d’images et de vidéos, le traitement du langage naturel, la détection d’anomalies et les chatbots de questions-réponses. L’utilisation de la recherche sémantique permet de trouver des éléments, des motifs ou des relations pertinents au sein de données de grande dimension, rendant possible une récupération d’information plus précise et plus efficace.
La recherche vectorielle est une méthode puissante pour analyser et récupérer des informations à partir d’espaces de grande dimension. Elle permet aux utilisateurs de trouver des éléments similaires ou étroitement liés à une requête donnée, ce qui la rend cruciale dans divers domaines. Voici les avantages de la recherche vectorielle :
Récupération basée sur la similarité— La recherche sémantique permet une récupération basée sur la similarité, permettant aux utilisateurs de trouver des éléments similaires ou étroitement liés à une requête donnée. La récupération basée sur la similarité est cruciale dans divers domaines, tels que les systèmes de recommandation, où les utilisateurs attendent des recommandations personnalisées en fonction de leurs préférences ou de leurs similarités avec d’autres utilisateurs.
Analyse de données à haute dimension — Avec la disponibilité croissante de données à haute dimension, telles que les images, l’audio et les données textuelles, les méthodes de recherche traditionnelles deviennent moins efficaces. La recherche vectorielle fournit un moyen puissant d’analyser et de récupérer des informations à partir d’espaces à haute dimension, permettant une exploration des données plus précise et plus efficace.
Recherche des plus proches voisins — Les algorithmes efficaces de recherche des plus proches voisins trouvent les plus proches voisins d’un vecteur de requête donné. La recherche des plus proches voisins est pratique pour des tâches critiques telles que la recherche de similarité d’images ou de documents, la récupération basée sur le contenu, ou la détection d’anomalies qui nécessitent de trouver les correspondances les plus proches ou des éléments similaires.
Expérience utilisateur améliorée— En tirant parti de la recherche sémantique, les applications peuvent fournir aux utilisateurs des résultats plus pertinents et personnalisés. Qu’il s’agisse de fournir des recommandations pertinentes, de récupérer des images visuellement similaires ou de trouver des documents au contenu similaire, la recherche vectorielle améliore l’expérience utilisateur globale en fournissant des résultats plus ciblés et significatifs.
Scalabilité — Les algorithmes de recherche vectorielle et les structures d’indexation gèrent efficacement les ensembles de données à grande échelle et les espaces à haute dimension. Ils permettent des opérations de recherche et de récupération rapides, rendant possible l’exécution de requêtes basées sur la similarité en temps réel, même sur des ensembles de données massifs.
Comment fonctionne un moteur de recherche vectorielle ?
Avec la popularité de l’IA et des LLMs, chaque outil de développement, moteur de recherche et base de données ajoute des capacités de recherche vectorielle à son ensemble de fonctionnalités, et de ce fait, les termes moteur vectoriel et moteurs de recherche vectorielle sont souvent utilisés de manière interchangeable avec bases de données vectorielles. Les moteurs de recherche vectorielle effectueront une recherche sémantique vectorielle (parfois appelée recherche vectorielle). La recherche vectorielle est une technique permettant de trouver des éléments ou des points de données similaires dans un ensemble de données en fonction de leur représentation sous forme de vecteurs dans un espace à haute dimension. Chaque élément est associé à un point dans cet espace, chaque dimension vectorielle représentant une caractéristique spécifique. Le processus de recherche vectorielle implique l’indexation, l’interrogation, le classement et la récupération.
Pour effectuer une recherche vectorielle, vous représentez d’abord vos éléments de données sous forme de vecteurs, en utilisant des techniques comme Word2Vec ou pour les données textuelles. Une structure de données d’index stocke efficacement ces vecteurs pour une récupération rapide, en utilisant des méthodes comme les KD-trees ou les tables de hachage. Lorsqu’un utilisateur soumet un élément de requête, il est converti en représentation vectorielle, comparé aux vecteurs indexés à l’aide de métriques de similarité comme la similarité cosinus ou la distance euclidienne, et les éléments les plus similaires sont récupérés et classés.
Cas d’utilisation de la recherche vectorielle
- Recherche de similarité d’images, de vidéos, d’audio
- Découverte de médicaments par IA
- Moteur de recherche sémantique
- Classification de séquences d’ADN
- Système de réponse aux questions
- Système de recommandation
- Détection d’anomalies
- Génération augmentée par récupération (RAG)
Maintenant que nous avons couvert les bases de la recherche vectorielle, examinons les détails plus techniques en regardant un exemple de plongement lexical et terminons par un aperçu général de la recherche des plus proches voisins.
Comparaison des embeddings
Une fois que les utilisateurs décident de se lancer dans la création d’une recherche vectorielle dans leur solution, la question suivante qu’ils posent souvent est « Quel modèle de Machine Learning devrais-je utiliser pour créer des Vector Embeddings. » Avant de pouvoir choisir un modèle, il est important de comprendre les plongements vectoriels en comparant quelques exemples. Passons en revue quelques exemples de plongements lexicaux. Par souci de simplicité, nous utiliserons word2vec, un ancien modèle qui utilise une méthodologie d’entraînement basée sur les skipgrams. BERT et d’autres modèles modernes basés sur des transformeurs pourront vous fournir des plongements lexicaux plus contextualisés, mais nous nous en tiendrons à word2vec pour simplifier. Jay Alammar propose un excellent tutoriel sur word2vec, si vous souhaitez utiliser un peu plus les modèles de machine learning.
Quelques préparatifs
Avant de commencer, nous devrons installer la bibliothèque gensim et charger un modèle word2vec.
% pip install gensim --disable-pip-version-check
% wget https://s3.amazonaws.com/dl4j-distribution/GoogleNews-vectors-negative300.bin.gz
% gunzip GoogleNews-vectors-negative300.bin
Requirement already satisfied: gensim in /Users/fzliu/.pyenv/lib/python3.8/site-packages (4.1.2)
Requirement already satisfied: smart-open>=1.8.1 in /Users/fzliu/.pyenv/lib/python3.8/site-packages (from gensim) (5.2.1)
Requirement already satisfied: numpy>=1.17.0 in /Users/fzliu/.pyenv/lib/python3.8/site-packages (from gensim) (1.19.5)
Requirement already satisfied: scipy>=0.18.1 in /Users/fzliu/.pyenv/lib/python3.8/site-packages (from gensim) (1.7.3)
--2022-02-22 00:30:34-- https://s3.amazonaws.com/dl4j-distribution/GoogleNews-vectors-negative300.bin.gz
Resolving s3.amazonaws.com (s3.amazonaws.com)... 52.216.20.165
Connecting to s3.amazonaws.com (s3.amazonaws.com)|52.216.20.165|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 1647046227 (1.5G) [application/x-gzip]
Saving to: GoogleNews-vectors-negative300.bin.gz
GoogleNews-vectors- 100%[===================>] 1.53G 2.66MB/s in 11m 23s
2022-02-22 00:41:57 (2.30 MB/s) - GoogleNews-vectors-negative300.bin.gz saved [1647046227/1647046227]
gunzip: GoogleNews-vectors-negative300.bin: unknown suffix -- ignored
Maintenant que nous avons effectué tout le travail de préparation nécessaire pour générer des plongements mot-vers-vecteur, chargeons le modèle word2vec entraîné.
>>> from gensim.models import KeyedVectors
>>> model = KeyedVectors.load_word2vec_format('GoogleNews-vectors-negative300.bin', binary=True)
Exemple 0 : Marlon Brando
Voyons comment word2vec interprète le célèbre acteur Marlon Brando.
>>> print(model.most_similar(positive=['Marlon_Brando']))
[('Brando', 0.757453978061676), ('Humphrey_Bogart', 0.6143958568572998), ('actor_Marlon_Brando', 0.6016287207603455), ('Al_Pacino', 0.5675410032272339), ('Elia_Kazan', 0.5594002604484558), ('Steve_McQueen', 0.5539456605911255), ('Marilyn_Monroe', 0.5512186884880066), ('Jack_Nicholson', 0.5440199375152588), ('Shelley_Winters', 0.5432392954826355), ('Apocalypse_Now', 0.5306933522224426)]
Marlon Brando a travaillé avec Al Pacino dans The Godfather et Elia Kazan dans A Streetcar Named Desire. Il a également joué dans Apocalypse Now.
Exemple 1 : Si tous les rois avaient leurs reines sur le trône
Les vecteurs peuvent être additionnés et soustraits les uns des autres afin de démontrer les changements sémantiques sous-jacents.
>>> print(model.most_similar(positive=['king', 'woman'], negative=['man'], topn=1))
[('queen', 0.7118193507194519)]
Qui a dit que les ingénieurs ne pouvaient pas apprécier un peu de dance-pop de temps en temps ?
Exemple 2 : Apple, l’entreprise, le fruit, ... ou les deux ?
Le mot « apple » peut désigner à la fois l’entreprise ainsi que le délicieux fruit rouge. Dans cet exemple, nous pouvons voir que Word2Vec conserve les deux sens.
>>> print(model.most_similar(positive=['samsung', 'iphone'], negative=['apple'], topn=1))
>>> print(model.most_similar(positive=['fruit'], topn=10)[9:])
[('droid_x', 0.6324754953384399)]
[('apple', 0.6410146951675415)]
« Droid » fait référence au premier smartphone 4G LTE de Samsung (« Samsung » + « iPhone » - « Apple » = « Droid »), tandis que « apple » est le 10e mot le plus proche de « fruit ».
Stratégies de recherche vectorielle
Maintenant que nous avons vu la puissance des plongements vectoriels, examinons brièvement certaines des façons dont nous pouvons effectuer une recherche du plus proche voisin. Il ne s’agit pas d’une liste exhaustive ; nous allons simplement passer brièvement en revue quelques méthodes courantes afin de fournir un aperçu général de la façon dont la recherche vectorielle est menée à grande échelle. Notez que certaines de ces méthodes ne s’excluent pas mutuellement - il est possible, par exemple, d’utiliser la quantification conjointement avec le partitionnement de l’espace.
(Nous examinerons également chacune de ces méthodes en détail dans de futurs tutoriels, alors restez à l’écoute.)
Recherche linéaire
L’algorithme de recherche du plus proche voisin le plus simple, mais aussi le plus naïf, est la bonne vieille recherche linéaire : calculer la distance entre un vecteur de requête et tous les autres vecteurs de la base de données vectorielle.
Pour des raisons évidentes, la recherche naïve ne fonctionne pas lorsque l’on tente de faire passer notre base de données vectorielle à des dizaines ou des centaines de millions de vecteurs. Mais lorsque le nombre total d’éléments dans la base de données est faible, cela peut en fait être la manière la plus efficace d’effectuer une recherche vectorielle, puisqu’une structure de données distincte pour l’index n’est pas nécessaire, tandis que les insertions et les suppressions peuvent être mises en œuvre assez facilement.
En raison de l’absence de complexité spatiale ainsi que de la surcharge d’espace constante associée à la recherche naïve, cette méthode peut souvent surpasser le partitionnement de l’espace même lors de requêtes portant sur un nombre modéré de vecteurs.
Partitionnement de l’espace
Le partitionnement de l’espace n’est pas un algorithme unique, mais plutôt une famille d’algorithmes qui utilisent tous le même concept.
Les arbres k-dimensionnels (kd-trees) sont peut-être les plus connus de cette famille, et fonctionnent en bissectant continuellement l’espace de recherche (en divisant les vecteurs en compartiments “gauche” et “droite”) d’une manière similaire aux arbres de recherche binaires.
L’index de fichier inversé (IVF) est également une forme de partitionnement de l’espace, et fonctionne en attribuant chaque vecteur à son centroïde le plus proche - les recherches sont ensuite effectuées en déterminant d’abord le centroïde le plus proche du vecteur de requête et en menant la recherche autour de celui-ci, ce qui réduit considérablement le nombre total de vecteurs à rechercher. IVF est une stratégie d’indexation assez populaire et est couramment combinée avec d’autres algorithmes d’indexation pour améliorer les performances.
Quantification
La quantification est une technique permettant de réduire la taille totale de la base de données en réduisant la précision des vecteurs.
La quantification scalaire (SQ), par exemple, fonctionne en multipliant des vecteurs à virgule flottante de haute précision par une valeur scalaire, puis en convertissant les éléments du vecteur résultant en leurs entiers les plus proches. Cela réduit non seulement la taille effective de l’ensemble de la base de données (par exemple d’un facteur huit pour une conversion de float64_t vers int8_t), mais a également l’effet secondaire positif d’accélérer les calculs de distance vectorielle entre vecteurs.
La quantification produit (PQ) est une autre technique de quantification qui fonctionne de manière similaire à la compression par dictionnaire. Dans PQ, tous les vecteurs sont divisés en sous-vecteurs de taille égale, et chaque sous-vecteur est ensuite remplacé par un centroïde.
Hierarchical Navigable Small Worlds (HNSW)
Hierarchical Navigable Small Worlds est un algorithme d’indexation et de récupération basé sur les graphes.
Cela fonctionne différemment de la quantification produit : au lieu d’améliorer la capacité de recherche dans la base de données en réduisant sa taille effective, HNSW crée un graphe multicouche à partir des données d’origine. Les couches supérieures ne contiennent que des "connexions longues", tandis que les couches inférieures ne contiennent que des "connexions courtes" entre les vecteurs de la base de données (voir la section suivante pour un aperçu des métriques de distance vectorielle). Les connexions individuelles du graphe sont créées à la manière des skip lists.
Avec cette architecture en place, la recherche devient assez simple – nous parcourons gloutonnement le graphe le plus haut (celui avec les connexions inter-vecteurs les plus longues) pour trouver le vecteur le plus proche de notre vecteur de requête. Nous faisons ensuite de même pour la deuxième couche, en utilisant le résultat de la recherche de la première couche comme point de départ. Cela continue jusqu’à ce que nous terminions la recherche à la couche la plus basse, dont le résultat devient le plus proche voisin du vecteur de requête.
HNSW, visualisé. Source de l’image : https://arxiv.org/abs/1603.09320
Approximate Nearest Neighbors Oh Yeah
C’est probablement mon algorithme ANN préféré, simplement en raison de son nom ludique et peu intuitif. Approximate Nearest Neighbors Oh Yeah (ANNOY) est un algorithme fondé sur des arbres, popularisé par Spotify (il est utilisé dans leur système de recommandation musicale). Malgré ce nom étrange, le concept sous-jacent d’ANNOY est en réalité assez simple : des arbres binaires.
ANNOY fonctionne en sélectionnant d’abord aléatoirement deux vecteurs dans la base de données et en bissectant l’espace de recherche le long de l’hyperplan séparant ces deux vecteurs. Cela est fait de manière itérative jusqu’à ce qu’il y ait moins qu’un certain paramètre prédéfini NUM_MAX_ELEMS par nœud. Puisque l’index obtenu est essentiellement un arbre binaire, cela nous permet d’effectuer notre recherche avec une complexité en O(log n).
ANNOY, visualisé. Source de l’image : https://github.com/spotify/annoy
Métriques de similarité couramment utilisées
Les toutes meilleures bases de données vectorielles sont inutiles sans métriques de similarité : des méthodes pour calculer la distance entre deux vecteurs. De nombreuses métriques existent, nous ne discuterons donc ici que du sous-ensemble le plus couramment utilisé.
Métriques de similarité pour vecteurs à virgule flottante
Les métriques de similarité pour vecteurs à virgule flottante les plus courantes sont, sans ordre particulier, la distance L1, la distance L2 et la similarité cosinus. Les deux premières valeurs sont des métriques de distance (des valeurs plus faibles impliquent une plus grande similarité tandis que des valeurs plus élevées impliquent une similarité plus faible), tandis que la similarité cosinus est une métrique de similarité (des valeurs plus élevées impliquent une plus grande similarité).
La distance L1 est aussi couramment appelée distance de Manhattan, nommée à juste titre d’après le fait qu’aller du point A au point B à Manhattan nécessite de se déplacer le long de l’une de deux directions perpendiculaires. La deuxième équation, la distance L2, est simplement la distance entre deux vecteurs dans l’espace euclidien. La troisième et dernière équation est la distance cosinus, équivalente au cosinus de l’angle entre deux vecteurs. Notez que l’équation de la similarité cosinus revient au produit scalaire entre les versions normalisées des vecteurs d’entrée a et b.
Avec un peu de mathématiques, nous pouvons également montrer que la distance L2 et la similarité cosinus sont effectivement équivalentes lorsqu’il s’agit de classer la similarité pour des vecteurs de norme unitaire :
Rappelez-vous que les vecteurs de norme unitaire ont une magnitude de 1 :
Avec cela, nous obtenons :
Puisque nous avons des vecteurs de norme unitaire, la distance cosinus revient au produit scalaire entre a et b (le dénominateur dans l’équation 3 ci-dessus vaut 1) :
Essentiellement, pour des vecteurs de norme unitaire, la distance L2 et la similarité cosinus sont fonctionnellement équivalentes ! N’oubliez jamais de normaliser vos embeddings.
Métriques de similarité pour vecteurs binaires
Les vecteurs binaires, comme leur nom l’indique, n’ont pas de métriques fondées sur l’arithmétique à la manière des vecteurs à virgule flottante. Les métriques de similarité pour vecteurs binaires reposent plutôt sur la théorie des ensembles, la manipulation de bits, ou une combinaison des deux (ce n’est pas grave, moi aussi je déteste les mathématiques discrètes). Voici les formules de deux métriques de similarité pour vecteurs binaires couramment utilisées :
La première équation est appelée distance de Tanimoto/Jaccard, et constitue essentiellement une mesure du degré de chevauchement entre deux vecteurs binaires. La deuxième équation est la distance de Hamming, et correspond au nombre d’éléments vectoriels dans a et b qui diffèrent les uns des autres.
Vous pouvez très probablement ignorer ces métriques de similarité en toute sécurité, puisque la majorité des applications utilisent la similarité cosinus sur des embeddings à virgule flottante.
Conclusion
Dans ce tutoriel, nous avons examiné la recherche vectorielle, ainsi que quelques algorithmes courants de recherche vectorielle et métriques de distance. Voici quelques points clés à retenir :
Les vecteurs d’embedding sont des représentations puissantes, à la fois en termes de distance entre les vecteurs et en termes d’arithmétique vectorielle. En appliquant une quantité généreuse d’algèbre vectorielle aux embeddings, nous pouvons effectuer une analyse sémantique évolutive en utilisant uniquement des opérateurs mathématiques de base.
La recherche vectorielle sémantique surmonte la limitation de la recherche par mots-clés en vous permettant de rechercher en fonction du sens de votre requête. Elle permet une récupération rapide des réponses en effectuant une recherche vectorielle.
Il existe une grande variété d’algorithmes de recherche approximative des plus proches voisins et/ou de types d’index parmi lesquels choisir. Le plus couramment utilisé aujourd’hui est HNSW, mais un autre algorithme d’indexation peut mieux convenir à votre application particulière, en fonction du nombre total d’embeddings vectoriels dont vous disposez en plus de la longueur de chaque vecteur individuel.
Les deux principales métriques de distance utilisées aujourd’hui sont la distance L2/euclidienne et la distance cosinus. Ces deux métriques, lorsqu’elles sont utilisées sur des embeddings normalisés, sont fonctionnellement équivalentes.
Merci de nous avoir rejoints pour ce tutoriel ! La recherche vectorielle est un élément central de Milvus, et elle continuera de l’être. Dans de futurs tutoriels, nous approfondirons les algorithmes ANNS les plus couramment utilisés - HNSW et ScaNN.
Revoir les cours Vector Database 101
- Introduction aux données non structurées
- Qu’est-ce qu’une base de données vectorielle ?
- Comparer les bases de données vectorielles, les bibliothèques de recherche vectorielle et les plugins de recherche vectorielle
- Introduction à Milvus
- Démarrage rapide avec Milvus
- Introduction à la recherche de similarité vectorielle
- Bases de l’index vectoriel et de l’index de fichier inversé
- Quantification scalaire et quantification produit
- Hierarchical Navigable Small Worlds (HNSW)
- Approximate Nearest Neighbors Oh Yeah (ANNOY)
- Choisir le bon index vectoriel pour votre projet
- DiskANN et l’algorithme Vamana
Continuer à lire
What Exactly Are AI Agents? Why OpenAI and LangChain Are Fighting Over Their Definition?
AI agents are software programs powered by AI that can perceive their environment, make decisions, and take actions to achieve a goal—often autonomously.
How to Build RAG with Milvus, QwQ-32B and Ollama
Hands-on tutorial on how to create a streamlined, powerful RAG pipeline that balances efficiency, accuracy, and scalability using the QwQ-32B and Milvus.
Optimizing Embedding Model Selection with TDA Clustering: A Strategic Guide for Vector Databases
Discover how Topological Data Analysis (TDA) reveals hidden embedding model weaknesses and helps optimize vector database performance.