Une introduction rapide à la recherche vectorielle

De la recherche vectorielle aux puissantes API REST, Elasticsearch offre aux développeurs la boîte à outils de recherche la plus complète. Explorez nos notebooks d’exemples sur GitHub pour tester de nouveaux cas d’usage. Vous pouvez également démarrer votre essai gratuit ou exécuter Elasticsearch en local dès aujourd’hui.

Cet article est le premier d'une série de trois qui se pencheront sur les subtilités de la recherche vectorielle, également connue sous le nom de recherche sémantique, et sur la manière dont elle est mise en œuvre dans Elasticsearch.

Cette première partie se concentre sur une introduction générale aux bases de l'intégration des vecteurs et au fonctionnement de la recherche vectorielle.

Armé de toutes les connaissances acquises dans le premier article, la deuxième partie vous guidera dans les méandres de la mise en place de la recherche vectorielle dans Elasticsearch.

Dans la troisième partie, nous tirerons parti de ce que nous avons appris dans les deux premières parties, nous nous appuierons sur ces connaissances et nous nous pencherons sur la manière de créer de puissantes requêtes de recherche hybrides dans Elasticsearch.

Avant d'entrer dans le vif du sujet de cet article, remontons dans le temps et passons en revue l'histoire des vecteurs, un concept clé de la recherche sémantique.

Les vecteurs ne sont pas nouveaux

Tout le monde s'accorde à dire que depuis l'avènement de ChatGPT en novembre 2022, il ne se passe pas un jour sans que l'on entende ou lise parler de "recherche vectorielle". Elle est omniprésente et si répandue que nous avons souvent l'impression qu'il s'agit d'une nouvelle technologie de pointe qui vient de voir le jour, alors que la vérité est que cette technologie existe depuis plus de six décennies ! Les recherches sur le sujet ont commencé au milieu des années 1960 et les premiers documents de recherche ont été publiés en 1978 par Gerard Salton, un spécialiste de la recherche d'informations, et ses collègues de l'université de Cornell. Les travaux de Salton sur les modèles de vecteurs denses et épars constituent la base de la technologie moderne de recherche vectorielle.

Au cours des 20 dernières années, de nombreux SGBD vectoriels différents basés sur ses recherches ont été créés et mis sur le marché. Il s'agit notamment d'Elasticsearch alimenté par le projet Apache Lucene, qui a commencé à travailler sur la recherche vectorielle en 2019.

Les vecteurs sont aujourd'hui omniprésents et si répandus qu'il est important de bien comprendre leur théorie sous-jacente et leur fonctionnement interne avant de les utiliser. Avant de nous y plonger, examinons rapidement les différences entre la recherche lexicale et la recherche vectorielle afin de mieux comprendre en quoi elles diffèrent et comment elles peuvent se compléter l'une l'autre.

Recherche vectorielle vs. recherche lexicale

Une façon simple de présenter la recherche vectorielle est de la comparer à la recherche lexicale plus conventionnelle à laquelle vous êtes probablement habitué. La recherche vectorielle, également connue sous le nom de recherche sémantique, et la recherche lexicale fonctionnent de manière très différente. La recherche lexicale est le type de recherche que nous utilisons tous depuis des années dans Elasticsearch. Pour résumer très brièvement, il n'essaie pas de comprendre le sens réel de ce qui est indexé et interrogé, mais fait un gros effort pour faire correspondre lexicalement le littéral des mots ou de leurs variantes (pensez à l'extraction, aux synonymes, etc.) que l'utilisateur tape dans une requête avec tous les littéraux qui ont été précédemment indexés dans la base de données à l'aide d'algorithmes de similarité, tels que le TF-IDF.

Comme nous pouvons le voir, les trois documents en haut à gauche sont codés et analysés. Les termes obtenus sont ensuite indexés dans un index inversé, qui associe simplement les termes analysés aux identifiants des documents qui les contiennent. Notez que tous les termes ne sont présents qu'une seule fois et qu'aucun n'est partagé par un document. La recherche de "gentil professeur d'allemand" aboutira à trois documents avec des scores variables, même si aucun d'entre eux ne reflète réellement le sens de la requête.

Comme le montre la figure 2 ci-dessous, la situation devient encore plus délicate lorsqu'il s'agit de polysémie ou d'homographes, c'est-à-dire de mots qui s'écrivent de la même façon mais qui ont des sens différents (droite, paume, bat, signifie, etc.) Prenons le mot "droite", qui peut avoir trois sens différents, et voyons ce qu'il en est.

