Explorando algoritmos ANN en bases de datos vectoriales

Objetivos de aprendizaje

• Comprender cómo difieren los métodos de representación de datos y búsqueda entre bases de datos relacionales y vectoriales, destacando las limitaciones de la búsqueda binaria en espacios multidimensionales.
• Conocer algoritmos ANN basados en árboles como KD-trees y el método de la biblioteca Annoy para dividir puntos de datos utilizando hiperplanos aleatorios.
• Entender los algoritmos ANN basados en grafos, especialmente el algoritmo HNSW, y cómo construyen y navegan eficientemente por los grafos para encontrar vecinos más cercanos.
• Explorar algoritmos híbridos como NGT, que mejoran la velocidad y precisión de búsqueda integrando estructuras de árboles y grafos.
• Descubrir las aplicaciones prácticas de las bases de datos vectoriales en recomendaciones de música, productos, publicidad personalizada, y más.

¿Qué son los algoritmos ANN?

En las bases de datos relacionales, cada registro se representa en una fila y sus atributos se representan en columnas. Por ejemplo, considera una tabla con N nombres de autores y sus datos de artículos de investigación respectivos. Un enfoque ingenuo sería comparar el nombre del autor de la consulta con todos los valores en la columna Autor para encontrar los libros escritos por un autor en particular. Este método requiere N comparaciones.

Un método más eficiente es ordenar la columna Autor alfabéticamente. Luego, utilizando la búsqueda binaria, podemos encontrar utilizando solo log(N) comparaciones. Sin embargo, el escenario cambia cuando se trata de encontrar artículos de investigación relevantes basados en una consulta dada. El enfoque ingenuo es encontrar la similitud entre el vector de embeddings de la consulta y todos los vectores de embeddings de documentos, lo que requiere N comparaciones.

Ordenar el texto del artículo de investigación o los embeddings y usar la búsqueda binaria no funciona porque no estamos buscando una coincidencia exacta con el embedding de la consulta. Solo queremos encontrar los embeddings más similares. Además, los embeddings representan los datos en un espacio multidimensional. Ordenar por cualquier dimensión única no tiene sentido.

Entonces, necesitamos diferentes algoritmos que puedan buscar vectores de manera más eficiente. Estos algoritmos se llaman algoritmos de vecinos más cercanos aproximados (ANN). Si bien estos algoritmos pueden no encontrar siempre los vecinos más cercanos más precisos en comparación con el enfoque ingenuo, mejoran significativamente la velocidad y la eficiencia de búsqueda en grandes conjuntos de datos multidimensionales. La implementación de algoritmos ANN es lo que diferencia a las bases de datos vectoriales de las bases de datos relacionales tradicionales.

¿Cómo funcionan los algoritmos ANN?

Ahora que entiendes qué son los algoritmos ANN, averigüemos cómo funcionan diferentes algoritmos ANN.

Algoritmos basados en árboles

Los algoritmos basados en árboles organizan los puntos de datos donde los puntos que están más cerca en el espacio también están más cerca en el árbol. Algunos ejemplos de tales árboles son el árbol K-dimensional (KD-tree), el árbol de Punto de Vista (VP-tree), el árbol de Bolas (Ball tree) y el árbol Rectangular (R-tree).

Una biblioteca popular que implementa un algoritmo basado en árboles es Annoy (Approximate Nearest Neighbors Oh Yeah). Fue desarrollada por Erik Bernhardsson mientras trabajaba en Spotify. Annoy construye el árbol dividiendo puntos de datos utilizando hiperplanos aleatorios.

¿Cómo funciona Annoy?

1. Considera todos los puntos ubicados en el espacio como se muestra en la imagen.
2. Elige aleatoriamente dos puntos del conjunto de datos.
3. Calcula un hiperplano que sea perpendicular al segmento de línea que conecta los dos puntos y pase por el punto medio del segmento de línea. Podemos usar este hiperplano para dividir todos los puntos hacia el lado izquierdo o derecho del nodo del árbol.
4. Toma el vector normal del hiperplano y calcula el producto punto con cada punto de datos. Si el producto punto es positivo, el punto está en la misma dirección que el vector normal. Si el producto punto es negativo, el punto está en la dirección opuesta al vector normal. Basado en el producto punto, divide los puntos en nodos hijos izquierdo o derecho.
5. Divide recursivamente los nodos por hiperplanos hasta que solo queden unos pocos puntos en los nodos hoja. Esto divide el espacio total en cuadrículas, donde los nodos hoja almacenan los puntos y todos los demás nodos almacenan los hiperplanos utilizados para la división.
6. Para encontrar los vecinos más cercanos para un punto de consulta, calcula su producto punto con el vector normal del hiperplano del nodo raíz. Basado en el resultado, atraviesa hacia la izquierda o derecha del nodo. Continúa atravesando hasta llegar al nodo hoja. Luego, calcula la similitud entre la consulta y los puntos en el nodo hoja.
7. Como el árbol es un árbol binario, encontrar vecinos más cercanos requiere aproximadamente log(N) comparaciones.
8. Si el punto de consulta está cerca del borde de cualquier cuadrícula, considerar solo un nodo hoja puede omitir puntos similares en nodos hoja adyacentes. Para abordar esto, podemos construir múltiples árboles, cada uno con puntos de partida aleatorios diferentes, por lo tanto, hiperplanos diferentes. Atraviesa cada árbol con la consulta y calcula la similitud con puntos en los nodos hoja de todos los árboles, asegurando no omitir ningún vecino más cercano.
9. También podemos almacenar los nodos con similitudes calculadas en una cola de prioridad para devolver los k vecinos más cercanos principales.

