Présentation de la recherche du plus proche voisin approximatif dans Elasticsearch 8.0

L'intérêt pour rechercher des vecteurs a connu une forte augmentation, grâce à une nouvelle génération de modèles de Machine Learning capables de représenter toutes sortes de contenus sous forme de vecteurs, notamment le texte, les images, les événements, et bien plus encore. Souvent appelées « modèles d'embedding », ces représentations puissantes peuvent capturer la similarité entre deux éléments de contenu d'une manière qui dépasse leurs caractéristiques superficielles.

Les algorithmes de recherche des k plus proches voisins (kNN) trouvent les vecteurs dans un ensemble de données qui sont les plus similaires à un vecteur de requête. Associé à ces représentations vectorielles, le fait de rechercher avec kNN ouvre des possibilités passionnantes en matière de récupération :

• Trouver des passages susceptibles de contenir la réponse à une question
• Détection d'images quasi identiques dans un grand ensemble de données
• Trouver des chansons qui ressemblent à une chanson donnée

La recherche vectorielle est en passe de devenir un composant important de la boîte à outils de recherche, aux côtés de techniques traditionnelles comme l'attribution de scores basée sur les termes.

Elasticsearch prend actuellement en charge le stockage de vecteurs via le type de champ dense_vector et leur utilisation pour calculer les scores des documents. Cela permet aux utilisateurs d'effectuer une recherche kNN exacte en analysant tous les documents. Elasticsearch 8.0 s'appuie sur cette fonctionnalité pour prendre en charge la recherche rapide du plus proche voisin approximatif (ANN). Cela représente une approche offrant beaucoup plus de scalabilité, permettant l'exécution efficace de l'opération de rechercher des vecteurs sur de grands ensembles de données.

ANN dans Elasticsearch

Qu'est-ce que rechercher le plus proche voisin approximatif ?

Il existe des structures de données bien établies pour le kNN sur des vecteurs de faible dimensionnalité, comme les arbres KD. En fait, Elasticsearch intègre des arbres KD pour prendre en charge les recherches sur les données géospatiales et numériques. Mais les modèles d’embedding modernes pour le texte et les images produisent généralement des vecteurs à haute dimensionnalité de 100 à 1 000 éléments, voire plus. Ces représentations vectorielles présentent un défi unique, car il est très difficile de trouver efficacement les plus proches voisins dans des espaces à haute dimensionnalité.

Face à cette difficulté, les algorithmes du plus proche voisin sacrifient généralement la précision parfaite pour améliorer leur vitesse. Ces algorithmes du plus proche voisin approximatif (ANN) peuvent ne pas toujours renvoyer les k vrais vecteurs les plus proches. Mais leur exécution est efficace, scaling à de grands ensembles de données tout en assurant la maintenance de bonnes performances.

Choisir un algorithme ANN

La conception d'algorithmes ANN est un domaine de recherche universitaire actif, et il existe de nombreux algorithmes prometteurs parmi lesquels choisir. Ils présentent souvent des compromis différents en termes de vitesse de recherche, de complexité de mise en œuvre et de coût d'indexation. Heureusement, il existe un excellent projet open source appelé ann-benchmarks qui teste les principaux algorithmes sur plusieurs ensembles de données et publie des comparaisons.

Elasticsearch 8.0 utilise un algorithme ANN appelé Hierarchical Navigable Small World graphes (HNSW), qui organise les vecteurs dans un graphe en fonction de leur similarité. HNSW affiche de solides performances de recherche sur divers ensembles de données ann-benchmarks, et a également obtenu de bons résultats lors de nos propres tests. Un autre avantage de HNSW est qu'il est largement utilisé dans l'industrie, ayant été implémenté dans plusieurs systèmes différents. En plus de l'article universitaire original, il existe de nombreuses ressources utiles pour en savoir plus sur les détails de l'algorithme. Bien que l'ANN d'Elasticsearch soit actuellement basé sur HNSW, cette fonctionnalité est conçue de manière flexible pour nous permettre d'intégrer différentes approches à l'avenir.

Montrez-moi le code !

Pour indexer des vecteurs pour la rechercher ANN, nous devons définir index: true et spécifier l'indicateur de similarité que nous utilisons pour les comparer :

Dans cet exemple, la recherche ANN est nettement plus rapide que l'approche exacte. Son rappel est d'environ 95 %, donc en moyenne, il trouve plus de 9 des 10 véritables voisins les plus proches.

