Découvrir de nouveaux algorithmes avec AlphaTensor

La première extension d’AlphaZero aux mathématiques ouvre de nouvelles possibilités pour la recherche

Les algorithmes aident les mathématiciens à effectuer des opérations fondamentales depuis des milliers d’années. Les anciens Égyptiens ont créé un algorithme pour multiplier deux nombres sans nécessiter de table de multiplication, et le mathématicien grec Euclide a décrit un algorithme pour calculer le plus grand diviseur commun, qui est encore utilisé aujourd'hui.

Durant l'âge d'or islamique, le mathématicien persan Muhammad ibn Musa al-Khwarizmi conçu de nouveaux algorithmes pour résoudre des équations linéaires et quadratiques. En fait, le nom d'al-Khwarizmi, traduit en latin par Algorithmes, a conduit au terme algorithme. Mais, malgré la familiarité actuelle avec les algorithmes – utilisés dans toute la société, depuis l’algèbre en classe jusqu’à la recherche scientifique de pointe – le processus de découverte de nouveaux algorithmes est incroyablement difficile et constitue un exemple des étonnantes capacités de raisonnement de l’esprit humain.

Dans notre papierpublié aujourd'hui dans Nature, nous présentons AlphaTenseur, le premier système d'intelligence artificielle (IA) permettant de découvrir de nouveaux algorithmes efficaces et dont l'exactitude est prouvée pour des tâches fondamentales telles que la multiplication matricielle. Cela met en lumière une question ouverte vieille de 50 ans en mathématiques concernant la recherche du moyen le plus rapide de multiplier deux matrices.

Cet article constitue un tremplin dans la mission de DeepMind visant à faire progresser la science et à résoudre les problèmes les plus fondamentaux grâce à l'IA. Notre système, AlphaTensor, s'appuie sur AlphaZero, un agent qui a fait preuve de performances surhumaines dans les jeux de société, comme les échecs, le Go et le shogiet cet ouvrage montre le parcours d'AlphaZero, du jeu à la résolution de problèmes mathématiques non résolus pour la première fois.

Multiplication matricielle

La multiplication matricielle est l’une des opérations les plus simples de l’algèbre, couramment enseignée dans les cours de mathématiques au lycée. Mais en dehors de la salle de classe, cette humble opération mathématique a une énorme influence dans le monde numérique contemporain et est omniprésente dans l’informatique moderne.

Cette opération est utilisée pour traiter des images sur les smartphones, reconnaître des commandes vocales, générer des graphiques pour des jeux informatiques, exécuter des simulations pour prédire la météo, compresser des données et des vidéos pour les partager sur Internet, et bien plus encore. Les entreprises du monde entier consacrent beaucoup de temps et d’argent au développement de matériel informatique pour multiplier efficacement les matrices. Ainsi, même des améliorations mineures de l’efficacité de la multiplication matricielle peuvent avoir un impact considérable.

Pendant des siècles, les mathématiciens ont cru que l’algorithme standard de multiplication matricielle était le meilleur que l’on puisse obtenir en termes d’efficacité. Mais en 1969, le mathématicien allemand Volker Strassen a choqué la communauté mathématique en montrant que de meilleurs algorithmes existent.

En étudiant de très petites matrices (taille 2×2), il a découvert une manière ingénieuse de combiner les entrées des matrices pour produire un algorithme plus rapide. Malgré des décennies de recherche qui ont suivi la percée de Strassen, des versions plus grandes de ce problème sont restées non résolues – dans la mesure où on ne sait pas avec quelle efficacité il est possible de multiplier deux matrices aussi petites que 3×3.

Dans notre article, nous avons exploré comment les techniques modernes d’IA pourraient faire progresser la découverte automatique de nouveaux algorithmes de multiplication matricielle. S'appuyant sur les progrès de l'intuition humaine, AlphaTensor a découvert des algorithmes plus efficaces que l'état de l'art pour de nombreuses tailles de matrice. Nos algorithmes conçus par l’IA surpassent ceux conçus par l’homme, ce qui constitue une avancée majeure dans le domaine de la découverte algorithmique.

Le processus et les progrès de l'automatisation de la découverte algorithmique

Premièrement, nous avons converti le problème de la recherche d’algorithmes efficaces pour la multiplication matricielle en un jeu solo. Dans ce jeu, le tableau est un tenseur tridimensionnel (un tableau de nombres), capturant à quel point l'algorithme actuel est loin d'être correct. Grâce à un ensemble de mouvements autorisés, correspondant aux instructions de l'algorithme, le joueur tente de modifier le tenseur et de mettre à zéro ses entrées. Lorsque le joueur parvient à le faire, cela se traduit par un algorithme de multiplication matricielle prouvée correct pour n'importe quelle paire de matrices, et son efficacité est capturée par le nombre d'étapes prises pour mettre à zéro le tenseur.