Esta descripción detallada explica cómo funcionan los algoritmos ANN basados en árboles, particularmente en la división de puntos de datos y la búsqueda de vecinos más cercanos de manera eficiente. Al considerar casos límite y utilizar múltiples árboles, el algoritmo puede mejorar la precisión y el rendimiento en la búsqueda de vecinos más cercanos.

Algoritmos basados en grafos

En estos algoritmos, los puntos de datos se representan como vértices del grafo, y los bordes se utilizan para atravesar el grafo para encontrar vecinos más cercanos. Entendámoslo en detalle usando el algoritmo más popular actualmente, el Pequeño Mundo Navegable Jerárquico (HNSW).

¿Cómo funciona HNSW?

1. Como se muestra en la imagen anterior, cada vértice en el grafo representa un punto de datos.
2. Conecta cada vértice con un número configurable de vértices más cercanos de manera codiciosa.
3. Para encontrar los vecinos más cercanos para una consulta, comienza desde cualquier vértice aleatorio, digamos A.
4. Encuentra los vértices conectados a A, que podrían ser C, G y D.
5. Calcula la distancia entre la consulta y cada uno de estos vértices (A, C, G, D).
6. Compara las distancias y muévete al vértice más cercano a la consulta, que es D en este caso.
7. Repite este proceso con el vértice D y sus vértices conectados, moviéndote luego a E.
8. Cuando repetimos este proceso comenzando en E, encontramos que E es el vértice más cercano a la Consulta nuevamente. Entonces, encontramos el vecino más cercano a nuestra consulta.

Si te preguntas cómo construimos el grafo en primer lugar, así como encontramos los vecinos más cercanos para una consulta, podemos encontrar los vecinos más cercanos para un nuevo vértice mientras lo insertamos. Luego podemos conectar el nuevo vértice a los vértices más cercanos predefinidos a través de bordes.

En el grafo, cada vértice se conecta a solo unos pocos vértices cercanos, creando así una red de pequeño mundo. A medida que navegamos, esto se llama un pequeño mundo navegable.

Cuando se trata de millones de puntos de datos, atravesar el grafo para encontrar el vecino más cercano comenzando desde un punto aleatorio puede llevar tiempo, ya que cada vértice está conectado a solo unos pocos vértices. Aumentar el número de bordes para cada vértice también lleva mucho tiempo, ya que se necesitan calcular más distancias.

Para superar este problema, se construyen múltiples grafos con diferentes números de vértices. Cada grafo puede considerarse una capa.

¿Cómo funciona esto?

1. En la primera capa, usa una fracción de los puntos de datos para construir el grafo, por ejemplo, N/4.
2. En la siguiente capa, usa N/2 puntos de datos para construir el grafo.
3. En la última capa, usa todos los puntos de datos.
4. Para encontrar los vecinos más cercanos a la consulta, comienza desde la capa 1.
5. Dado que el número de vértices es menor, los bordes son más largos, lo que permite una rápida travesía a un vértice más cercano en esa capa (por ejemplo, H).
6. Comienza desde el vértice H en la siguiente capa y atraviesa el grafo hasta encontrar el vecino más cercano en esa capa (vértice B).
7. Continúa este proceso hasta encontrar el vecino más cercano en la última capa.

Así, el número de travesías y cálculos de distancia son menores en comparación con el algoritmo NSW.

Fórmula e implementación del HNSW

¿Cómo decidimos el número de capas y cuántos puntos de datos deben estar en cada una? El documento del HNSW proporciona la siguiente fórmula para asignar puntos de datos a diferentes capas.

floor(-ln(unif(0,1))*mL)

Aquí,

