Des algorithmes de tri qui pourraient révolutionner les fondements de l'informatique sont découverts,

Par les chercheurs de Deepmind et Google

Des algorithmes de tri qui pourraient révolutionner les fondements de l'informatique sont découverts par les chercheurs de Deepmind et Google, les performances des algorithmes découverts ont été comparées avec des algorithmes de tri par insertion, de tri rapide ou de tri introspectif. Les chercheurs montrent comment l’intelligence artificielle peut aller au-delà de l’état de l’art actuel en découvrant des routines inconnues jusqu’à présent. Pour ce faire, ils ont formulé la tâche de trouver une meilleure routine de tri comme un jeu à un seul joueur. Ils ont ensuite entraîné un nouvel agent d’apprentissage par renforcement profond (DRL), AlphaDev, à jouer à ce jeu.

Les chercheurs ont formulé la tâche de trouver un meilleur algorithme de tri comme un jeu à un seul joueur, et ont entraîné un nouvel agent DRL, AlphaDev, à jouer à ce jeu. AlphaDev a découvert à partir de zéro de petits algorithmes de tri qui ont surpassé les références humaines connues. Ces algorithmes ont été intégrés dans la bibliothèque standard C++ LLVM 3. Les auteurs présentent également des résultats dans des domaines supplémentaires, montrant la généralité de l’approche.

Des algorithmes fondamentaux tels que le tri ou le hachage sont utilisés des milliards de fois chaque jour. La demande de calcul augmentant, il est devenu essentiel que ces algorithmes soient aussi performants que possible. Bien que des progrès remarquables aient été réalisés dans le passé, l'amélioration de l'efficacité de ces routines s'est avérée difficile, tant pour les scientifiques que pour les approches informatiques. Les chercheurs montrent comment l'intelligence artificielle peut aller au-delà de l'état actuel de la technique en découvrant des routines jusqu'alors inconnues.


Pour ce faire, ils ont formulé la tâche consistant à trouver une meilleure routine de tri sous la forme d'un jeu à un seul joueur. Ils ont ensuite entraîné un nouvel agent d'apprentissage par renforcement profond, AlphaDev, à jouer ce jeu. AlphaDev a découvert de petits algorithmes de tri à partir de zéro qui ont surpassé les références humaines précédemment connues.

Ces algorithmes ont été intégrés dans la bibliothèque de tri standard C++ de LLVM3. Cette modification de cette partie de la bibliothèque de tri représente le remplacement d'un composant par un algorithme qui a été découvert automatiquement à l'aide de l'apprentissage par renforcement.

AlphaDev utilise une architecture d’apprentissage par renforcement profond basée sur l’acteur-critique, qui apprend une politique (acteur) et une fonction de valeur (critique) à partir d’expériences générées par interaction avec l’environnement. L’environnement est constitué d’un compilateur LLVM et d’un processeur x86-64. L’agent reçoit en entrée une séquence d’entiers à trier et produit en sortie un programme C++ qui implémente un algorithme de tri.

Le programme est compilé et exécuté sur le processeur, et le temps d’exécution est mesuré comme la latence du programme. La récompense est une fonction inversement proportionnelle à la latence, qui encourage l’agent à trouver des programmes plus rapides. L’agent utilise également un mécanisme d’exploration basé sur l’entropie pour encourager la diversité des programmes générés.

Les auteurs ont évalué AlphaDev sur plusieurs tailles de séquences à trier, allant de 4 à 16 éléments. Ils ont comparé les performances des algorithmes découverts par AlphaDev avec celles des algorithmes humains connus, tels que le tri par insertion, le tri rapide ou le tri introspectif. Ils ont constaté qu’AlphaDev était capable de trouver des algorithmes plus rapides que les références humaines pour toutes les tailles de séquences testées.

Par exemple, pour une séquence de 16 éléments, AlphaDev a trouvé un algorithme qui était 11% plus rapide que le tri introspectif, qui est considéré comme l’un des algorithmes de tri les plus efficaces en pratique. Les auteurs ont également testé AlphaDev sur d’autres domaines que le tri, tels que le hachage ou la recherche binaire. Ils ont montré qu’AlphaDev pouvait également trouver des algorithmes plus performants que les références humaines pour ces domaines.

Les chercheurs démontrent que l’intelligence artificielle peut découvrir des algorithmes fondamentaux qui surpassent les connaissances humaines actuelles. Ils soulignent que leur méthode est générale et peut être appliquée à d’autres domaines que le tri ou le hachage. Ils suggèrent également que leur approche pourrait être combinée avec des techniques de synthèse de programmes classiques ou basées sur l’apprentissage profond pour générer des programmes corrects et performants.

L'intuition et le savoir-faire humains ont joué un rôle crucial dans l'amélioration des algorithmes. Cependant, de nombreux algorithmes ont atteint un stade où les experts humains n'ont pas été en mesure de les optimiser davantage, ce qui a conduit à un goulot d'étranglement informatique de plus en plus important. Les travaux de la littérature classique sur la synthèse de programmes, qui s'étendent sur plusieurs décennies, visent à générer des programmes corrects et/ou à optimiser les programmes à l'aide d'indicateurs de latence.

