DeepMind a transformé la multiplication matricielle en un jeu à un joueur et battu un record vieux de 50 ans

Ars Technica a rapporté en octobre 2022 que DeepMind avait trouvé un moyen plus efficace de multiplier des matrices, battant un record vieux de 50 ans. En 1969, Volker Strassen a trouvé un algorithme qui multiplie deux matrices 4x4 en 49 multiplications au lieu de 64 par la méthode scolaire. À l'aide d'un réseau de neurones appelé AlphaTensor, DeepMind a trouvé un moyen de le faire en 47, et a publié dans Nature.

DeepMind a posé le problème comme un jeu à un joueur. Le « plateau » est un tenseur tridimensionnel capturant à quel point l'algorithme actuel s'éloigne de la correction ; les coups autorisés correspondent aux instructions de l'algorithme, et le joueur tente d'annuler les entrées du tenseur. Cela produit un algorithme prouvablement correct pour toute paire de matrices, l'efficacité étant capturée par le nombre d'étapes. Entraîné par apprentissage par renforcement, comme AlphaGo, AlphaTensor a d'abord redécouvert les travaux de Strassen et ceux d'autres mathématiciens, puis les a surpassés, selon DeepMind.

Pour les matrices 5x5, AlphaTensor a trouvé une méthode en 96 étapes contre 98 pour l'ancienne. Une semaine plus tard, Manuel Kauers et Jakob Moosbauer de l'université Johannes Kepler de Linz ont rapporté 95, écrivant que leur solution avait été obtenue à partir du schéma de DeepMind par une séquence de transformations qui éliminait une multiplication. Ars note que la multiplication matricielle sous-tend la reconnaissance vocale et d'images et les graphismes, et que des billions de tels calculs s'exécutent sur des GPU chaque jour, de sorte que de petites économies peuvent s'accumuler.

Reformuler la recherche d'algorithmes matriciels plus rapides comme un jeu à un joueur sur un tenseur, afin qu'une IA joueuse puisse découvrir des algorithmes prouvablement corrects.

Un algorithme correct est un tenseur réduit à zéro, de sorte que la correction est intégrée aux règles du jeu.

Le nombre d'étapes utilisées est un score net, de sorte que l'IA peut apprendre quels coups mènent à des algorithmes plus courts.

La multiplication matricielle est si largement utilisée que même passer de 49 à 47 étapes compte à l'échelle des GPU.

La publication du schéma découvert a permis aux chercheurs humains de s'appuyer dessus en une semaine.

Si un problème de recherche peut être formulé comme un jeu avec un score clair, une IA joueuse peut l'explorer, et ses résultats peuvent alimenter de nouvelles améliorations humaines.

Une semaine après l'annonce de DeepMind, les deux chercheurs autrichiens ont revendiqué un schéma à 95 multiplications pour les matrices 5x5, en s'appuyant sur celui de DeepMind. Ars a spéculé qu'avec l'IA désormais à la recherche de nouveaux algorithmes, d'autres records mathématiques de longue date pourraient tomber bientôt.