Le système d’IA apporte les premières optimisations au code de tri depuis plus d’une décennie

Toute personne ayant suivi un cours d’informatique de base a sans aucun doute passé du temps à concevoir un algorithme de tri, c’est-à-dire un code qui prend une liste non ordonnée d’éléments et les place dans l’ordre croissant ou décroissant. Il s’agit d’un défi intéressant parce qu’il existe de nombreuses façons de procéder et parce que les gens ont passé beaucoup de temps à trouver le moyen d’effectuer ce tri de la manière la plus efficace possible.

Le tri est tellement élémentaire que des algorithmes sont intégrés dans la plupart des bibliothèques standard des langages de programmation. Et, dans le cas de la bibliothèque C++ utilisée avec le compilateur LLVM, le code n’a pas été modifié depuis plus de dix ans.

Mais le groupe DeepMind AI de Google vient de mettre au point un outil d’apprentissage par renforcement capable de développer des algorithmes extrêmement optimisés sans avoir été formé au préalable sur des exemples de code humain. L’astuce a consisté à le configurer de manière à ce qu’il traite la programmation comme un jeu.

Tout est un jeu

DeepMind, entre autres, est connue pour avoir développé un logiciel qui s’apprend à jouer à des jeux. Cette approche s’est avérée très efficace, conquérant des jeux aussi variés que les échecs, Goet StarCraft. Bien que les détails varient en fonction du jeu auquel il s’attaque, le logiciel apprend en jouant lui-même et découvre des options qui lui permettent de maximiser son score.

Parce qu’il n’a pas été formé aux jeux auxquels jouent les humains, le système DeepMind peut découvrir des approches aux jeux auxquelles les humains n’ont pas pensé. Bien sûr, comme il joue toujours contre lui-même, il y a des cas où il a développé des angles morts que les humains peuvent exploiter.

Cette approche est très pertinente pour la programmation. Les grands modèles de langage écrivent des codes efficaces parce qu’ils ont vu de nombreux exemples humains. Mais pour cette raison, il est peu probable qu’ils développent quelque chose que les humains n’ont pas fait auparavant. Si nous cherchons à optimiser des algorithmes bien compris, tels que des fonctions de tri, le fait de s’inspirer d’un code humain existant permettra, au mieux, d’obtenir des performances équivalentes. Mais comment faire pour qu’une IA identifie une approche réellement nouvelle ?

Les chercheurs de DeepMind ont adopté la même approche que pour les échecs et les jeux d’argent. Go: Ils ont transformé l’optimisation du code en un jeu. Le système AlphaDev a développé des algorithmes d’assemblage x86 qui traitent la latence du code comme un score et tentent de minimiser ce score tout en s’assurant que le code s’exécute jusqu’au bout sans erreur. Grâce à l’apprentissage par renforcement, AlphaDev développe progressivement la capacité d’écrire un code serré et très efficace.

A l’intérieur d’AlphaDev

Dire que le système optimise la latence est très différent d’expliquer comment il fonctionne. Comme la plupart des autres systèmes d’IA complexes, AlphaDev se compose de plusieurs éléments distincts. L’un d’entre eux est une fonction de représentation, qui suit la performance globale du code au fur et à mesure de son développement. Cela inclut la structure générale de l’algorithme, ainsi que l’utilisation des registres x86 et de la mémoire.

Le système ajoute des instructions d’assemblage individuellement, choisies par une recherche arborescente de Monte Carlo – une fois encore, une approche empruntée aux systèmes de jeu. L’aspect « arbre » de cette approche permet au système de se concentrer rapidement sur une zone limitée de la vaste gamme d’instructions potentielles, tandis que la méthode Monte Carlo ajoute un certain degré d’aléatoire à l’instruction précise qui est choisie à partir de cette branche. (Il convient de noter que le terme « instruction » dans ce contexte inclut des éléments tels que les registres spécifiques choisis pour créer un assemblage valide et complet).

Le système évalue ensuite l’état du code d’assemblage en termes de latence et de validité et lui attribue un score, en le comparant au score du code précédent. Grâce à l’apprentissage par renforcement, il s’accroche aux informations sur la manière dont les différentes branches de l’arbre fonctionnent, compte tenu de l’état du programme. Au fil du temps, il « apprend » comment atteindre un état de jeu gagnant – un tri terminé – avec un score maximal, ce qui signifie un temps de latence minimal.

Le principal avantage de ce système est que son apprentissage ne nécessite aucun exemple de code. Au lieu de cela, le système génère ses propres exemples de code et les évalue. Au cours de ce processus, il conserve des informations sur les combinaisons d’instructions qui sont efficaces pour le tri.