AlphaTensor accélère les calculs matriciels

L’engouement actuel autour du machine learning, et surtout du deep learning, marque le règne d’une forme de puissance brute sur la compréhension fine. Certains programmes sont efficaces, mais peu satisfaisant intellectuellement. AlphaTensor relève de cette catégorie.

Multiplier des tableaux de nombres est un sujet sérieux

Une équipe DeepMind de Google a sorti un papier qui présente un nouvel algorithme dit d'intelligence artificielle. AlphaTensor permet de trouver une méthode de calcul qui accélère certains produits matriciels. C’est un sujet compliqué, mais passionnant si aime les tableaux de nombres.

La multiplication de tableaux de nombres est un sujet important, surtout en grande dimension. La méthode simple qu’on apprend au lycée ne suffit pas pour multiplier des matrices de taille supérieure à 1000x1000. Des millions d’éléments à multiplier entre eux, ça donne des milliards d’opérations. C’est long. Même un processeur prendra un peu de temps, surtout si les nombres sont grands. Il devient donc judicieux d'utiliser des algorithmes un peu rusés.

Ce papier parle de multiplication de matrices. Une matrice est un tableau de nombres. On peut multiplier des matrices entre elles, pour obtenir d’autres matrices. C’est une base de l’algèbre linéaire, branche fondamentale des mathématiques. Dire que le calcul matriciel est très utilisé est un euphémisme : traitement d’image, simulation numérique, mais aussi physique quantique, relativité générale … On en trouve partout. C’est un sujet important, et tous les gains sont bons à prendre.

Les calculs finissent par être vraiment coûteux

Le calcul des produits matriciels est une opération centrale dans de nombreux algorithmes de calcul numérique. Ces calculs peuvent être gourmands en puissance de calcul, donc en temps. C’est un des problèmes les plus étudiés en calcul numérique.

On reste dans le cas de matrices carrées, avec n lignes et n colonnes. Au lycée, on apprend à multiplier deux matrices A et B avec un algorithme manuel, ou naïf. Il faut réaliser n³ multiplications de nombres et à peu près autant d’additions. Pour un processeur, la multiplication est nettement plus coûteuse que l’addition. C’est donc le nombre de multiplication qui définit la complexité du calcul. L’optimisation du calcul matriciel est ainsi une chasse aux multiplications.

On parle de grosses matrices, de taille n > 2¹⁰. En dessous, les coûts engendrés par les complications nécessaires de ces améliorations peuvent surpasser les bénéfices. Le lecteur intéressé par le sujet connexe de la multiplication de nombres trouvera son bonheur ici.

Deepmind a réalisé une jolie performance technique

Le papier écrit par une équipe de Deepmind montre deux choses.

1. Ils ont construit une méthode de calcul qui s’appuie sur un algorithme de reinforcement learning (RL). C’est une heuristique de recherche de solution dans un espace de très grande dimension

2. L’application de cette heuristique à la multiplication de matrices permet d’aboutir à de nouveaux résultats . La méthode proposée permet de découvrir des algorithmes de calculs au moins aussi efficaces que l’état de l’art. Et dans certains cas, plus efficaces. Bravo à eux.

Le RL est une technique d’apprentissage automatique par renforcement, avec des réseaux de neurones profonds. Un agent informatique, appelons-le Smith, tente de résoudre un problème qu’il ne connaît pas, en adoptant une démarche d’essais et erreurs. A chaque pas, on calcule ses progrès dans la résolution du problème, à l’aide de formules compliquées. S’il va dans la bonne direction, on le récompense. Sinon, on le flagelle un peu (numériquement). C’est un peu crétin, mais ça marche bien si on définit bien les choses. Et si on dispose de beaucoup de puissance de calcul. Car Smith va beaucoup se tromper.

C’est ce qu’a fait l’équipe de DeepMind. Ils ont transformé le problème de la multiplication de matrices en un horrible labyrinthe dans lequel ils ont lâché une ribambelle de Smiths. Ils les ont ensuite gaiement et astucieusement fouettés, jusqu’à ce que quelques-uns en sortent, avec un nouvel algorithme de calcul dans le sac à dos.

Intéressant, oui. Révolutionnaire, non

Cette équipe de DeepMind a donc trouvé une méthode astucieuse pour reformuler le problème de la multiplication de matrice sous la forme d’un jeu. La recherche de solution de ce jeu se prête bien à une approche par RL, qui fait grand usage de réseaux de neurones profonds. Autrement dit, ils ont canalisé une puissance de calcul brute et l’ont dirigée vers l'attaque d’un problème compliqué. Le tour de force tient, à mes yeux, dans la reformulation du problème. Le reste relève surtout de l’ingénierie des données, qu’on imagine réalisée avec brio et technicité. Ou avec moultes horreurs informatiques et un code encore tout à fait prototypal. On n’en sait rien, et ça n'est pas le sujet. 

L’exercice est sympathique. La méthode de calcul pourrait être transposable à d'autres problèmes compliqués, voire très compliqués (NP-hard). Les problèmes d’optimisation numérique chevelus ne manquent pas. Il serait intéressant de voir cette heuristique fonctionner sur d’autres cas. En ingénierie, on a d’abord besoin de solutions qui fonctionnent.

Un point me dérange. Mon prof de prépa n’aimait pas les astuces. Si une bonne astuce peut trivialiser un problème mathématique, ça n'est pas une stratégie gagnante. La résolution d’un problème passe par une compréhension profonde du résultat. Suis-je capable d’expliquer pourquoi la solution fonctionne ? Est-ce élégant ? À la rigueur, le chemin est plus important que la destination.

C’est une limite du papier. Il n’y a aucune démarche théorique digne de ce nom dans ce travail. L’approche par tenseur est classique. L’astuce vient de la formulation du problème pour le RL, mais on ne sait pas grand-chose de la solution trouvée par l'heuristique. Elle fonctionne, elle est performante, et c’est tout. Les différentes solutions exhibées sont-elles généralisables ? Sont-elles la manifestation d’une structure cachée ? La solution est-elle juste un enchaînement d’astuces ? Cet algorithme de calcul sera-t-il utilisé dans l’industrie ? N’est-ce qu’une curiosité de laboratoire ?

Au final, qu’a-t-on appris ?

Certains se demandent d’ailleurs si ce papier méritait un Nature. D’autant qu’il semble limité à un corps fini (ℤ/2ℤ) : pourquoi ? Ca ne marche pas pour des entiers ? De plus, il existe des algorithmes de calcul plus efficaces que Strassens (1969). Quid de la stabilité numérique ? Certains spécialistes sont sceptiques. D’autres se moquent.

L’intuition humaine n'est pas si mauvaise.

J'aimerais proposer une autre lecture de leur résultat, tendance techno-réac’. Malgré toute cette belle puissance de calcul, cette intelligence et cette technicité, les gains en performance sont minimes, voire nuls. L'intuition humaine et le raisonnement font jeu égal avec le silicium. C’est rassurant. Nous autres, êtres à cerveau mou, ne sommes pas si nuls.

A mes yeux, l’engouement actuel autour du machine learning, et surtout du deep learning, marque le règne d’une forme de puissance brute sur la compréhension fine. C’est efficace, mais peu satisfaisant intellectuellement.

Ceux qui veulent aller plus loin pourront lire une synthèse récente sur les avancées de multiplication de matrices.

Thomas