Prédire…

Dans cet article, Max Dauchet, professeur émérite d’informatique, met à notre portée la notion de « prédiction » telle que proposée en informatique théorique. Tandis que dès le lycée on formalise la notion de prédiction à travers les probabilités (est prédictible ce qui va fort probablement arriver), on peut utiliser les algorithmes pour proposer une autre vision de ce qui est prédictible, à lui de nous l’expliquer. Serge Abiteboul et Thierry Viéville.

Prédire est difficile, surtout quand il s’agit de l’avenir.
Niels Bohr, Pierre Dac, et bien d’autres…

Prédire…

Nous essayons tout le temps de prédire, radio-trafic prédit les embouteillages, la météo le temps, les sondeurs le prochain chef d’état et nous l’humeur de notre voisin de bureau. Prédire fait même partie du métier de chercheur. Encore faut-il prédire correctement, et nous tombons rarement d’accord, le contraire se verrait en politique, et les « vérités alternatives » ne prospéreraient pas. Les chercheurs, eux, ont une règle qui marche bien : favoriser les hypothèses simples sans en négliger aucune.
Depuis qu’il y a des philosophes, ils réfléchissent à des règles pour prévoir juste. Les religieux aussi, car jadis, c’étaient souvent les mêmes. L’histoire a retenu Guillaume d’Ockham^[1] et son rasoir : « Pluralitas non est ponenda sine necessitate  », rasons le superflu qui nous éloigne de la vérité de Dieu – c’est une formulation dans les termes scolastiques du 14e siècle.
De nos jours, la règle d’Ockham balise toujours la recherche sous le nom de principe de parcimonie, sur lequel  les chercheuses et chercheurs s’accordent, se basant sur des notions « de cause possible » plus tangibles que Dieu.

C’est ici qu’intervient l’objet de ce billet, le théorème de convergence de Ray Solomonoff.

« Toutes les mesures universelles convergent^[2] vers les mêmes prédictions. »

Cet énoncé inspire aussi peu celui qui ne parle pas couramment les maths, que celui d’Ockham pour qui ne parle pas latin. Il est peu connu en dehors d’un cercle de spécialistes, car il est mathématiquement plutôt ardu et souvent présenté dans sa gangue technique.
Avant de l’expliquer, signalons que Lê Nguyên Hoang, jeune et talentueux startuper et youtubeur dont Serge vantait récemment le dernier ouvrage^[3], y a consacré un livre de 400 pages intitulé «  La formule du savoir », rien que ça !
Pour Marvin Minsky, un père fondateur de l’informatique, « Ray Solomonoff’s discovery of Induction, Algorithmic Probability, is the most important discovery in philosophy of science since Gödel »^[4]. En effet, c’est en transposant, dans un cadre formel rigoureux, les questions qui hantaient les philosophes que Gödel et Solomonoff obtiennent leurs résultats fondateurs. 

Le cadre formel rigoureux est celui du monde numérisé, des algorithmes et des data, les algorithmes sont les causes (ce qui évite de se poser la question de l’existence de Dieu …) et les data sont les processus que l’on observe ; l’inférence consiste à prédire la suite d’un processus avec une certaine probabilité.

Un exemple : à « 1 ; 2 ; 4 ; 8 ; 16 ; 32 ; ? » tout le monde répond avec assurance « 64 » en pensant au simple et court « fois 2 » : le processus observé semble régi par un algorithme simple. Au contraire, à pile ou face, les tirages antérieurs ne permettent en rien de prédire le tirage suivant.

Solomonoff munit d’une mesure de probabilité l’ensemble des programmes (peu importe le langage informatique utilisé pour les écrire). Assez simplement, une  telle mesure reflète une « conception du monde » où l’on accorde plus ou moins de vraisemblance à telle ou telle cause, et où (par supposé bon sens ou par parti pris) on veut en ignorer certaines (il suffit de leur attribuer une probabilité nulle). Tout le monde pouvait avoir cette idée simple. La grande idée de Solomonoff  est l’introduction d’un ensemble particulier de mesures, les mesures universelles, dont les propriétés sont remarquables. Elles ont une définition mathématique précise, qui englobe le principe du rasoir d’Ockham, et prennent pour critère de simplicité la longueur des programmes. La mère de ces mesures est la mesure de Solomonoff, à la base de la « belle formule de Ray » pour les processus.

Le théorème dit donc que toutes les « conceptions du monde » convergent vers les mêmes prédictions au fil des observations, pourvu qu’elles « tiennent compte de toutes les hypothèses, notamment des plus simples ».

On ne rase pas gratis.

Cette limite commune à toutes les mesures universelles est parfois qualifiée de vraie, car elle satisfait tout ce que la science sait des processus stochastiques, et elle se vérifie expérimentalement autant que l’on parvienne à mener à bien des calculs, car rien de tout cela  n’est calculable mais seulement approximable^[5] (c’est l’indécidabilité de l’arrêt des programmes, établie par Turing en même temps qu’il imaginait sa machine, qui empêche ces calculs, du reste sinon, on disposerait d’une machine à prédire universelle, ce qui n’est pas possible).

De Bayes au lycée à Solomonoff.