Il s'agit notamment de techniques de recherche énumérative et de recherche stochastique ainsi que de la tendance plus récente consistant à utiliser l'apprentissage profond dans la synthèse de programmes pour générer des programmes corrects. En utilisant l'apprentissage par renforcement profond (DRL), nous pouvons aller plus loin en générant des algorithmes corrects et performants en optimisant la latence réelle mesurée au niveau des instructions du processeur, en recherchant et en considérant plus efficacement l'espace des programmes corrects et rapides par rapport aux travaux antérieurs.

Représentation des algorithmes sous forme d'instructions de l'unité centrale de bas niveau


a. Implémentation en C++ d'une fonction de tri variable 2 qui trie toute séquence d'entrée comportant jusqu'à deux éléments. b. L'implémentation en C++ en a est compilée dans cette représentation équivalente en assembleur de bas niveau.

Lors de la compilation d'algorithmes en code machine à partir d'un langage de haut niveau tel que le C++ (par exemple, la fonction de tri de la figure a ci-dessus), l'algorithme est d'abord compilé en langage assembleur (figure b). L'assembleur convertit ensuite le programme d'assemblage en code machine exécutable.

Dans ce travail, les chercheurs optimisent les algorithmes au niveau de l'assemblage. Dans un programme d'assemblage typique, les valeurs sont copiées de la mémoire vers les registres, manipulées entre les registres, puis réinscrites dans la mémoire. L'ensemble des instructions d'assemblage prises en charge dépend de l'architecture du processeur. Dans le cadre de ce travail, nous les chercheurs se concentrent sur un sous-ensemble d'instructions d'assemblage supportées par l'architecture de processeur x86 utilisant la syntaxe AT&T. Chaque instruction se présente sous la forme Opcode⟨OperandA, OperandB⟩.

Un exemple d'instruction est mov, qui se définit comme le déplacement d'une valeur de la source (A) vers la destination (B). D'autres définitions d'instructions telles que la comparaison (cmp), le déplacement conditionnel (cmovX) et le saut (jX) figurent dans le tableau de données étendu. Dans l'exemple de la figure b, %eax, %ecx, %edx, %edi correspondent à quatre emplacements de registre différents et (%rsi), (%rsi) correspondent à deux emplacements de mémoire différents. Le symbole $2 est un espace réservé pour une valeur constante, qui correspond à la longueur du vecteur dans cet exemple.

Les termes programme d'assemblage et algorithme d'assemblage sont utilisés de manière interchangeable dans ce travail. Ceci est dû au fait qu'AlphaDev construit un programme d'assemblage à partir de zéro, à partir d'un ensemble d'instructions initialement non ordonnées, chaque fois qu'il joue à AssemblyGame, en définissant un nouvel algorithme efficace.

Apprentissage par renforcement profond pour découvrir des algorithmes plus rapides


a, AssemblyGame est joué par AlphaDev, qui reçoit en entrée l'algorithme d'assemblage courant généré jusqu'à présent St et joue le jeu en sélectionnant une action à exécuter. Dans cet exemple, l'action est une instruction d'assemblage mov<Register0,Memory1>, qui est ajoutée à l'algorithme actuel. L'agent reçoit une récompense qui est fonction de la correction de l'algorithme, discutée en b, ainsi que de la latence de l'algorithme. Le jeu est remporté par le joueur qui découvre un algorithme correct et à faible latence. b) Les calculs de correction et de latence du programme sont utilisés pour calculer la récompense rt. Dans cet exemple, des séquences de test sont introduites dans l'algorithme ; par exemple, dans le cas du tri de trois éléments, les entrées de test comprennent toutes les séquences d'éléments non triés de longueur 3. Pour chaque séquence, la sortie de l'algorithme est comparée à la sortie attendue (dans le cas du tri, la sortie attendue est constituée par les éléments triés). Dans cet exemple, la sortie D′ ne correspond pas à la sortie attendue B′ et l'algorithme est donc incorrect.

L'optimisation des algorithmes au niveau des instructions du processeur est formulée comme un problème d'apprentissage par renforcement, dans lequel l'environnement est modélisé comme un jeu à un seul joueur que nous appelons AssemblyGame. Chaque état dans ce jeu est défini comme un vecteur St = ⟨Pt, Zt⟩ où Pt est une représentation de l'algorithme généré jusqu'à présent dans le jeu et Zt représente l'état de la mémoire et des registres après l'exécution de l'algorithme actuel sur un ensemble d'entrées prédéfinies. Comme le montre la figure a ci-dessus 2, à l'étape t, le joueur reçoit l'état actuel St et exécute une action at.

Cette action consiste à ajouter une instruction d'assemblage légale (par exemple, mov<A,B>) à l'algorithme actuel généré jusqu'à présent. Le joueur reçoit une récompense r qui comprend à la fois une mesure de l'exactitude de l'algorithme et du temps de latence. L'exactitude de l'algorithme (figure b ci-dessus) implique l'entrée d'un ensemble de N séquences de test dans l'algorithme actuel Pt pour générer N sorties. Ces résultats sont ensuite comparés aux résultats attendus et une récompense de correction rt est calculée.

