Des algorithmes de tri plus rapides découverts grâce à l'apprentissage par renforcement profond

Nature volume 618, pages 257-263 (2023)Citer cet article

355 000 accès

1 Citation

1148 Altmétrique

Détails des métriques

Les algorithmes fondamentaux tels que le tri ou le hachage sont utilisés des milliards de fois chaque jour1. À mesure que la demande de calcul augmente, 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é2, améliorer encore l’efficacité de ces routines s’est avéré un défi tant pour les scientifiques humains que pour les approches informatiques. Nous montrons ici comment l’intelligence artificielle peut aller au-delà de l’état actuel de l’art en découvrant des routines jusqu’alors inconnues. Pour y parvenir, nous avons formulé la tâche consistant à trouver une meilleure routine de tri sous forme de jeu solo. Nous avons ensuite formé un nouvel agent d’apprentissage par renforcement profond, AlphaDev, pour jouer à ce jeu. AlphaDev a découvert de toutes pièces de petits algorithmes de tri qui ont surpassé les références humaines connues auparavant. Ces algorithmes ont été intégrés dans la bibliothèque de tri C++ standard LLVM3. Cette modification apportée à cette partie de la bibliothèque de tri représente le remplacement d'un composant par un algorithme qui a été automatiquement découvert grâce à l'apprentissage par renforcement. Nous présentons également des résultats dans des domaines supplémentaires, démontrant la généralité de l'approche.

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 ne sont plus en mesure de les optimiser davantage, ce qui entraîne un goulot d'étranglement informatique toujours croissant. Les travaux dans 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 des programmes en utilisant des proxys pour la latence. Il s'agit notamment des techniques de recherche énumérative4,5,6,7 et de la recherche stochastique5,6,8,9,10 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 corrects11,12,13,14,15,16. . Grâce à 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 précédents. .

L’une des questions fondamentales en informatique est de savoir comment trier une séquence17,18,19,20. Ceci est enseigné dans les cours élémentaires d’informatique du monde entier21,22 et est utilisé partout dans une vaste gamme d’applications23,24,25. Des décennies de recherche en informatique se sont concentrées sur la découverte et l’optimisation d’algorithmes de tri26,27,28. Un élément clé des solutions pratiques est un petit tri sur une courte séquence d’éléments ; cet algorithme est appelé à plusieurs reprises lors du tri de grands tableaux qui utilisent des approches diviser pour régner29. Dans ce travail, nous nous concentrons sur deux types d’algorithmes de petit tri : (1) le tri fixe et (2) le tri variable. Les algorithmes de tri fixes trient des séquences d'une longueur fixe (par exemple, le tri variable 3 ne peut trier que les séquences de longueur 3), tandis que les algorithmes de tri variables peuvent trier une séquence de taille variable (par exemple, le tri variable 5 peut trier des séquences allant de un à cinq). éléments).

Nous formulons le problème de la découverte de nouveaux algorithmes de tri efficaces sous la forme d'un jeu solo que nous appelons AssemblyGame. Dans ce jeu, le joueur sélectionne une série d’instructions CPU de bas niveau, que nous appelons instructions d’assemblage30, à combiner pour produire un nouvel algorithme de tri efficace. C'est un défi car le joueur doit prendre en compte l'espace combinatoire des instructions d'assemblage pour produire un algorithme dont l'exactitude et la rapidité sont à la fois prouvées. La dureté de AssemblyGame ne vient pas seulement de la taille de l’espace de recherche, qui est similaire à des jeux extrêmement difficiles tels que les échecs (10 120 parties)31 et le Go (10 700 parties)32, mais aussi de la nature de la fonction de récompense. Une seule instruction incorrecte dans AssemblyGame peut potentiellement invalider l’ensemble de l’algorithme, rendant l’exploration dans cet espace de jeux incroyablement difficile.