L'IA révèle de nouvelles possibilités dans la multiplication matricielle

Les mathématiciens aiment un bon puzzle. Même quelque chose d'aussi abstrait que la multiplication de matrices (tableaux de nombres à deux dimensions) peut ressembler à un jeu lorsque vous essayez de trouver le moyen le plus efficace de le faire. C'est un peu comme essayer de résoudre un Rubik's Cube en aussi peu de mouvements que possible - difficile, mais séduisant. Sauf que pour un Rubik's Cube, le nombre de coups possibles à chaque étape est de 18 ; pour la multiplication matricielle, même dans des cas relativement simples, chaque étape peut présenter plus de 10¹² options.

Au cours des 50 dernières années, les chercheurs ont abordé ce problème de plusieurs manières, toutes basées sur des recherches informatiques assistées par l'intuition humaine. Le mois dernier, une équipe de la société d'intelligence artificielle DeepMind a montré comment aborder le problème dans une nouvelle direction, rapportant dans un papier in Nature qu'ils avaient formé avec succès un réseau de neurones pour découvrir de nouveaux algorithmes rapides pour la multiplication matricielle. C'était comme si l'IA avait trouvé une stratégie inconnue pour résoudre un Rubik's Cube monstrueusement complexe.

"C'est un très beau résultat", a déclaré Josh Alman, informaticien à l'université de Columbia. Mais lui et d'autres spécialistes de la multiplication matricielle ont également souligné qu'une telle assistance par l'IA viendra compléter plutôt que remplacer les méthodes existantes, du moins à court terme. "C'est comme une preuve de concept pour quelque chose qui pourrait devenir une percée", a déclaré Alman. Le résultat aidera simplement les chercheurs dans leur quête.

Comme pour le prouver, trois jours après le Nature article est sorti, une paire de chercheurs autrichiens a illustré comment les nouvelles et les anciennes méthodes pouvaient se compléter. Ils ont utilisé une recherche conventionnelle assistée par ordinateur pour améliorer encore l'un des algorithmes découverts par le réseau de neurones.

Les résultats suggèrent que, comme le processus de résolution d'un Rubik's Cube, le chemin vers de meilleurs algorithmes sera plein de rebondissements.

Matrices multiplicatrices

La multiplication matricielle est l'une des opérations les plus fondamentales et les plus omniprésentes dans toutes les mathématiques. Pour multiplier une paire de nParn matrices, chacune avec n² éléments, vous multipliez et additionnez ces éléments ensemble dans des combinaisons particulières pour générer le produit, un troisième nParn matrice. La recette standard pour multiplier deux nParn matrices nécessite n³ opérations de multiplication, donc une matrice 2 par 2, par exemple, nécessite huit multiplications.

Pour les matrices plus grandes, avec des milliers de lignes et de colonnes, ce processus devient rapidement fastidieux. Mais en 1969, le mathématicien Volker Strassen découvert une procédure pour multiplier une paire de matrices 2 par 2 en utilisant sept plutôt que huit étapes de multiplication, au prix de l'introduction de plusieurs étapes d'addition.

L'algorithme de Strassen est inutilement alambiqué si vous voulez simplement multiplier une paire de matrices 2 par 2. Mais il s'est rendu compte que cela fonctionnerait également pour des matrices plus grandes. C'est parce que les éléments d'une matrice peuvent eux-mêmes être des matrices. Par exemple, une matrice avec 20,000 20,000 lignes et 2 2 colonnes peut être réimaginée comme une matrice 10,000 par 10,000 dont les quatre éléments sont chacun des matrices de 5,000 5,000 par 2 2. Chacune de ces matrices peut ensuite être subdivisée en quatre blocs de XNUMX XNUMX par XNUMX XNUMX, et ainsi de suite. Strassen pourrait appliquer sa méthode pour multiplier des matrices XNUMX par XNUMX à chaque niveau de cette hiérarchie imbriquée. À mesure que la taille de la matrice augmente, les économies réalisées grâce à moins de multiplications augmentent.

