Mise en œuvre de documents universitaires : Leçons tirées d'Elasticsearch et Lucene

Connectez-vous facilement aux principales plateformes d’IA et de machine learning. Démarrez un essai gratuit sur le cloud pour explorer les fonctionnalités d’IA générative d’Elastic, ou testez-les dès maintenant sur votre machine locale.

Cet article présente des stratégies pour intégrer des documents académiques dans une application logicielle. Il s'appuie sur des exemples tirés d'Elasticsearch et de Lucene dans l'espoir d'aider d'autres ingénieurs à tirer parti de nos expériences. En lisant ces stratégies, vous vous dites peut-être "mais ce n'est que du développement logiciel !". Et ce serait en effet vrai : en tant qu'ingénieurs, nous disposons déjà des bonnes pratiques et des bons outils, il suffit de les adapter à un nouveau défi.

Arrière-plan

Lors du développement d'Elasticsearch, nous rencontrons parfois un problème important pour lequel il n'existe pas d'approche simple ou établie. Il est naturel de se demander s'il existe un document universitaire traitant de cette question. D'autres fois, le travail universitaire est une source d'inspiration. Nous tombons sur un article proposant un nouvel algorithme ou une nouvelle structure de données et nous nous disons "ce serait tellement utile !". Voici quelques exemples de la façon dont Elasticsearch et Apache Lucene intègrent des travaux universitaires :

• HyperLogLog++ pour les agrégations de cardinalité
• Algorithme C3 pour la sélection adaptative des répliques
• Graphes hiérarchiques navigables du petit monde (HNSW) pour la recherche du vecteur le plus proche dans Lucene
• Statistique MIC pour améliorer la classification par apprentissage automatique
• Block-max WAND pour une recherche plus rapide des meilleurs résultats dans Lucene
• ... et bien d' autres encore

Les articles universitaires constituent une ressource inestimable pour les ingénieurs qui développent des systèmes à forte intensité de données. Mais leur mise en œuvre peut être intimidante et sujette à des erreurs - les descriptions d'algorithmes sont souvent complexes et des détails pratiques importants sont omis. Les tests constituent un véritable défi : par exemple, comment tester de manière approfondie un algorithme d'apprentissage automatique dont le résultat dépend étroitement de l'ensemble de données ?

Évaluez le document comme vous le feriez pour une dépendance logicielle.

L'ajout d'une nouvelle dépendance logicielle nécessite une évaluation minutieuse : si l'autre paquet est incorrect, lent ou peu sûr, notre projet pourrait l'être aussi. Avant d'intégrer une dépendance, les développeurs veillent à en évaluer la qualité.

Il en va de même pour les travaux universitaires que vous envisagez de mettre en œuvre. On peut penser que parce qu'un algorithme a été publié dans un article, il doit être correct et performant. Mais même s'il a été soumis à un processus d'examen, un document universitaire peut présenter des problèmes. Peut-être que la preuve d'exactitude repose sur des hypothèses qui ne sont pas réalistes. Il se peut aussi que la section "expériences" montre des performances nettement supérieures à celles de la ligne de base, mais que cela ne soit valable que pour un ensemble de données spécifique. Même si le document est de grande qualité, son approche peut ne pas convenir à votre projet.

Lorsque l'on se demande si l'on doit accepter une "dépendance" à l'égard d'un document universitaire, il est utile de se poser les mêmes questions que celles que l'on se poserait à l'égard d'un logiciel :

• La bibliothèque est-elle largement utilisée et "testée au combat" ? → D'autres paquets ont-ils mis en œuvre ce document, et cela a-t-il bien fonctionné pour eux ?
• Existe-t-il des critères de performance ? Ces données vous semblent-elles exactes et équitables ? → L'article comporte-t-il des expériences réalistes ? Sont-ils bien conçus ?
• L'amélioration des performances est-elle suffisamment importante pour justifier la complexité ? → Le document est-il comparable à une approche de référence solide ? Dans quelle mesure la performance est-elle supérieure à celle de la base de référence ?
• L'approche s'intégrera-t-elle bien à notre système ? → Les hypothèses et les compromis de l'algorithme sont-ils adaptés à notre cas d'utilisation ?