Ce jeu est incroyablement difficile : le nombre d’algorithmes possibles à considérer est bien supérieur au nombre d’atomes dans l’univers, même pour de petits cas de multiplication matricielle. Par rapport au jeu de Go, qui restait un défi pour l’IA depuis des décenniesle nombre de coups possibles à chaque étape de notre jeu est 30 ordres de grandeur plus grand (au-dessus de 1033 pour l'un des paramètres que nous considérons).

Essentiellement, pour bien jouer à ce jeu, il faut identifier la plus petite des aiguilles dans une gigantesque botte de foin de possibilités. Pour relever les défis de ce domaine, qui s'écarte considérablement des jeux traditionnels, nous avons développé plusieurs composants cruciaux, notamment une nouvelle architecture de réseau neuronal qui intègre des biais inductifs spécifiques à un problème, une procédure pour générer des données synthétiques utiles et une recette pour exploiter les symétries du problème.

Nous avons ensuite formé un agent AlphaTensor à l’aide de l’apprentissage par renforcement pour jouer au jeu, en commençant sans aucune connaissance des algorithmes de multiplication matricielle existants. Grâce à l'apprentissage, AlphaTensor s'améliore progressivement au fil du temps, redécouvrant des algorithmes historiques de multiplication matricielle rapide tels que celui de Strassen, dépassant finalement le domaine de l'intuition humaine et découvrant des algorithmes plus rapidement que prévu.

Par exemple, si l’algorithme traditionnel enseigné à l’école multiplie une matrice 4×5 par 5×5 en utilisant 100 multiplications, et que ce nombre a été réduit à 80 grâce à l’ingéniosité humaine, AlphaTensor a trouvé des algorithmes qui font la même opération en utilisant seulement 76 multiplications.

Au-delà de cet exemple, l'algorithme d'AlphaTensor améliore l'algorithme à deux niveaux de Strassen dans un champ fini pour la première fois depuis sa découverte il y a 50 ans. Ces algorithmes de multiplication de petites matrices peuvent être utilisés comme primitives pour multiplier des matrices beaucoup plus grandes de taille arbitraire.

De plus, AlphaTensor découvre également un ensemble diversifié d'algorithmes d'une complexité de pointe – jusqu'à des milliers d'algorithmes de multiplication matricielle pour chaque taille, montrant que l'espace des algorithmes de multiplication matricielle est plus riche qu'on ne le pensait auparavant.

Les algorithmes de cet espace riche ont des propriétés mathématiques et pratiques différentes. Tirant parti de cette diversité, nous avons adapté AlphaTensor pour trouver spécifiquement des algorithmes rapides sur un matériel donné, tels que le GPU Nvidia V100 et Google TPU v2. Ces algorithmes multiplient les grandes matrices 10 à 20 % plus rapidement que les algorithmes couramment utilisés sur le même matériel, ce qui met en valeur la flexibilité d'AlphaTensor dans l'optimisation d'objectifs arbitraires.

Explorer l’impact sur la recherche et les applications futures

D'un point de vue mathématique, nos résultats peuvent guider de nouvelles recherches sur la théorie de la complexité, qui visent à déterminer les algorithmes les plus rapides pour résoudre des problèmes informatiques. En explorant l'espace des algorithmes possibles d'une manière plus efficace que les approches précédentes, AlphaTensor contribue à faire progresser notre compréhension de la richesse des algorithmes de multiplication matricielle. Comprendre cet espace pourrait débloquer de nouveaux résultats permettant de déterminer la complexité asymptotique de la multiplication matricielle, l'un des problèmes ouverts les plus fondamentaux en informatique.

Étant donné que la multiplication matricielle est un élément essentiel de nombreuses tâches informatiques, allant de l'infographie aux communications numériques, en passant par la formation des réseaux neuronaux et le calcul scientifique, les algorithmes découverts par AlphaTensor pourraient rendre les calculs dans ces domaines beaucoup plus efficaces. La flexibilité d'AlphaTensor pour prendre en compte tout type d'objectif pourrait également stimuler de nouvelles applications pour la conception d'algorithmes qui optimisent des mesures telles que la consommation d'énergie et la stabilité numérique, aidant ainsi à empêcher les petites erreurs d'arrondi de faire boule de neige pendant le fonctionnement d'un algorithme.

Bien que nous nous soyons concentrés ici sur le problème particulier de la multiplication matricielle, nous espérons que notre article inspirera d’autres personnes à utiliser l’IA pour guider la découverte algorithmique pour d’autres tâches informatiques fondamentales. Nos recherches montrent également qu’AlphaZero est un algorithme puissant qui peut être étendu bien au-delà du domaine des jeux traditionnels pour aider à résoudre des problèmes ouverts en mathématiques. En nous appuyant sur nos recherches, nous espérons stimuler un plus grand nombre de travaux : appliquer l’IA pour aider la société à résoudre certains des défis les plus importants en mathématiques et dans les sciences.

Vous pouvez trouver plus d'informations dans Dépôt GitHub d'AlphaTensor.