🚀 Essayez Zilliz Cloud, la version entièrement gérée de Milvus, gratuitement—découvrez des performances 10x plus rapides ! Essayez maintenant>>

Commencer

Home BlogsPremiers pas avec HNSWlib

Premiers pas avec HNSWlib

Engineering

November 25, 2024

Haziqa Sajid

Larecherche sémantique permet aux machines de comprendre le langage et d'obtenir de meilleurs résultats de recherche, ce qui est essentiel pour l'intelligence artificielle et l'analyse des données. Une fois le langage représenté sous forme d'encastrements, la recherche peut être effectuée à l'aide de méthodes exactes ou approximatives. La recherche approximative du plus proche voisin(ANN) est une méthode utilisée pour trouver rapidement les points d'un ensemble de données qui sont les plus proches d'un point d'interrogation donné, contrairement à la recherche exacte du plus proche voisin, qui peut s'avérer coûteuse en termes de calcul pour les données de haute dimension. L'ANN permet une recherche plus rapide en fournissant des résultats qui sont approximativement proches des plus proches voisins.

L'un des algorithmes de recherche du plus proche voisin (ANN) est HNSW (Hierarchical Navigable Small Worlds), implémenté sous HNSWlib, qui sera au centre de la discussion d'aujourd'hui. Dans ce blog, nous allons :

Comprendre l'algorithme HNSW.
Explorer HNSWlib et ses principales caractéristiques.
Configurer HNSWlib, en couvrant la construction de l'index et la mise en œuvre de la recherche.
Le comparer avec Milvus.

Comprendre HNSW

HierarchicalNavigable Small Worlds (HNSW) est une structure de données basée sur un graphe qui permet des recherches de similarité efficaces, en particulier dans les espaces à haute dimension, en construisant un graphe multicouche de réseaux de "petits mondes". Introduit en 2016, HNSW résout les problèmes d'évolutivité associés aux méthodes de recherche traditionnelles telles que la force brute et les recherches basées sur les arbres. Il est idéal pour les applications impliquant de grands ensembles de données, telles que les systèmes de recommandation, la reconnaissance d'images et la génération augmentée par récupération (RAG).

L'importance de HNSW

HNSW améliore considérablement les performances de la recherche du plus proche voisin dans les espaces à haute dimension. La combinaison de la structure hiérarchique et de la navigabilité du petit monde évite l'inefficacité informatique des anciennes méthodes, ce qui permet d'obtenir de bons résultats même avec des ensembles de données massifs et complexes. Pour mieux comprendre, voyons comment cela fonctionne aujourd'hui.

Fonctionnement de HNSW

Couches hiérarchiques : HNSW organise les données en une hiérarchie de couches, où chaque couche contient des nœuds reliés par des arêtes. Les couches supérieures sont plus clairsemées, ce qui permet de faire de larges "sauts" dans le graphique, un peu comme si l'on faisait un zoom arrière sur une carte pour ne voir que les principales autoroutes entre les villes. Les couches inférieures augmentent en densité, fournissant des détails plus fins et davantage de connexions entre les voisins les plus proches.
Concept de petits mondes navigables : Chaque couche de HNSW repose sur le concept de "petit monde", où les nœuds (points de données) ne sont qu'à quelques "sauts" les uns des autres. L'algorithme de recherche commence par la couche la plus haute et la plus éparse, puis descend vers des couches de plus en plus denses afin d'affiner la recherche. Cette approche revient à passer d'une vue globale à des détails au niveau du voisinage, en réduisant progressivement la zone de recherche.

Fig 1: Exemple de graphe du petit monde navigable

Structure de type "liste à sauter" : L'aspect hiérarchique de HNSW ressemble à une "skip list", une structure de données probabiliste dans laquelle les couches supérieures ont moins de nœuds, ce qui permet des recherches initiales plus rapides.

Fig 2: Exemple de structure de type "skip list

Pour rechercher 96 dans la liste d'exclusion donnée, nous commençons au niveau supérieur, à l'extrême gauche, par le nœud d'en-tête. En nous déplaçant vers la droite, nous rencontrons 31, moins que 96, et nous passons donc au nœud suivant. Maintenant, nous devons descendre d'un niveau où nous voyons à nouveau 31 ; comme il est toujours inférieur à 96, nous descendons d'un autre niveau. Nous trouvons à nouveau 31, puis nous nous déplaçons vers la droite et atteignons 96, notre valeur cible. Ainsi, nous trouvons 96 sans avoir à descendre jusqu'aux niveaux les plus bas de la liste de saut.

