Búsqueda de similitud, Parte 3 Mezclando el índice de archivo invertido y la cuantificación de productos.

Similarity search, Part 3 Mixing inverted file indexing and product quantization.

Descubre cómo combinar dos índices básicos de búsqueda de similitud para obtener las ventajas de ambos

La búsqueda de similitud es un problema en el que, dada una consulta, el objetivo es encontrar los documentos más similares a ella entre todos los documentos de la base de datos.

Introducción

En ciencia de datos, la búsqueda de similitud aparece a menudo en el dominio de NLP, los motores de búsqueda o los sistemas de recomendación donde es necesario recuperar los documentos o elementos más relevantes para una consulta. Existe una amplia variedad de formas diferentes de mejorar el rendimiento de la búsqueda en grandes volúmenes de datos.

En las dos primeras partes de esta serie hemos discutido dos algoritmos fundamentales en la recuperación de información: el índice de archivo invertido y la cuantización de productos. Ambos optimizan el rendimiento de la búsqueda pero se centran en aspectos diferentes: el primero acelera la velocidad de búsqueda mientras que el segundo comprime vectores a una representación más pequeña y eficiente en memoria.

Búsqueda de similitud, Parte 1: kNN e Índice de Archivo Invertido

towardsdatascience.com

Búsqueda de similitud, Parte 2: Cuantización de Producto

En la primera parte de esta serie de artículos analizamos kNN e índice de archivo invertido para realizar búsqueda de similitud…

Zepes.com

Dado que ambos algoritmos se centran en aspectos diferentes, surge naturalmente la pregunta de si es posible fusionar estos dos algoritmos en uno nuevo.

En este artículo, combinaremos las ventajas de ambos enfoques para producir un algoritmo rápido y eficiente en memoria. Para obtener más información, la mayoría de las ideas discutidas se basarán en este documento.

Antes de entrar en detalles, es necesario comprender qué son los vectores residuales y obtener una intuición simple sobre sus propiedades útiles. Los utilizaremos más adelante al diseñar un algoritmo.

Vectores residuales

Imagina que se ejecuta un algoritmo de agrupamiento y produce varios grupos. Cada grupo tiene un centroide y puntos asociados a él. El residual es un desplazamiento de un punto (vector) desde su centroide. Básicamente, para encontrar un residual para un vector particular, hay que restar el vector de su centroide.

Si el grupo fue construido por el algoritmo k-means, entonces el centroide del grupo es la media de todos los puntos que pertenecen a ese grupo. Así, encontrar un residual de cualquier punto sería equivalente a restar la media de un grupo de él. Al restar el valor medio de todos los puntos que pertenecen a un grupo particular, los puntos se centrarían en 0.

En la izquierda se muestra un grupo original de puntos. Luego se resta el centroide del grupo de todos los puntos del grupo. Los vectores residuales resultantes se muestran a la derecha.

Podemos observar un hecho útil:

Reemplazar vectores originales con sus residuales no cambia su posición relativa entre sí.

Es decir, la distancia entre vectores siempre permanece la misma. Simplemente observemos las dos ecuaciones a continuación.

Restar la media no cambia la distancia relativa

La primera ecuación es la fórmula de la distancia euclidiana entre un par de vectores. En la segunda ecuación, se resta el valor medio del clúster de ambos vectores. Podemos ver que el término medio simplemente se cancela: ¡toda la expresión se convierte en la distancia euclidiana de la primera ecuación!

Probamos esta afirmación usando la fórmula para la métrica L2 (distancia euclidiana). Es importante recordar que esta regla puede no funcionar para otras métricas.

Por lo tanto, si para una consulta dada el objetivo es encontrar el vecino más cercano, es posible restar la media del clúster de la consulta y proceder al procedimiento de búsqueda normal entre residuos.

Restar una media de una consulta no cambia su posición relativa a otros vectores

Ahora veamos otro ejemplo en la figura siguiente con dos clústeres donde se calculan los residuos para los vectores de cada clúster por separado.

Restar la media del centroide correspondiente de cada vector de un clúster centrará todos los vectores del conjunto de datos alrededor de 0.

