Introducción a HNSWlib

La búsqueda semántica permite a las máquinas comprender el lenguaje y obtener mejores resultados de búsqueda, lo que resulta esencial en la IA y el análisis de datos. Una vez representado el lenguaje como incrustaciones, la búsqueda puede realizarse mediante métodos exactos o aproximados. La búsqueda aproximada por vecino más próximo (RNA) es un método utilizado para encontrar rápidamente en un conjunto de datos los puntos más cercanos a un punto de consulta dado, a diferencia de la búsqueda exacta por vecino más próximo, que puede ser costosa desde el punto de vista computacional para datos de alta dimensión. La RNA permite una recuperación más rápida al proporcionar resultados aproximadamente próximos a los vecinos más cercanos.

Uno de los algoritmos de búsqueda de vecinos más próximos aproximados (RNA) es HNSW (Hierarchical Navigable Small Worlds), implementado en HNSWlib, que será el tema central de la discusión de hoy. En este blog:

• Entenderemos el algoritmo HNSW.

• Exploraremos HNSWlib y sus principales características.

• Configurar HNSWlib, incluyendo la creación de índices y la implementación de búsquedas.

• Compararlo con Milvus.

Entender HNSW

Hierarchical Navigable Small Worlds (HNSW) es una estructura de datos basada en gráficos que permite búsquedas eficientes de similitud, particularmente en espacios de alta dimensión, mediante la construcción de un gráfico de múltiples capas de redes de "mundo pequeño". Introducido en 2016, HNSW aborda los problemas de escalabilidad asociados con los métodos de búsqueda tradicionales como la fuerza bruta y las búsquedas basadas en árboles. Es ideal para aplicaciones que implican grandes conjuntos de datos, como los sistemas de recomendación, el reconocimiento de imágenes y la generación de recuperación aumentada (RAG).

Por qué es importante HNSW

HNSW mejora significativamente el rendimiento de la búsqueda del vecino más próximo en espacios de gran dimensión. Al combinar la estructura jerárquica con la navegabilidad en mundos pequeños, se evita la ineficacia computacional de los métodos antiguos, lo que permite obtener buenos resultados incluso con conjuntos de datos masivos y complejos. Para entenderlo mejor, veamos cómo funciona ahora.

Cómo funciona HNSW

1. Capas jerárquicas: HNSW organiza los datos en una jerarquía de capas, donde cada capa contiene nodos conectados por aristas. Las capas superiores son más dispersas, lo que permite "saltar" ampliamente por el gráfico, de forma parecida a cuando se aleja el zoom en un mapa para ver sólo las principales autopistas entre ciudades. Las capas inferiores son más densas y ofrecen más detalles y conexiones entre los vecinos más cercanos.

2. Concepto de pequeños mundos navegables: Cada capa de HNSW se basa en el concepto de una red de "mundos pequeños", en la que los nodos (puntos de datos) se encuentran a pocos "saltos" unos de otros. El algoritmo de búsqueda comienza en la capa más alta y dispersa y va descendiendo hacia capas cada vez más densas para refinar la búsqueda. De este modo, se pasa de una visión global a un nivel de vecindad más detallado, reduciendo gradualmente el área de búsqueda.

Fig. 1: Ejemplo de gráfico de mundo pequeño navegable

3. Estructura jerárquica: El aspecto jerárquico de HNSW se asemeja a una lista de exclusión, una estructura de datos probabilística en la que las capas superiores tienen menos nodos, lo que permite realizar búsquedas iniciales más rápidas.

Fig. 2: Ejemplo de estructura de lista de exclusión

Para buscar 96 en la lista de exclusión dada, empezamos en el nivel superior, en el extremo izquierdo, en el nodo de cabecera. Moviéndonos hacia la derecha, encontramos 31, menos que 96, así que continuamos hasta el siguiente nodo. Ahora, tenemos que bajar un nivel donde volvemos a ver 31; como sigue siendo menor que 96, bajamos otro nivel. Al encontrar 31 una vez más, nos movemos a la derecha y llegamos a 96, nuestro valor objetivo. Así, localizamos 96 sin necesidad de descender a los niveles más bajos de la lista de saltos.