• unif(0,1) representa un número aleatorio tomado de una distribución uniforme entre 0 y 1.
• −ln(unif(0,1)) el logaritmo natural de un número aleatorio uniforme se usa para transformar la distribución uniforme en una distribución exponencial. Esta transformación junto con el signo negativo la convierte en una distribución sesgada a la derecha.
• mL es un multiplicador que escala el valor logarítmico. Generalmente se establece en 1/ln(M), donde M es el número máximo de vecinos que cada nodo puede tener.
• La función floor redondea el valor resultante al entero más cercano. Esto determina el nivel discreto en el que se colocará el nodo.

HNSW es el algoritmo predeterminado para la mayoría de las bases de datos vectoriales. Spotify también lanzó una nueva biblioteca Voyager basada en HNSW.

Probemos el algoritmo HNSW

import numpy as np
import faiss

# Podemos elegir algunos números aleatorios para la base de datos y las consultas.
d = 256  # dimensión
nb = 100000  # tamaño de la base de datos
nq = 10000  # número de consultas
np.random.seed(1234)  # hacer reproducible
xb = np.random.random((nb, d)).astype('float32')
xb[:, 0] += np.arange(nb) / 1000.
xq = np.random.random((nq, d)).astype('float32')
xq[:, 0] += np.arange(nq) / 1000.

# Primero, intentemos el enfoque ingenuo construyendo el FlatIndex.
flat_index = faiss.IndexFlatL2(d)  # construir el índice
print(flat_index.is_trained)
>>> True

flat_index.add(xb)  # agregar vectores al índice
print(flat_index.ntotal)
>>> 100000

# Ahora, podemos buscar
%%time  # este comando dará el tiempo tomado para ejecutarse en jupyter notebook
k = 5  # podemos obtener 5 vecinos más cercanos
D, I = flat_index.search(xq, k)  # búsqueda actual
print(I[:5])  # vecinos de las primeras 5 consultas
print(D[:5])  # distancias de las primeras 5 consultas

>>> [[  69  525  628  595 1413]
 [ 603   25   14 1616  698]
 [ 732  744  739  589 1185]
 [ 447  841  347  373  631]
 [1053  924  163  101  302]]
[[33.871002 33.979095 34.67044  34.738922 35.204865]
 [34.497314 34.682297 35.488464 35.671005 35.864685]
 [32.993195 34.401352 34.411896 34.514572 34.659515]
 [33.948517 34.039062 34.364456 34.466248 35.244644]
 [33.487595 34.77111  34.81253  34.893692 35.152557]]

# Ahora intentemos el algoritmo HNSW
M = 32  # cada vértice se conectará a otros M vértices más cercanos
hnsw_index = faiss.IndexHNSWFlat(d, M)  # construir el índice
print(hnsw_index.is_trained)

>>> True

# Podemos agregar los datos al índice.

# Para conectar a M otros vértices, buscará codiciosamente hasta 'efConstruction' vértices.
# el valor predeterminado es 40, podemos cambiarlo antes de agregar el conjunto de datos
hnsw_index.hnsw.efConstruction = 48

hnsw_index.add(xb)

# después de agregar nuestros datos, encontraremos que el nivel se ha establecido automáticamente
hnsw_index.hnsw.max_level
>>> 3

# y los niveles (o capas) ahora están poblados
levels = faiss.vector_to_array(hnsw_index.hnsw.levels)
np.bincount(levels)
>>> array([    0, 96812,  3093,    92,     3])

# Ahora podemos buscar

# cuántos puntos de entrada se explorarán entre capas durante la búsqueda.
# por ejemplo, podemos seleccionar 30 vértices más cercanos en una capa,
# luego comenzar a atravesar el grafo desde esos vértices en la siguiente capa
hnsw_index.hnsw.efSearch = 30

%%time
hnsw_index.search(xq[:5], k=4)

>>> (array([[33.870995, 33.979073, 34.67042 , 34.738907],
        [34.497334, 34.682304, 35.488453, 35.67101 ],
        [32.993187, 34.401337, 34.411903, 34.514584],
        [33.948494, 34.039097, 34.36444 , 34.46623 ],
        [33.487595, 34.771133, 34.81257 , 34.893723]], dtype=float32),
 array([[  69,  525,  628,  595],
        [ 603,   25,   14, 1616],
        [ 732,  744,  739,  589],
        [ 447,  841,  347,  373],
        [1053,  924,  163,  101]]))

Algoritmos híbridos

En estos algoritmos, usamos tanto árboles como grafos para encontrar los vecinos más cercanos. Un ejemplo es Neighborhood Graph and Tree (NGT), que es el algoritmo ANN de mejor rendimiento actualmente. NGT utiliza un árbol de punto de vista dinámico y un grafo. Veamos cómo funciona.