D'une manière ou d'une autre, lorsqu'un logiciel publie une comparaison de ses performances avec celles de ses concurrents, c'est toujours le logiciel qui est le plus rapide ! Si une tierce partie a conçu les critères de référence, ils peuvent être plus équilibrés. Le même phénomène s'applique aux travaux universitaires. Si un algorithme donne de bons résultats non seulement dans l'article original, mais apparaît également dans d'autres articles comme une référence solide, il est très probable qu'il soit solide.

Soyez créatifs avec les tests

Les algorithmes tirés d'articles universitaires ont souvent un comportement plus sophistiqué que les types d'algorithmes que nous rencontrons couramment. Il s'agit peut-être d'un algorithme d'approximation qui troque la précision contre une plus grande rapidité. Il peut aussi s'agir d'une méthode d'apprentissage automatique qui prend en compte un vaste ensemble de données et produit des résultats (parfois inattendus). Comment pouvons-nous écrire des tests pour ces algorithmes si nous ne pouvons pas caractériser leur comportement de manière simple ?

Focus sur les invariants

Lors de la conception des tests unitaires, il est courant de penser en termes d'exemples : si nous donnons à l'algorithme cet exemple d'entrée, il devrait produire cette sortie. Malheureusement, pour la plupart des algorithmes mathématiques, les tests basés sur des exemples ne couvrent pas suffisamment leur comportement.

Considérons l'algorithme C3, qu'Elasticsearch utilise pour déterminer quel nœud doit traiter une requête de recherche. Il classe chaque nœud à l'aide d'une formule nuancée qui incorpore le service précédent et les temps de réponse du nœud, ainsi que la taille de sa file d'attente. Tester quelques exemples ne permet pas vraiment de vérifier que nous avons compris la formule correctement. Il est utile de prendre du recul et de réfléchir au test des invariants : si le temps de service augmente, le rang du nœud diminue-t-il ? Si la taille de la file d'attente est de 0, le rang est-il déterminé par le temps de réponse, comme le prétend le document ?

Se concentrer sur les invariants peut s'avérer utile dans un certain nombre de cas courants :

• La méthode est-elle censée ne pas tenir compte de l'ordre ? Si c'est le cas, le fait de passer les données d'entrée dans un ordre différent devrait produire le même résultat.
• Certaines étapes de l'algorithme produisent-elles des probabilités de classe ? Si c'est le cas, la somme de ces probabilités doit être égale à 1.
• La fonction est-elle symétrique par rapport à l'origine ? Si c'est le cas, l'inversion du signe de l'entrée devrait simplement inverser le signe de la sortie.

Lorsque nous avons mis en œuvre C3 pour la première fois, nous avons eu un problème dans la formule où nous avons accidentellement utilisé l'inverse du temps de réponse à la place du temps de réponse. Cela signifie que les nœuds les plus lents peuvent être mieux classés ! Lors de la correction du problème, nous avons veillé à ajouter des vérifications invariantes afin d'éviter de nouvelles erreurs.

Comparer avec une implémentation de référence

