Búsqueda aproximada de vecinos más cercanos en sistemas de recomendación
Introducción
En febrero de 2024, escuchamos a Yury Malkov en el SF Unstructured Data Meetup hablar sobre Approximate Nearest Neighbor (ANN) y su papel clave en los sistemas de recomendación. La búsqueda ANN ya está integrada en los stacks de producción de las herramientas más populares del mundo. Yury nos ayuda a comprender los conceptos clave y el contexto que han impulsado la adopción de ANN en sistemas de recomendación a gran escala.
Enlace a la repetición en YouTube de la charla de Yury Malkov: Ver la charla en YouTube
¿Por qué debería importarte ANN?
Yuri Malkov es literalmente un genio. Si no me crees, revisa su perfil en Google Scholar https://scholar.google.com/citations?user=KvAyakQAAAAJ&hl=en. Físico, investigador de láseres e inventor de HNSW, un algoritmo de indexación basado en grafos ahora integrado de serie en todas las principales bases de datos vectoriales. Ahora trabaja para OpenAI como Research Scientist. Dime que eso no suena como una biografía plausible de Tony Stark en 2024.
Con eso, profundicemos en la charla de Yuri sobre “Búsqueda aproximada de vecinos más cercanos en sistemas de recomendación.”
¿Qué es la búsqueda ANN?
Seremos breves, ya que ya hemos cubierto los conceptos básicos de la búsqueda ANN de forma resumida y en detalle.
Las búsquedas de vecinos más cercanos son un conjunto de técnicas estadísticas que podemos usar para realizar búsquedas de similitud en aplicaciones de aprendizaje automático o ciencia de datos. A diferencia de su primo con sabor especial K, KNN, que compara cada punto de datos de un sistema con todos los demás al completar su búsqueda, los algoritmos de búsqueda ANN utilizan diversas técnicas de indexación para devolver vecinos más cercanos aproximados. Las búsquedas ANN se han vuelto fundamentales para muchas aplicaciones y tecnologías orientadas al cliente hoy en día. Desde motores de búsqueda (como Google, no búsqueda vectorial) hasta sitios de redes sociales, ANN y los sistemas de recomendación ya están integrados en todo el stack, en producción.
ANN no era la única solución para los sistemas de recomendación. Entonces, ¿cómo llegamos hasta aquí? Repasaremos las soluciones ANN maduras que existen hoy en el mercado, qué hace que los sistemas de recomendación sean un problema difícil para los algoritmos de vecinos más cercanos, cómo los desarrolladores han estructurado los sistemas de recomendación y cómo los investigadores están usando ANN para reescribir el stack de sistemas de recomendación. Yuri señala en su charla que existen muchas soluciones ANN maduras. Muchos de estos temas se cubren en profundidad en nuestra Guía visual para elegir un índice vectorial, pero he preparado una tabla con las herramientas enumeradas en la presentación de Yuri.
Tabla de índices ANN mencionados
| Índice ANN | Clasificación | Escenario |
|---|---|---|
| LSH | Índice basado en grafos | - Grandes conjuntos de datos multidimensionales altamente complejos - Usa distancia euclidiana para agrupar puntos de datos en buckets - Solo devuelve los resultados más cercanos |
| HNSW | Índice basado en grafos | - Consulta de muy alta velocidad - Requiere una tasa de recuperación lo más alta posible - Grandes recursos de memoria |
| SCANN | Índice basado en cuantización | - Consulta de muy alta velocidad - Requiere una tasa de recuperación lo más alta posible - Grandes recursos de memoria |
| IVF_PQ | Índice basado en cuantización (invertido) | - Índice invertido - Consulta de muy alta velocidad - Recursos de memoria limitados - Acepta un compromiso sustancial en la tasa de recuperación |
| IVF_HSNW | Índice basado en grafos (invertido) | - Índice invertido - Basado en HSNW - Requiere una tasa de recuperación lo más alta posible - Grandes recursos de memoria |
| DiskANN | Múltiples índices de vecinos más cercanos | - Modificaciones de ANN y toolkit para búsquedas ANN |
| ANNOY | Múltiples índices de vecinos más cercanos | - Implementaciones de LSH o KDtrees - Búsqueda rápida y eficiente en memoria en espacios de alta dimensión |
| Muchos más | - | - FAISS, cuHNSW, ngt, song |
Acerca de los benchmarks de ANN
Yuri pasa por los benchmarks de ANN rapidísimo, señalando ANNBenchmarks con la advertencia de que comparar algoritmos ANN inversos puede complicarse. Vamos a ralentizar eso:
¿Qué es ANN-Benchmarks?
ANN-Benchmarks es un entorno de benchmarking que evalúa varios algoritmos de búsqueda aproximada de vecinos más cercanos, proporcionando resultados divididos por medida de distancia y conjunto de datos en su sitio web. Los benchmarks muestran métricas de rendimiento como la tasa de recuperación y las consultas por segundo, y los usuarios pueden contribuir enviando su código mediante solicitudes pull de GitHub .
Aunque puedes encontrar datos de benchmarking de algoritmos ANN en muchos lugares (github, ANN-Benchmarks, incluso documentación del producto), siempre verás gráficos que trazan QPS - consultas por segundo. ¡Más QPS, mejor! ¡Brum brum!
Una nota sobre la elección de algoritmos ANN (y otros de búsqueda vectorial)
Si mirar benchmarks de algoritmos te provoca sangrado de nariz, no eres el único. Por eso el equipo de Milvus creó Knowhere. Knowhere es el motor central de ejecución vectorial open-source de Milvus que incorpora varias bibliotecas de búsqueda de similitud vectorial, incluidas Faiss, Hnswlib y Annoy. Knowhere controla en qué hardware (CPU o GPU) ejecutar la construcción de índices y las solicitudes de búsqueda. Así es como Knowhere obtiene su nombre: saber dónde ejecutar las operaciones. Más tipos de hardware, incluidos DPU y TPU, serán compatibles en futuras versiones.
Basándose en Knowhere, el equipo de Zilliz Cloud lanzó Cardinal, que es el motor principal de búsqueda vectorial de Zilliz. Este motor de búsqueda ya ha demostrado un aumento de rendimiento de tres veces en comparación con la versión anterior, ofreciendo un rendimiento de búsqueda (QPS) que alcanza diez veces el de Milvus. La búsqueda ANN lleva mucho tiempo integrada en los sistemas de recomendación. Para descubrir por qué los algoritmos de búsqueda ANN se han vuelto tan populares en los sistemas de recomendación en producción, necesitamos dar un paso atrás y observar las motivaciones, la arquitectura y las soluciones novedosas a las que ANN superó.
Aplicaciones de sistemas de recomendación a escala: motivaciones y desafíos
Objetivo: El objetivo básico de todos los sistemas de recomendación es devolver un elemento (video, producto, documento, mensaje) a una consulta (usuario, aplicación, contexto). Recuerda esta relación elemento-consulta: es importante para entender los algoritmos de búsqueda (recomendación).
Mercado: Las tecnologías de recomendación han presentado y representan un gran mercado dada su capacidad para generar comportamiento del consumidor.
Desafíos típicos a escala:
Generalizabilidad:
- Tradicionalmente, los sistemas de recomendación han tenido baja generalizabilidad, en gran medida debido a la dependencia de datos, modelos e infraestructura internos.
Corpus enormes:
Los grandes conjuntos de datos (de millones a billones de elementos, consultas) generan grandes costos de inferencia.
La eficiencia y la limitación de los costos de inferencia son muy importantes.
El procesamiento intensivo de video e imágenes ha requerido ingenieros dedicados para mantener la infraestructura.
Soluciones, madurez:
Las soluciones/infraestructura internas suelen ser desarrolladas internamente (p. ej., Google, Meta, X)
Típicamente, un embudo de recomendación de múltiples etapas (ver abajo) para ahorrar costos de inferencia
Las herramientas listas para usar han ido ganando popularidad e impulso con el auge de las bases de datos vectoriales y los LLM.
Embudo típico de múltiples etapas
Yuri profundiza en un diagrama de un sistema de recomendación típico en producción. En el ejemplo siguiente de recomendación de videos, a una aplicación se le entregan elementos y una consulta, y debe devolver un pin de recomendación de video. Estas aplicaciones son embudos de múltiples etapas donde se generan candidatos de elementos y se ejecutan a través de modelos de clasificación sucesivos para refinar los resultados de búsqueda.
Paso 1: Generación de candidatos - ANN + Modelo ligero
En esta etapa inicial, el sistema utiliza vecinos más cercanos aproximados para examinar rápidamente la vasta base de datos de videos e identificar una lista preliminar de videos candidatos que sean relevantes para la consulta del usuario. Este proceso está diseñado para ser rápido y eficiente, manejando potencialmente millones de elementos al centrarse en aquellos con más probabilidades de coincidir con las características de la consulta. El 'Modelo ligero' utilizado en este paso suele ser un modelo más simple y menos intensivo computacionalmente que ayuda a reducir el conjunto de candidatos a aquellos que mejor se alinean con los intereses o términos de búsqueda del usuario.
Paso 2: Clasificación ligera - Fuerza bruta + Modelo intermedio
Una vez que se genera un conjunto de candidatos, el siguiente paso implica un examen más detallado de estos candidatos. Esto se hace utilizando un enfoque de 'Fuerza bruta', donde cada candidato se evalúa más exhaustivamente usando un 'Modelo intermedio', que es más complejo que el Modelo ligero utilizado en el primer paso. Este modelo tiene en cuenta características adicionales, como métricas de participación del usuario, relevancia contextual y calidad del contenido, para clasificar los candidatos de manera que los videos más relevantes se impulsen hacia la parte superior de la lista de recomendaciones. Este paso logra un equilibrio entre rendimiento y precisión, refinando la selección al centrarse más en la calidad y la relevancia.
Paso 3: Clasificación completa - Fuerza bruta + Modelo pesado
El paso final en el proceso de recomendación es la etapa de Clasificación Completa, que emplea un "Modelo Pesado": el más sofisticado y con mayor consumo de recursos de los modelos utilizados. Este modelo incorpora una amplia variedad de señales y puntos de datos, incluido un análisis más profundo del perfil de usuario, preferencias a largo plazo, análisis detallado del contenido y posiblemente datos en tiempo real como las tendencias de visualización actuales. El método de Fuerza Bruta aplicado aquí garantiza que cada video sea puntuado y clasificado de forma exhaustiva, asegurando que las recomendaciones finales sean altamente personalizadas y relevantes. Este paso garantiza recomendaciones de la más alta calidad, pero requiere más potencia de procesamiento y tiempo, lo que lo hace adecuado para el refinamiento final de la lista de recomendaciones.
Por qué HSNW falla en los sistemas de recomendación tradicionales y soluciones (imperfectas) Sabiendo que los sistemas de recomendación de producción a gran escala están limitados por grandes conjuntos de datos y los costos asociados, Yuri afirma que los ítems y las consultas se encuentran en dos - planos incompatibles. Cuando las consultas y los ítems residen en espacios diferentes e incompatibles, los algoritmos tradicionales de búsqueda por similitud como Hierarchical Navigable Small World (HNSW) enfrentan desafíos porque estos algoritmos dependen de una relación medible o función de distancia directamente entre la consulta y los ítems. Sin una métrica clara para evaluar la cercanía, HNSW no puede desempeñar eficazmente su función, que consiste en navegar por un grafo de ítems para encontrar las coincidencias más cercanas a una consulta.****
Una revisión de soluciones novedosas para la incompatibilidad ítem-consulta
Distancia L2 en vectores de datos
Cómo funciona: Utiliza la distancia L2 entre entradas de datos vectorizadas para crear una estructura de grafo sustituta para sistemas de recomendación.
Ventajas: Simplifica el proceso mediante el uso de un cálculo de distancia sencillo, ofreciendo una ventaja de velocidad durante las fases de generación de candidatos y reordenamiento.
Desventajas: Puede no capturar relaciones complejas o matices entre ítems y consultas tan eficazmente como modelos más sofisticados, lo que potencialmente conduce a recomendaciones menos personalizadas.
Clasificación con grafo bipartito
Cómo funciona: Proyecta ítems y consultas en un grafo bipartito donde los ítems se vinculan con sus usuarios o consultas más cercanos, lo que permite generar aristas basadas en estas relaciones.
Ventajas: Eficaz para estructurar datos relacionales entre usuarios e ítems, aunque las comparaciones directas con otros métodos son limitadas.
Desventajas: La construcción y el mantenimiento del grafo bipartito pueden requerir muchos recursos, y la eficacia puede variar enormemente según la densidad y la calidad de las conexiones del grafo.
Fuente de la imagen: https://www.vldb.org/pvldb/vol15/p794-tan.pdf
Reordenamiento mediante grafo (centrado en texto)
Cómo funciona: Utiliza un grafo creado a partir de vectores para la generación de candidatos, aplicando directamente un clasificador pesado al grafo para la recuperación de texto, lo que mejora la calidad de los resultados.
Ventajas: Elimina el embudo tradicional de múltiples etapas, lo que permite corregir errores cometidos en etapas anteriores del filtrado de candidatos.
Desventajas: Es principalmente eficaz para la recuperación basada en texto; puede no ser tan eficaz en otros contextos donde predominan características no textuales, lo que limita su aplicabilidad.
Fuente de la imagen: https://arxiv.org/pdf/2208.08942
Búsqueda en grafo en cascada
Cómo funciona: Comienza con una función de distancia ligera para la búsqueda inicial y pasa sin interrupciones a una función de distancia más pesada durante el proceso de búsqueda.
Ventajas: Proporciona flexibilidad al adaptar la función de distancia en tiempo real, optimizando tanto la velocidad como la precisión durante todo el proceso de búsqueda.
Desventajas: La complejidad de gestionar y optimizar funciones de distancia duales puede aumentar la sobrecarga computacional y la complejidad del sistema, lo que podría afectar la escalabilidad.
Fuente de la imagen: https://arxiv.org/pdf/2202.10226
¿Por qué la búsqueda ANN es tan popular?
Poniendo todo eso en conjunto: Yuri ha presentado una buena imagen de por qué los algoritmos ANN han tenido una implementación tan amplia, especialmente en aplicaciones (como sistemas de recomendación a gran escala) que trabajan con conjuntos de datos de alta dimensionalidad.
Coincidencia suficientemente buena (o mejor) - Si no necesitas una coincidencia perfecta, una variante ANN casi siempre es una mejor solución que otros algoritmos NN.
Flexibilidad - con una amplia gama de implementaciones, un desarrollador puede elegir el costo
Madurez - ANN se ha implementado en todos los principales lenguajes de programación, y existen varios frameworks populares para seleccionar y ejecutar búsquedas ANN.
Recursos adicionales
https://zilliz.com/learn/Local-Sensitivity-Hashing-A-Comprehensive-Guide
https://zilliz.com/learn/how-to-pick-a-vector-index-in-milvus-visual-guide
Enlace a la repetición en YouTube de la charla de Yury Malkov: Ver la charla en YouTube
Sigue leyendo
Zilliz Cloud BYOC Now Available Across AWS, GCP, and Azure
Zilliz Cloud BYOC is now generally available on all three major clouds. Deploy fully managed vector search in your own AWS, GCP, or Azure account — your data never leaves your VPC.
VidTok: Rethinking Video Processing with Compact Tokenization
VidTok tokenizes videos to reduce redundancy while preserving spatial and temporal details for efficient processing.
Building RAG Pipelines for Real-Time Data with Cloudera and Milvus
explore how Cloudera can be integrated with Milvus to effectively implement some of the key functionalities of RAG pipelines.