La première extension d’AlphaZero pour les mathématiques ouvre de nouvelles possibilités de recherche
Les algorithmes ont aidé les mathématiciens à effectuer des opérations de base pendant des milliers d’années. Les anciens Égyptiens ont conçu un algorithme pour multiplier deux nombres sans avoir besoin d’une 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 est traduit en latin par Algorithmes, 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 constitue un exemple des incroyables capacités de raisonnement de l’esprit humain.
Dans notre article publié aujourd’hui dans la revue NatureEt Nous offrons Tenseur alpha, le premier système d’intelligence artificielle (IA) à découvrir de nouveaux algorithmes efficaces et corrects pour des tâches de base telles que la multiplication de matrices. 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.
Cet article est un point de départ dans la mission de DeepMind pour faire avancer la science et débloquer les problèmes fondamentaux de l’intelligence artificielle. Notre système AlphaTensor est basé sur AlphaZero, un proxy qui a montré des performances révolutionnaires sur les jeux de société, tels que 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.
multiplication matricielle
La multiplication matricielle est l’une des opérations les plus simples en algèbre, et elle est généralement enseignée dans les cours de mathématiques du secondaire. Mais en dehors de la salle de classe, cette humble opération arithmétique a un impact énorme dans le monde numérique contemporain et est omniprésente dans l’informatique moderne.
Ce processus est utilisé pour traiter des images sur des smartphones, reconnaître des commandes vocales, créer des graphiques pour des jeux informatiques, exécuter des simulations pour prévoir 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 à développer du matériel informatique pour une multiplication matricielle efficace. Par conséquent, même de petites améliorations de l’efficacité de la multiplication matricielle peuvent avoir un impact généralisé.
Pendant des siècles, les mathématiciens ont cru que l’algorithme de multiplication matricielle standard était le meilleur algorithme réalisable en termes d’efficacité. Mais en 1969, le mathématicien allemand Volker Strassen a choqué la communauté mathématique en prouvant qu’il existe de meilleurs algorithmes.
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 après la percée de Strassen, des versions plus importantes de ce problème sont restées non résolues – à tel point qu’on ne sait pas avec quelle efficacité deux matrices aussi petites que 3×3 peuvent être multipliées.
Dans notre article, nous explorons comment les nouvelles technologies d’IA peuvent améliorer la détection 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 la dernière technologie pour de nombreuses tailles de tableaux. Les algorithmes conçus avec notre technologie d’IA sont supérieurs aux algorithmes conçus par l’homme, ce qui constitue un énorme pas en avant dans le domaine de la découverte informatique.
Processus et avancées dans l’automatisation de la découverte algorithmique
Tout d’abord, nous avons transformé le problème de la recherche d’algorithmes efficaces pour la multiplication matricielle en un jeu à joueur unique. Dans ce jeu, le tableau est un tenseur 3D (une collection de nombres), et il capture à quel point l’algorithme actuel est loin de le corriger. Grâce à un ensemble de mouvements autorisés, qui correspondent aux instructions de l’algorithme, le joueur tente de modifier le tenseur et d’annuler ses entrées. Lorsque le joueur peut le faire, il en résulte un algorithme de multiplication matricielle correct pour n’importe quelle paire de matrices, dont l’efficacité est noté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 doublement de matrice. Comparé au Go, qui défie l’IA depuis des décennies, le nombre de mouvements possibles dans chaque mouvement de notre jeu est supérieur de 30 ordres de grandeur (au lieu de 1033 pour l’un des paramètres que nous considérons).
Fondamentalement, pour bien jouer à ce jeu, il faut identifier les plus petites aiguilles dans une botte de foin géante de possibilités. Pour relever les défis de ce domaine, qui diffèrent considérablement des jeux traditionnels, nous avons développé plusieurs composants critiques, notamment une nouvelle architecture de réseau de neurones qui intègre des biais inductifs spécifiques au problème, une procédure de génération de données synthétiques utiles et une recette pour tirer parti du problème. symétries.
Nous avons ensuite formé l’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 Strassen, dépassant finalement le domaine de l’intuition humaine et découvrant des algorithmes plus rapidement que ceux connus auparavant.
Par exemple, si un algorithme traditionnel enseigné à l’école multiplie une matrice 4 x 5 x 5 x 5 en utilisant 100 multiplications, et que ce nombre est réduit à 80 par l’ingéniosité humaine, AlphaTensor a trouvé des algorithmes qui effectuent la même opération en utilisant seulement 76 multiplications.
Au-delà de cet exemple, l’algorithme AlphaTensor améliore l’algorithme de Strassen à deux niveaux dans un corps 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 base pour multiplier des matrices plus grandes de taille arbitraire.
De plus, AlphaTensor détecte également une variété d’algorithmes avec une complexité de pointe – jusqu’à des milliers d’algorithmes de multiplication matricielle par taille, ce qui montre que l’espace pour les 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. Profitant de cette polyvalence, nous avons adapté AlphaTensor pour trouver des algorithmes rapides spécifiquement sur un appareil spécifique, comme le GPU Nvidia V100 et Google TPU v2. Ces algorithmes multiplient de grands tableaux 10 à 20 % plus rapidement que les algorithmes couramment utilisés sur la même machine, démontrant la flexibilité d’AlphaTensor dans l’optimisation de cibles arbitraires.
Explorer l’impact sur la recherche et les applications futures
D’un point de vue mathématique, nos résultats peuvent guider d’autres recherches en théorie de la complexité, qui visent à identifier les algorithmes les plus rapides pour résoudre des problèmes de calcul. En explorant l’espace des algorithmes possibles de manière plus efficace que les méthodes précédentes, AlphaTensor Il aide à faire progresser notre compréhension de la richesse des algorithmes de multiplication matricielle. La compréhension de cet espace peut ouvrir 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 clé de nombreuses tâches de calcul, y compris l’infographie, les communications numériques, la formation de réseaux de neurones et le calcul scientifique, les algorithmes AlphaTensor découverts pourraient rendre les calculs dans ces domaines beaucoup plus efficaces. La flexibilité d’AlphaTensor à considérer tout type de cible pourrait également stimuler de nouvelles applications pour la conception d’algorithmes qui améliorent des métriques telles que la consommation d’énergie et la stabilité numérique, aidant à empêcher la multiplication des petites erreurs d’arrondi au fur et à mesure que l’algorithme fonctionne.
Bien que nous nous soyons concentrés ici sur le problème de la multiplication matricielle, nous espérons que notre article inspirera d’autres personnes à utiliser l’intelligence artificielle pour guider la découverte algorithmique pour d’autres tâches arithmétiques de base. 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. Sur la base de nos recherches, nous espérons stimuler une plus grande action – en appliquant l’IA pour aider la société à résoudre certains des défis les plus importants en mathématiques et dans toutes les sciences.
Vous pouvez trouver plus d’informations dans le référentiel GitHub d’AlphaTensor.