Implementación de artículos académicos: Lecciones aprendidas de Elasticsearch y Lucene

Conéctate fácilmente con las principales plataformas de inteligencia artificial y machine learning. Inicia una prueba gratuita en el cloud para explorar las capacidades de IA generativa de Elastic o pruébalo en tu máquina ahora mismo.

Esta publicación comparte estrategias para implementar trabajos académicos en una aplicación de software. Se basa en ejemplos de Elasticsearch y Lucene con la esperanza de ayudar a otros ingenieros a aprender de nuestras experiencias. Puedes leer estas estrategias y pensar "¡pero esto es solo desarrollo de software!" Y eso sería, efectivamente: como ingenieros ya tenemos las prácticas y herramientas adecuadas, solo necesitan adaptar a un nuevo reto.

Fondo

Mientras desarrollamos Elasticsearch, ocasionalmente nos encontramos con un problema importante sin un enfoque sencillo o establecido para solucionarlo. Es natural preguntar: "hmm, ¿existe algún artículo académico que aborde esto?" Otras veces, el trabajo académico es una fuente de inspiración. Nos encontramos con un artículo que propone un nuevo algoritmo o estructura de datos y pensamos "¡esto sería muy útil!" Aquí tienes solo algunos ejemplos de cómo Elasticsearch y Apache Lucene incorporan el trabajo académico:

• HyperLogLog++ para agregaciones de cardinalidad
• Algoritmo C3 para la selección adaptativa de réplicas
• Grafos jerárquicos navegables de mundos pequeños (HNSW) para búsqueda vectorial más cercana en Lucene
• Estadística MIC para mejorar la clasificación del aprendizaje automático
• WAND de bloqueo máximo para una recuperación más rápida de top-hits en Lucene
• ... y muchos más

Los artículos académicos son un recurso invaluable para los ingenieros que desarrollan sistemas intensivos en datos. Pero implementarlas puede ser intimidante y propenso a errores: las descripciones de algoritmos suelen ser complejas, omitiendo detalles prácticos importantes. Y las pruebas son un verdadero desafío: por ejemplo, ¿cómo podemos probar a fondo un algoritmo de aprendizaje automático cuya salida depende estrechamente del conjunto de datos?

Evalúa el trabajo como si fuera una dependencia de software

Agregar una nueva dependencia de software requiere una evaluación cuidadosa: si el otro paquete es incorrecto, lento o inseguro, nuestro proyecto también podría serlo. Antes de incorporar una dependencia, los desarrolladores se cercioran de evaluar su calidad.

Lo mismo ocurre con los trabajos académicos que estás considerando implementar. Puede parecer que, porque un algoritmo se publicó en un artículo, debe ser correcto y funcionar bien. Pero aunque pasó un proceso de revisión, un artículo académico puede tener problemas. Quizá la demostración de corrección se basa en suposiciones que no son realistas. O quizá la sección de "experimentos" muestra un rendimiento mucho mejor que la línea base, pero esto solo se cumple en un conjunto de datos específico. Aunque el trabajo sea de gran calidad, su enfoque puede no encajar bien con tu proyecto.

Al pensar si tomar una "dependencia" de un artículo académico, es útil plantear las mismas preguntas que haríamos con un paquete de software:

• ¿La biblioteca está ampliamente empleada y "probada en batalla"? → ¿Otros paquetes implementaron este artículo y les funcionó bien?
• ¿Están disponibles los benchmarks de rendimiento? ¿Te parecen precisos y justos? → ¿El artículo incluye experimentos realistas? ¿Están bien diseñadas?
• ¿Es suficiente una mejora de rendimiento como para justificar la complejidad? → ¿El artículo se compara con un enfoque de línea base fuerte? ¿Cuánto supera esta línea base?
• ¿Se integrará bien este enfoque con nuestro sistema? → ¿Encajan las suposiciones y compensaciones del algoritmo en nuestro caso de uso?