La recherche de "I'm not right" renvoie à un document dont la signification est exactement opposée à celle du premier résultat obtenu. Si vous recherchez exactement les mêmes termes mais que vous les ordonnez différemment pour produire un sens différent, par exemple "tourner à droite" et "tourner à droite", vous obtiendrez exactement le même résultat (c'est-à-dire le troisième document "Prendre un virage à droite"). Certes, nos requêtes sont trop simplifiées et n'utilisent pas les requêtes plus avancées telles que la correspondance des phrases, mais cela illustre le fait que la recherche lexicale ne comprend pas la véritable signification de ce qui est indexé et de ce qui est recherché. Si cela n'est pas clair, ne vous inquiétez pas, nous reviendrons sur cet exemple dans le troisième article pour voir comment la recherche vectorielle peut être utile dans ce cas.

Pour rendre justice à la recherche lexicale, lorsque vous avez le contrôle sur la façon dont vous indexez vos données structurées (pensez aux mappings, à l'analyse de texte, aux pipelines d'acquisition, etc.) et sur la façon dont vous élaborez vos requêtes (pensez aux requêtes DSL intelligemment conçues, à l'analyse des termes de la requête, etc. Les résultats d'Elasticsearch concernant ses capacités de recherche lexicale sont tout simplement stupéfiants. Ce qu'il a réalisé et à quel point il a popularisé et amélioré le domaine de la recherche lexicale au cours des dernières années est vraiment remarquable.

Cependant, lorsqu'il s'agit de fournir une assistance pour l'interrogation de données non structurées (images, vidéos, audios, texte brut, etc.) à des utilisateurs qui ont besoin de poser des questions en texte libre, la recherche lexicale n'est pas à la hauteur. De plus, il arrive que la requête ne soit même pas un texte, mais une image, comme nous le verrons bientôt. La principale raison pour laquelle la recherche lexicale est inadéquate dans de telles situations est que les données non structurées ne peuvent être ni indexées ni interrogées de la même manière que les données structurées. Lorsqu'il s'agit de données non structurées, la sémantique entre en jeu. Que signifie la sémantique ? Tout simplement, le sens !

Prenons l'exemple simple d'un moteur de recherche d'images (par exemple, Google Image Search ou Lens). Vous glissez et déposez une image, et le moteur de recherche sémantique de Google trouvera et renverra les images les plus similaires à celle que vous avez interrogée. Dans la figure 3 ci-dessous, on peut voir à gauche la photo d'un berger allemand et à droite toutes les photos similaires qui ont été recherchées, le premier résultat étant la même photo que celle qui a été fournie (c'est-à-dire la plus similaire).

Même si cela semble simple et logique pour nous, les humains, c'est une toute autre histoire pour les ordinateurs. C'est ce que la recherche vectorielle permet et contribue à réaliser. Le pouvoir libéré par la recherche vectorielle est énorme, comme le monde l'a récemment constaté. Soulevons maintenant le capot et découvrons ce qui s'y cache.

Vecteurs d'intégration

Comme nous l'avons vu précédemment, avec les moteurs de recherche lexicaux, les données structurées telles que le texte peuvent facilement être transformées en termes qui peuvent être comparés au moment de la recherche, quelle que soit la signification réelle des termes. Les données non structurées, quant à elles, peuvent prendre différentes formes, telles que des objets binaires de grande taille (images, vidéos, audios, etc.), et ne se prêtent pas du tout au même processus de tokénisation. En outre, l'objectif de la recherche sémantique est d'indexer les données de manière à ce qu'elles puissent être recherchées sur la base de la signification qu'elles représentent. Comment y parvenir ? La réponse tient en deux mots : Apprentissage automatique! Ou plus précisément l'apprentissage en profondeur (Deep Learning) !

L'apprentissage profond est un domaine spécifique de l'apprentissage automatique qui repose sur des modèles basés sur des réseaux neuronaux artificiels composés de plusieurs couches de traitement qui peuvent progressivement extraire le véritable sens des données. Le fonctionnement de ces modèles de réseaux neuronaux s'inspire fortement du cerveau humain. La figure 4, ci-dessous, montre à quoi ressemble un réseau neuronal, avec ses couches d'entrée et de sortie ainsi que ses multiples couches cachées :

La véritable prouesse des réseaux neuronaux est qu'ils sont capables de transformer une simple donnée non structurée en une séquence de valeurs à virgule flottante, connues sous le nom de vecteurs d'intégration ou simplement d'intégration. En tant qu'êtres humains, nous comprenons assez bien ce que sont les vecteurs à condition de les visualiser dans un espace à deux ou trois dimensions. Chaque composante du vecteur représente une coordonnée dans un plan 2D x-y ou un espace 3D x-y-z.

Cependant, les vecteurs d'intégration sur lesquels fonctionnent les modèles de réseaux neuronaux peuvent avoir plusieurs centaines, voire des milliers de dimensions et représentent simplement un point dans un espace multidimensionnel. Chaque dimension vectorielle représente une caractéristique des données non structurées. Illustrons cela avec un modèle d'apprentissage profond qui transforme les images en vecteurs d'intégration de 2048 dimensions. Ce modèle transformerait l'image du berger allemand que nous avons utilisée dans la figure 3 en un vecteur d'intégration présenté dans le tableau ci-dessous. Notez que nous ne montrons que les trois premiers et derniers éléments, mais qu'il y aurait 2 042 colonnes/dimensions supplémentaires dans le tableau.

Chaque colonne est une dimension du modèle et représente une caractéristique que le réseau neuronal sous-jacent cherche à modéliser. Chaque entrée donnée au modèle sera caractérisée en fonction de sa similarité avec chacune des 2048 dimensions. Par conséquent, la valeur de chaque élément du vecteur d'intégration indique la similarité de cette entrée avec une dimension spécifique. Dans cet exemple, nous pouvons voir que le modèle a détecté une grande similarité entre les chiens et les bergers allemands ainsi que la présence d'un peu de ciel bleu.

Contrairement à la recherche lexicale, où un terme peut correspondre ou non, la recherche vectorielle permet d'avoir une bien meilleure idée de la similitude d'un élément de données non structurées avec chacune des dimensions prises en charge par le modèle. En tant que tels, les vecteurs d'intégration constituent une formidable représentation sémantique des données non structurées.

La sauce secrète

Maintenant que nous savons comment les données non structurées sont découpées par les réseaux neuronaux d'apprentissage profond en vecteurs d'intégration qui capturent la similarité des données selon un grand nombre de dimensions, nous devons comprendre comment fonctionne la mise en correspondance de ces vecteurs. Il s'avère que la réponse est assez simple. Les vecteurs d'intégration qui sont proches les uns des autres représentent des éléments de données sémantiquement similaires. Ainsi, lorsque nous interrogeons une base de données vectorielles, l'entrée de recherche (image, texte, etc.) est d'abord transformée en un vecteur d'intégration à l'aide du même modèle que celui utilisé pour l'indexation de toutes les données non structurées, et l'objectif final est de trouver les vecteurs voisins les plus proches de ce vecteur d'interrogation. Par conséquent, tout ce que nous avons à faire est de trouver comment mesurer la "distance" ou la "similarité" entre le vecteur de la requête et tous les vecteurs existants indexés dans la base de données, c'est à peu près tout.

Distance et similarité

Heureusement pour nous, la mesure de la distance entre deux vecteurs est un problème facile à résoudre grâce à l'arithmétique vectorielle. Examinons donc les fonctions de distance et de similarité les plus populaires qui sont prises en charge par les bases de données de recherche vectorielle modernes, telles qu'Elasticsearch. Attention, mathématiques en perspective !

Distance L1

La distance L1, également appelée distance de Manhattan, de deux vecteurs x et y est mesurée en additionnant la différence absolue par paire de tous leurs éléments. Il est évident que plus la distance d est petite, plus les deux vecteurs sont proches. La formule est assez simple, comme on peut le voir ci-dessous :

Visuellement, la distance L1 peut être illustrée comme le montre la figure 5 ci-dessous :

Prenons deux vecteurs x et y, tels que x = (1, 2) et y = (4, 3), la distance L1 des deux vecteurs serait alors | 1 - 4 | + | 2 - 3 | = 4.

Distance L2

La distance L2, également appelée distance euclidienne, de deux vecteurs x et y est mesurée en additionnant d'abord le carré de la différence par paire de tous leurs éléments, puis en prenant la racine carrée du résultat. Il s'agit du chemin le plus court entre deux points (également appelé hypoténuse). Comme pour L1, plus la distance d est petite, plus les deux vecteurs sont proches :

La distance L2 est indiquée dans la figure 6 ci-dessous :

Réutilisons les deux mêmes vecteurs d'échantillonnage x et y que nous avons utilisés pour la distance L1, et nous pouvons maintenant calculer la distance L2 comme $(1 - 4)^2 + (2 - 3)^2 = 10.$ En prenant la racine carrée de 10, on obtient 3,16.

Distance Linf

La distance Linf (pour L infini), également appelée distance de Tchebychev ou distance de l'échiquier, de deux vecteurs x et y est simplement définie comme la plus longue distance entre deux de leurs éléments ou la plus longue distance mesurée le long de l'un des axes/dimensions. La formule est très simple et est illustrée ci-dessous :

Une représentation de la distance Linf est présentée dans la figure 7 ci-dessous :

De nouveau, en prenant les deux mêmes vecteurs d'échantillonnage x et y, nous pouvons calculer la distance à l'infini comme suit : max ( | 1 - 4 | , | 2 - 3 | ) = max (3, 1) = 3.

Similitude du cosinus

Contrairement à L1, L2 et Linf, la similarité en cosinus ne mesure pas la distance entre deux vecteurs x et y, mais plutôt leur angle relatif, c'est-à-dire s'ils pointent tous deux à peu près dans la même direction. Plus la similarité s est élevée, plus les deux vecteurs sont "proches". La formule est à nouveau très simple et illustrée ci-dessous :

La figure 8 ci-dessous présente une façon de représenter la similarité cosinus entre deux vecteurs :

En outre, comme les valeurs du cosinus sont toujours comprises dans l'intervalle [-1, 1], -1 signifie une similarité opposée (c'est-à-dire un angle de 180° entre les deux vecteurs), 0 signifie une similarité sans rapport (c'est-à-dire un angle de 90°) et 1 signifie une similarité identique (c'est-à-dire un angle de 0°), comme le montre la figure 9 ci-dessous :

Réutilisons à nouveau les mêmes vecteurs d'échantillons x et y et calculons la similitude en cosinus à l'aide de la formule ci-dessus. Tout d'abord, nous pouvons calculer le produit en points des deux vecteurs comme suit : $(1 - 4) + (2 - 3) = 10$. Ensuite, nous multiplions la longueur (également appelée magnitude) des deux vecteurs : $(1^2 + 2^2)^{1/2}$ + (4^2 + 3^2)^{1/2} = 11,18034. Enfin, nous divisons le produit en points par la longueur multipliée 10 / 11,18034 = 0,894427 (c'est-à-dire un angle de 26°), qui est assez proche de 1, de sorte que les deux vecteurs peuvent être considérés comme assez similaires.

Similitude du produit de points

L'un des inconvénients de la similitude en cosinus est qu'elle ne prend en compte que l'angle entre deux vecteurs et non leur magnitude (c'est-à-dire leur longueur), ce qui signifie que si deux vecteurs pointent à peu près dans la même direction mais que l'un est beaucoup plus long que l'autre, les deux seront tout de même considérés comme similaires. La similarité par produit de points, également appelée produit scalaire ou produit intérieur, améliore cette situation en tenant compte à la fois de l'angle et de la magnitude des vecteurs, ce qui permet d'obtenir une mesure de similarité beaucoup plus précise.

