Búsqueda de similitud, Parte 2 Cuantización de productos
Similarity Search, Part 2 Product Quantization.
Aprende una técnica poderosa para comprimir eficazmente grandes datos
La búsqueda de similitud es un problema donde, 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 la ciencia de datos, la búsqueda de similitud a menudo aparece en el dominio NLP, los motores de búsqueda o los sistemas de recomendación donde se deben recuperar los documentos o elementos más relevantes para una consulta. Existe una gran variedad de formas diferentes de mejorar el rendimiento de la búsqueda en volúmenes masivos de datos.
En la primera parte de esta serie de artículos, examinamos kNN y la estructura de índice de archivo invertido para realizar búsquedas de similitud. Como aprendimos, kNN es el enfoque más sencillo mientras que el índice de archivo invertido actúa sobre él sugiriendo un compromiso entre la aceleración de velocidad y la precisión. Sin embargo, ambos métodos no utilizan técnicas de compresión de datos que podrían provocar problemas de memoria, especialmente en casos de conjuntos de datos grandes y RAM limitada. En este artículo, intentaremos abordar este problema examinando otro método llamado Product Quantization.
Búsqueda de similitud, Parte 1: kNN & Índice de archivo invertido
La búsqueda de similitud es un problema popular donde, dada una consulta Q, necesitamos encontrar los documentos más similares a ella entre todos…
towardsdatascience.com
- Bootcamp LLM de Pila Completa Gratis
- Definir el interés público en nuevas tecnologías.
- Comprender la política de gradientes construyendo la entropía cruza...
Definición
Quantización de producto es el proceso donde cada vector de conjunto de datos se convierte en una representación corta y eficiente en memoria (llamada código PQ). En lugar de mantener completamente todos los vectores, se almacenan sus representaciones cortas. Al mismo tiempo, la cuantización de producto es un método de compresión con pérdida que da como resultado una precisión de predicción más baja, pero en la práctica, este algoritmo funciona muy bien.
En general, la cuantización es el proceso de asignar valores infinitos a valores discretos.
Entrenamiento
En primer lugar, el algoritmo divide cada vector en varias partes iguales: subvectores. Cada una de las partes respectivas de todos los vectores de conjunto de datos forma subespacios independientes y se procesa por separado. Luego, se ejecuta un algoritmo de agrupamiento para cada subespacio de vectores. Al hacerlo, se crean varios centroides en cada subespacio. Cada subvector se codifica con el ID del centroide al que pertenece. Además, se almacenan las coordenadas de todos los centroides para su uso posterior.
Los centroides de subespacio también se llaman vectores cuantizados.
En la cuantización de productos, a menudo se hace referencia a un ID de cluster como un valor de reproducción.
Nota. En las figuras a continuación, un rectángulo representa un vector que contiene varios valores mientras que un cuadrado indica un solo número.
Como resultado, si un vector original se divide en n partes, entonces se puede codificar mediante n números: ID de los centroides respectivos para cada uno de sus subvectores. Por lo general, el número de centroides creados k se elige como una potencia de 2 para un uso de memoria más eficiente. De esta manera, la memoria requerida para almacenar un vector codificado es n * log(k) bits.
La colección de todos los centroides dentro de un subespacio se llama libro de códigos. Ejecutar n algoritmos de agrupamiento para todos los subespacios produce n libros de códigos separados.
Ejemplo de compresión
Imaginemos un vector original de tamaño 1024 que almacena flotantes (32 bits) se dividió en n = 8 subvectores donde cada subvector se codifica por uno de k = 256 clusters. Por lo tanto, codificar el ID de un solo cluster requeriría log(256) = 8 bits. Comparemos los tamaños de memoria para la representación del vector en ambos casos:
- Vector original: 1024 * 32 bits = 4096 bytes.
- Vector codificado: 8 * 8 bits = 8 bytes.
¡La compresión final es de 512 veces! Esta es la verdadera potencia de la cuantificación de productos.
Aquí algunos apuntes importantes:
- El algoritmo puede ser entrenado en un subconjunto de vectores (por ej., para crear grupos) y ser utilizado en otro: una vez que el algoritmo está entrenado, se pasa otro conjunto de datos de vectores donde los nuevos vectores son codificados utilizando los centroides ya construidos para cada subespacio.
- Por lo general, k-means es elegido como algoritmo de agrupamiento. Una de sus ventajas es que el número de grupos k es un hiperparámetro que puede ser definido manualmente, de acuerdo a los requerimientos de uso de memoria.
Inferencia
Para tener una mejor comprensión, primero echemos un vistazo a varios enfoques ingenuos y descubramos sus desventajas. Esto también nos ayudará a comprender por qué no deben ser utilizados normalmente.
Enfoques ingenuos
El primer enfoque ingenuo consiste en descomprimir todos los vectores concatenando los centroides correspondientes de cada vector. Después de eso, se puede calcular la distancia L2 (o otra métrica) desde un vector de consulta hasta todos los vectores del conjunto de datos. Obviamente, este método funciona pero es muy lento porque se realiza una búsqueda de fuerza bruta y el cálculo de la distancia se realiza en vectores descomprimidos de alta dimensión.
Otra posible forma es dividir un vector de consulta en subvectores y calcular una suma de distancias desde cada subvector de consulta hasta los vectores cuantizados respectivos de un vector de base, basado en su código PQ. Como consecuencia, se utiliza nuevamente la técnica de búsqueda de fuerza bruta y el cálculo de la distancia aquí aún requiere un tiempo lineal de la dimensionalidad original de los vectores, como en el caso anterior.
Otro método posible es codificar el vector de consulta en un código PQ. Luego, este código PQ se utiliza directamente para calcular distancias a todos los demás códigos PQ. El vector del conjunto de datos con el código PQ correspondiente que tiene la distancia más corta se considera como el vecino más cercano a la consulta. Este enfoque es más rápido que los dos anteriores porque siempre se calcula la distancia entre códigos PQ de baja dimensión. Sin embargo, los códigos PQ están compuestos por IDs de grupo que no tienen mucho significado semántico y pueden considerarse como una variable categórica utilizada explícitamente como una variable real. Claramente, esta es una mala práctica y este método puede llevar a una mala calidad de predicción.
Enfoque optimizado
Un vector de consulta se divide en subvectores. Para cada uno de sus subvectores, se calculan las distancias a todos los centroides del subespacio correspondiente. Finalmente, esta información se almacena en la tabla d .
Las distancias parciales calculadas de subvector a centroide a menudo se denominan distancias parciales .
Al utilizar esta tabla de distancias de subvector a centroide d , la distancia aproximada desde la consulta a cualquier vector de la base de datos puede ser fácilmente obtenida por sus códigos PQ:
- Para cada uno de los subvectores de un vector de la base de datos, se encuentra el centroide más cercano j (utilizando valores de mapeo de códigos PQ) y se toma la distancia parcial d[i][j] desde ese centroide hasta el subvector de consulta i (utilizando la matriz calculada d ).
- Se elevan al cuadrado todas las distancias parciales y se suman. Al tomar la raíz cuadrada de este valor, se obtiene la distancia euclidiana aproximada. Si quieres saber cómo obtener resultados aproximados para otras métricas también, navega hasta la sección “Aproximación de otras métricas de distancia” .
Utilizar este método para calcular distancias aproximadas asume que las distancias parciales d son muy cercanas a las distancias reales a entre la consulta y los subvectores de la base de datos.
Sin embargo, esta condición puede no cumplirse, especialmente cuando la distancia c entre el subvector de la base de datos y su centroide es grande. En tales casos, los cálculos resultan en una menor precisión.
Después de haber obtenido distancias aproximadas para todas las filas de la base de datos, buscamos los vectores con los valores más pequeños. Esos vectores serán los vecinos más cercanos a la consulta.
Aproximación de otras métricas de distancia
Hasta ahora hemos visto cómo aproximar la distancia euclidiana mediante el uso de distancias parciales. Generalicemos la regla para otras métricas también.
Imaginemos que queremos calcular una métrica de distancia entre un par de vectores. Si conocemos la fórmula de la métrica, podemos aplicarla directamente para obtener el resultado. Pero a veces podemos hacerlo por partes de la siguiente manera:
- Ambos vectores se dividen en n subvectores.
- Para cada par de subvectores respectivos, se calcula la métrica de distancia.
- Las n métricas calculadas se combinan para producir la distancia real entre los vectores originales.
La distancia euclidiana es un ejemplo de una métrica que puede calcularse por partes. Basándonos en la figura anterior, podemos elegir las funciones de agregación para ser h(z) = z² , g(z₀, z₁, …, zₙ) = sum(z₀, z₁, …, zₙ) y f(z) = √z .
El producto interno es otro ejemplo de una métrica de este tipo con funciones de agregación h(z) = z, g(z₀, z₁, …, zₙ) = sum(z₀, z₁, …, zₙ) y f(z) = z .
En el contexto de la cuantificación de productos, esta es una propiedad muy importante porque durante la inferencia el algoritmo calcula distancias por partes. Esto significa que sería mucho más problemático utilizar métricas para la cuantificación de productos que no tienen esta propiedad. La distancia del coseno es un ejemplo de tal métrica.
Si todavía hay una necesidad de utilizar una métrica sin esta propiedad, entonces se deben aplicar heurísticas adicionales para agregar distancias parciales con algún error.
Rendimiento
La principal ventaja de la cuantificación de productos es una compresión masiva de vectores de base de datos que se almacenan como códigos PQ cortos. ¡Para algunas aplicaciones, esta tasa de compresión puede ser incluso superior al 95%! Sin embargo, aparte de los códigos PQ, se debe almacenar la matriz d de tamaño k x n que contiene vectores cuantificados de cada subespacio.
La cuantificación de productos es un método de compresión con pérdida, por lo que cuanto mayor sea la compresión, es más probable que disminuya la precisión de la predicción.
Construir un sistema para representación eficiente requiere el entrenamiento de varios algoritmos de agrupamiento. Además, durante la inferencia, se deben calcular en modo de fuerza bruta k * n distancias parciales y sumarlas para cada uno de los vectores de la base de datos, lo que puede llevar algún tiempo.
Implementación de Faiss
Faiss (Facebook AI Search Similarity) es una biblioteca de Python escrita en C++ utilizada para búsqueda de similitud optimizada. Esta biblioteca presenta diferentes tipos de índices que son estructuras de datos utilizadas para almacenar los datos y realizar consultas de manera eficiente.
Basándose en la información de la documentación de Faiss, veremos cómo se utiliza la cuantificación de productos.
La cuantificación de productos se implementa en la clase IndexPQ. Para la inicialización, necesitamos proporcionarle 3 parámetros:
- d: número de dimensiones en los datos.
- M: número de divisiones para cada vector (el mismo parámetro que n utilizado anteriormente).
- nbits: número de bits que se necesitan para codificar un solo ID de clúster. Esto significa que el número de clústeres totales en un solo subespacio será igual a k = 2^nbits.
Para la división de dimensiones de subespacio iguales, el parámetro dim debe ser divisible por M.
El número total de bytes necesarios para almacenar un solo vector es igual a:
Como se puede ver en la fórmula anterior, para un uso más eficiente de la memoria, el valor de M * nbits debe ser divisible por 8.
Conclusión
Hemos examinado un algoritmo muy popular en sistemas de recuperación de información que comprime eficientemente grandes volúmenes de datos. Su principal desventaja es una velocidad lenta de inferencia. A pesar de este hecho, el algoritmo se utiliza ampliamente en aplicaciones modernas de Big data, especialmente en combinación con otras técnicas de búsqueda de similitud.
En la primera parte de la serie de artículos, describimos el flujo de trabajo del índice de archivo invertido. De hecho, podemos fusionar estos dos algoritmos en uno más eficiente que poseerá las ventajas de ambos. ¡Esto es exactamente lo que haremos en la próxima parte de esta serie!
Búsqueda de similitud, Parte 3: Mezcla del índice de archivo invertido y la cuantificación de productos
En las dos primeras partes de esta serie, hemos discutido dos algoritmos fundamentales en la recuperación de información: invertido…
Zepes.com
Recursos
- Cuantificación de productos para búsqueda del vecino más cercano
- Documentación de Faiss
- Repositorio de Faiss
- Resumen de los índices de Faiss
Todas las imágenes, salvo que se indique lo contrario, son del autor.