La découverte de Strassen a conduit à une recherche d'algorithmes efficaces pour la multiplication matricielle, qui a depuis inspiré deux sous-domaines distincts. L'un se concentre sur une question de principe : si vous imaginez multiplier deux nParn matrices et laissez n courir vers l'infini, comment le nombre d'étapes de multiplication dans l'algorithme le plus rapide possible évolue-t-il avec n? le enregistrement actuel pour la meilleure mise à l'échelle, n^2.3728596, appartient à Alman et Virginie Vassilevska Williams, informaticien au Massachusetts Institute of Technology. (Une récente inédit pré-impression ont rapporté une petite amélioration en utilisant une nouvelle technique.) Mais ces algorithmes sont d'un intérêt purement théorique, ne l'emportant sur des méthodes comme celle de Strassen que pour des matrices absurdement grandes.

Le deuxième sous-domaine pense à une plus petite échelle. Peu de temps après les travaux de Strassen, l'informaticien israélo-américain Shmuel Winograd montré que Strassen avait atteint une limite théorique : il n'est pas possible de multiplier des matrices 2 par 2 avec moins de sept étapes de multiplication. Mais pour toutes les autres tailles de matrice, le nombre minimum de multiplications requises reste une question ouverte. Et les algorithmes rapides pour les petites matrices pourraient avoir un impact démesuré, car les itérations répétées d'un tel algorithme pourraient battre l'algorithme de Strassen lorsque des matrices de taille raisonnable sont multipliées.

Malheureusement, le nombre de possibilités est énorme. Même pour les matrices 3 par 3, "le nombre d'algorithmes possibles dépasse le nombre d'atomes dans l'univers", a déclaré Alhussein Fawzi, un chercheur de DeepMind et l'un des leaders du nouveau travail.

Face à ce menu vertigineux d'options, les chercheurs ont fait des progrès en transformant la multiplication matricielle en ce qui semble être un problème mathématique totalement différent - un problème plus facile à gérer pour les ordinateurs. Il est possible de représenter la tâche abstraite de multiplication de deux matrices comme un type spécifique d'objet mathématique : un tableau tridimensionnel de nombres appelé tenseur. Les chercheurs peuvent alors décomposer ce tenseur en une somme de composantes élémentaires, appelées tenseurs de « rang 1 » ; chacun d'eux représentera une étape différente dans l'algorithme de multiplication matricielle correspondant. Cela signifie que trouver un algorithme de multiplication efficace revient à minimiser le nombre de termes dans une décomposition tensorielle - moins il y a de termes, moins il y a d'étapes impliquées.

Ainsi, les chercheurs ont découvert de nouvelles algorithmes qui se multiplient nParn matrices utilisant moins que la norme n³ étapes de multiplication pour de nombreuses petites tailles de matrice. Mais les algorithmes qui surpassent non seulement la norme mais aussi l'algorithme de Strassen pour les petites matrices sont restés hors de portée - jusqu'à présent.

Game On

L'équipe DeepMind a abordé le problème en transformant la décomposition du tenseur en un jeu solo. Ils ont commencé avec un algorithme d'apprentissage en profondeur issu d'AlphaGo - une autre IA DeepMind qui en 2016 appris à jouer au jeu de société Go assez bien pour battre les meilleurs joueurs humains.

Tous les algorithmes d'apprentissage en profondeur sont construits autour de réseaux de neurones : des réseaux de neurones artificiels triés en couches, avec des connexions dont la force peut varier, représentant à quel point chaque neurone influence ceux de la couche suivante. La force de ces connexions est modifiée au cours de nombreuses itérations d'une procédure de formation, au cours desquelles le réseau de neurones apprend à transformer chaque entrée qu'il reçoit en une sortie qui aide l'algorithme à atteindre son objectif global.

Dans le nouvel algorithme de DeepMind, baptisé AlphaTensor, les entrées représentent les étapes vers un schéma de multiplication matricielle valide. La première entrée du réseau de neurones est le tenseur de multiplication matricielle d'origine, et sa sortie est le tenseur de rang 1 qu'AlphaTensor a choisi pour son premier mouvement. L'algorithme soustrait ce tenseur de rang 1 de l'entrée initiale, produisant un tenseur mis à jour qui est réinjecté dans le réseau en tant que nouvelle entrée. Le processus se répète jusqu'à ce que chaque élément du tenseur de départ soit finalement réduit à zéro, ce qui signifie qu'il n'y a plus de tenseurs de rang 1 à retirer.