Esa es una observación útil que se utilizará en el futuro. Además, para una consulta dada, podemos calcular los residuos de la consulta para todos los clústeres. Los residuos de la consulta nos permiten calcular las distancias a los residuos originales del clúster.

Después de restar los valores medios de cada clúster, todos los puntos quedan centrados alrededor de 0. La posición relativa de la consulta y los residuos de la consulta a otros puntos de los clústeres correspondientes no cambia.

Entrenamiento

Teniendo en cuenta las observaciones útiles de la sección anterior, podemos comenzar a diseñar el algoritmo.

Dada una base de datos de vectores, se construye un índice de archivo invertido que divide el conjunto de vectores en n particiones de Voronoi y, por lo tanto, reduce el ámbito de búsqueda durante la inferencia.

Dentro de cada partición de Voronoi, se resta las coordenadas del centroide de cada vector. Como resultado, los vectores de todas las particiones se acercan entre sí y se centran alrededor de 0. En este momento, no es necesario almacenar los vectores originales ya que almacenamos sus residuos en su lugar.

Después de eso, se ejecuta el algoritmo de cuantificación de productos en vectores de todas las particiones.

Aspecto importante: la cuantificación del producto no se ejecuta para cada partición por separado, esto sería ineficiente porque el número de particiones tiende a ser alto y podría resultar en una gran cantidad de memoria necesaria para almacenar todos los libros de códigos. En su lugar, el algoritmo se ejecuta para todos los residuos de todas las particiones simultáneamente.

Efectivamente, ahora cada subespacio contiene subvectores de diferentes particiones de Voronoi. Luego, para cada subespacio, se realiza un algoritmo de clustering y se construyen k clústeres con sus centroides, como de costumbre.

Proceso de entrenamiento

¿Cuál fue la importancia de reemplazar los vectores con sus residuos? Si los vectores no se reemplazan con sus residuos, entonces cada subespacio contendría más subvectores diferentes (porque los subespacios almacenarían subvectores de diferentes particiones de Voronoi no intersectantes que podrían haber estado muy lejos entre sí en el espacio). Ahora, los vectores (residuos) de diferentes particiones se superponen entre sí. Dado que ahora hay menos variedad en cada subespacio, se necesitan menos valores de reproducción para representar efectivamente los vectores. En otras palabras:

Con la misma longitud de códigos PQ utilizados antes, los vectores pueden ser representados con más precisión porque tienen menos varianza.

Inferencia

Para una consulta dada, se encuentran los k centroides más cercanos de las particiones de Voronoi. Todos los puntos dentro de estas regiones se consideran como candidatos. Dado que los vectores originales fueron reemplazados inicialmente por sus residuos en cada región de Voronoi, también se necesita calcular el residuo de la consulta. En este caso, el residuo de la consulta debe calcularse por separado para cada partición de Voronoi (porque cada región tiene diferentes centroides). Solo los residuos de las particiones de Voronoi elegidas van a los candidatos.

La consulta residual se divide en subvectores. Como en el algoritmo original de cuantificación de productos, para cada subespacio se calcula la matriz de distancia d que contiene las distancias desde los centroides del subespacio hasta el subvector de consulta. Es fundamental tener en cuenta que la consulta residual es diferente para cada partición Voronoi. Básicamente, esto significa que la matriz de distancia d debe calcularse por separado para cada una de las residuales de consulta. Ese es el precio de cómputo para la optimización deseada.

Finalmente, las distancias parciales se suman como se hizo previamente en el algoritmo de cuantificación de productos.

Ordenar resultados

Después de calcular todas las distancias, se deben seleccionar los k vecinos más cercanos. Para hacerlo eficientemente, los autores proponen mantener una estructura de datos MaxHeap. Tiene una capacidad limitada de k y en cada paso almacena las k distancias más pequeñas actuales. Cada vez que se calcula una nueva distancia, su valor se agrega a MaxHeap solo si el valor calculado es menor que el valor más grande en MaxHeap. Después de calcular todas las distancias, la respuesta a la consulta ya está almacenada en MaxHeap. La ventaja de usar MaxHeap es su rápido tiempo de construcción que es O(n).