Deux formules équivalentes sont utilisées pour calculer la similitude du produit de points. La première est la même que celle que nous avons vue plus haut dans le numérateur de la similitude du cosinus :

La deuxième formule multiplie simplement la longueur des deux vecteurs par le cosinus de l'angle qui les sépare :

La similitude du produit des points est illustrée dans la figure 10 ci-dessous :

Une dernière fois, nous prenons les vecteurs x et y de l'échantillon et calculons leur produit en points en utilisant la première formule, comme nous l'avons fait pour la similitude du cosinus plus tôt, soit (1 $- 4$) + (2 $- 3$) = 10.

En utilisant la deuxième formule, nous multiplions la longueur des deux vecteurs : $(1^2 + 2^2)^{1/2}$ + (4^2 + 3^2)^{1/2} = 11,18034 et multiplions ce résultat par le cosinus de l'angle de 26° entre les deux vecteurs, et nous obtenons 11,18034 $- cos$(26°) = 10.

Il convient de noter que si tous les vecteurs sont d'abord normalisés (c'est-à-dire que leur longueur est égale à 1), la similitude du produit de points devient exactement la même que la similitude du cosinus (parce que |x| |y| = 1), c'est-à-dire le cosinus de l'angle entre les deux vecteurs. Comme nous le verrons plus loin, la normalisation des vecteurs est une bonne pratique à adopter afin de rendre la magnitude du vecteur non pertinente, de sorte que la similitude se concentre simplement sur l'angle. Il accélère également le calcul de la distance au moment de l'indexation et de l'interrogation, ce qui peut s'avérer problématique lorsque l'on travaille sur des milliards de vecteurs.