Les récompenses pour la latence peuvent être générées soit en pénalisant l'agent pour avoir augmenté la longueur de l'algorithme (lorsque la longueur et la latence sont fortement corrélées), ce que nous appelons la récompense pour la longueur de l'algorithme, soit en mesurant la latence réelle de l'algorithme. Le jeu est exécuté pendant un nombre limité d'étapes, après quoi il est terminé. Gagner le jeu correspond à la génération d'un algorithme correct et à faible latence à l'aide d'instructions d'assemblage. Perdre le jeu correspond à la génération d'un algorithme incorrect ou d'un algorithme correct mais inefficace.

Nouveaux algorithmes de tri de variables


a. Diagramme de flux de l'algorithme de référence humain de tri de variable (VarSort4). Dans cet algorithme, une séquence de nombres non triés est introduite dans l'algorithme. Si la longueur de la séquence est de quatre, trois ou deux nombres, le réseau de tri correspondant (sort 4, sort 3 ou sort 2) est appelé pour trier la séquence résultante. Le résultat est ensuite renvoyé et produit par la fonction. b, L'algorithme VarSort découvert par AlphaDev. Cet algorithme reçoit également en entrée des séquences de longueur quatre, trois ou deux nombres. Dans ce cas, si la longueur est de deux, il appelle le réseau de tri sort 2 et renvoie le résultat. Si la longueur est de trois, il appelle le réseau sort 3 pour trier les trois premiers nombres et retourne. Si, en revanche, la longueur est supérieure à trois, il appelle le tri 3, suivi d'une routine de tri 4 simplifiée qui trie les nombres non triés restants. C'est cette partie de la routine qui permet de réduire considérablement le temps de latence.

L'algorithme VarSort4 découvert par AlphaDev est particulièrement intéressant. Le diagramme de flux de l'algorithme de référence humain et celui d'AlphaDev sont présentés respectivement dans les figurea et b ci-dessus. L'algorithme de référence humain détermine la longueur du vecteur d'entrée, puis appelle le réseau de tri correspondant pour trier les éléments. La solution AlphaDev a une approche complètement différente, comme le montre la figure b.

Si la longueur du vecteur d'entrée est strictement supérieure à 2, le tri 3 est immédiatement appelé, ce qui permet de trier les trois premiers éléments. Si le vecteur comporte plus de trois éléments, un algorithme de tri simplifié est appelé pour trier les éléments non triés restants dans le vecteur d'entrée. C'est cette partie simplifiée de la routine qui permet d'obtenir des gains significatifs en termes de longueur algorithmique et de temps de latence.

In fine, AlphaDev découvre de nouveaux algorithmes de tri de pointe à partir de zéro qui ont été incorporés dans la bibliothèque LLVM C++, utilisée par des millions de développeurs et d'applications dans le monde entier. AlphaDev et la recherche stochastique sont tous deux des algorithmes puissants. Une direction intéressante pour la recherche future est d'étudier la combinaison de ces algorithmes afin de réaliser les avantages complémentaires des deux approches.

Il est important de noter qu'AlphaDev peut, en théorie, se généraliser à des fonctions qui ne nécessitent pas une vérification exhaustive des cas de test. Par exemple, les fonctions de hachage ainsi que les fonctions de hachage cryptographique définissent la correction de la fonction par le nombre de collisions de hachage. Par conséquent, dans ce cas, AlphaDev peut optimiser pour minimiser les collisions ainsi que la latence.

AlphaDev peut également, en théorie, optimiser les composants logiques compliqués dans le corps de grandes fonctions impressionnantes. Il reste à espérer qu'AlphaDev pourra fournir des informations intéressantes et inspirer de nouvelles approches dans les communautés de l'intelligence artificielle et de la synthèse de programmes.

Source : Nature

Et vous ?

Les résultats de ces travaux de recherche sont-ils pertinents ?

Quelles sont les limites et les biais potentiels des données utilisées pour entraîner les algorithmes de cri ?

Comment AlphaDev peut-il garantir la correction et la robustesse des algorithmes qu’il génère, notamment face à des données imprévues ?

Quels sont les domaines d’application et les limites des algorithmes découverts par AlphaDev, en termes de complexité, de mémoire, de parallélisme, etc. ?

Comment AlphaDev peut-il être rendu accessible et compréhensible aux développeurs et aux chercheurs qui souhaitent utiliser ou reproduire ses algorithmes ?

Voir aussi :

Pourquoi l'intelligence artificielle pourrait sauver le monde, d'après Marc Andreessen, qui suggère que l'IA rendra le monde plus chaleureux et plus agréable

Un algorithme candidat au chiffrement post-quantique est craqué par un PC utilisant un seul cœur et en 1 heure, les chercheurs se sont appuyés sur les mathématiques pures pour le craquer