La introducción de la búsqueda vectorial (KNN), con su puntuación de similitud basada en la distancia, en el paradigma de búsqueda existente exigió un cambio en la forma de concebir los resultados "relevantes" y de medirlos.
Los índices basados en texto utilizan tf-idf como mecanismo de puntuación, con los mismos resultados en todas las búsquedas, dado un corpus fijo de palabras (en este caso, los documentos de una partición).
En cambio, una búsqueda KNN no garantiza el mismo nivel de idempotencia. Los resultados son aproximadoque a menudo difieren entre consultas. En este artículo, el equipo de búsqueda pasa de la búsqueda exacta a la aproximada. Por el camino, respondemos a preguntas sobre por qué los resultados aproximados pueden convertirse en la nueva normalidad y cuánta aproximación es aceptable.
Preparar el escenario
Cada partición del índice de búsqueda es una Bleve índice compuesto por varios segmentos de zap (arquitectura segmentada), conteniendo cada segmento un índice vectorial. Éstos se compactan periódicamente mediante una rutina de fusión para el índice Bleve.
Usos de la búsqueda FAISS para la creación de índices vectoriales, la formación, la búsqueda y otras funciones relacionadas.
Las dos grandes clases de índices utilizados actualmente por Couchbase Search son:
-
- Índices planos: realizan búsquedas exhaustivas, como si almacenaran los vectores en una matriz.
- Índices de FIV - Índices basados en centroides que implican la agrupación (KMeans en este caso) del conjunto de datos y, a continuación, el poblamiento de esos clústeres.
Breve descripción de KNN
Como ya he comentado antes, el testware (e igualmente importante, nuestra forma de pensar) estaba predispuesto a la puntuación exacta. La búsqueda por texto es fundamentalmente exhaustivo en el sentido de que un índice invertido incluye todos los tokens de los documentos de la partición. Todos los documentos de un índice invertido son elegible para la búsqueda y se buscará a través de él.
Un índice vectorial basado en el centroide, por comparación, limita el conjunto de vectores elegibles de buenas a primeras, buscando únicamente en grupos específicos, que pueden ser o no los mismos para cada consulta. Esto significa que, para una consulta determinada, la búsqueda exhaustiva, que puede llevar mucho tiempo, se sustituye por una aproximación.
(Si la palabra "retirada" le ha despistado un poco, no se mueva: hablaremos de ello dentro de un rato).
Teniendo en cuenta que limitamos nuestro espacio de búsqueda desde el principio, es importante "agrupar bien".
Uno de los primeros pasos en una búsqueda consiste en elegir cuántos y qué clusters buscar. Si son demasiado pocos, se pierden algunos vectores potencialmente similares. Si son demasiados, la latencia de la búsqueda aumenta considerablemente a cambio de un incremento relativamente pequeño de la calidad de la búsqueda.
La métrica utilizada para la calidad de la búsqueda es retirada - qué porcentaje de los resultados devueltos son objetivamente los más próximos a los vectores de la consulta. El conjunto de los vectores más cercanos al vector de consulta se denomina verdad básica y se utiliza como referencia para medir la recuperación. Dado que la puntuación KNN es la distancia entre dos vectores, es independiente de los demás documentos en la partición (a diferencia del tf-idf) y, lo que es más importante, esto ayuda a realizar una comparación objetiva entre la verdad sobre el terreno evaluada de forma independiente y el resultado.
Cuánto (aproximado) es demasiado (aproximado): Recuerdo de conducción de 0,06 a 90+:
Con todos estos conocimientos, decidimos empezar a hacer pruebas de recuperación. Nuestras primeras pruebas mostraron un recuerdo sorprendentemente bajo, cercano al 0, 0,06 para ser precisos.
Aunque habíamos descargado la búsqueda de índices vectoriales a FAISS, había algunos aspectos que debíamos gestionar desde nuestro lado. Uno de ellos es la asignación de ID de documentos a los vectores. La búsqueda asigna cada número de documento a un hash vectorial único. Estos hashes se pasan como ID personalizados a FAISS para aprovechar el soporte para mapear vectores a ID personalizados y las búsquedas devuelven el ID personalizado. Teniendo en cuenta que los vectores (cada uno de los cuales tiene el mismo tamaño) están concatenados en un gran vector y también lo están los ID, conseguir el orden correcto determina el mapeo del vector al ID. Internamente, FAISS utiliza un hashmap para almacenar los vectores y sus IDs.
|
1 |
[<vec1>,<vec2>,...<vec_n>],[id1,id2,...id_n] => vec1 → id1, vec2 → id2, ... vec_n → id_n |
Un examen más detallado mostró que estábamos asignando ID ordenados aleatoriamente a vectores al reconstruir índices durante una fusión, lo que provocaba que el conjunto de resultados fuera esencialmente aleatorio. Esto afectaba tanto a los índices planos como a los IVF, ya que ambos se basaban en el método solicitud de los ID al recuperar los resultados.
Una vez resuelto el problema del orden, junto con algunas otras correcciones de la ruta de fusión, la retirada se elevó a unos 70 usuarios. Ahora íbamos por el buen camino: no teníamos ningún error fundamental que nos afectara. Empezamos a echar un vistazo a los botones que podíamos ajustar.
Girar mandos - Centroides y Nprobe
La estrategia inicial utilizaba un número fijo (100) de centroides para todos los índices vectoriales con más de 10.000 vectores. En esencia, se trataba igual a 1M de vectores que a 20k vectores.
La agrupación FAISS por defecto tiene un número mínimo (39) y máximo (256) de puntos por agrupación. Los puntos restantes son submuestreados. 100 centroides pueden haber sido suficientes para 100 * 256 = 25600 vectores como máximo, pero para cualquier cosa por encima de eso, había exceso de submuestreo, como se refleja en la recuperación. Lo que necesitábamos era una fórmula para los centroides que se ajustara al conjunto de datos.
Qué queremos optimizar: Recall@Ksin que la indexación y la latencia de búsqueda se resientan demasiado, si es posible.
Configurar
La configuración era bastante sencilla: los scripts creaban un índice FAISS (formación y adición de ID) y los consultaban, conociendo de antemano los resultados de la verdad sobre el terreno. Utilicé el SIFT10K y SIFT1M conjuntos de datos del documento original ya que proporcionaron vectores de referencia utilizando la distancia euclídea. El recall@K es la media de 100/10k consultas respectivamente.
Aumento de los centroides
La primera fase consistió en ajustar el número de conglomerados.
Resultados de Sift1M - 10.000 consultas
| # centroides | Tiempo de formación | Tiempo de búsqueda | retirada@100 |
| 100 | 1.83 | 20.72 | 0.61 |
| 200 | 1.856 | 14.423 | 0.558 |
| 500 | 4.75 | 4.101 | 0.4833 |
| 1000 | 15.13 | 2.4113 | 0.43 |
Resultados de Sift10k - 100 consultas
| # centroides | Tiempo de entrenamiento (ms) | Tiempo de búsqueda (ms) | retirada@100 |
| 10 | 30.78 | 1370 | 0.82 |
| 50 | 103 | 368.9 | 0.69 |
| 100 | 100 | 188.48 | 0.6 |
Perspectivas
-
- La línea de base actual muestra un recuerdo de 0,61, que sin duda puede mejorarse.
- La retirada disminuye con el aumento del número de centroides.
- El tiempo de búsqueda disminuye gracias a localización creciente aunque aumente el tiempo de entrenamiento.
A la inversa, el tiempo de búsqueda aumenta, a pesar del bajo tiempo de entrenamiento, para un menor número de centroides, ya que esto implica buscar en celdas más grandes con un mayor número de vectores.
Una vez establecido que el aumento de los centroides tiene un impacto negativo en el recuerdo, intentemos comprender intuitivamente por qué es así.
Con un conjunto de datos de tamaño fijo, aumentar el número de centroides podría disminuir el número de documentos de cada clúster. Con clusters más pequeños buscar menos vectores en general y elige los K vectores más cercanos.
Por lo tanto, un aumento del número de conglomerados debería ir acompañado de un aumento correspondiente del número de conglomerados buscados.
Aumentar nprobe
Sift1M - 10.000 consultas
| nlist | nprobe | Tiempo de formación | Tiempo total de búsqueda | retirada@100 |
| 100 (base actual) | 1 | 1.43 | 21.24 | 0.61 |
| 100 | 10 | 0.778 | 119.5 | 0.993 |
| 200 | 14 | 1.12 | 84.54 | 0.99 |
| 500 | 22 | 3.23 | 52.80 | 0.988 |
| 1000 | 31 | 10.033 | 37.79 | 0.988 |
| 2000 | 44 | 36.36 | 27.61 | 0.985 |
| 3000 | 54 | 80.94 | 22.74 | 0.985 |
| 3906 (1M/256) | 62 | 134.61 | 20s | 0.984 |
| 4000 | 32 | 136.71 | 10.09 | 0.956 |
| 4000 | 64 | 138.57 | 20.36 | 0.987 |
Sift10k - 100 consultas
| nlist | nprobe | Tiempo de formación | Tiempo total de búsqueda | retirada@100 |
| 10 | 1 | 33,85 ms | 1.52s | 0.82 |
| 39 (10000/256) | 6 | 70,6 ms | 1.91s | 0.96 |
| 50 | 7 | 70,26 ms | 1.68s | 0.99 |
| 100 | 5 | 91,5 ms | 677,14 ms | 0.9 |
| 100 | 10 | 99ms | 1.317s | 0.96 |
| 200 | 14 | 133,26 ms | 930,2 ms | 1.0 |
Perspectivas
-
- Para el conjunto de datos 1M, la recuperación de referencia es baja debido a nprobe = 1.
- Una vez solucionado, la recuperación aumenta rápidamente y deja de ser un problema, a pesar del submuestreo.
- Sin embargo, una gran capacidad de recuperación conlleva una mayor latencia de búsqueda.
- En el caso del conjunto de datos de 10.000, la recuperación de referencia, aunque no es tan baja como la del conjunto de datos de 1.000, sigue siendo preocupante.
- Esto también se remedia fácilmente aumentando nprobe.
- Para el conjunto de datos 1M, la recuperación de referencia es baja debido a nprobe = 1.
Los valores por defecto para determinar nlist y nprobe se cambiaron entonces a:
|
1 2 3 4 5 6 7 8 9 10 |
si nVecs >= 1M: nlist = 4 * √nVecs // A partir de un cierto número de vectores, // el aumento de nlist no aumenta la recuperación. si nVecs >= 1000: nlist = nVecs/100 // 100 puntos por cluster parece un // punto medio razonable entre el mínimo // y puntos máximos por agrupación. nprobe = √nlist |
Basta decir que así es como se sintió el equipo una vez que encontramos una solución al problema de la retirada:
Ajuste de un índice vectorial
Afinar un índice vectorial Couchbase definitivamente no es algo para sudar.
Dado que el equilibrio entre recuperación y latencia es crucial en la búsqueda vectorial, queríamos que el usuario tuviera cierta flexibilidad a la hora de inclinarse. Además de las consideraciones relativas al usuario, como la facilidad de comprensión y la intuitividad, la compatibilidad con el futuro y la arquitectura segmentada implicaban algunas limitaciones en la API.
Cada segmento es un índice vectorial con un número diferente de vectores. En el momento de la consulta, un el usuario no es consciente de la distribución de los datos a nivel de partición, y mucho menos a nivel de segmento. Dependiendo de la naturaleza de las mutaciones (gran número de borrados, por ejemplo), el el número de vectores puede variar bastante al fusionar segmentos. Por lo tanto, un no se puede aplicar un enfoque único para todos los segmentos.
Además, la compatibilidad con el futuro exige que el los mandos no son específicos de un tipo de índice FAISS ya que se trata de un área que, en su mayor parte, debería abstraerse del usuario, a pesar de cambiar los tipos de índice que se utilizan en la implementación. Por ejemplo, si el usuario especifica nprobe o nlist sería muy específico del índice IVF y supondría un cambio radical si cambiasen los tipos de índice que alimentan la búsqueda vectorial.
Permitir al usuario alternar qué métrica optimizar (recall/latencia) se ajusta a la perfección. Aunque el ajuste de la recuperación se realiza de forma diferente para un índice IVF y, por ejemplo, para un índice HNSW, la recuperación es aplicable a ambos y puede ajustarse a nivel de segmento. En los datos anteriores, si se duplica nprobe, se duplica el tiempo de búsqueda, pero el aumento correspondiente de la recuperación es de unos pocos puntos. Por tanto, al optimizar la latencia, reducir a la mitad el índice nprobe mejora la latencia sin afectar demasiado a la capacidad de recuperación.
El ajuste de definición del índice en el que el usuario puede alternar entre recuperación y latencia puede modificarse es vector_index_optimized_for. Esta configuración está documentada en la documentación oficial.
Permanezca atento para conocer más detalles y novedades sobre Couchbase Vector Search.