4. Eficacia de la búsqueda: El algoritmo HNSW parte de un nodo de entrada en la capa más alta y avanza hacia los vecinos más cercanos en cada paso. Desciende a través de las capas, utilizando cada una de ellas para una exploración de grano grueso a fino, hasta llegar a la capa más baja, donde probablemente se encuentren los nodos más similares. Esta navegación por capas reduce el número de nodos y aristas que hay que explorar, haciendo que la búsqueda sea rápida y precisa.

5. Inserción y mantenimiento: Al añadir un nuevo nodo, el algoritmo determina su capa de entrada en función de la probabilidad y lo conecta a los nodos cercanos mediante una heurística de selección de vecinos. La heurística pretende optimizar la conectividad, creando enlaces que mejoren la navegabilidad al tiempo que equilibran la densidad del grafo. Este enfoque mantiene la estructura robusta y adaptable a nuevos puntos de datos.

Aunque tenemos un conocimiento básico del algoritmo HNSW, aplicarlo desde cero puede resultar abrumador. Afortunadamente, la comunidad ha desarrollado bibliotecas como HNSWlib para simplificar su uso, haciéndolo accesible sin tener que rascarse la cabeza. Echemos un vistazo a HNSWlib.

Visión general de HNSWlib

HNSWlib, una popular librería que implementa HNSW, es altamente eficiente y escalable, funcionando bien incluso con millones de puntos. Alcanza una complejidad temporal sublineal al permitir saltos rápidos entre capas de grafos y optimizar la búsqueda de datos densos y de alta dimensión. Estas son las principales características de HNSWlib

• Estructura basada en grafos: Un grafo de varias capas representa los puntos de datos, lo que permite realizar búsquedas rápidas por proximidad.

• Eficiencia en altas dimensiones: Optimizado para datos de alta dimensión, proporciona búsquedas aproximadas rápidas y precisas.

• Tiempo de búsqueda sublineal: logra una complejidad sublineal saltándose capas, lo que mejora significativamente la velocidad.

• Actualizaciones dinámicas: Permite insertar y eliminar nodos en tiempo real sin necesidad de reconstruir todo el grafo.

• Eficiencia de memoria: Uso eficiente de la memoria, adecuado para grandes conjuntos de datos.

• Escalabilidad: Se adapta bien a millones de puntos de datos, por lo que es ideal para aplicaciones de escala media como los sistemas de recomendación.

Nota: HNSWlib es excelente para crear prototipos sencillos de aplicaciones de búsqueda vectorial. Sin embargo, debido a las limitaciones de escalabilidad, puede haber mejores opciones, como bases de datos vectoriales creadas específicamente para escenarios más complejos que impliquen cientos de millones o incluso miles de millones de puntos de datos. Veámoslo en acción.

Primeros pasos con HNSWlib: Guía paso a paso

Esta sección demostrará el uso de HNSWlib como biblioteca de búsqueda vectorial mediante la creación de un índice HNSW, la inserción de datos y la realización de búsquedas. Comencemos con la instalación:

Instalación e importaciones

Para empezar con HNSWlib en Python, primero instálalo usando pip:

pip install hnswlib

Luego, importa las librerías necesarias:

import hnswlib 
import numpy as np

Preparación de datos

En este ejemplo, vamos a utilizar NumPypara generar un conjunto de datos aleatorios con 10.000 elementos, cada uno con una dimensión de tamaño 256.

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

Vamos a crear los datos:

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

Ahora que nuestros datos están listos, vamos a construir un índice.

Creación de un índice

Para construir un índice, necesitamos definir la dimensionalidad de los vectores y el tipo de espacio. Creemos un índice:

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

• space='l2': Este parámetro define la métrica de distancia utilizada para la similitud. Si se establece en 'l2', se utilizará la distancia euclidiana (norma L2). Si por el contrario lo establecemos en 'ip', se utilizará el producto interior, que es útil para tareas como la similitud coseno.