Vous pouvez vérifier les performances de rechercher kNN dans les benchmarks nocturnes d’Elasticsearch. Ces benchmarks sont alimentés par es-rally, un outil d'évaluation comparative pour Elasticsearch, et plus précisément par le nouveau track Rally dense_vector. Nous prévoyons d'étendre Rally pour rapporter le rappel en plus de la latence, car il est également important de suivre la précision de l'algorithme. Actuellement, ces benchmarks testent un ensemble de données de quelques millions de vecteurs, mais la recherche ANN peut certainement scaler au-delà de cela avec un temps d'indexation plus long ou l'ajout de ressources matérielles.

Propulsé par Apache Lucene

Bon nombre des capacités de rechercher du noyau d'Elasticsearch sont optimisées par la bibliothèque Lucene, un projet open source régi par l'Apache Software Foundation. La recherche ANN d'Elasticsearch ne fait pas exception et repose sur une nouvelle fonctionnalité passionnante de Lucene permettant de stocker et de rechercher des vecteurs numériques. Cette fonctionnalité est le résultat d'une formidable collaboration impliquant plusieurs développeurs au sein de différentes organisations. Démarré comme une proposition audacieuse, il a rapidement progressé vers une implémentation fonctionnelle (et rapide). Vint ensuite le défi de la conception de l'API et de la finalisation de la fonctionnalité.

Depuis, la communauté Lucene a continué à collaborer pour faire avancer cette fonctionnalité. Plusieurs développeurs se sont montrés intéressés et ont apporté leurs contributions, allant de la refonte des noms aux mises à jour d'algorithmes, en passant par les améliorations des performances, et bien plus encore. Les capacités de recherche vectorielle de Lucene se développent rapidement grâce aux efforts de chacun.

Outre cette collaboration fructueuse, le développement de l'ANN dans Lucene apporte d'autres avantages majeurs. L'implémentation de Lucene est conçue à bas niveau pour s'intégrer correctement aux fonctionnalités existantes, ce qui permet à la recherche ANN d'interagir de manière transparente avec d'autres fonctionnalités d'Elasticsearch. Une intégration aussi poussée ne serait pas vraiment possible si nous dépendions d'une bibliothèque ANN externe. Par exemple, l'ANN de Lucene gère de manière transparente les documents supprimés en ignorant les « tombstones » lors de la recherche dans le graphe. Elle respecte également toutes les garanties de compatibilité des données de Lucene, vous pouvez donc être certain que les données vectorielles fonctionneront toujours après une mise à niveau. Enfin, l'implémentation est écrite en Java, tout comme Elasticsearch, ce qui nous permet d'assurer sa sécurité et de simplifier la gestion de la mémoire.

Et ensuite ?

Dans la version 8.0, le point de terminaison _knn_search pour rechercher efficacement des ANN sera publié en « préversion technique ». La recherche ANN est un sujet relativement nouveau, non seulement pour Elastic, mais aussi pour l'industrie, et il existe d'importantes questions en suspens sur la manière dont elle devrait se comporter. Quelle est la meilleure façon de combiner les scores de similarité vectorielle avec les scores BM25 traditionnels ? La recherche kNN devrait-elle prendre en charge la pagination ? Développer l'ANN en tant que point de terminaison expérimental propre nous permettra d'itérer rapidement et de tester son comportement. Nous prévoyons d'intégrer à terme l'ANN dans le point de terminaison de l'API _search une fois que nous aurons des réponses solides à ces questions. (Bien que _knn_search ne soit pas encore en disponibilité générale, le type de champ dense_vector a été rendu disponible en disponibilité générale dans la version 7.6 et continue de disposer d'une API stable.)

Parmi les capacités clés que nous prévoyons de prendre en charge, citons l'ANN avec filtres, ainsi que la recherche « hybride » où les résultats ANN sont combinés avec ceux d'une requête traditionnelle. Nous travaillons également à améliorer la vitesse d'indexation, car la construction de graphes HNSW peut être une opération coûteuse. Nous considérons cette version comme un simple début et nous avons hâte d'améliorer la recherche ANN dans les prochaines versions. Votre avis nous est très précieux et nous aide à définir l'orientation de cette fonctionnalité. Nous serions ravis de connaître votre avis sur GitHub et sur nos forums Discuss (et dans Lucene également) !

Essayez de rechercher ANN sur Elastic Cloud en utilisant logging pour vous connecter à la console Elastic Cloud ou en vous inscrivant à un essai gratuit de 14 jours.