Découvrir de nouveaux algorithmes avec alphatenseur

La première extension de l’alphazer aux mathématiques débloque de nouvelles possibilités de recherche

Les algorithmes ont aidé 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 une table de multiplication, et le mathématicien grec Euclide a décrit un algorithme pour calculer le plus grand diviseur commun, qui est toujours utilisé aujourd’hui.

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

Dans notre papierpublié aujourd’hui dans la nature, Nous présentons Alphatenseurle premier système d’intelligence artificielle (IA) pour découvrir de nouveaux algorithmes efficaces, efficaces et provêtement corrects pour des tâches fondamentales telles que la multiplication matricielle. Cela met en lumière une question ouverte de 50 ans en mathématiques sur la recherche du moyen le plus rapide de multiplier deux matrices.

Cet article est un tremplin dans la mission de Deepmind pour faire progresser la science et déverrouiller les problèmes les plus fondamentaux en utilisant l’IA. Notre système, alphatenseur, s’appuie sur Alphazero, un agent qui a Montré des performances surhumaines dans les jeux de société, comme les échecs, Go et Shogiet ce travail montre le voyage d’Alphazero de jouer à des jeux à la résolution des 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ées dans les cours de mathématiques du secondaire. Mais en dehors de la classe, cette humble fonctionnement mathématique a une énorme influence dans le monde numérique contemporain et est omniprésent dans l’informatique moderne.

Cette opération est utilisée pour traiter les images sur les smartphones, la reconnaissance des commandes de la parole, la génération de graphiques pour les jeux informatiques, l’exécution de simulations pour prédire la météo, la compression des données et des vidéos pour le partage sur Internet, et bien plus encore. Les entreprises du monde entier consacrent beaucoup de temps et d’argent à développer un matériel informatique pour multiplier efficacement les matrices. Ainsi, même des améliorations mineures à l’efficacité de la multiplication matricielle peuvent avoir un impact généralisé.

Pendant des siècles, les mathématiciens pensaient que l’algorithme de multiplication standard de la matrice était le meilleur pouvait réaliser en termes d’efficacité. Mais en 1969, le mathématicien allemand Volker Strassen 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 donner un algorithme plus rapide. Malgré des décennies de recherche après la percée de Strassen, les versions plus importantes de ce problème sont restées non résolues – dans la mesure où on ne sait pas à quel point il est possible de multiplier deux matrices aussi petites que 3×3.

Dans notre article, nous avons exploré comment les techniques d’IA modernes pourraient faire avancer la découverte automatique de nouveaux algorithmes de multiplication matricielle. S’appuyant sur la progression de l’intuition humaine, l’alphatenseur a découvert des algorithmes plus efficaces que l’état de l’art pour de nombreuses tailles de matrice. Nos algorithmes conçus sur l’IA surpassent ceux conçus par l’homme, ce qui est un pas en avant majeur dans le domaine de la découverte algorithmique.

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

Tout d’abord, 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 (tableau de numéros), capturant à quelle distance de corriger l’algorithme actuel. Grâce à un ensemble de mouvements autorisés, correspondant aux instructions d’algorithme, le joueur tente de modifier le tenseur et de zéro ses entrées. Lorsque le joueur parvient à le faire, cela se traduit par un algorithme de multiplication matriciel prouvant correct pour toute paire de matrices, et son efficacité est capturée par le nombre d’étapes prises pour zéro le tenseur.

Ce jeu est incroyablement difficile – le nombre d’algorithmes possibles à considérer est beaucoup plus élevé que le nombre d’atomes dans l’univers, même pour les petits cas de multiplication matricielle. Par rapport au jeu de go, qui est resté Un défi pour l’IA depuis des décenniesle nombre de mouvements possibles à chaque étape de notre jeu est de 30 ordres de grandeur plus grande (au-dessus de 1033 pour l’un des paramètres que nous considérons).

Essentiellement, pour bien jouer à ce jeu, il faut identifier les plus petites 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 aux problèmes, 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.

Nous avons ensuite formé un agent alphatenseur utilisant l’apprentissage du renforcement pour jouer au jeu, à commencer sans aucune connaissance des algorithmes de multiplication matricielle existants. Grâce à l’apprentissage, l’alphatenseur s’améliore progressivement au fil du temps, en redouvant des algorithmes de multiplication de la matrice rapide historiques tels que celui de Strassen, dépassant finalement le domaine de l’intuition humaine et découvrent les algorithmes plus rapides qu’auparavant.

Par exemple, si l’algorithme traditionnel enseigné dans l’école se multiplie une matrice 4×5 par 5×5 en utilisant 100 multiplications, et ce nombre a été réduit à 80 avec l’ingéniosité humaine, l’alphatenseur a trouvé des algorithmes qui effectuent 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 pour multiplier les 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 avec 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’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é l’alphatenseur pour trouver spécifiquement des algorithmes qui sont rapides sur un matériel donné, tel que le GPU NVIDIA V100 et Google TPU V2. Ces algorithmes multiplient les matrices grandes 10 à 20% plus rapides que les algorithmes couramment utilisés sur le même matériel, ce qui présente la flexibilité de l’alphatenseur dans l’optimisation des objectifs arbitraires.

Explorer l’impact sur les recherches et les applications futures

D’un point de vue mathématique, nos résultats peuvent guider des recherches supplémentaires sur la théorie de la complexité, qui vise à déterminer les algorithmes les plus rapides pour résoudre les problèmes de calcul. En explorant l’espace des algorithmes possibles de manière plus efficace que les approches précédentes, l’alphatenseur aide à faire progresser notre compréhension de la richesse des algorithmes de multiplication matricielle. Comprendre cet espace peut débloquer de nouveaux résultats pour aider à déterminer la complexité asymptotique de la multiplication de la matrice, L’un des problèmes ouverts les plus fondamentaux de l’informatique.

Étant donné que la multiplication matricielle est un composant central dans de nombreuses tâches de calcul, couvrant l’infographie, les communications numériques, la formation de réseau neuronal et l’informatique scientifique, les algorithmes découverts par des alphatenseurs pourraient rendre les calculs dans ces domaines beaucoup plus efficaces. La flexibilité de l’alphatenseur pour considérer tout type d’objectif pourrait également stimuler de nouvelles applications pour la conception d’algorithmes qui optimisent les mesures telles que la consommation d’énergie et la stabilité numérique, aidant à empêcher les petites erreurs d’arrondi de faire la boule de neige à mesure qu’un algorithme fonctionne.

Bien que nous nous concentrions ici sur le problème particulier de la multiplication matricielle, nous espérons que notre article inspirera les autres à utiliser l’IA pour guider la découverte algorithmique pour d’autres tâches de calcul fondamentales. Nos recherches montrent également qu’Alphazer est un algorithme puissant qui peut être étendu bien au-delà du domaine des jeux traditionnels pour aider à résoudre les problèmes ouverts en mathématiques. S’appuyant sur nos recherches, nous espérons stimuler un plus grand nombre de travaux – en appliquant une 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 Référentiel Github d’Alphatensor.