Récapitulatif rapide

Nous avons parcouru beaucoup d'informations jusqu'à présent, alors arrêtons-nous un instant et faisons un rapide récapitulatif de notre situation. Nous avons appris que...

• ...la recherche sémantique est basée sur des modèles de réseaux neuronaux d'apprentissage profond qui excellent dans la transformation de données non structurées en vecteurs d'intégration multidimensionnels.
• ...chaque dimension du modèle représente une caractéristique des données non structurées.
• ...un vecteur d'intégration est une séquence de valeurs de similarité (une pour chaque dimension) qui représente le degré de similarité d'un élément donné de données non structurées par rapport à chaque dimension.
• ...plus deux vecteurs sont "proches" (c'est-à-dire les plus proches voisins), plus ils représentent des concepts sémantiquement similaires.
• ...les fonctions de distance (L1, L2, Linf) nous permettent de mesurer la proximité de deux vecteurs.
• ...les fonctions de similitude (cosinus et produit de points) nous permettent de mesurer à quel point deux vecteurs se dirigent dans la même direction.

Le dernier élément qu'il nous reste à examiner est le moteur de recherche vectoriel lui-même. Lorsqu'une requête arrive, elle est d'abord vectorisée, puis le moteur de recherche vectorielle trouve les vecteurs voisins les plus proches du vecteur de la requête. L'approche brute consistant à mesurer la distance ou la similarité entre le vecteur de la requête et tous les vecteurs de la base de données peut fonctionner pour de petits ensembles de données, mais s'avère rapidement insuffisante lorsque le nombre de vecteurs augmente. En d'autres termes, comment pouvons-nous indexer des millions, des milliards, voire des trillions de vecteurs et trouver les plus proches voisins du vecteur interrogé dans un délai raisonnable ? C'est là que nous devons faire preuve d'intelligence et trouver des moyens optimaux d'indexer les vecteurs de manière à ce que nous puissions trouver les plus proches voisins aussi rapidement que possible sans trop dégrader la précision.

Algorithmes et techniques de recherche vectorielle

Au fil des ans, de nombreuses équipes de recherche ont investi beaucoup d'efforts dans le développement d'algorithmes de recherche vectorielle très intelligents. Nous allons ici présenter brièvement les principaux d'entre eux. Selon le cas d'utilisation, certains sont mieux adaptés que d'autres.

Recherche linéaire

Nous avons brièvement abordé la recherche linéaire, ou indexation plate, lorsque nous avons mentionné l'approche brute consistant à comparer le vecteur de la requête à tous les vecteurs présents dans la base de données. Bien qu'elle puisse donner de bons résultats sur de petits ensembles de données, les performances diminuent rapidement lorsque le nombre de vecteurs et de dimensions augmente (complexité O(n)).

Heureusement, il existe des approches plus efficaces, appelées approximation du plus proche voisin (ANN), dans lesquelles les distances entre les vecteurs d'intégration sont calculées à l'avance et les vecteurs similaires sont stockés et organisés de manière à rester proches les uns des autres, par exemple à l'aide de grappes, d'arbres, de hachages ou de graphes. Ces approches sont dites "approximatives" car elles ne garantissent généralement pas une précision de 100%. L'objectif final est de réduire l'étendue de la recherche autant et aussi rapidement que possible afin de se concentrer uniquement sur les zones les plus susceptibles de contenir des vecteurs similaires ou de réduire la dimensionnalité des vecteurs.

Arbres à K dimensions

Un arbre à K dimensions, ou arbre KD, est une généralisation d'un arbre de recherche binaire qui stocke des points dans un espace à k dimensions et fonctionne en divisant continuellement l'espace de recherche en arbres plus petits à gauche et à droite où les vecteurs sont indexés. Au moment de la recherche, l'algorithme doit simplement visiter quelques branches de l'arbre autour du vecteur de la requête (le point rouge dans la figure 11) afin de trouver le plus proche voisin (le point vert dans la figure 11). Si plus de k voisins sont demandés, la zone jaune est étendue jusqu'à ce que l'algorithme trouve d'autres voisins.

Le principal avantage de l'algorithme de l'arbre KD est qu'il nous permet de nous concentrer rapidement sur certaines branches localisées de l'arbre, éliminant ainsi la plupart des vecteurs. Toutefois, l'efficacité de cet algorithme diminue à mesure que le nombre de dimensions augmente, car il faut visiter beaucoup plus de branches que dans les espaces de dimensions inférieures.

Index de fichier inversé

L'approche de l'index inversé des fichiers (IVF) est également un algorithme de partitionnement de l'espace qui affecte les vecteurs proches les uns des autres à leur centroïde commun. Dans l'espace 2D, le diagramme de Voronoï, comme le montre la figure 12, permet de mieux visualiser ce phénomène :

Nous pouvons voir que l'espace 2D ci-dessus est divisé en 20 groupes, chacun ayant son centroïde représenté par des points noirs. Tous les vecteurs d'intégration dans l'espace sont affectés au groupe dont le centroïde est le plus proche. Au moment de la recherche, l'algorithme détermine d'abord le groupe sur lequel il doit se concentrer en trouvant le centroïde le plus proche du vecteur de la requête, puis il peut simplement se concentrer sur cette zone, ainsi que sur les zones environnantes si nécessaire, afin de trouver les voisins les plus proches.

Cet algorithme souffre du même problème que les arbres KD lorsqu'il est utilisé dans des espaces à haute dimension. C'est ce qu'on appelle la malédiction de la dimensionnalité, qui se produit lorsque le volume de l'espace augmente tellement que toutes les données semblent éparses et que la quantité de données nécessaires pour obtenir des résultats plus précis croît de manière exponentielle. Lorsque les données sont éparses, il est plus difficile pour ces algorithmes de partitionnement de l'espace d'organiser les données en grappes. Heureusement pour nous, il existe d'autres algorithmes et techniques qui atténuent ce problème, comme indiqué ci-dessous.

Quantification

La quantification est une approche basée sur la compressionqui nous permet de réduire la taille totale de la base de données en diminuant la précision des vecteurs d'intégration. Ceci peut être réalisé en utilisant la quantification scalaire (SQ) en convertissant les valeurs vectorielles à virgule flottante en valeurs entières. Cela permet non seulement de réduire la taille de la base de données d'un facteur 8, mais aussi de diminuer la consommation de mémoire et d'accélérer le calcul de la distance entre les vecteurs au moment de la recherche.

Une autre technique, appelée quantification par produit (PQ), divise d'abord l'espace en sous-espaces de dimensions inférieures, puis les vecteurs proches les uns des autres sont regroupés dans chaque sous-espace à l'aide d'un algorithme de regroupement (similaire aux k-moyennes).

Il convient de noter que la quantification diffère de la réduction de la dimensionnalité, où le nombre de dimensions est réduit, c'est-à-dire que les vecteurs deviennent simplement plus courts.

Petits mondes navigables hiérarchiques (PMNH)

Si le nom semble complexe, ne vous inquiétez pas, ce n'est pas vraiment le cas ! En résumé, Hierarchical Navigable Small Worlds est un algorithme basé sur un graphe multicouche qui est très populaire et efficace. Il est utilisé par de nombreuses bases de données vectorielles, dont Apache Lucene. La figure 13 ci-dessous présente une représentation conceptuelle de HNSW.

Sur la couche supérieure, nous pouvons voir un graphique de très peu de vecteurs qui ont les liens les plus longs entre eux, c'est-à-dire un graphique de vecteurs connectés avec le moins de similarité. Plus nous plongeons dans les couches inférieures, plus nous trouvons de vecteurs et plus le graphique devient dense, avec de plus en plus de vecteurs proches les uns des autres. Dans la couche la plus basse, on trouve tous les vecteurs, les plus similaires étant les plus proches les uns des autres.

Au moment de la recherche, l'algorithme part de la couche supérieure à un point d'entrée arbitraire et trouve le vecteur le plus proche du vecteur de la requête (représenté par le point gris). Ensuite, il se déplace d'une couche à l'autre et répète le même processus, en partant du même vecteur que celui qu'il a laissé dans la couche précédente, et ainsi de suite, une couche après l'autre, jusqu'à ce qu'il atteigne la couche la plus basse et trouve le voisin le plus proche du vecteur de la requête.

Hachage sensible à la localité (LSH)

Dans la même veine que toutes les autres approches présentées jusqu'à présent, le hachage sensible à la localité vise à réduire considérablement l'espace de recherche afin d'augmenter la vitesse d'extraction. Avec cette technique, les vecteurs d'intégration sont transformés en valeurs de hachage, tout en préservant les informations de similarité, de sorte que l'espace de recherche devient finalement une simple table de hachage qui peut être consultée au lieu d'un graphe ou d'un arbre qui doit être parcouru. Le principal avantage des méthodes basées sur les hachages est que les vecteurs contenant un nombre arbitraire (important) de dimensions peuvent être mis en correspondance avec des hachages de taille fixe, ce qui accélère considérablement le temps de recherche sans sacrifier trop de précision.

Il existe de nombreuses façons de hacher les données en général, et d'intégrer des vecteurs en particulier, mais cet article n'entrera pas dans les détails de chacune d'entre elles. Les méthodes de hachage conventionnelles produisent généralement des hachages très différents pour des données qui semblent très similaires. Les vecteurs d'intégration étant composés de valeurs flottantes, prenons deux exemples de valeurs flottantes considérées comme très proches l'une de l'autre dans l'arithmétique vectorielle (par exemple, 0,73 et 0,74) et soumettons-les à quelques fonctions de hachage courantes. En regardant les résultats ci-dessous, il est évident que les fonctions de hachage courantes ne conservent pas la similarité entre les entrées.

Alors que les méthodes de hachage classiques tentent de minimiser les collisions de hachage entre des données similaires, l'objectif principal du hachage sensible à la localité est de faire exactement le contraire, c'est-à-dire de maximiser les collisions de hachage afin que des données similaires tombent dans le même bac avec une forte probabilité. Ainsi, les vecteurs d'intégration qui sont proches les uns des autres dans un espace multidimensionnel seront hachés en une valeur de taille fixe tombant dans le même panier. Comme LSH permet à ces vecteurs hachés de conserver leur proximité, cette technique s'avère très pratique pour le regroupement de données et la recherche du voisin le plus proche.

Tout le travail se fait au moment de l'indexation, lorsque les hachages doivent être calculés, tandis qu'au moment de la recherche, il suffit de hacher le vecteur de la requête pour rechercher le seau contenant les vecteurs d'intégration les plus proches. Une fois le seau candidat trouvé, un deuxième tour a généralement lieu pour identifier les vecteurs voisins les plus proches du vecteur d'interrogation.

Concluons

Pour présenter la recherche vectorielle, nous avons dû couvrir un certain nombre de points dans cet article. Après avoir comparé les différences entre la recherche lexicale et la recherche vectorielle, nous avons appris comment les modèles de réseaux neuronaux d'apprentissage profond parviennent à capturer la sémantique des données non structurées et à transcoder leur signification en vecteurs d'intégration à haute dimension, une séquence de nombres à virgule flottante représentant la similarité des données selon chacune des dimensions du modèle. Il convient également de noter que la recherche vectorielle et la recherche lexicale ne sont pas des techniques de recherche d'informations concurrentes mais complémentaires (comme nous le verrons dans la troisième partie de cette série, lorsque nous nous pencherons sur la recherche hybride).

Nous avons ensuite présenté un élément fondamental de la recherche vectorielle, à savoir les fonctions de distance (et de similarité) qui nous permettent de mesurer la proximité de deux vecteurs et d'évaluer la similarité des concepts qu'ils représentent.

Enfin, nous avons passé en revue les différentes variantes des algorithmes et techniques de recherche vectorielle les plus populaires, qui peuvent être basés sur des arbres, des graphes, des grappes ou des hachages, et dont l'objectif est de se concentrer rapidement sur une zone spécifique de l'espace multidimensionnel afin de trouver les voisins les plus proches sans avoir à visiter l'ensemble de l'espace comme le ferait une recherche linéaire par force brute.

Si vous aimez ce que vous lisez, n'hésitez pas à consulter les autres parties de cette série :

• Partie 2 : Comment configurer la recherche vectorielle dans Elasticsearch
• Partie 3 : Recherche hybride avec Elasticsearch

Questions fréquentes