L’intelligence artificielle de DeepMind trouve l’algorithme le plus rapide pour des calculs essentiels en informatique
Les chercheurs de DeepMind, la branche de Google chargée de l’innovation en matière d’intelligence artificielle, viennent d’entraîner un algorithme d’apprentissage automatique à trouver de nouveaux algorithmes plus efficaces pour les produits matriciels.
Il y a plusieurs choses très remarquables dans cette recherche, qui pourrait améliorer considérablement la vitesse à laquelle les ordinateurs effectuent des tâches et économiser de l’énergie. Mais d’abord, une rapide introduction au produit matriciel. Une matrice est un terme mathématique pour désigner une grille, avec des nombres disposés en lignes et en colonnes.
Les matrices et les produits matriciels constituent l’épine dorsale de l’informatique. Pratiquement tous les logiciels sont liés à cette opération de base et même certains matériels. Votre écran, par exemple, vous montre cet article parce que ses pixels sont représentés sous la forme d’une grille, et ces pixels se rafraîchissent avec de nouvelles informations plus vite que vos yeux ne peuvent le faire.
En algèbre linéaire, la multiplication de matrices est une opération binaire qui produit une matrice à partir de deux matrices. Elle s’effectue généralement en multipliant les lignes d’une matrice par les colonnes de l’autre, mais il existe en fait de nombreuses autres méthodes de multiplication de matrices. En fait, il existe des milliards de milliards de façons de multiplier des matrices, mais il n’y en a qu’une seule qui soit la plus rapide, c’est-à-dire qui nécessite le moins d’étapes de calcul, pour une certaine taille de grille.
Pour un produit matriciel, le nombre de colonnes de la première matrice doit être égal au nombre de lignes de la deuxième. La matrice résultante a le nombre de lignes de la première matrice et le nombre de colonnes de la deuxième. (Quartl)
Exemple (Wikimedia) :
Face à un nombre presque infini de possibilités, comment faire pour trouver la plus efficace ? C’est là qu’interviennent les informaticiens de DeepMind, qui se sont penchés sur cette énigme et l’ont résolue en faisant ce qu’ils font le mieux : rendre les IA expertes dans les jeux.
Auparavant, DeepMind avait fait parler d’elle suite à la victoire de son IA AlphaZero sur les meilleurs humains aux jeux de société comme les échecs ou le go, en réalisant au passage de grandes avancées dans la résolution de structures protéiques. Aujourd’hui, ils ont modifié AlphaZero pour en faire une nouvelle version qui traite les problèmes de produit matriciel comme une sorte de jeu de société en 3D.
Selon les chercheurs de DeepMind dans un récent billet de blog
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 y parvient, il en résulte un algorithme de multiplication matricielle prouvé correct pour toute paire de matrices, et son efficacité est capturée par le nombre d’étapes nécessaires pour mettre à zéro le tenseur.
Ce jeu est incroyablement difficile, le nombre d’algorithmes possibles à considérer est bien plus grand que le nombre d’atomes dans l’univers, même pour les petits cas de multiplication de matrices. Par rapport au jeu de Go, qui est resté un défi pour l’IA pendant des décennies, le nombre de coups possibles à chaque étape de notre jeu est 30 ordres de grandeur plus grand (plus de 1033 pour l’un des paramètres que nous considérons).
La nouvelle IA, connue sous le nom d’AlphaTensor, a commencé par une page vierge, ce qui signifie qu’elle n’avait aucune connaissance préalable des solutions à la multiplication matricielle. Elle a simplement été chargée de trouver un algorithme de produit matriciel qui nécessite le moins d’étapes possible, c’est tout.
C’est la même approche qui a été utilisée pour aider AlphaZero à devenir le champion invaincu aux échecs et au go, même si, au début, l’IA ne savait même pas quels mouvements étaient autorisés. Son secret réside dans un type d’apprentissage automatique appelé apprentissage par renforcement, dans lequel l’IA interagit initialement avec l’environnement pour atteindre un objectif fixé par les programmeurs, et reçoit une « récompense » chaque fois qu’elle effectue une action qui la rapproche de l’objectif.
AlphaTensor utilise également des algorithmes d’arbre de décision dans lesquels il évalue les résultats d’une quantité stupéfiante de possibilités de branchement, comme l’endroit où les pièces pourraient se trouver dix coups plus tard dans une partie d’échecs, et choisit le chemin à privilégier pour une efficacité optimale dans la réalisation de son objectif.
Imaginez deux matrices, chacune comprenant deux lignes et deux colonnes. C’est la configuration la plus élémentaire qui soit et si vous deviez les multiplier de la manière conventionnelle, vous vous retrouveriez avec huit multiplications. Mais en 1969, le mathématicien Volker Strassen a trouvé une astuce pour réduire le nombre de multiplications à 7.
Dans la nouvelle étude, AlphaTensor a réussi à multiplier deux matrices 4×4 en utilisant seulement 47 multiplications, au lieu des 64 nécessaires si vous deviez laborieusement multiplier chaque ligne avec chaque colonne de la matrice correspondante. C’est également deux étapes de moins que les 49 trouvées par Strassen, dont la méthode de multiplication pour les matrices 4×4 a détenu le record de la plus rapide pendant plus de 50 ans.
AlphaTensor a recherché des algorithmes de multiplication/ produit pour plus de 70 tailles de matrices différentes. Dans chaque cas, il a soit battu les meilleurs algorithmes existants, soit obtenu la même solution que l’algorithme le plus rapide actuellement utilisé pour une taille de matrice donnée. Par exemple, AlphaTensor a résolu deux matrices 9×9 en 498 étapes au lieu du précédent record de 511 et a multiplié deux matrices 11×11 en 896 étapes au lieu de 919.
Lorsque l’équipe du DeepMind a mis ces nouveaux algorithmes à l’œuvre dans les GPU Nvidia V100 et les processeurs Google TPU, deux jeux de puces couramment utilisés pour former des réseaux neuronaux, elle a constaté que les algorithmes étaient 10 à 20 % plus rapides que ce que ces puces utilisent généralement pour multiplier des matrices.
Il n’est pas certain que les processeurs et les cartes graphiques grand public, comme ceux qui équipent votre smartphone ou votre tablette, puissent réaliser les mêmes économies d’énergie, mais les chercheurs sont prêts à explorer cette question. Quoi qu’il en soit, les scientifiques qui travaillent avec des superordinateurs pour modéliser le climat, établir des prévisions météorologiques ou calculer des systèmes dynamiques complexes vont certainement accélérer leurs travaux grâce à ces développements.
Et, en utilisant ce résultat comme une preuve de concept, rien n’empêche AlphaTensor de développer de nouveaux et meilleurs algorithmes pour une multitude de tâches de calcul.
Selon les chercheurs de DeepMind :
Notre recherche montre é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 nous appuyant sur nos recherches, nous espérons stimuler un plus grand nombre de travaux, en appliquant l’IA pour aider la société à résoudre certains des défis les plus importants en mathématiques et dans les sciences.
L’étude publiée dans Nature : Discovering faster matrix multiplication algorithms with reinforcement learning et présentée sur le site de DeepMind : Discovering novel algorithms with AlphaTensor.