De alguna manera, cuando un paquete de software publica una comparación de rendimiento con sus competidores, ¡el paquete siempre sale más rápido! Si un tercero diseñó los benchmarks, podrían estar más equilibrados. El mismo fenómeno se aplica a los artículos académicos. Si un algoritmo funciona bien no solo en el artículo original, sino que también aparece en otros como una línea base estable, entonces es muy probable que sea estable.

Sé creativo con las pruebas

Los algoritmos de artículos académicos suelen tener un comportamiento más sofisticado que los tipos de algoritmos que habitualmente nos encontramos. Quizá sea un algoritmo de aproximación que sacrifica la precisión por una mejor velocidad. O quizá sea un método de aprendizaje automático que absorbe un gran conjunto de datos y produce resultados (a veces inesperados). ¿Cómo podemos escribir pruebas para estos algoritmos si no podemos caracterizar su comportamiento de forma sencilla?

Enfoque en invariantes

Al diseñar pruebas unitarias, es común pensar en términos de ejemplos: si damos al algoritmo esta entrada de ejemplo, debería tener esa salida. Desafortunadamente, para la mayoría de los algoritmos matemáticos, las pruebas basadas en ejemplos no cubren suficientemente su comportamiento.

Consideremos el algoritmo C3, que Elasticsearch emplea para determinar qué nodo debe gestionar una solicitud de búsqueda. Clasifica cada nodo usando una fórmula matizada que incorpora el servicio y los tiempos de respuesta previos del nodo, así como el tamaño de su cola. Probar un par de ejemplos realmente no verifica que entendiéramos bien la fórmula. Ayuda dar un paso atrás y pensar en probar invariantes: si aumenta el tiempo de servicio, ¿disminuye el rango del nodo? Si el tamaño de la cola es 0, ¿el rango se determina por el tiempo de respuesta, como afirma el artículo?

Centrar en los invariantes puede ayudar en varios casos comunes:

• ¿Se supone que el método es agnóstico respecto al orden? Si es así, pasar los datos de entrada en un orden diferente debería dar el mismo resultado.
• ¿Algún paso del algoritmo produce probabilidades de clase? Si es así, estas probabilidades deberían sumar 1.
• ¿Es la función simétrica alrededor del origen? Si es así, invertir el signo de la entrada debería simplemente invertir el signo de la salida.

Cuando implementamos C3 por primera vez, tuvimos un error en la fórmula donde accidentalmente usamos el inverso del tiempo de respuesta en lugar del tiempo de respuesta. ¡Esto significaba que los nodos más lentos podían estar más bien clasificados! Al solucionar el problema, nos cercioramos de agregar comprobaciones invariantes para evitar futuros errores.

Comparar con una implementación de referencia

Junto al artículo, los autores esperan publicar una implementación del algoritmo. (Esto es especialmente probable si el artículo contiene experimentos, ya que muchas revistas requieren que los autores envíen el código para reproducir los resultados.) Puedes probar tu enfoque con esta implementación de referencia para cerciorarte de que no te perdiste detalles importantes del algoritmo.

Mientras desarrollábamos la implementación HNSW de Lucene para la búsqueda de vecinos más cercanos, probamos contra una biblioteca de referencia de los autores del artículo. Ejecutamos tanto Lucene como la biblioteca con el mismo conjunto de datos, comparando la precisión de sus resultados y el número de cálculos que realizaron. Cuando estos números coinciden de cerca, sabemos que Lucene implementa fielmente el algoritmo.

Al incorporar un algoritmo en un sistema, a menudo necesitas hacer modificaciones o extensiones, como escalarlo a múltiples núcleos o agregar heurísticas para mejorar el rendimiento. Lo mejor es implementar primero una versión "vanilla", probarla con la referencia y luego hacer cambios incrementales. Así puedes estar seguro de que capturaste todas las piezas clave antes de hacer personalizaciones.

Duelo contra un algoritmo existente