Efficacité de la recherche : L'algorithme HNSW part d'un nœud d'entrée situé dans la couche la plus haute, et progresse vers des voisins plus proches à chaque étape. Il descend le long des couches, en utilisant chacune d'entre elles pour une exploration plus ou moins fine, jusqu'à ce qu'il atteigne la couche la plus basse où les nœuds les plus similaires sont susceptibles d'être trouvés. Cette navigation par couches réduit le nombre de nœuds et d'arêtes à explorer, ce qui rend la recherche rapide et précise.
Insertion et maintenance: Lors de l'ajout d'un nouveau nœud, l'algorithme détermine sa couche d'entrée en fonction de la probabilité et le connecte aux nœuds voisins à l'aide d'une heuristique de sélection des voisins. Cette heuristique vise à optimiser la connectivité, en créant des liens qui améliorent la navigabilité tout en équilibrant la densité du graphe. Cette approche permet à la structure de rester robuste et de s'adapter à de nouveaux points de données.

Bien que nous ayons une compréhension fondamentale de l'algorithme HNSW, sa mise en œuvre à partir de zéro peut s'avérer fastidieuse. Heureusement, la communauté a développé des bibliothèques comme HNSWlib pour en simplifier l'utilisation et le rendre accessible sans se gratter la tête. Voyons donc de plus près ce qu'est HNSWlib.

Vue d'ensemble de HNSWlib

HNSWlib, une bibliothèque populaire implémentant HNSW, est très efficace et évolutive, et fonctionne bien même avec des millions de points. Elle atteint une complexité temporelle sous-linéaire en permettant des sauts rapides entre les couches du graphe et en optimisant la recherche pour les données denses et de haute dimension. Voici les principales caractéristiques de HNSWlib :

Structure basée sur un graphe : Un graphe multicouche représente les points de données, ce qui permet d'effectuer des recherches rapides sur les plus proches voisins.
Efficacité en haute dimension : Optimisée pour les données à haute dimension, elle permet des recherches approximatives rapides et précises.
Temps de recherche sous-linéaire : permet d'obtenir une complexité sous-linéaire en sautant des couches, ce qui améliore considérablement la vitesse.
Mises à jour dynamiques : Prend en charge l'insertion et la suppression de nœuds en temps réel sans nécessiter une reconstruction complète du graphe.
Efficacité de la mémoire : Utilisation efficace de la mémoire, adaptée aux grands ensembles de données.
Évolutivité : S'adapte bien à des millions de points de données, ce qui le rend idéal pour des applications de taille moyenne telles que les systèmes de recommandation.

Note : HNSWlib est excellent pour créer des prototypes simples d'applications de recherche vectorielle. Cependant, en raison des limitations d'évolutivité, il peut y avoir de meilleurs choix tels que des bases de données vectorielles spécifiques pour des scénarios plus complexes impliquant des centaines de millions ou même des milliards de points de données. Voyons cela en action.

Démarrer avec HNSWlib : Un guide pas à pas

Cette section présente l'utilisation de HNSWlib comme bibliothèque de recherche vectorielle en créant un index HNSW, en insérant des données et en effectuant des recherches. Commençons par l'installation :

Installation et importations

Pour commencer à utiliser HNSWlib en Python, installez-la d'abord avec pip :

pip install hnswlib

Ensuite, importez les bibliothèques nécessaires :

import hnswlib 
import numpy as np

Préparation des données

Dans cet exemple, nous utiliserons NumPypour générer un ensemble de données aléatoires avec 10 000 éléments, chacun ayant une dimension de 256.

dim = 256  # Dimensionality of your vectors
num_elements = 10000  # Number of elements to insert

Créons les données :

data = np.random.rand(num_elements, dim).astype(np.float32)  # Example data

Maintenant que nos données sont prêtes, construisons un index.

Construction d'un index

Pour construire un index, nous devons définir la dimensionnalité des vecteurs et le type d'espace. Créons un index :

p = hnswlib.Index(space='l2', dim=dim)