Proceso de inferencia

Rendimiento

El algoritmo aprovecha tanto el índice de archivo invertido como la cuantificación de productos. Dependiendo del número de particiones Voronoi sondeadas durante la inferencia, se deben calcular y almacenar en la memoria la misma cantidad de matrices d de subvector a centroide. Esto puede parecer una desventaja, pero en comparación con las ventajas generales, es un intercambio bastante bueno.

El algoritmo hereda una buena velocidad de búsqueda del índice de archivo invertido y eficiencia de compresión de la cuantificación de productos

Implementación de Faiss

Faiss (Facebook AI Search Similarity) es una biblioteca de Python escrita en C++ utilizada para la búsqueda de similitud optimizada. Esta biblioteca presenta diferentes tipos de índices que son estructuras de datos utilizadas para almacenar eficientemente los datos y realizar consultas.

Basado en la información de la documentación de Faiss, veremos cómo los índices de archivo invertido y cuantificación de productos pueden combinarse para formar un nuevo índice.

Faiss implementa el algoritmo descrito en la clase IndexIVFPQ que acepta los siguientes argumentos:

  • quantizer: especifica cómo se calcula la distancia entre vectores.
  • d: dimensionalidad de los datos.
  • nlist: número de particiones Voronoi.
  • M: número de subespacios.
  • nbits: número de bits que lleva codificar un solo ID de clúster. Esto significa que el número total de clústeres en un solo subespacio será igual a k = 2^nbits.

Además, es posible ajustar el atributo nprobe, que especifica cuántas particiones Voronoi deben usarse para la búsqueda de candidatos durante la inferencia. Cambiar este parámetro no requiere volver a entrenar.

Implementación de Faiss de IndexIVFPQ

La memoria requerida para almacenar un solo vector es la misma que en el método original de cuantificación de productos, excepto que ahora se agregan 8 bytes más para almacenar información sobre el vector en el índice de archivo invertido.

Conclusión

Usando el conocimiento de las partes anteriores del artículo, hemos recorrido la implementación de un algoritmo de última generación que logra una alta compresión de memoria y una velocidad de búsqueda acelerada. Este algoritmo se utiliza ampliamente en sistemas de recuperación de información cuando se trata con volúmenes masivos de datos.

Recursos

  • Quantization del producto para la búsqueda más cercana
  • Documentación de Faiss
  • Repositorio de Faiss
  • Resumen de los índices de Faiss

Todas las imágenes, a menos que se indique lo contrario, son del autor.

We will continue to update Zepes; if you have any questions or suggestions, please contact us!

Share:

Was this article helpful?

93 out of 132 found this helpful

Discover more

Ciencia de Datos

Predicción de rendimiento de cultivos utilizando Aprendizaje Automático e implementación de Flask.

Introducción La predicción del rendimiento de los cultivos es una técnica esencial de análisis predictivo en la indus...

Noticias de Inteligencia Artificial

Los doctores están utilizando chatbots de una manera inesperada.

A pesar de las desventajas de recurrir a la inteligencia artificial en medicina, algunos médicos encuentran que ChatG...

Inteligencia Artificial

Ingeniería de software aumentada por IA Todo lo que necesitas saber

Con esta guía completa, aprende sobre el campo en rápido crecimiento de la ingeniería de software aumentada por la IA...

Inteligencia Artificial

Google AI presenta Visually Rich Document Understanding (VRDU) un conjunto de datos para un mejor seguimiento del progreso de la tarea de comprensión de documentos

Cada vez se crean y almacenan más documentos por parte de las empresas en la era digital de hoy en día. Aunque estos ...

Inteligencia Artificial

Investigadores de Microsoft y ETH Zurich presentan HoloAssist un conjunto de datos multimodal para copilotos de IA de próxima generación para el mundo físico.

En el campo de la inteligencia artificial, un desafío persistente ha sido desarrollar asistentes de IA interactivos q...