La última sección plantea otra idea para un invariante de prueba: comparar la salida del algoritmo con la salida de un algoritmo más simple y mejor entendido. Como ejemplo, consideremos el algoritmo WAND de bloques máximas en Lucene, que acelera la recuperación de documentos saltar documentos que no pueden aparecer en los resultados principales. Es difícil describir exactamente cómo debería comportar la WAND con bloque máximo en todos los casos, pero sí sabemos que aplicarla no debería cambiar los mejores resultados. Así que nuestras pruebas pueden generar varias consultas de búsqueda aleatoria, luego ejecutarlas tanto con como sin la optimización WAND y comprobar que sus resultados siempre coinciden.

Un aspecto importante de estas pruebas es que generan entradas aleatorias sobre las que realizar la comparación. Esto puede ayudar a resolver casos que no consideraste y a sacar a la luz problemas inesperados. Por ejemplo, la prueba de comparación aleatoria de Lucene para el puntaje BM25F ayudó a detectar errores en casos extremos sutiles. La idea de alimentar a un algoritmo con entradas aleatorias está estrechamente relacionada con el concepto de fuzzing, una técnica común de pruebas en seguridad informática.

Elasticsearch y Lucene emplean frecuentemente este enfoque de prueba. Si ves una prueba que menciona un "duelo" entre dos algoritmos (TestDuelingAnalyzers, testDuelTermsQuery...), entonces sabes que esta estrategia está en acción.

Emplea la terminología del artículo

Cuando otro desarrollador trabaje con tu código, necesitará consultar el documento para seguir sus detalles. El comentario sobre la implementación de HyperLogLog++ de Elasticsearch lo dice bien: "Intentar entender qué hace esta clase sin leer el artículo se considera aventurero." Este comentario sobre el método también da un buen ejemplo. Incluye un enlace al artículo académico y destaca qué modificaciones se hicieron al algoritmo tal y como fue descrito originalmente.

Como los desarrolladores basan su comprensión del código en el papel, es útil usar exactamente la misma terminología. Dado que la notación matemática es concisa, esto puede dar lugar a nombres que normalmente no se considerarían de "buen estilo", pero que son muy claros en el contexto del artículo. Las fórmulas de artículos académicos son una de las pocas ocasiones en las que te encontrarás con nombres de variables crípticos en Elasticsearch, como rS y muBarSInverse.

La forma recomendada por el autor de leer un artículo: con un café grande.

Puedes enviar un email al autor

Al trabajar en un trabajo difícil, puedes pasar horas dándole vueltas a una fórmula, sin saber si estás malinterpretando o si simplemente hay un error tipográfico. Si fuera un proyecto de código abierto, podrías hacer una pregunta en GitHub o StackOverflow. Pero, ¿a dónde puedes acudir para un artículo académico? Los autores parecen ocupados y pueden molestar por tus correos.

Al contrario, a muchos académicos les encanta saber que sus ideas se están poniendo en práctica y están encantados de responder preguntas por email. Si trabajas en un producto que ellos conocen, ¡incluso pueden poner la solicitud en su sitio web!

También hay una tendencia creciente de académicos a debatir artículos en público, empleando muchas de las mismas herramientas del desarrollo de software. Si un artículo incluye un paquete de software adjunto, puede que encuentres respuestas a preguntas comunes en Github. Las comunidades de Stack Exchange como "Theoretical Computer Science" y "Cross Validated" también contienen discusiones detalladas sobre artículos populares. Algunas conferencias empezaron a publicar todas las reseñas de artículos en línea. Estas revisiones contienen conversaciones de ida y vuelta con los autores que pueden aportar ideas útiles sobre el enfoque.

Continuará

Esta publicación se centra en los fundamentos para elegir un trabajo académico y

Implementarlo correctamente, pero no cubre todos los aspectos del despliegue real del algoritmo. Por ejemplo, si el algoritmo es solo un componente en un sistema complejo, ¿cómo cercioramos que los cambios en el componente conduzcan a mejoras de extremo a extremo? ¿Y qué pasa si integrar el algoritmo requiere modificaciones o extensiones sustanciales que el artículo original no cubre? Son temas importantes sobre los que esperamos compartir más en futuras publicaciones.