¿Cómo funciona NGT?

1. El dvp-tree comienza con un solo nodo hoja que representa todo el espacio de datos.
2. A medida que añadimos nuevos puntos, el árbol atraviesa para encontrar el nodo hoja apropiado para la inserción.
3. Cuando el número de puntos en un nodo hoja excede un máximo predefinido, el nodo hoja se divide en subespacios más pequeños. Esta división es similar al método del árbol de punto de vista (vp-tree), donde se elige un punto de vista y el espacio se divide utilizando hiperesferas centradas en este punto de vista.
4. Para cada punto en el nodo, calculamos la distancia al punto de vista.
5. Elegimos un radio ‘r’ que equilibre los puntos entre el interior y el exterior de la hiperesfera.
6. Los puntos con una distancia d ≤ r desde el punto de vista están dentro de la hiperesfera, y los puntos con d > r están fuera. Los círculos y arcos en la imagen representan estas hiperesferas.
7. Este proceso de división se repite recursivamente, creando una estructura jerárquica de nodos y subnodos.
8. El dvp-tree soporta actualizaciones dinámicas, lo que significa que podemos añadir puntos incrementalmente sin reconstruir todo el árbol.
9. El proceso continúa hasta que cada nodo hoja contiene un número manejable de puntos.
10. Luego, podemos atravesar solo los nodos hoja en un grafo utilizando el algoritmo NSW explicado anteriormente.

Aplicaciones de los algoritmos ANN en bases de datos vectoriales

Exploremos ahora algunas de las aplicaciones más comunes de los algoritmos ANN.

1. Recomendaciones Basadas en Similitud

Estas aplicaciones se centran en encontrar coincidencias aproximadas a las preferencias del usuario o características del contenido.

• Recomendaciones de Música: Plataformas como Spotify usan bases de datos vectoriales para recomendar música basada en los hábitos de escucha del usuario y las características de las canciones.
• Recomendaciones de Productos: Los sitios de comercio electrónico usan bases de datos vectoriales para sugerir productos similares a los que un usuario ha visto o comprado.
• Publicidad Personalizada: Las bases de datos vectoriales emparejan anuncios con usuarios según su comportamiento y preferencias, mejorando las tasas de participación y conversión.

2. Búsqueda Basada en Embeddings

Estas aplicaciones utilizan embeddings para buscar elementos similares en varios tipos de medios, mejorando la precisión y relevancia de la búsqueda.

• Búsqueda de Texto: En el procesamiento de lenguaje natural, las bases de datos vectoriales almacenan embeddings de texto para búsquedas semánticas, recuperación de documentos y sistemas de preguntas y respuestas.
• Búsqueda de Imágenes y Videos: Permiten la recuperación de imágenes visualmente similares, utilizadas en búsquedas inversas de imágenes, recuperación de contenido basado en imágenes o videos, y gestión de activos digitales.
• Búsqueda de Moléculas: En bioinformática y descubrimiento de fármacos, los embeddings de moléculas ayudan a encontrar moléculas estructuralmente similares, apoyando la identificación de posibles candidatos a fármacos.

3. Miscellaneous

Otras aplicaciones incluyen la detección de anomalías, el análisis geoespacial, entre otras.

Conclusión

Las bases de datos vectoriales, mediante algoritmos ANN eficientes como métodos basados en árboles, grafos e híbridos, mejoran significativamente las capacidades de búsqueda en espacios multidimensionales. Sus aplicaciones prácticas abarcan diversas industrias, ofreciendo poderosas soluciones para recomendaciones basadas en similitud, búsqueda basada en embeddings y publicidad personalizada.

Espero que este artículo te haya brindado una idea detallada de los algoritmos ANN en bases de datos vectoriales. Consulta nuestros otros artículos sobre bases de datos vectoriales para aprender más. ¡Feliz aprendizaje!

Puntos clave

• Las bases de datos vectoriales sobresalen en el manejo de búsquedas de datos multidimensionales, superando en eficiencia y velocidad a las bases de datos relacionales tradicionales.
• Los algoritmos ANN basados en árboles como KD-trees y Annoy mejoran el rendimiento de búsqueda organizando puntos de datos mediante hiperplanos aleatorios.
• Los algoritmos basados en grafos, como HNSW, navegan eficientemente por espacios de datos complejos conectando puntos de datos a través de vértices y bordes.
• Los algoritmos híbridos como NGT combinan las fortalezas de árboles y grafos para lograr búsquedas de vecinos más cercanos más rápidas y precisas.
• Las bases de datos vectoriales son cruciales en aplicaciones como recomendaciones, publicidad personalizada y búsqueda basada en embeddings en varios tipos de medios.

Preguntas frecuentes