À ce stade, le réseau de neurones a découvert une décomposition de tenseur valide, car il est mathématiquement garanti que la somme de tous les tenseurs de rang 1 est exactement égale au tenseur de départ. Et les étapes qu'il a fallu pour y arriver peuvent être retraduites en étapes de l'algorithme de multiplication matricielle correspondant.

Voici le jeu : AlphaTensor décompose à plusieurs reprises un tenseur en un ensemble de composants de rang 1. À chaque fois, AlphaTensor est récompensé s'il trouve un moyen de réduire le nombre d'étapes. Mais les raccourcis vers la victoire ne sont pas du tout intuitifs, tout comme vous devez parfois brouiller un visage parfaitement ordonné sur un Rubik's Cube avant de pouvoir résoudre le tout.

L'équipe disposait désormais d'un algorithme qui pouvait, théoriquement, résoudre son problème. Ils devaient juste l'entraîner d'abord.

Nouveaux chemins

Comme tous les réseaux de neurones, AlphaTensor a besoin de beaucoup de données pour s'entraîner, mais la décomposition du tenseur est un problème notoirement difficile. Il y avait peu d'exemples de décompositions efficaces que les chercheurs pouvaient alimenter le réseau. Au lieu de cela, ils ont aidé l'algorithme à démarrer en l'entraînant sur le problème inverse beaucoup plus facile : additionner un tas de tenseurs de rang 1 générés aléatoirement.

"Ils utilisent le problème facile pour produire plus de données pour le problème difficile", a déclaré Michel Litman, informaticien à l'Université Brown. La combinaison de cette procédure de formation en arrière avec l'apprentissage par renforcement, dans laquelle AlphaTensor a généré ses propres données de formation alors qu'il se trompait à la recherche de décompositions efficaces, fonctionnait beaucoup mieux que l'une ou l'autre des méthodes de formation.

L'équipe DeepMind a entraîné AlphaTensor à décomposer des tenseurs représentant la multiplication de matrices jusqu'à 12 par 12. Il recherchait des algorithmes rapides pour multiplier des matrices de nombres réels ordinaires ainsi que des algorithmes spécifiques à un cadre plus contraint connu sous le nom d'arithmétique modulo 2. (Il s'agit de mathématiques basées sur seulement deux nombres, donc les éléments de la matrice ne peuvent être que 0 ou 1, et 1 + 1 = 0.) Les chercheurs commencent souvent avec cet espace plus restreint mais toujours vaste, dans l'espoir que les algorithmes découverts ici puissent être adaptés à travailler sur des matrices de nombres réels.

Après la formation, AlphaTensor a redécouvert l'algorithme de Strassen en quelques minutes. Il a ensuite découvert jusqu'à des milliers de nouveaux algorithmes rapides pour chaque taille de matrice. Ceux-ci étaient différents des algorithmes les plus connus mais avaient le même nombre d'étapes de multiplication.

Dans quelques cas, AlphaTensor a même battu des records existants. Ses découvertes les plus surprenantes se sont produites dans l'arithmétique modulo 2, où il a trouvé un nouvel algorithme pour multiplier des matrices 4 par 4 en 47 étapes de multiplication, une amélioration par rapport aux 49 étapes requises pour deux itérations de l'algorithme de Strassen. Il a également battu l'algorithme le plus connu pour les matrices 5 par 5 modulo 2, réduisant le nombre de multiplications requises par rapport au précédent record de 98 à 96. (Mais ce nouveau record est toujours en retard sur les 91 étapes qui seraient nécessaires pour battre Algorithme de Strassen utilisant des matrices 5 par 5.)