space='l2': Ce paramètre définit la métrique de distance utilisée pour la similarité. En le fixant à 'l2', vous utilisez la distance euclidienne (norme L2). Si vous lui attribuez la valeur 'ip', le produit intérieur sera utilisé, ce qui est utile pour des tâches telles que la similarité en cosinus.

dim=dim: Ce paramètre spécifie la dimensionnalité des points de données avec lesquels vous travaillerez. Il doit correspondre à la dimension des données que vous prévoyez d'ajouter à l'index.

Voici comment initialiser un index :

p.init_index(max_elements=num_elements, ef_construction=200, M=16)

max_elements=num_elements: Ceci définit le nombre maximum d'éléments qui peuvent être ajoutés à l'index. Num_elements est la capacité maximale, nous la fixons donc à 10 000 car nous travaillons avec 10 000 points de données.

ef_construction=200: Ce paramètre contrôle le compromis entre la précision et la vitesse de construction lors de la création de l'index. Une valeur plus élevée améliore le rappel (précision) mais augmente l'utilisation de la mémoire et le temps de construction. Les valeurs courantes sont comprises entre 100 et 200.

M=16: Ce paramètre détermine le nombre de liens bidirectionnels créés pour chaque point de données, ce qui influe sur la précision et la vitesse de recherche. Les valeurs typiques se situent entre 12 et 48 ; 16 est souvent un bon équilibre pour une précision et une vitesse modérées.

p.set_ef(50)  # This parameter controls the speed/accuracy trade-off

ef: Le paramètre ef, abréviation de "facteur d'exploration", détermine le nombre de voisins examinés au cours d'une recherche. Une valeur plus élevée de ef entraîne l'exploration d'un plus grand nombre de voisins, ce qui augmente généralement la précision (rappel) de la recherche, mais la rend également plus lente. À l'inverse, une valeur plus faible de ef permet d'accélérer la recherche, mais peut en réduire la précision.

Dans ce cas, définir ef sur 50 signifie que l'algorithme de recherche évaluera jusqu'à 50 voisins lors de la recherche des points de données les plus similaires.

Remarque : ef_construction définit l'effort de recherche des voisins lors de la création de l'index, ce qui améliore la précision mais ralentit la construction. ef contrôle l'effort de recherche lors de l'interrogation, en équilibrant dynamiquement la vitesse et le rappel pour chaque interrogation.

Exécution des recherches

Pour effectuer une recherche par le plus proche voisin à l'aide de HNSWlib, nous créons d'abord un vecteur de requête aléatoire. Dans cet exemple, la dimensionnalité du vecteur correspond aux données indexées.

query_vector = np.random.rand(dim).astype(np.float32)  # Example query

labels, distances = p.knn_query(query_vector, k=5)  # k is the number of nearest neighbors

query_vector: Cette ligne génère un vecteur aléatoire ayant la même dimensionnalité que les données indexées, ce qui assure la compatibilité avec la recherche du plus proche voisin.
knn_query: La méthode recherche les k plus proches voisins de query_vector dans l'index p. Elle renvoie deux tableaux : labels, qui contiennent les indices des plus proches voisins, et distances, qui indiquent les distances entre le vecteur de la requête et chacun de ces voisins. Ici, k=5 indique que nous voulons trouver les cinq plus proches voisins.

Voici les résultats après impression des étiquettes et des distances :

print("Nearest neighbors' labels:", labels)
print("Distances:", distances)

> Nearest neighbors' labels: [[4498 1751 5647 4483 2471]]
> Distances: [[33.718    35.484592 35.627766 35.828312 35.91495 ]]

Voilà, un guide simple pour démarrer avec HNSWlib.

Comme nous l'avons mentionné, HNSWlib est un excellent moteur de recherche vectorielle pour le prototypage ou l'expérimentation avec des ensembles de données de taille moyenne. Si vous avez des exigences plus élevées en matière d'évolutivité ou si vous avez besoin d'autres fonctionnalités de niveau entreprise, vous devrez peut-être choisir une base de données vectorielle spécialisée comme Milvus, une base de données open-source, ou son service entièrement géré sur Zilliz Cloud. Dans la section suivante, nous allons donc comparer HNSWlib avec Milvus.

HNSWlib vs. les bases de données vectorielles spécifiques comme Milvus

