Quiconque a suivi un cours d’informatique de base a sans aucun doute passé du temps à concevoir un algorithme de tri – un code qui prend une liste non ordonnée d’éléments et les place dans l’ordre croissant ou décroissant. C’est un défi intéressant parce qu’il y a tellement de façons de le faire et parce que les gens ont passé beaucoup de temps à trouver comment faire ce tri le plus efficacement possible.
Le tri est si basique que des algorithmes sont intégrés dans la plupart des bibliothèques standard pour les langages de programmation. Et, dans le cas de la bibliothèque C++ utilisée avec le compilateur LLVM, le code n’a pas été touché depuis plus d’une décennie.
Mais le groupe DeepMind AI de Google a maintenant développé un outil d’apprentissage par renforcement qui peut développer des algorithmes extrêmement optimisés sans avoir d’abord été formé sur des exemples de code humain. L’astuce consistait à le configurer pour traiter la programmation comme un jeu.
Tout n’est qu’un jeu
DeepMind, entre autres, est remarquable pour avoir développé un logiciel qui apprend tout seul à jouer à des jeux. Cette approche s’est avérée très efficace, conquérant des jeux aussi variés que les échecs, Alleret StarCraft. Alors que les détails varient selon le jeu auquel il s’attaque, le logiciel apprend en jouant lui-même et découvre des options qui lui permettent de maximiser un score.
Parce qu’il n’est pas formé aux jeux auxquels les humains jouent, le système DeepMind peut découvrir des approches des 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 du code efficace parce qu’ils ont vu de nombreux exemples humains. Mais à cause de cela, 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, comme les fonctions de tri, alors baser quelque chose sur du code humain existant vous procurera, au mieux, des performances équivalentes. Mais comment faire en sorte qu’une IA identifie une approche vraiment nouvelle ?
Les gens de DeepMind ont adopté la même approche qu’ils avaient avec les échecs et Aller: Ils ont transformé l’optimisation du code en un jeu. Le système AlphaDev a développé des algorithmes d’assemblage x86 qui traitaient la latence du code comme un score et tentaient de minimiser ce score tout en garantissant que le code s’exécutait jusqu’à la fin sans erreur. Grâce à l’apprentissage par renforcement, AlphaDev développe progressivement la capacité d’écrire du code serré et très efficace.
À 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 composants distincts. L’un d’eux est une fonction de représentation, qui suit les performances globales 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 – encore une fois, une approche empruntée aux systèmes de jeu. L’aspect « arborescent » de cette approche permet au système de se concentrer rapidement sur une zone limitée de la large gamme d’instructions potentielles, tandis que le Monte Carlo ajoute un degré d’aléatoire à l’instruction précise qui est choisie dans cette branche. (Notez que « l’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 pour la latence et la validité et lui attribue un score, en le comparant au score du précédent. Et, grâce à l’apprentissage par renforcement, il s’accroche à des informations sur le fonctionnement des différentes branches de l’arbre, 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 maximum, c’est-à-dire une latence minimum.
Le principal avantage de ce système est que sa formation ne doit pas impliquer d’exemples de code. Au lieu de cela, le système génère ses propres exemples de code, puis les évalue. Dans le processus, il s’accroche à des informations sur les combinaisons d’instructions efficaces pour le tri.