Explorando el camino hacia la búsqueda rápida del vecino más cercano con Hierarchical Navigable Small Worlds
Hierarchical Navigable Small World (HNSW) se ha vuelto popular como uno de los enfoques de mejor rendimiento para la búsqueda aproximada del vecino más cercano. Sin embargo, HNSW es un poco complejo y las descripciones a menudo carecen de una explicación completa e intuitiva. Esta publicación hace un recorrido por la historia de la idea HNSW para ayudar a explicar qué significa realmente “mundo pequeño navegable jerárquico” y por qué es efectivo.
- Búsqueda aproximada de vecino más cercano
- Pequeñas palabras
- Pequeños mundos navegables
- Pequeños mundos navegables jerárquicos
- Resumen
- Apéndice
– Búsqueda mejorada
– Búsqueda e inserción de HNSW
– Inserción mejorada - Referencias
Una aplicación común del aprendizaje automático es búsqueda de vecino más cercanolo que significa encontrar los elementos más similares* a un objetivo; por ejemplo, recomendar elementos que sean similares a las preferencias de un usuario o buscar elementos que sean similares a la consulta de búsqueda de un usuario.
El método simple consiste en calcular la similitud de cada elemento con el objetivo y devolver los más cercanos. Sin embargo, si hay una gran cantidad de elementos (tal vez millones), esto será lento.
En su lugar, podemos utilizar una estructura llamada índice para hacer las cosas mucho más rápidas.
Sin embargo, existe una compensación. A diferencia del método simple, los índices sólo dan resultados aproximados: es posible que no recuperemos todos los vecinos más cercanos (es decir, la recuperación puede ser inferior al 100%).
Hay varios tipos diferentes de índice (por ejemplo, hash sensible a la localidad; índice de archivos invertido), pero HNSW ha demostrado ser particularmente efectivo en varios conjuntos de datos, logrando altas velocidades y manteniendo una alta recuperación.
*Normalmente, los elementos se representan como incrustaciones, que son vectores producidos por un modelo de aprendizaje automático; la similitud entre ítems corresponde a la distancia entre las incrustaciones. Esta publicación generalmente hablará de vectores y distancias, aunque en general HNSW puede manejar cualquier tipo de elementos con cierta similitud.
Los mundos pequeños fueron famosos por el experimento de mundos pequeños de Stanley Milgram. (1).
Los participantes recibieron una carta que contenía la dirección y otros detalles básicos de un individuo objetivo elegido al azar, junto con las instrucciones del experimento. En el improbable caso de que conocieran personalmente al objetivo, se les ordenó que les enviaran la carta; de lo contrario, se les decía que pensaran en alguien que conocieran y que tuviera más probabilidades de conocer al objetivo y que les enviaran la carta.
La sorprendente conclusión fue que las cartas normalmente sólo se enviaban unas seis veces antes de llegar al objetivo, lo que demuestra la famosa idea de “seis grados de separación”: dos personas cualesquiera generalmente pueden estar conectadas por una pequeña cadena de amigos.
En el campo matemático de la teoría de grafos, un grafico es un conjunto de puntos, algunos de los cuales están conectados. Podemos pensar en una red social como un gráfico, con las personas como puntos y las amistades como conexiones. El experimento del mundo pequeño encontró que la mayoría de los pares de puntos en este gráfico están conectados por caminos cortos que tienen una pequeña cantidad de pasos. (Esto se describe técnicamente como que el gráfico tiene una baja diámetro.)
Tener caminos cortos no es tan sorprendente en sí mismo: la mayoría de los gráficos tienen esta propiedad, incluidos los gráficos creados simplemente conectando pares aleatorios de puntos. Pero las redes sociales no se conectan al azar, son altamente local: los amigos tienden a vivir cerca uno del otro, y si conoces a dos personas, es muy probable que ellas también se conozcan. (Esto se describe técnicamente como que el gráfico tiene un alto coeficiente de agrupamiento.) Lo sorprendente del experimento del mundo pequeño es que dos puntos distantes sólo están separados por un corto camino, a pesar de que las conexiones suelen ser de corto alcance.
En casos como estos, cuando un grafo tiene muchas conexiones locales, pero también tiene caminos cortos, decimos que el grafo es un mundo pequeño.
Otro buen ejemplo de un mundo pequeño es la red global de aeropuertos. Los aeropuertos de la misma región están muy conectados entre sí, pero es posible realizar un viaje largo en sólo unas pocas paradas utilizando los principales aeropuertos centrales. Por ejemplo, un viaje de Manchester, Reino Unido a Osaka, Japón, normalmente comienza con un vuelo local de Manchester a Londres, luego un vuelo de larga distancia de Londres a Tokio y, finalmente, otro vuelo local de Tokio a Osaka. Los centros de largo alcance son una forma común de lograr la propiedad del mundo pequeño.
Un último ejemplo interesante de gráficos con la propiedad del mundo pequeño son las redes neuronales biológicas como el cerebro humano.
En gráficos mundiales pequeños, podemos alcanzar rápidamente un objetivo en unos pocos pasos. Esto sugiere una idea prometedora para la búsqueda del vecino más cercano: tal vez si creamos conexiones entre nuestros vectores de tal manera que formen un pequeño gráfico mundial, podamos encontrar rápidamente los vectores cerca de un objetivo comenzando desde un vector de “punto de entrada” arbitrario. y luego navegar a través del gráfico hacia el objetivo.
Esta posibilidad fue explorada por Kleinberg (2). Observó que la existencia de caminos cortos no era lo único interesante del experimento de Miller: también era sorprendente que las personas pudieran encontrar estos caminos cortos, sin utilizar ningún conocimiento global sobre el gráfico. Más bien, la gente seguía un simple algoritmo codicioso. En cada paso, examinaron cada una de sus conexiones inmediatas y las enviaron a la que pensaban que estaba más cerca del objetivo. Podemos usar un algoritmo similar para buscar un gráfico que conecte vectores.
Kleinberg quería saber si este codicioso algoritmo siempre encontraría un camino corto. Realizó simulaciones simples de mundos pequeños en los que todos los puntos estaban conectados a sus vecinos inmediatos, con conexiones adicionales más largas creadas entre puntos aleatorios. Descubrió que el algoritmo codicioso sólo encontraría un camino corto en condiciones específicas, dependiendo de la longitud de las conexiones de largo alcance.
Si las conexiones de largo alcance fueran demasiado largas (como era el caso cuando conectaban pares de puntos en ubicaciones completamente aleatorias), el algoritmo codicioso podría seguir una conexión de largo alcance para alcanzar rápidamente el área aproximada del objetivo, pero después de eso, el Las conexiones de largo alcance no servían de nada y el camino tenía que pasar por las conexiones locales para acercarse. Por otro lado, si las conexiones de largo alcance fueran demasiado cortas, simplemente se necesitarían demasiados pasos para llegar al área del objetivo.
Sin embargo, si las longitudes de las conexiones de largo alcance fueran las correctas (para ser precisos, si estuvieran distribuidas uniformemente, de modo que todas las longitudes fueran igualmente probables), el algoritmo codicioso normalmente alcanzaría la vecindad del objetivo en un tiempo especialmente pequeño. número de pasos (para ser más específicos, un número proporcional a registro(n)dónde norte es el número de puntos en el gráfico).
En casos como este, donde el algoritmo codicioso puede encontrar el objetivo en una pequeña cantidad de pasos, decimos que el mundo pequeño es un navegable mundo pequeño (Nueva Gales del Sur).
Un NSW parece un índice ideal para nuestros vectores, pero para vectores en un espacio complejo y de alta dimensión, no está claro cómo construir uno. Afortunadamente, Malkov et al. (3) descubrió un método: insertamos un vector elegido aleatoriamente a la vez en el gráfico y lo conectamos a un número pequeño metro de vecinos más cercanos que ya estaban insertados.
Este método es notablemente simple y no requiere una comprensión global de cómo se distribuyen los vectores en el espacio. También es muy eficiente, ya que podemos usar el gráfico creado hasta ahora para realizar la búsqueda del vecino más cercano para insertar cada vector.
Los experimentos confirmaron que este método produce un NSW. Debido a que los vectores insertados desde el principio se eligen al azar, tienden a estar bastante alejados. Por tanto, forman las conexiones de largo alcance necesarias para un mundo pequeño. No es tan obvio por qué el mundo pequeño es navegable, pero a medida que insertamos más vectores, las conexiones se acortarán gradualmente, por lo que es plausible que la distribución de las longitudes de las conexiones sea bastante uniforme, según sea necesario.
Los mundos pequeños navegables pueden funcionar bien para la búsqueda aproximada de vecinos más cercanos, pero un análisis más detallado reveló áreas de mejora, lo que llevó a Markov et al. (4) para proponer HNSW.
Un camino típico a través de una Nueva Gales del Sur desde el punto de entrada hacia el objetivo pasó por dos fases: una fase de “alejar”, en la que las longitudes de las conexiones aumentan de cortas a largas, y una fase de “acercarse”, en la que la longitud de las conexiones aumenta de corta a larga. sucede lo contrario.
La primera mejora simple es utilizar un concentrador de largo alcance (como el primer vector insertado) como punto de entrada. De esta manera, podemos saltarnos la fase de alejamiento y pasar directamente a la fase de acercamiento.
En segundo lugar, aunque los caminos de búsqueda fueron cortos (con un número de pasos proporcional a registro(n)), todo el procedimiento de búsqueda no fue tan rápido. En cada vector a lo largo del camino, el algoritmo codicioso debe examinar cada uno de los vectores conectados, calculando su distancia al objetivo para elegir el más cercano. Si bien la mayoría de los vectores conectados localmente tenían sólo unas pocas conexiones, la mayoría de los centros de largo alcance tenían muchas conexiones (nuevamente, un número proporcional a registro(n)); Esto tiene sentido ya que estos vectores generalmente se insertaban al principio del proceso de construcción y tenían muchas oportunidades para conectarse con otros vectores. Como resultado, el número total de cálculos durante una búsqueda fue bastante grande (proporcional a log(n)²).
Para mejorar esto, debemos limitar la cantidad de conexiones verificadas en cada concentrador. Esto lleva a la idea principal de HNSW: distinguir explícitamente entre conexiones de corto y largo alcance. En la etapa inicial de la búsqueda, consideraremos únicamente las conexiones de largo alcance entre centros. Una vez que la búsqueda codiciosa ha encontrado un centro cerca del objetivo, pasamos a utilizar conexiones de corto alcance.
Como el número de hubs es relativamente pequeño, deberían tener pocas conexiones para comprobar. También podemos imponer explícitamente un número máximo de conexiones de largo y corto alcance de cada vector cuando construimos el índice. Esto da como resultado un tiempo de búsqueda rápido (proporcional a registro(n)).
La idea de separar conexiones cortas y largas se puede generalizar para incluir varios niveles intermedios de longitudes de conexión. Podemos visualizar esto como un jerarquía de capas de vectores conectados, y cada capa utiliza solo una fracción de los vectores de la capa inferior.