Une base de données vectorielle stocke les données sous forme de représentations mathématiques, ce qui permet aux modèles d'apprentissage automatique d'alimenter la recherche, les recommandations et la génération de texte en identifiant les données par des mesures de similarité pour une compréhension contextuelle.

Les bibliothèques d'indices vectoriels comme HNSWlib améliorent larecherche et l'extraction de donnéesvectorielles, mais ne disposent pas des fonctions de gestion d'une base de données complète. En revanche, les bases de données vectorielles, telles que Milvus, sont conçues pour traiter les encastrements vectoriels à grande échelle, offrant des avantages en termes de gestion des données, d'indexation et d'interrogation que les bibliothèques autonomes n'ont généralement pas. Voici d'autres avantages liés à l'utilisation de Milvus :

Recherche de similarité vectorielle à grande vitesse: Milvus offre des performances de recherche de l'ordre de la milliseconde sur des ensembles de données vectorielles à l'échelle du milliard, ce qui est idéal pour des applications telles que la recherche d'images, les systèmes de recommandation, le traitement du langage naturel(NLP) et la génération augmentée de recherche(RAG).
Évolutivité et haute disponibilité : Conçu pour traiter des volumes de données massifs, Milvus évolue horizontalement et comprend des mécanismes de réplication et de basculement pour la fiabilité.
Architecture distribuée : Milvus utilise une architecture distribuée et évolutive qui sépare le stockage et le calcul sur plusieurs nœuds pour plus de flexibilité et de robustesse.
Recherche hybride: Milvus prend en charge la recherche multimodale, la recherche hybride dense et clairsemée, ainsi que la recherche hybride dense et en texte intégral, offrant ainsi une fonctionnalité de recherche polyvalente et flexible.
Prise en charge flexible des données: Milvus prend en charge différents types de données (vecteurs, scalaires et données structurées), ce qui permet une gestion et une analyse transparentes au sein d'un système unique.
Communauté et supportactifs: Une communauté florissante fournit régulièrement des mises à jour, des tutoriels et une assistance, ce qui permet à Milvus de rester en phase avec les besoins des utilisateurs et les avancées dans le domaine.
Intégration de l'IA: Milvus s'est intégré à divers frameworks et technologies d'IA populaires, ce qui permet aux développeurs de créer plus facilement des applications à l'aide de leurs piles technologiques habituelles.

Milvus fournit également un service entièrement géré sur Ziliz Cloud, qui est sans tracas et 10 fois plus rapide que Milvus.

Comparaison : Milvus vs. HNSWlib

Fonctionnalité	Milvus	HNSWlib
Évolutivité	Traite facilement des milliards de vecteurs	Convient aux petits ensembles de données en raison de l'utilisation de la RAM
Idéal pour	Prototypage, expérimentation et applications d'entreprise	Se concentre sur les prototypes et les tâches ANN légères
Indexation	Prend en charge plus de 10 algorithmes d'indexation, notamment HNSW, DiskANN, quantification et binaire.	Utilise uniquement un algorithme HNSW basé sur un graphe
Intégration	Offre des API et des services cloud-native	Sert de bibliothèque légère et autonome
Performances	Optimisation pour les données volumineuses et les requêtes distribuées	Offre une vitesse élevée mais une évolutivité limitée

Dans l'ensemble, Milvus est généralement préférable pour les applications de production à grande échelle avec des besoins d'indexation complexes, tandis que HNSWlib est idéal pour le prototypage et les cas d'utilisation plus simples.

Conclusion

La recherche sémantique peut être gourmande en ressources, c'est pourquoi la structuration interne des données, comme celle effectuée par HNSW, est essentielle pour une récupération plus rapide des données. Les bibliothèques comme HNSWlib se préoccupent de l'implémentation, de sorte que les développeurs ont les recettes prêtes à l'emploi pour prototyper les capacités vectorielles. Avec seulement quelques lignes de code, nous pouvons construire notre propre index et effectuer des recherches.

HNSWlib est un excellent moyen de commencer. Cependant, si vous souhaitez créer des applications d'IA complexes et prêtes pour la production, les bases de données vectorielles conçues à cet effet sont la meilleure option. Par exemple, Milvus est une base de données vectorielles open-source qui présente de nombreuses caractéristiques adaptées aux entreprises, telles que la recherche vectorielle à grande vitesse, l'évolutivité, la disponibilité et la flexibilité en termes de types de données et de langage de programmation.