Des avancées récentes dans la multiplication matricielle promettent d'accélérer les modèles d'intelligence artificielle (IA). Des chercheurs ont découvert une nouvelle méthode pour multiplier de grandes matrices plus efficacement, éliminant une inefficacité jusqu'alors inconnue. Cette découverte pourrait avoir un impact significatif sur des domaines clés de l'IA tels que la reconnaissance vocale, la vision par ordinateur et les chatbots. En utilisant une approche théorique plutôt que des solutions pratiques immédiates, cette recherche vise à réduire l'exposant de complexité, ω, rapprochant ainsi la multiplication matricielle de la valeur théorique idéale de 2. Ces progrès pourraient conduire à des temps de formation plus rapides pour les modèles d'IA, une exécution plus efficace des tâches, et potentiellement rendre les technologies d'IA plus accessibles en réduisant la puissance de calcul et la consommation d'énergie nécessaires. Bien que des limites actuelles existent, ces avancées représentent la plus grande amélioration dans le domaine depuis plus d'une décennie, ouvrant la voie à des modèles d'IA plus rapides et plus écoénergétiques à l'avenir.
En mathématiques, et plus particulièrement en algèbre linéaire, la multiplication matricielle est une opération binaire qui produit une matrice à partir de deux matrices. Pour une multiplication matricielle, le nombre de colonnes de la première matrice doit être égal au nombre de lignes de la seconde matrice. La matrice résultante, appelée produit matriciel, comporte le nombre de lignes de la première matrice et le nombre de colonnes de la seconde. Le produit des matrices A et B est noté AB.
La multiplication matricielle a été décrite pour la première fois par le mathématicien français Jacques Philippe Marie Binet en 1812 pour représenter la composition de cartes linéaires représentées par des matrices. La multiplication matricielle est donc un outil de base de l'algèbre linéaire et, en tant que tel, a de nombreuses applications dans de nombreux domaines des mathématiques, ainsi que dans les mathématiques appliquées, les statistiques, la physique, l'économie et l'ingénierie. Le calcul des produits matriciels est une opération centrale dans toutes les applications informatiques de l'algèbre linéaire.
En novembre dernier, trois chercheurs, à savoir Ran Duan et Renfei Zhou de l'université de Tsinghua, ainsi que Hongxun Wu de l'université de Californie à Berkeley, ont dévoilé des résultats innovants lors de la conférence Foundations of Computer Science. Bien que l'amélioration en question soit relativement modeste, François Le Gall l'a qualifiée de « conceptuellement plus importante que les précédentes », soulignant qu'elle révèle une source d'améliorations potentielles jusqu'alors non explorée. Ces découvertes ont été exploitées dans un second article publié en janvier, détaillant la manière dont la multiplication matricielle peut être encore optimisée grâce à cette approche novatrice.
« Il s'agit d'une avancée technique majeure », a déclaré William Kuszmaul, informaticien théoricien à l'université de Harvard. « C'est la plus grande amélioration de la multiplication matricielle que nous ayons vue depuis plus d'une décennie.
Plongez-vous dans la matrice
Cela peut sembler un problème obscur, mais la multiplication matricielle est une opération informatique fondamentale. Elle est incorporée dans une grande partie des algorithmes que les gens utilisent chaque jour pour toute une série de tâches, de l'affichage de graphiques informatiques plus nets à la résolution de problèmes logistiques dans la théorie des réseaux. Et comme dans d'autres domaines de l'informatique, la vitesse est primordiale. Même de légères améliorations pourraient éventuellement conduire à des économies significatives de temps, de puissance de calcul et d'argent. Mais pour l'instant, les théoriciens s'intéressent surtout à la rapidité du processus.
La méthode traditionnelle de multiplication de deux matrices n par n - en multipliant les nombres de chaque ligne de la première matrice par les nombres des colonnes de la seconde - nécessite n3 multiplications distinctes. Pour des matrices 2 par 2, cela représente 23 ou 8 multiplications.
En 1969, le mathématicien Volker Strassen a révélé une procédure plus compliquée permettant de multiplier des matrices 2 par 2 en seulement sept étapes multiplicatives et 18 additions. Deux ans plus tard, l'informaticien Shmuel Winograd a démontré que sept est effectivement le minimum absolu pour les matrices 2 par 2.
Strassen a exploité cette même idée pour montrer que toutes les grandes matrices n-par-n peuvent également être multipliées en moins de n3 étapes. Un élément clé de cette stratégie implique une procédure appelée décomposition, qui consiste à diviser une grande matrice en sous-matrices successivement plus petites, qui peuvent être aussi petites que 2 par 2 ou même 1 par 1 (il ne s'agit que de nombres simples).
Selon Virginia Vassilevska Williams, informaticienne au Massachusetts Institute of Technology et coauteur de l'un des nouveaux articles, la raison d'être de la division d'une matrice géante en minuscules morceaux est assez simple. « Il est difficile pour un humain de regarder une grande matrice (disons de l'ordre de 100 par 100) et de penser au meilleur algorithme possible », a déclaré Virginia Vassilevska Williams. Même les matrices de 3 x 3 n'ont pas encore été entièrement résolues. « Néanmoins, il est possible d'utiliser un algorithme rapide déjà développé pour les petites matrices afin d'obtenir un algorithme rapide pour les matrices plus grandes. »
La clé de la rapidité, ont déterminé les chercheurs, est de réduire le nombre d'étapes de multiplication, en abaissant l'exposant de n3 (pour la méthode standard) autant qu'ils le peuvent. La valeur la plus basse possible, n2, correspond en fait au temps qu'il faut pour écrire la réponse. Les informaticiens désignent cet exposant par le terme oméga, ω, nω étant le nombre le plus faible possible d'étapes nécessaires pour multiplier avec succès deux matrices n-par-n lorsque n devient très grand. « L'intérêt de ce travail, a déclaré Zhou, qui a également cosigné l'article de janvier 2024, est de voir à quel point il est possible de s'approcher de 2 et si c'est réalisable en théorie ».
Une focalisation laser
En 1986, Strassen a fait une autre grande percée en introduisant ce que l'on appelle la méthode laser pour la multiplication des matrices. Strassen l'a utilisée pour établir une valeur supérieure de 2,48 pour l'oméga. Bien que cette méthode ne soit qu'une étape dans les grandes multiplications matricielles, c'est l'une des plus importantes car les chercheurs ont continué à l'améliorer.
Un an plus tard, Winograd et Don Coppersmith ont introduit un nouvel algorithme qui complète admirablement la méthode laser. Cette combinaison d'outils a été utilisée dans pratiquement tous les efforts déployés par la suite pour accélérer la multiplication des matrices.
Voici une manière simplifiée de réfléchir à la manière dont ces différents éléments s'articulent. Commençons par deux grandes matrices, A et B, que nous voulons multiplier ensemble. Tout d'abord, vous les décomposez en plusieurs sous-matrices plus petites, ou blocs, comme on les appelle parfois. Ensuite, vous pouvez utiliser l'algorithme de Coppersmith et Winograd comme une sorte de manuel d'instructions pour manipuler et finalement assembler les blocs. « Il me dit ce qu'il faut multiplier et ce qu'il faut ajouter, et quelles entrées vont où » dans la matrice du produit C, a déclaré Vassilevska Williams. « C'est juste une recette pour construire C à partir de A et B. »
Mais il y a un hic : on se retrouve parfois avec des blocs qui ont des entrées en commun. Les laisser dans le produit reviendrait à les compter deux fois. Il faut donc, à un moment donné, se débarrasser de ces termes dupliqués, appelés chevauchements. Les chercheurs y parviennent en "tuant" les blocs dans lesquels ils se trouvent - en fixant leurs composantes à zéro pour les éliminer du calcul.
C'est là que la méthode du laser de Strassen entre enfin en jeu. « La méthode du laser fonctionne généralement très bien et trouve généralement un bon moyen de tuer un sous-ensemble de blocs pour éliminer le chevauchement », a déclaré Le Gall. Une fois que le laser a éliminé, ou « brûlé », tous les chevauchements, vous pouvez construire la matrice du produit final, C.
En combinant ces différentes techniques, on obtient un algorithme permettant de multiplier deux matrices avec un nombre de multiplications délibérément réduit - du moins en théorie. La méthode laser n'est pas destinée à être mise en pratique ; il s'agit simplement d'un moyen de réfléchir à la manière idéale de multiplier les matrices. « Nous n'exécutons jamais la méthode [sur un ordinateur], précise Zhou, nous l'analysons ». Et c'est cette analyse qui a conduit à la plus grande amélioration d'Oméga depuis plus d'une décennie.
Une perte est constatée
L'article publié l'été dernier par Duan, Zhou et Wu a montré que le processus de Strassen pouvait encore être accéléré de manière significative. Tout cela grâce à un concept qu'ils ont appelé « perte cachée », enfoui dans les analyses précédentes, « résultat de l'élimination involontaire d'un trop grand nombre de blocs », a déclaré Zhou.
La méthode du laser consiste à étiqueter les blocs qui se chevauchent comme des déchets, destinés à être éliminés ; d'autres blocs sont jugés dignes d'intérêt et seront sauvés. Le processus de sélection est toutefois quelque peu aléatoire. Un bloc classé comme déchet peut, en fait, s'avérer utile. Ce n'était pas une surprise totale, mais en examinant un grand nombre de ces choix aléatoires, l'équipe de Duan a déterminé que la méthode du laser sous-évaluait systématiquement les blocs : Plus de blocs devraient être conservés et moins jetés. Et, comme c'est généralement le cas, moins de déchets se traduit par une plus grande efficacité.
« Le fait de pouvoir conserver plus de blocs sans qu'ils se chevauchent conduit donc à un algorithme de multiplication matricielle plus rapide », explique Le Gall. Après avoir prouvé l'existence de cette perte, l'équipe de Duan a modifié la façon dont la méthode laser étiquetait les blocs, ce qui a permis de réduire considérablement le gaspillage. En conséquence, ils ont fixé une nouvelle limite supérieure pour omega à environ 2,371866 - une amélioration par rapport à la limite supérieure précédente de 2,3728596, fixée en 2020 par Josh Alman et Vassilevska Williams. Ce changement peut sembler modeste, puisqu'il n'abaisse la limite que d'environ 0,001. Mais il s'agit de l'amélioration la plus importante que les scientifiques aient connue depuis 2010. En comparaison, le résultat obtenu par Vassilevska Williams et Alman en 2020 n'améliorait son prédécesseur que de 0,00001.
Mais ce qui est le plus excitant pour les chercheurs, ce n'est pas seulement le nouveau record lui-même, qui n'a pas duré longtemps. C'est aussi le fait que l'article a révélé une nouvelle voie d'amélioration qui, jusqu'alors, était passée totalement inaperçue. Pendant près de quarante ans, tout le monde s'est appuyé sur la même méthode laser, explique Le Gall. « Ils ont alors découvert que nous pouvions faire mieux. »
Au-delà des limites : nouvelles perspectives dans la réduction de l'oméga pour l'optimisation des modèles d'IA
L'article de janvier 2024 a affiné cette nouvelle approche, permettant à Vassilevska Williams, Zhou et leurs coauteurs de réduire encore la perte cachée. Cela a conduit à une amélioration supplémentaire de la limite supérieure d'oméga, la ramenant à 2,371552. Les auteurs ont également généralisé cette même technique pour améliorer le processus de multiplication des matrices rectangulaires (n par m) - une procédure qui trouve des applications dans la théorie des graphes, l'apprentissage automatique et d'autres domaines.
Il est presque certain que de nouveaux progrès seront réalisés dans ce sens, mais il y a des limites. En 2015, Le Gall et deux collaborateurs ont prouvé que l'approche actuelle - la méthode laser couplée à la recette de Coppersmith-Winograd - ne peut pas donner un oméga inférieur à 2,3078. Selon Le Gall, pour obtenir d'autres améliorations, « il faut améliorer l'approche originale de Coppersmith et Winograd, qui n'a pas vraiment changé depuis 1987 ». Mais jusqu'à présent, personne n'a trouvé de meilleure méthode. Il se peut même qu'il n'y en ait pas.
« L'amélioration de l'oméga fait en fait partie de la compréhension de ce problème », a déclaré Zhou. « Si nous comprenons bien le problème, nous pourrons concevoir de meilleurs algorithmes. Or, on en est encore aux toutes premières étapes de la compréhension de ce problème séculaire. »
Ce travail met en lumière les récents progrès dans le domaine de la multiplication matricielle, mettant en avant leur capacité à accélérer les modèles d'intelligence artificielle. Ces découvertes sont saluées pour leur possible impact sur des aspects essentiels de l'IA, tels que la reconnaissance vocale, la vision par ordinateur et les chatbots. L'approche théorique adoptée dans cette étude, visant à réduire l'exposant de complexité ω, suggère des améliorations fondamentales susceptibles de rapprocher la multiplication matricielle de la valeur théorique idéale de 2.
Les implications de ces progrès sont considérables, offrant la perspective de temps de formation plus rapides pour les modèles d'IA, une exécution plus efficace des tâches, et la possibilité de rendre les technologies d'IA plus accessibles en réduisant la puissance de calcul et la consommation d'énergie nécessaires. Malgré les limites actuelles, ces avancées sont qualifiées de plus grandes améliorations dans le domaine depuis plus d'une décennie, laissant entrevoir des modèles d'IA futurs plus rapides et écoénergétiques. Cependant, des interrogations subsistent quant aux applications concrètes et à la nécessité de combiner ces avancées algorithmiques avec des optimisations matérielles pour pleinement exploiter leur potentiel.
Source : Tsinghua University and University of California at Berkeley, New Breakthrough Brings Matrix Multiplication Closer to Ideal
Et vous ?
Quel est votre avis sur le sujet ? Est-ce que les résultats présentés par les chercheurs concernant la multiplication matricielle, susceptibles d'aboutir à des modèles d'IA plus rapides et plus efficaces, sont pertinents ?Voir aussi :
Google DeepMind a utilisé un grand modèle de langage pour résoudre un problème mathématique insoluble « c'est une façon intéressante d'exploiter la puissance des LLM », déclare Terence Tao Un expert en informatique déclare que les programmeurs ont besoin de plus de mathématiques, ajoutant que les écoles devraient repenser la façon dont elles enseignent l'informatique