Parallèlement à l'article, les auteurs ont publié une mise en œuvre de l'algorithme. (Cela est particulièrement probable si l'article contient des expériences, car de nombreuses revues exigent que les auteurs publient le code permettant de reproduire les résultats). Vous pouvez tester votre approche par rapport à cette implémentation de référence pour vous assurer que vous n'avez pas oublié des détails importants de l'algorithme.

Lors du développement de l'implémentation HNSW de Lucene pour la recherche du plus proche voisin, nous avons testé une bibliothèque de référence créée par les auteurs de l'article. Nous avons testé Lucene et la bibliothèque sur le même ensemble de données, en comparant la précision de leurs résultats et le nombre de calculs qu'ils ont effectués. Lorsque ces nombres correspondent étroitement, nous savons que Lucene met fidèlement en œuvre l'algorithme.

Lors de l'intégration d'un algorithme dans un système, il est souvent nécessaire de procéder à des modifications ou à des extensions, comme l'adaptation à plusieurs cœurs ou l'ajout d'heuristiques pour améliorer les performances. Il est préférable de commencer par mettre en œuvre une version "vanilla", de la tester par rapport à la référence, puis d'y apporter des modifications incrémentielles. Vous pouvez ainsi être sûr d'avoir capturé tous les éléments clés avant de procéder à des personnalisations.

Duel contre un algorithme existant

La dernière section propose une autre idée d'invariant de test : comparer le résultat de l'algorithme à celui d'un algorithme plus simple et mieux compris. Prenons l'exemple de l'algorithme WAND block-max de Lucene, qui accélère la recherche de documents en ignorant ceux qui ne peuvent pas figurer dans les premiers résultats. Il est difficile de décrire exactement le comportement de l'outil WAND block-max dans tous les cas, mais nous savons que son application ne devrait pas modifier les premiers résultats ! Nos tests peuvent donc générer plusieurs requêtes de recherche aléatoires, puis les exécuter avec et sans l'optimisation WAND et vérifier que les résultats correspondent toujours.

Un aspect important de ces tests est qu'ils génèrent des entrées aléatoires sur lesquelles la comparaison est effectuée. Cela peut permettre de mettre en œuvre des cas auxquels vous n'auriez pas pensé et de mettre en évidence des problèmes inattendus. Par exemple, le test de comparaison aléatoire de Lucene pour la notation BM25F a permis de détecter des bogues dans des cas subtils. L'idée d'alimenter un algorithme avec des entrées aléatoires est étroitement liée au concept de fuzzing, une technique de test courante dans le domaine de la sécurité informatique.

Elasticsearch et Lucene utilisent fréquemment cette approche de test. Si vous voyez un test qui mentionne un duel "" entre deux algorithmes (TestDuelingAnalyzers, testDuelTermsQuery...), vous savez que cette stratégie est en action.

Utiliser la terminologie du document

Lorsqu'un autre développeur travaillera avec votre code, il devra consulter le document pour en suivre les détails. Le commentaire sur l'implémentation HyperLogLog++ d'Elasticsearch le dit bien : "Essayer de comprendre ce que fait cette classe sans avoir lu le document est considéré comme aventureux." Ce commentaire de méthode constitue également un bon exemple. Elle comprend un lien vers l'article universitaire et met en évidence les modifications apportées à l'algorithme tel qu'il a été décrit à l'origine.

Étant donné que les développeurs fonderont leur compréhension du code sur le document, il est utile d'utiliser exactement la même terminologie. La notation mathématique étant laconique, il peut en résulter des noms qui ne seraient pas habituellement considérés comme "de bon style", mais qui sont très clairs dans le contexte de l'article. Les formules tirées d'articles universitaires sont l'une des rares occasions où vous rencontrerez des noms de variables cryptiques dans Elasticsearch, comme rS et muBarSInverse.

La façon recommandée par l'auteur pour lire un article : avec un grand café.

Vous pouvez envoyer un courriel à l'auteur

Lorsque vous travaillez sur un document difficile, vous pouvez passer des heures à réfléchir à une formule, sans savoir si vous avez mal compris ou s'il s'agit simplement d'une erreur de frappe. S'il s'agissait d'un projet open source, vous pourriez poser une question sur GitHub ou StackOverflow. Mais à qui s'adresser pour obtenir un travail universitaire ? Les auteurs semblent occupés et pourraient être ennuyés par vos courriels.

Au contraire, de nombreux universitaires aiment entendre que leurs idées sont mises en pratique et sont heureux de répondre à des questions par courrier électronique. Si vous travaillez sur un produit qu'ils connaissent bien, il se peut même qu'ils listent l'application sur leur site web !

Les universitaires ont également de plus en plus tendance à discuter de leurs articles en public, en utilisant les mêmes outils que ceux utilisés pour le développement de logiciels. Si un article est accompagné d'un logiciel, vous pouvez trouver des réponses aux questions les plus courantes sur Github. Les communautés Stack Exchange telles que "Theoretical Computer Science" et "Cross Validated" contiennent également des discussions détaillées sur les articles les plus populaires. Certaines conférences ont commencé à publier en ligne tous les comptes rendus d'articles. Ces revues contiennent des discussions avec les auteurs qui peuvent apporter des informations utiles sur l'approche.

A suivre

Cet article se concentre sur les bases du choix d'un document académique et sur la manière de le choisir.

L'algorithme doit être mis en œuvre correctement, mais il ne couvre pas tous les aspects du déploiement réel de l'algorithme. Par exemple, si l'algorithme n'est qu'un élément d'un système complexe, comment s'assurer que les modifications apportées à cet élément conduisent à des améliorations de bout en bout ? Et que se passe-t-il si l'intégration de l'algorithme nécessite des modifications ou des extensions substantielles que l'article original ne couvre pas ? Il s'agit là de sujets importants sur lesquels nous espérons revenir dans de prochains articles.