• dim=dim: Este parámetro especifica la dimensionalidad de los puntos de datos con los que trabajará. Debe coincidir con la dimensión de los datos que planea añadir al índice.

Así es como se inicializa un índice:

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

• max_elements=num_elements: Establece el número máximo de elementos que se pueden añadir al índice. Num_elements es la capacidad máxima, así que lo establecemos en 10.000 ya que estamos trabajando con 10.000 puntos de datos.

• ef_construction=200: Este parámetro controla la compensación entre precisión y velocidad de construcción durante la creación del índice. Un valor más alto mejora la recuperación (precisión) pero aumenta el uso de memoria y el tiempo de construcción. Los valores comunes oscilan entre 100 y 200.

• M=16: Este parámetro determina el número de enlaces bidireccionales creados para cada punto de datos, lo que influye en la precisión y la velocidad de búsqueda. Los valores típicos están entre 12 y 48; 16 suele ser un buen equilibrio para una precisión y velocidad moderadas.

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

• ef: El parámetro ef, abreviatura de "factor de exploración", determina cuántos vecinos se examinan durante una búsqueda. A mayor valor de ef, más vecinos se exploran, lo que generalmente aumenta la precisión (recall) de la búsqueda, pero también la hace más lenta. Por el contrario, un valor menor de ef puede hacer que la búsqueda sea más rápida pero puede reducir la precisión.

En este caso, establecer ef a 50 significa que el algoritmo de búsqueda evaluará hasta 50 vecinos cuando encuentre los puntos de datos más similares.

Nota: ef_construction establece el esfuerzo de búsqueda de vecinos durante la creación del índice, mejorando la precisión pero ralentizando la construcción. ef controla el esfuerzo de búsqueda durante la consulta, equilibrando la velocidad y la recuperación dinámicamente para cada consulta.

Realización de búsquedas

Para realizar una búsqueda de vecinos más cercanos con HNSWlib, primero creamos un vector de consulta aleatorio. En este ejemplo, la dimensionalidad del vector coincide con los datos indexados.

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: Esta línea genera un vector aleatorio con la misma dimensionalidad que los datos indexados, lo que garantiza la compatibilidad para la búsqueda del vecino más próximo.
• knn_query: El método busca los k vecinos más cercanos de query_vector dentro del índice p. Devuelve dos matrices: labels, que contiene los índices de los vecinos más cercanos, y distances, que indica las distancias desde el vector de consulta a cada uno de estos vecinos. Aquí, k=5 especifica que queremos encontrar los cinco vecinos más cercanos.

Aquí están los resultados después de imprimir las etiquetas y las distancias:

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 ]]

Aquí lo tenemos, una guía sencilla para poner las ruedas en marcha con HNSWlib.

Como ya hemos mencionado, HNSWlib es un gran motor de búsqueda vectorial para crear prototipos o experimentar con conjuntos de datos de tamaño medio. Si tiene requisitos de escalabilidad más altos o necesita otras características de nivel empresarial, es posible que tenga que elegir una base de datos vectorial creada específicamente, como Milvus de código abierto o su servicio totalmente gestionado en Zilliz Cloud. Por lo tanto, en la siguiente sección, compararemos HNSWlib con Milvus.

HNSWlib frente a bases de datos vectoriales específicas como Milvus

Una base de datos vectorial almacena datos como representaciones matemáticas, lo que permite a los modelos de aprendizaje automático potenciar la búsqueda, las recomendaciones y la generación de texto mediante la identificación de datos a través de métricas de similitud para la comprensión contextual.

Las bibliotecas de índices vectoriales como HNSWlib mejoran labúsqueda y recuperación de vectores, pero carecen de las funciones de gestión de una base de datos completa. Por otro lado, las bases de datos vectoriales, como Milvus, están diseñadas para manejar incrustaciones vectoriales a escala, proporcionando ventajas en la gestión de datos, indexación y capacidades de consulta que las bibliotecas independientes suelen carecer. He aquí algunas otras ventajas de utilizar Milvus:

• Búsqueda de similitud vectorial de alta velocidad: Milvus proporciona un rendimiento de búsqueda a nivel de milisegundos en conjuntos de datos vectoriales a escala de miles de millones, ideal para aplicaciones como la recuperación de imágenes, los sistemas de recomendación, el procesamiento del lenguaje natural(PLN) y la generación de recuperación aumentada(RAG).

• Escalabilidad y alta disponibilidad: Diseñado para manejar grandes volúmenes de datos, Milvus se escala horizontalmente e incluye mecanismos de replicación y conmutación por error para mayor fiabilidad.

• Arquitectura distribuida: Milvus utiliza una arquitectura distribuida y escalable que separa el almacenamiento y la computación en múltiples nodos para mayor flexibilidad y robustez.

• Búsqueda híbrida: Milvus admite la búsqueda multimodal, la búsqueda híbrida dispersa y densa, y la búsqueda híbrida densa y de texto completo, ofreciendo una funcionalidad de búsqueda versátil y flexible.

• Soporte flexible de datos: Milvus admite varios tipos de datos -vectores, escalares y datos estructurados-, lo que permite una gestión y un análisis sin fisuras dentro de un único sistema.

• Comunidad y soporteactivos: Una próspera comunidad proporciona actualizaciones periódicas, tutoriales y soporte, asegurando que Milvus permanezca alineado con las necesidades de los usuarios y los avances en el campo.

• Integración de IA: Milvus se ha integrado con varios marcos y tecnologías de IA populares, lo que facilita a los desarrolladores la creación de aplicaciones con sus pilas tecnológicas familiares.

Milvus también proporciona un servicio totalmente gestionado en Ziliz Cloud, que no presenta problemas y es 10 veces más rápido que Milvus.

Comparación: Milvus frente a HNSWlib

Características	Milvus	HNSWlib
Escalabilidad	Maneja miles de millones de vectores con facilidad	Adecuado para conjuntos de datos más pequeños debido al uso de RAM
Ideal para	Prototipos, experimentos y aplicaciones empresariales	Centrado en prototipos y tareas ligeras de RNA
Indexación	Admite más de 10 algoritmos de indexación, como HNSW, DiskANN, cuantización y binario.	Sólo utiliza HNSW basado en grafos
Integración	Ofrece API y servicios nativos en la nube	Funciona como una biblioteca ligera e independiente
Rendimiento	Optimizado para grandes volúmenes de datos y consultas distribuidas	Ofrece alta velocidad pero escalabilidad limitada

En general, Milvus es preferible para aplicaciones de producción a gran escala con necesidades de indexación complejas, mientras que HNSWlib es ideal para la creación de prototipos y casos de uso más sencillos.

Conclusión

La búsqueda semántica puede consumir muchos recursos, por lo que la estructuración interna de datos, como la que realiza HNSW, es esencial para una recuperación de datos más rápida. Las bibliotecas como HNSWlib se preocupan por la implementación, por lo que los desarrolladores tienen las recetas listas para crear prototipos de capacidades vectoriales. Con unas pocas líneas de código, podemos construir nuestro propio índice y realizar búsquedas.

HNSWlib es una buena forma de empezar. Sin embargo, si queremos crear aplicaciones de IA complejas y listas para la producción, la mejor opción son las bases de datos vectoriales creadas a tal efecto. Por ejemplo, Milvus es una base de datos vectorial de código abierto con muchas características empresariales, como búsqueda vectorial de alta velocidad, escalabilidad, disponibilidad y flexibilidad en cuanto a tipos de datos y lenguaje de programación.

Más información

• ¿Qué es Faiss (Facebook AI Similarity Search)?

• ¿Qué es HNSWlib? Una biblioteca basada en grafos para la búsqueda rápida de RNA

• ¿Qué es ScaNN (Scalable Nearest Neighbors)?

• VectorDBBench: Una herramienta de evaluación comparativa de VectorDB de código abierto

• Generative AI Resource Hub | Zilliz

• ¿Qué son las bases de datos vectoriales y cómo funcionan?

• ¿Qué es RAG?

• Modelos de IA de alto rendimiento para tus aplicaciones de GenAI | Zilliz