Le monde navigable hiérarchique à petit monde (HNSW) est un algorithme de recherche approximative du plus proche voisin. Il est utilisé pour trouver des éléments similaires à un élément de requête dans une grande collection, sans comparer la requête avec chaque élément un par un. L'algorithme est couramment utilisé pour rechercher des données vectorielles, où des éléments tels que des documents, des images, des chansons ou des profils d'utilisateurs sont représentés sous forme de listes de nombres appelées vecteurs. Les éléments ayant des vecteurs similaires sont traités comme similaires selon le modèle qui a produit les vecteurs, et HNSW fournit un moyen de rechercher ces vecteurs rapidement, en particulier dans de grands ensembles de données.
HNSW stocke les vecteurs dans un graphe. Chaque vecteur est un nœud, et des liens le connectent à certains vecteurs proches. Le graphe a plusieurs couches : les couches supérieures contiennent moins de nœuds et agissent comme une carte approximative, tandis que la couche inférieure contient tous les nœuds et offre une vue plus détaillée. Une recherche commence dans une couche supérieure, suit les liens vers des nœuds plus proches de la requête, puis répète le processus dans les couches inférieures jusqu'à ce qu'elle trouve un ensemble de voisins les plus probables.
Contexte
Le problème de la recherche du plus proche voisin demande quels éléments d'un ensemble de données sont les plus proches d'un élément de requête. Une recherche directe peut comparer la requête avec chaque élément de l'ensemble de données, mais cela devient lent lorsque l'ensemble de données est volumineux. Les méthodes de recherche exacte basées sur des arbres spatiaux, comme l'arbre k-d et l'arbre R, peuvent également devenir moins efficaces pour des données de haute dimension, un problème souvent associé à la malédiction de la dimensionnalité.
Les méthodes approximatives du plus proche voisin échangent une partie de l'exactitude contre de la vitesse ou une utilisation moindre des ressources. Au lieu de garantir toujours l'élément le plus proche exact, elles tentent de renvoyer rapidement des éléments proches. D'autres méthodes approximatives incluent le hachage sensible à la localité et la quantification de produits.
HNSW s'appuie sur la recherche sur les réseaux à petit monde et les graphes navigables. Dans un graphe à petit monde, la plupart des nœuds peuvent être atteints à partir d'autres nœuds par une courte chaîne de liens. Dans un graphe navigable, une procédure de recherche peut utiliser des informations locales pour se déplacer vers une cible. Les travaux de Jon Kleinberg sur la navigation dans les réseaux à petit monde sont un exemple important de ce domaine de recherche. Des travaux ultérieurs ont étudié des moyens d'ajouter des liens qui rendent les graphes plus faciles à naviguer de manière gloutonne.
L'algorithme HNSW étend les méthodes antérieures de monde navigable à petit monde pour la recherche de similarité en ajoutant une hiérarchie de couches de graphe. Cette hiérarchie aide l'algorithme à trouver une bonne région du graphe avant d'effectuer une recherche plus détaillée dans la couche inférieure.
Algorithme
HNSW est basé sur un graphe de proximité. Dans ce graphe, les vecteurs proches sont connectés par des arêtes. L'algorithme utilise ces arêtes pour se déplacer dans l'ensemble de données, plutôt que de scanner chaque vecteur.
Le graphe est hiérarchique. Chaque vecteur apparaît dans la couche inférieure. Certains vecteurs sont également placés dans des couches supérieures, avec moins de vecteurs apparaissant à mesure que les couches montent. Les couches supérieures permettent un mouvement à longue portée à travers l'ensemble de données, tandis que les couches inférieures permettent une recherche plus détaillée près des candidats prometteurs.
Une recherche typique se déroule comme suit :
- La recherche commence à partir d'un point d'entrée dans la couche la plus élevée.
- À chaque étape, l'algorithme examine les nœuds voisins et se déplace vers un voisin plus proche de la requête.
- Lorsqu'il ne peut pas trouver un voisin plus proche dans cette couche, il descend à la couche suivante.
- Dans la couche inférieure, il explore un ensemble plus large de nœuds candidats et renvoie les candidats les plus proches trouvés.
Cette stratégie de recherche est souvent décrite comme une navigation gloutonne. L'algorithme choisit à plusieurs reprises des nœuds localement meilleurs, en utilisant la structure du graphe pour s'approcher du point de requête.
Construction et paramètres
Le graphe HNSW est construit de manière incrémentale. Lorsqu'un nouveau vecteur est inséré, l'algorithme lui attribue une couche maximale, recherche les nœuds existants proches et connecte le nouveau nœud à des voisins sélectionnés dans chaque couche où il apparaît.
Les implémentations exposent généralement des paramètres qui contrôlent le compromis entre vitesse, précision, utilisation de la mémoire et temps de construction. Un nombre plus élevé de connexions de graphe peut améliorer le rappel mais nécessite plus de mémoire. Une liste de candidats de recherche plus grande peut améliorer la précision mais rend les requêtes plus lentes. Une liste de candidats de construction plus grande peut améliorer la qualité du graphe mais rend la construction de l'index plus lente.
Parce que HNSW est approximatif, ses résultats ne sont pas toujours identiques à une recherche exacte complète. Ses performances pratiques dépendent de l'ensemble de données, de la mesure de distance, de l'implémentation et des paramètres. Des études de référence ont montré que les bibliothèques basées sur HNSW sont de solides performeurs parmi les méthodes approximatives du plus proche voisin, bien que les performances dans le pire des cas puissent différer des performances sur des ensembles de données de référence courants.
Utilisation dans les systèmes de recherche vectorielle
HNSW est utilisé comme index dans les systèmes qui stockent et recherchent des vecteurs de haute dimension. Ces systèmes incluent les bases de données vectorielles, les moteurs de recherche et les extensions de bases de données. Les utilisations typiques incluent la recherche sémantique, les systèmes de recommandation, la recherche de similarité d'images et la génération augmentée par récupération, qui est souvent appliquée dans les pipelines de IA générative et de grands modèles de langage.
Plusieurs projets logiciels implémentent ou prennent en charge HNSW. Les bibliothèques incluent hnswlib, qui est associé aux auteurs originaux de HNSW, et FAISS. Les systèmes de bases de données et de recherche qui documentent la prise en charge de HNSW incluent Apache Lucene, Chroma, ClickHouse, DuckDB, MariaDB, Milvus, pgvector, Qdrant et Redis. Ces outils sont couramment déployés sur des plateformes cloud telles que Amazon Web Services, Microsoft Azure et Google Cloud pour des charges de travail de apprentissage automatique en production.
Voir aussi
- Recherche approximative du plus proche voisin
- Base de données vectorielle
- Hachage sensible à la localité
- Quantification de produits