DeepMind a utilisé son intelligence artificielle (IA) baptisée AlphaZero, qui joue aux jeux de société, pour découvrir un moyen plus rapide de résoudre un problème mathématique fondamental en informatique. Il bat ainsi un record établi il y a plus de 50 ans.
Le problème en question, la multiplication matricielle, est un type de calcul crucial au coeur de nombreuses applications différentes, allant de l'affichage d'images sur un écran à la simulation de phénomènes physiques complexes. Il est également fondamental pour l'apprentissage automatique lui-même. Trouver un moyen d'accélérer ce calcul pourrait avoir un impact conséquent sur des milliers de tâches informatiques quotidiennes en réduisant les coûts et en économisant de l'énergie.
"C'est un résultat vraiment étonnant", déclare François Le Gall, mathématicien à l'université de Nagoya au Japon, qui n'a pas participé aux travaux. "La multiplication matricielle est utilisée partout en ingénierie", explique-t-il. "Pour tout ce que vous souhaitez résoudre numériquement, vous utilisez généralement des matrices".
Malgré l'omniprésence de ce calcul, il n'est pas toujours bien compris. Pour l'expliquer simplement, une matrice c'est une grille de chiffres représentant tout ce que vous voulez. Multiplier deux matrices ensemble implique généralement de multiplier les lignes de l'une avec les colonnes de l'autre. La technique de base pour résoudre le problème est enseignée au lycée. "C'est comme l'ABC de l'informatique", expose Pushmeet Kohli, responsable de l'équipe AI for Science de DeepMind.
Toutefois, les choses se compliquent lorsqu'on essaie de trouver une méthode permettant d'aller plus vite. "Personne ne connaît le meilleur algorithme pour cela", poursuit François Le Gall. "C'est l'un des plus gros problèmes ouverts de l'informatique".
En effet, il existe plus de façons de multiplier deux matrices ensemble qu'il n'y a d'atomes dans l'univers (10 à la puissance 33 pour certains cas examinés par les chercheurs). "Le nombre d'actions possibles est presque infini", détaille Thomas Hubert, ingénieur chez DeepMind.
Pour l'équipe de DeepMind, l'astuce a consisté à transformer le problème en une sorte de jeu de société tridimensionnel nommé TensorGame. Le plateau représente le problème de multiplication à résoudre et chaque mouvement symbolise l'étape suivante de la résolution de ce problème. La série de mouvements effectués dans un jeu représente donc un algorithme.
Les chercheurs ont entraîné une nouvelle version d'AlphaZero, appelée AlphaTensor, à jouer à ce jeu. Au lieu d'apprendre la meilleure série de mouvements à effectuer au jeu de Go ou aux échecs, AlphaTensor a assimilé la meilleure série de pas à effectuer lors de la multiplication de matrices. Il a été récompensé pour avoir gagné la partie en un minimum de coups.
"Nous avons transformé cela en un jeu, notre cadre préféré", indique Thomas Hubert qui était l'un des principaux chercheurs à avoir travaillé sur AlphaZéro.
Les chercheurs décrivent leurs travaux dans un article publié ce mercredi 05 octobre 2022 dans la revue Nature. L'information à retenir est qu'AlphaTensor a découvert un moyen de multiplier deux matrices de taille 4 par 4 plus rapidement qu'une méthode conçue en 1969 par le mathématicien allemand Volker Strassen. Une performance jamais atteinte avant aujourd'hui. La méthode de base enseignée au lycée comporte 64 étapes. Celle de Volker Strassen n'en compte que 49. AlphaTensor a trouvé un moyen de réaliser l'opération en 47 étapes.
Au final, AlphaTensor a battu les meilleurs algorithmes existants pour plus de 70 tailles de matrices différentes. Il a réduit le nombre d'étapes nécessaires pour multiplier deux matrices de taille 9 par 9 de 511 à 498. Le nombre requis pour multiplier deux matrices de taille 11 par 11 est passé de 919 à 896. Dans de nombreux autres cas, AlphaTensor est retombé sur le meilleur algorithme existant.
Les chercheurs ont été surpris par le nombre d'algorithmes corrects différents trouvés par AlphaTensor pour chaque taille de matrice. "C'est époustouflant de voir qu'il existe au moins 14.000 façons de multiplier des matrices de 4 par 4", s'enthousiasme Hussein Fawzi, chercheur chez DeepMind.
Après avoir recherché les algorithmes les plus rapides en théorie, l'équipe de DeepMind a voulu savoir lesquels seraient les plus rapides dans la pratique. Les performances des algorithmes peuvent varier en fonction du matériel mis à disposition car les puces informatiques sont souvent conçues pour des types de calculs spécifiques. L'équipe de DeepMind s'est servi d'AlphaTensor pour rechercher des algorithmes adaptés aux processeurs GPU Nvidia V100 et Google TPU, deux des puces les plus couramment utilisées pour la formation des réseaux neuronaux. Les algorithmes trouvés étaient 10 à 20% plus rapides pour la multiplication de matrices que ceux généralement utilisés avec ces puces.
Virginia Williams, informaticienne au Computer Science and Artificial Intelligence Laboratory du MIT, est enthousiasmée par ces résultats. Elle fait remarquer que, depuis un certain temps, on utilise des approches informatiques afin de trouver de nouveaux algorithmes de multiplication matricielle - et nombre des algorithmes les plus rapides existants ont été conçus de cette manière. Cependant, aucun n'a été capable d'améliorer les résultats obtenus de longues dates par Volker Strassen.
"Cette nouvelle méthode propose quelque chose de complètement différent de ce que faisaient les autres", explique Virginia Williams. "Il serait bien de déterminer si cette nouvelle méthode englobe réellement les précédentes ou si vous pouvez les combiner afin d'obtenir quelque chose d'encore meilleur".
DeepMind prévoit maintenant d'utiliser AlphaTensor pour rechercher d'autres types d'algorithmes. "C'est une nouvelle façon de faire de l'informatique", conclut Pushmeet Kohli.
Article de Will Douglas Heaven, traduit de l'anglais par Kozi Pastakia.
- Accès à tous les articles réservés aux abonnés, sur le site et l'appli
- Le magazine en version numérique
- Navigation sans publicité
- Sans engagement
