Deep Mind AlphaTensor va découvrir de nouveaux algorithmes

Deep Mind a étendu AlphaZero aux mathématiques pour ouvrir de nouvelles possibilités pour les algorithmes de recherche.

AlphaTensor, s'appuie sur AlphaZero, un agent qui a montré des performances surhumaines sur des jeux de société, comme les échecs, le go et le shogi, et ce travail montre le parcours d'AlphaZero, du jeu à la résolution de problèmes mathématiques non résolus pour la première fois.

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.

Au cours de l'âge d'or islamique, le mathématicien persan Muhammad ibn Musa al-Khwarizmi a 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 Algoritmi, a conduit au terme algorithme. Mais, malgré la familiarité avec les algorithmes d'aujourd'hui - utilisés dans toute la société, de l'algèbre en classe à la recherche scientifique de pointe - le processus de découverte de nouveaux algorithmes est incroyablement difficile, et un exemple des incroyables capacités de raisonnement de l'esprit humain.

Ils ont publié dans Nature. AlphaTensor est le premier système d'intelligence artificielle (IA) permettant de découvrir des algorithmes nouveaux, efficaces et prouvés corrects 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 sur la recherche du moyen le plus rapide de multiplier deux matrices.

Formé à partir de rien, AlphaTensor découvre des algorithmes de multiplication matricielle plus efficaces que les algorithmes humains et informatiques existants. Malgré l'amélioration par rapport aux algorithmes connus, ils notent qu'une limitation d'AlphaTensor est la nécessité de prédéfinir un ensemble d'entrées de facteur potentielles F, ce qui discrétise l'espace de recherche mais peut éventuellement conduire à manquer des algorithmes efficaces. Une direction intéressante pour les recherches futures consiste à adapter AlphaTensor à la recherche de F. Une force importante d'AlphaTensor est sa flexibilité pour prendre en charge des récompenses stochastiques et non différentiables complexes (du rang du tenseur à l'efficacité pratique sur du matériel spécifique), en plus de trouver des algorithmes pour des opérations personnalisées dans une grande variété d'espaces (tels que des champs finis). Ils pensent que cela incitera les applications d'AlphaTensor à concevoir des algorithmes qui optimisent des mesures que nous n'avons pas prises en compte ici, telles que la stabilité numérique ou la consommation d'énergie.

La découverte des algorithmes de multiplication matricielle a des implications considérables, car la multiplication matricielle est au cœur de nombreuses tâches de calcul, telles que l'inversion matricielle, le calcul du déterminant et la résolution de systèmes linéaires.

Le processus et les progrès de l'automatisation de la découverte algorithmique
Tout d'abord, ils ont converti le problème de la recherche d'algorithmes efficaces pour la multiplication matricielle en un jeu à un joueur. Dans ce jeu, le tableau est un tenseur tridimensionnel (tableau de nombres), capturant à quel point l'algorithme actuel est incorrect. 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 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. Comparé au jeu de Go, qui est resté un défi pour l'IA pendant des décennies, le nombre de mouvements possibles à chaque étape de leur jeu est de 30 ordres de grandeur supérieur (au-dessus de 10^33 pour l'un des paramètres qu'ils considèrent).

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 au problème, une procédure pour générer des données synthétiques utiles et une recette pour tirer parti des symétries du problème.

Ils ont ensuite formé un agent AlphaTensor en utilisant 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 les algorithmes historiques de multiplication matricielle rapide tels que ceux de Strassen, dépassant finalement le domaine de l'intuition humaine et découvrant des algorithmes plus rapidement que ceux connus auparavant.

Explorer l'impact sur la recherche et les applications futures
D'un point de vue mathématique, leurs résultats peuvent guider d'autres recherches en théorie de la complexité, qui visent à déterminer les algorithmes les plus rapides pour résoudre des problèmes de calcul. En explorant l'espace des algorithmes possibles d'une manière plus efficace que les approches précédentes, AlphaTensor aide à faire progresser notre compréhension de la richesse des algorithmes de multiplication matricielle. La compréhension de cet espace peut débloquer de nouveaux résultats pour aider à 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 central de nombreuses tâches de calcul, couvrant l'infographie, les communications numériques, la formation de réseaux de neurones et le calcul scientifique, les algorithmes découverts par AlphaTensor pourraient rendre les calculs dans ces domaines beaucoup plus efficaces. La flexibilité d'AlphaTensor à considérer tout type d'objectif pourrait également stimuler de nouvelles applications pour la conception d'algorithmes qui optimisent des métriques telles que la consommation d'énergie et la stabilité numérique, aidant à empêcher les petites erreurs d'arrondi de faire boule de neige lorsqu'un algorithme fonctionne.

Bien qu'ils se soient 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 de calcul fondamentales. Leurs 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 s'appuyant sur nos recherches, ils espèrent 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 toutes les sciences.

Nature - Découvrir des algorithmes de multiplication matricielle plus rapides avec l'apprentissage par renforcement

Abstract
L'amélioration de l'efficacité des algorithmes pour les calculs fondamentaux peut avoir un impact étendu, car elle peut affecter la vitesse globale d'un grand nombre de calculs. La multiplication matricielle est l'une de ces tâches primitives, qui se produit dans de nombreux systèmes, des réseaux de neurones aux routines de calcul scientifique. La découverte automatique d'algorithmes utilisant l'apprentissage automatique offre la possibilité d'aller au-delà de l'intuition humaine et de surpasser les meilleurs algorithmes actuels conçus par l'homme. Cependant, l'automatisation de la procédure de découverte d'algorithmes est complexe, car l'espace des algorithmes possibles est énorme. Nous rapportons ici une approche d'apprentissage par renforcement profond basée sur AlphaZero1 pour découvrir des algorithmes efficaces et prouvés corrects pour la multiplication de matrices arbitraires. Notre agent, AlphaTensor, est formé pour jouer à un jeu solo où l'objectif est de trouver des décompositions de tenseurs dans un espace à facteurs finis. AlphaTensor a découvert des algorithmes qui surpassent la complexité de pointe pour de nombreuses tailles de matrice. Le cas des matrices 4 × 4 dans un corps fini est particulièrement pertinent, où l'algorithme d'AlphaTensor améliore l'algorithme à deux niveaux de Strassen pour la première fois, à notre connaissance, depuis sa découverte il y a 50 ans2. Nous montrons en outre la flexibilité d'AlphaTensor à travers différents cas d'utilisation : des algorithmes d'une complexité de pointe pour la multiplication matricielle structurée et une efficacité pratique améliorée en optimisant la multiplication matricielle pour l'exécution sur du matériel spécifique. Nos résultats mettent en évidence la capacité d'AlphaTensor à accélérer le processus de découverte algorithmique sur une gamme de problèmes et à optimiser pour différents critères.