L'algèbre linéaire est la cause des progrès en intelligence artificielle depuis 70 ans
« La principale leçon que l’on peut tirer de 70 ans de recherche en IA, c’est que les méthodes générales qui exploitent la puissance de calcul sont en fin de compte les plus efficaces, et de loin. » Richard Sutton (2019)
Cette phrase ouvre le fameux billet de Dr Richard Sutton, the bitter lesson.
Richard Sutton travaille sur un certain type d’algorithmes d’apprentissage automatique : l’apprentissage par renforcement. Il conçoit des agents dont le but est de trouver des solutions à des problèmes complexes. Ces problèmes se situent souvent dans des espaces de grande dimension.
Le problème de la grande dimension
L’espace où nous vivons est structuré autour de quatre dimensions : longueur, largeur, hauteur et temps. Les physiciens des cordes modélisent plutôt cet espace avec une dizaine de dimensions, la plupart de ces dimensions échappant à notre perception.
En apprentissage automatique, on travaille régulièrement dans des espaces à plusieurs millions de dimensions. On parle communément de grande dimension. Les calculs deviennent bizarrement non intuitifs : le volume d'une sphère en grande dimension tend vers zero, les points sont presque tous au centre, le nombre de sphères voisines augmente drastiquement etc etc. L’optimisation numérique et l’exploration de données sont concernées. Tout le monde est concerné, en fait : jouer aux échecs, classer des images, engendrer des textes plausibles, gagner à 7 Wonders sont autant d’activités qui sont pratiquées dans des espaces à grande dimension.
La nature de ces espaces pose un tas de difficultés, notamment parce qu’il est difficile de se faire une idée de ce qu’il s’y passe. L’intuition ne suffit plus. Il faut faire son deuil de ce qui apparait naturel, comme souvent en mathématiques.
Pour attaquer ces problèmes, on doit recourir à des stratégies adaptées. Construire de tels algorithmes demande des compétences partagées entre différents domaines ardus dont les mathématiques appliquées, la simulation numérique, le calcul hautes performances et l’ingénierie logicielle. Pour obtenir des financements plus rapidement, et pour rendre le domaine un peu plus sexy, il a été décidé que ces programmes seraient « intelligents ». On parle donc d’intelligence artificielle depuis environ 2016~2018. Ces programmes ont vu leurs performances s’améliorer fortement depuis 70 ans.
Qui porte l'amélioration des performances ?
Une leçon essentielle et un peu amère à tirer de cette observation est la puissance des méthodes générales, capables de s'adapter à l'augmentation de lla puissance de calcul, même lorsqu'elles deviennent considérables. Parmi ces méthodes, la recherche et l'apprentissage (search and learn) semblent être les seules à en tirer pleinement profit. Richard Sutton (2019)
Richard Sutton soutient que l’augmentation de leurs performances est principalement due à l’amélioration d’un certain type d’algorithmes.
De manière contre-intuitive, l'augmentation de leurs performances n'est pas la conséquence de stratégies plus complexes. Elle est causée au contraire par des stratégies plus simples. Disons-le autrement : les algorithmes les plus efficaces sont les plus génériques ; on pourrait écrire qu'ils sont les plus simples ou les plus bêtes, mais ces termes ne sont pas adaptés. Ils ne reposent pas, ou peu, sur la compréhension humaine du problème à résoudre et sur les lois que des générations de chercheurs ont essayé d'extraire. Par contre, ils sont capables d'explorer efficacement les espaces en grande dimension pour déterminer, sans a priori, des solutions satisfaisantes.
Les algorithmes responsables de l'augmentation des performances depuis des dizaines d'années s'attaquent à une classe de problèmes génériques : l'algèbre linéaire. Les gains constatés concernant la multiplication de matrices carrées de taille un million sont autour de 400, avec un indice de complexité qui est passé de 2.81 à 2.38 entre 1969 et 1987. Cette variation n'est pas impressionnante si on oublie qu'il s'agit d'un exposant : les gains indicatifs en nombre d'opérations, et donc en temps de calcul sont de l'ordre de 1000 pour un million (106), 20000 pour un milliard (109), 389000 pour 1012 etc. Ces routines de calcul sont au coeur de nombreux problèmes numériques classiques en optimisation numérique, mais aussi dans le deep learning et les problèmes d’optimisation difficile comme la satisfaisabilité booléenne (SAT). La résolution de système linéaire a progressé d’un facteur plus important encore ; les ingénieurs sont heureux.
Amer ?
Ces algorithmes ont pu tirer profit de l’augmentation stupéfiante de la puissance de calcul en suivant la loi de Moore, d’une part, et en voyant une amélioration des méthodes de calculs, d’autre part. Il peut être amer, voire frustrant, de penser que l'intelligence humaine ne peut rien sans la puissance de calcul. D'une part, le processeur calcule vite, il faut bien se faire une raison. D'autre part, ce n'est pas ce que dit Sutton. Ça tombe bien.
Sutton nous enseigne qu'il est plus efficace d'exprimer le problème à résoudre sous une forme qui peut être traitée par une certaine classe d'outils mathématiques : l'algèbre linéaire.