Main driver for advances in artificial intelligence is computing power
Computing has been shaking the world since the 1950s. The computational power has drastically increased. The efficiency of algorithms too. Ready to scale the orders of magnitude?
70 Years of Progress
« The biggest lesson that can be read from 70 years of AI research is that general methods that leverage computation are ultimately the most effective, and by a large margin. » Richard Sutton (2019)
Renforcement
Richard Sutton works on a certain type of machine learning algorithms: reinforcement learning.
You've heard about it.
It's one of the buzzwords of recent years.
A technique used by major language models (LLM) including OpenAI's ChatGPT.
These systems use a variant of this type of learning.
They have coined a new name for it: RLHF.
RLHF
No, it's not a new rapper.
RLHF: Reinforcement Learning from Human Feedback.
Behind this barbaric acronym hides a somewhat questionable practice.
And yet common.
Who annotates the large datasets? Who decides if this video is problematic? Who judges the performance of algorithms? Not programs, obviously. There are many, these men and women, toiling to improve the performance of the machine. Often in developing countries.
For ridiculously low prices.
In short.
A technology also has social consequences. It's important to keep this point in mind.
Well, the post.
Richard Sutton was born in 1949.
He is Canadian.
He designs agents.
These are programs.
Their goal is to find solutions to complex problems.
These agents evolve in mathematical spaces, whose rules are defined by the problem to be solved. These problems are often located in high-dimensional spaces.
Dimensions
The space we live in is structured around four dimensions: length, width, height, and time. Insufficient for physicists specializing in string theory. They model the universe with about ten dimensions. Most are beyond our perception.
In mathematics, we regularly work in spaces with many dimensions. When objects are images, their number far exceeds a million. We thus speak of high-dimensional space.
Examples
Playing chess.
Classifying images.
Generating plausible texts.
Winning at games.
Also, more technical subjects like numerical optimization, data exploration, and machine learning. Solving these problems requires positioning oneself in high-dimensional spaces.
Intuition Is Not Enough
High dimensionality poses a host of difficulties.
The elements are predominantly isolated, far from each
We talk about sparse spaces.
It is difficult to get an idea of what is happening there.
Even vaguely.
Human intuition is no longer sufficient.
Dry or Sexy
To solve these problems, we must resort to complex programs that use appropriate strategies. Building such programs requires skills shared between different fields: applied mathematics, numerical simulation, high-performance computing. And a lot of software engineering. The whole thing is quite dry. To make the subject sexier, we've been talking about data science and intelligent programs since ~2015. It sounds a bit more impressive for securing funding.
Strategies
What are the strategies used in these programs capable of working in high dimension?
We don't play chess as we play go.
We don't build Deep Blue like AlphaGo.
One might expect complicated strategies, finely adapted to the problems to be solved...?
That's not quite true. The most effective algorithms are often less specialized. That's one of the lessons of the last decades. And it's at the heart of Richard Sutton's thesis.
Go read his post: the bitter lesson.
Research
These efficient search algorithms are capable of efficiently exploring high-dimensional spaces to identify satisfactory solutions with relatively few biases.
It may seem quite paradoxical.
The efficient search algorithms are thus quite dumb.
They rely on simple search strategies.
They do not rely on a human understanding of the problem.
Who are they?
Linear Algebra
They are algorithms that exploit linear algebra methods.
There are numerous linear algebra problems.
Mention can be made of matrix calculation and the solving of linear systems.
Or difficult optimization problems like boolean satisfiability (SAT).
They are often encountered in operational research.
Performance gains over the last 70 years are measured in orders of magnitude.
The gains are well beyond a million, even a billion.
We count the zeros.
These algorithms have been able to take advantage of the astounding increase in computing power following Moore's Law, on one hand, and seeing an improvement in calculation methods, on the other.
The Lesson
This is the lesson Richard Sutton draws from the last 70 years in artificial intelligence, whose progress is intimately linked to the advances made in solving general problems in linear algebra.
It upsets people.
Bref.
Une technologie a aussi des conséquences sociales.
Il faut garder ce point en tête.
Bon, le billet.
Richard Sutton est né 1949.
Il est canadien.
Il conçoit des agents.
Ce sont des programmes.
Leur but est de trouver des solutions à des problèmes complexes.
Ces agents évoluent dans des espaces mathématiques, dont les règles sont définies par le problème à résoudre.
Ces problèmes se situent souvent dans des espaces de grande dimension.
Dimensions
L’espace où nous vivons est structuré autour de quatre dimensions : longueur, largeur, hauteur et temps.
C'est insuffisant pour les physiciens spécialistes de la théorie des cordes.
Ils modélisent plutôt l'univers avec une dizaine de dimensions. La plupart échappent à notre perception.
En mathématiques, on travaille régulièrement dans des espaces avec de nombreuses dimensions. Quand les objets sont des images, leur nombre dépasse largement le million.
On parle ainsi d'espace à grande dimension.
Des exemples
Jouer aux échecs.
Classer des images.
Engendrer des textes plausibles.
Gagner à 7 Wonders.
...
Citons aussi des sujets plus techniques comme l'optimisation numérique, l'exploration de données et l'apprentissage automatique.
Résoudre ces problèmes nécessite de se placer dans des espaces à grande dimension.
L'intuition ne suffit plus
La grande dimension pose un tas de difficultés.
Les éléments sont majoritairement isolés, éloignés les uns des autres.
On parle d'espaces creux.
Il est difficile de se faire une idée de ce qu’il s’y passe.
Même vaguement.
L’intuition humaine ne suffit plus.
Sec / sexy
Pour résoudre ces problèmes, on doit recourir à des programmes complexes qui utilisent des stratégies adaptées.
Construire de tels programmes demande des compétences partagées entre différents domaines : mathématiques appliquées, simulation numérique, calcul hautes performances.
Et beaucoup d’ingénierie logicielle.
L'ensemble est assez sec.
Pour rendre le sujet plus sexy, on parle de data science et de programmes intelligents depuis ~2015.
Ca claque un peu plus pour obtenir des financements
Stratégies
Quelles sont les stratégies utilisées dans ces programmes capable de travailler en grande dimension ?
On ne joue pas aux échecs comme on joue au go.
On ne construit pas Deep Blue comme AlphaGo.
On pourrait s'attendre à des stratégies compliquées, finement adaptées aux problèmes à résoudre ... ?
Ca n'est pas tout à fait vrai.
Les algorithmes les plus efficaces sont souvent moins spécialisés.
C'est une des leçons des dernieres décennies.
Et c'est le coeur de la thèse de Richard Sutton. _
Allez lire son billet : la leçon amère.
Recherche
Ces algorithmes de recherche efficaces sont capables d'explorer efficacement les espaces en grande dimension pour identifier des solutions satisfaisantes avec assez peu de préjugés.
Ca peut paraitre assez paradoxal.
Les algorithmes de recherche efficaces sont donc assez bêtes.
Ils s'appuient sur des stratégies de recherche simples.
Ils ne s'appuient pas sur une compréhension humaine du problème.
Qui sont-ils ?
Algèbre linéaire
Ce sont des algorithmes qui exploitent des méthodes d'algèbre linéaire.
Les problèmes d'algèbre linéaire sont nombreux.
Citons le calcul matriciel et la résolution de système linéaire.
Ou les problèmes d’optimisation difficile comme la satisfaisabilité booléenne (SAT).
On en croise souvent en recherche opérationnelle.
Les gains en performances depuis 70 ans se comptent en ordre de grandeur.
Les gains sont largement au delà du million, voire du milliard.
On compte les zeros.
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.
La leçon
C’est la leçon que tire Richard Sutton des 70 dernières années en intelligence artificielle, dont les progrès sont intimement liés aux progrès réalisés sur la résolution de problèmes généraux en algèbre linéaire.