L’inférence de Solomonoff est la transposition, dans le monde numérique, de l’inférence bayésienne vue au lycée avec des urnes et des boules. Un exemple simple à la croisée des deux illustre qu’une mesure non universelle peut converger vers une absurdité.

L’urne A contient 2 fois plus de boules rouges que de bleues, et la B 2 fois plus de bleues que de rouges. On tire infiniment dans la même urne, on ne sait pas laquelle, en remettant chaque fois la boule dans l’urne. On ne tire que des rouges. La chose est peu probable, mais la formule de Bayes nous dit qu’il est infiniment plus probable qu’elle se produise en tirant dans A. Le coup d’après, on s’attend donc à avoir 2 fois plus de chances de tirer une rouge qu’une bleue. Tout observateur doué de raison, qui observe les tirages sans rien savoir du procédé, se demandera pourquoi seulement 2 sur 3, alors qu’il s’attendra à ce que la suivante soit presque à coup sûr rouge, et Solomonoff lui donnera raison : pour obtenir la bonne prédiction, il faut considérer tous les algorithmes en accordant l’essentiel du poids aux plus simples, et « sortir des rouges » est l’explication la plus simple.

Le dindon de Sir Bertrand Russel.

On attribue au célèbre philosophe l’histoire du dindon qui, chaque jour, se réjouit davantage de la venue du fermier qui l’engraisse. Jusqu’à Noël. Le dindon n’avait pas envisagé l’hypothèse que l’heureuse routine puisse s’arrêter un jour.

La formule du savoir.

Sans verser dans des débats ontologiques et épistémologiques, ces prédictions seraient « le savoir » et le théorème « sa formule » comme le titre Hoang. La question mérite en tous cas d’être discutée, au moins comme exercice de pensée. D’autant que ce résultat vaut si l’on se restreint à un sous-ensemble d’algorithmes (une sorte de sous-univers) : toutes les mesures universelles relativement à ce sous-univers convergent vers les mêmes prédictions (qui sont en général différentes de celles universelles). 

On peut alors se dire que chaque sous-univers est une bulle d’opinion dont les adeptes convergent vers des vérités relatives. Ces dernières sont des vérités alternatives face à une vérité qui les domine toutes, celle de la connaissance scientifique des savants qui, eux, examinent avec parcimonie tous les algorithmes. À ce compte on peut aussi se dire que cette connaissance scientifique n’est elle-même que relative à l’espèce humaine, car celle-ci est limitée par ses sens et ses instruments dans l’observation des phénomènes, et limitée par les choix sélectifs darwiniens de son espèce. Ces derniers ont structuré notre cortex en sous-estimant ou en ignorant les hypothèses qui ne servaient à rien (d’où nos biais cognitifs). Épisodiquement, un article paraît sur le sujet, surtout dans la mouvance informatique car les philosophes ne comprennent pas le théorème ; Nick Bostrom l’évoque néanmoins dans « Superintelligence ».

Un spot sur l’IA ?

Les débats font à nouveau rage cet automne, les distributeurs d’IA alertent sur les capacités mal maîtrisées de leurs créations, les médias amplifient les déclarations sans en comprendre le fond. Cela a commencé en 2016^[6] avec lesdits « coups de Dieu » d’AlphaGo contre Lee Sedol jusqu’aux cyberattaques récentes de Mythos^[7] ou de ChatGPT^[8]. À se demander si les IA sont de mystérieuses entités émergentes qui s’affranchissent des humains, ou seulement des paquets d’algorithmes dont nous ne maîtrisons pas les capacités. Ce sont des capacités algorithmiques que nous ne contrôlons pas, nous les avons conçues pour qu’elles explorent d’autres algorithmes, et elles en explorent certains que nous n’imaginions pas. Si ce sont des aliens, c’est au sens de machines qui traitent, à une échelle gigantesque, d’« autres » algorithmes.

L’inférence de Solomoff nous enseigne en effet que la capacité de prédiction découle de la capacité à traiter tous les algorithmes. Les IA en explorent beaucoup, en ajustant leurs milliards de paramètres au fil de l’apprentissage et des échanges entre elles, alors que nous, les humains, en imaginons peu, bridés par notre rationalité, la plupart des programmes possibles n’ayant aucun sens pour nous. Les IA empruntent des chemins algorithmiques de traverse, auxquels notre logique ne nous fait pas penser. C’est peut-être pourquoi elles nous semblent créatives, voire, selon certains, suspectes d’émancipation. Quoi qu’il en soit, ce point de vue souligne la difficulté de garantir l’alignement d’une IA (la certitude qu’elle se comporte comme nous l’attendons) sans trop la brider, et la nécessité de le faire.

Pour en savoir plus

Le site de Solomonoff (in memoriam) et celui de Levin, décoiffants, fournissent les bonnes références historiques. La « bible » dans le domaine est l’ouvrage de Li et Vitanyi, il est régulièrement mis à jour. Le site Science4all de Hoang foisonne de vidéos enthousiastes à la gloire de Solomonoff. Enfin, vos LLM favoris vous aideront dans vos recherches de références et dans l’articulation des idées, à utiliser avec un sens critique de tous les instants, bien entendu. 

L’article Prédire… est apparu en premier sur Blog binaire.