Le nouveau résultat très médiatisé a suscité beaucoup d'enthousiasme, avec certains chercheurs faisant l'éloge de l'amélioration basée sur l'IA sur le statu quo. Mais tout le monde dans la communauté de la multiplication matricielle n'a pas été aussi impressionné. "J'avais l'impression que c'était un peu surmédiatisé", a déclaré Vassilevska Williams. « C'est un autre outil. Ce n'est pas comme "Oh, les ordinateurs battent les humains", tu sais?"

Les chercheurs ont également souligné que les applications immédiates de l'algorithme record de 4 par 4 seraient limitées : non seulement il n'est valable qu'en arithmétique modulo 2, mais dans la vraie vie, il y a des considérations importantes en plus de la vitesse.

Fawzi a convenu que ce n'était vraiment que le début. "Il y a beaucoup de place pour l'amélioration et la recherche, et c'est une bonne chose", a-t-il déclaré.

Une touche finale

La plus grande force d'AlphaTensor par rapport aux méthodes de recherche informatiques bien établies est également sa plus grande faiblesse : il n'est pas limité par l'intuition humaine sur ce à quoi ressemblent les bons algorithmes, il ne peut donc pas expliquer ses choix. Il est donc difficile pour les chercheurs d'apprendre de ses réalisations.

Mais ce n'est peut-être pas un inconvénient aussi important qu'il n'y paraît. Quelques jours après le résultat d'AlphaTensor, le mathématicien Manuel Kauers et son étudiant diplômé Jacob Moosbauer, tous deux de l'Université Johannes Kepler de Linz en Autriche, ont fait état d'un autre pas en avant.

Lorsque l'article DeepMind est sorti, Kauers et Moosbauer étaient en train de rechercher de nouveaux algorithmes de multiplication à l'aide d'une recherche conventionnelle assistée par ordinateur. Mais contrairement à la plupart de ces recherches, qui recommencent avec un nouveau principe directeur, leur méthode fonctionne en modifiant à plusieurs reprises un algorithme existant dans l'espoir d'en tirer davantage d'économies de multiplication. Prenant comme point de départ l'algorithme d'AlphaTensor pour les matrices 5 par 5 modulo 2, ils ont été surpris de constater que leur méthode réduisait le nombre d'étapes de multiplication de 96 à 95 après seulement quelques secondes de calcul.

AlphaTensor les a également aidés à apporter une autre amélioration indirectement. Auparavant, Kauers et Moosbauer n'avaient pas pris la peine d'explorer l'espace des matrices 4x4, estimant qu'il ne serait pas possible de battre deux itérations de l'algorithme de Strassen. Le résultat d'AlphaTensor les a incités à reconsidérer, et après une semaine de temps de calcul à partir de zéro, leur méthode a révélé un autre algorithme en 47 étapes sans rapport avec celui qu'AlphaTensor avait découvert. "Si quelqu'un nous avait dit qu'il y avait quelque chose à découvrir pour 4-en-4, nous aurions pu le faire plus tôt", a déclaré Kauers. "Mais bon, eh bien, c'est comme ça que ça marche."

Littman s'attend à plus de telles surprises, comparant la situation à la première fois qu'un coureur a terminé un mile en moins de quatre minutes, un exploit qui avait été largement considéré comme impossible. "Les gens étaient comme, 'Oh, attendez, nous pouvons le faire', et maintenant beaucoup de gens peuvent le faire", a-t-il déclaré.

Pour l'avenir, Fawzi espère généraliser AlphaTensor pour s'attaquer à un plus large éventail de tâches mathématiques et informatiques, tout comme son ancêtre AlphaGo s'est finalement diversifié dans d'autres jeux.

Kauers y voit le véritable test décisif pour l'application de l'apprentissage automatique à la découverte de nouveaux algorithmes. Il rappelle que la recherche d'algorithmes rapides de multiplication matricielle est un problème combinatoire auquel les recherches informatiques, avec ou sans assistance humaine, sont bien adaptées. Mais tous les problèmes mathématiques ne sont pas si faciles à cerner. Si l'apprentissage automatique peut découvrir une idée algorithmique qualitativement nouvelle, a-t-il déclaré, "cela changerait alors la donne".