Ray Solomonoff

Ray Solomonoff (25 juillet 1926 – 7 décembre 2009) était un mathématicien américain qui a inventé la probabilité algorithmique , sa théorie générale de l'inférence inductive (également connue sous le nom d'inférence inductive universelle), et a été l'un des fondateurs de la théorie de l'information algorithmique . Il a été l'un des initiateurs de la branche de l'intelligence artificielle basée sur l'apprentissage automatique , la prédiction et les probabilités . Il a diffusé le premier rapport sur l'apprentissage automatique non sémantique en 1956.

Solomonoff a décrit pour la première fois la probabilité algorithmique en 1960, en publiant le théorème qui a lancé la complexité de Kolmogorov et la théorie de l'information algorithmique . Il a décrit ces résultats pour la première fois lors d'une conférence au Caltech en 1960, et dans un rapport, en février 1960, « A Preliminary Report on a General Theory of Inductive Inference ». Il a clarifié ces idées plus en détail dans ses publications de 1964, « A Formal Theory of Inductive Inference », partie I et partie II.

La probabilité algorithmique est une combinaison mathématiquement formalisée du rasoir d'Occam , et du principe des explications multiples. Il s'agit d'une méthode indépendante de la machine permettant d'attribuer une valeur de probabilité à chaque hypothèse (algorithme/programme) qui explique une observation donnée, l'hypothèse la plus simple (le programme le plus court) ayant la probabilité la plus élevée et les hypothèses de plus en plus complexes recevant des probabilités de plus en plus faibles.

Solomonoff a fondé la théorie de l'inférence inductive universelle , qui repose sur des fondements philosophiques solides et trouve son origine dans la complexité de Kolmogorov et la théorie de l'information algorithmique . La théorie utilise la probabilité algorithmique dans un cadre bayésien . La priorité universelle est reprise dans la classe de toutes les mesures calculables ; aucune hypothèse n'aura une probabilité nulle. Cela permet d' utiliser la règle de Bayes (de causalité) pour prédire l'événement suivant le plus probable dans une série d'événements, et sa probabilité.

Bien qu'il soit surtout connu pour les probabilités algorithmiques et sa théorie générale de l'inférence inductive , il a fait de nombreuses autres découvertes importantes tout au long de sa vie, la plupart d'entre elles orientées vers son objectif en intelligence artificielle : développer une machine capable de résoudre des problèmes difficiles en utilisant des méthodes probabilistes.

Ray Solomonoff est né le 25 juillet 1926 à Cleveland, dans l'Ohio , fils d'immigrants juifs russes Phillip Julius et Sarah Mashman Solomonoff. Il a fréquenté le lycée de Glenville, dont il a obtenu son diplôme en 1944. La même année, il s'est engagé dans la marine américaine en tant qu'instructeur en électronique. De 1947 à 1951, il a fréquenté l' université de Chicago , où il a étudié avec des professeurs tels que Rudolf Carnap et Enrico Fermi , et a obtenu une maîtrise en physique en 1951.

Dès son plus jeune âge, il fut motivé par la pure joie de la découverte mathématique et par le désir d'explorer des endroits où personne n'était allé auparavant. À l'âge de 16 ans, en 1942, il commença à chercher une méthode générale pour résoudre les problèmes mathématiques.

En 1952, il rencontre Marvin Minsky , John McCarthy et d’autres personnes intéressées par l’intelligence artificielle. En 1956, Minsky, McCarthy et d’autres organisent la Conférence d’été de recherche sur l’intelligence artificielle de Dartmouth , où Solomonoff est l’un des 10 premiers invités. Lui, McCarthy et Minsky sont les seuls à rester tout l’été. C’est pour ce groupe que l’intelligence artificielle a été pour la première fois désignée comme science. À l’époque, les ordinateurs pouvaient résoudre des problèmes mathématiques très spécifiques, mais pas grand-chose d’autre. Solomonoff voulait s’attaquer à une question plus vaste, à savoir comment rendre les machines plus intelligentes en général et comment les ordinateurs pourraient utiliser les probabilités à cette fin.

Il a écrit trois articles, dont deux avec Anatol Rapoport , entre 1950 et 1952, qui sont considérés comme la première analyse statistique des réseaux.

Il était l'un des 10 participants au projet de recherche d'été de Dartmouth de 1956 sur l'intelligence artificielle . Il a écrit et diffusé un rapport parmi les participants : « Une machine d'inférence inductive ». Il considérait l'apprentissage automatique comme probabiliste, en mettant l'accent sur l'importance des séquences d'entraînement et sur l'utilisation de parties de solutions précédentes aux problèmes dans la construction de solutions d'essai pour de nouveaux problèmes. Il a publié une version de ses découvertes en 1957. Ce furent les premiers articles à être écrits sur l'apprentissage automatique probabiliste.

À la fin des années 1950, il a inventé les langages probabilistes et leurs grammaires associées. Un langage probabiliste attribue une valeur de probabilité à chaque chaîne possible.

La généralisation du concept de grammaires probabilistes l'a conduit à sa découverte en 1960 de la probabilité algorithmique et de la théorie générale de l'inférence inductive.

Avant les années 1960, la méthode habituelle de calcul des probabilités était basée sur la fréquence : on prenait le rapport entre les résultats favorables et le nombre total d'essais. Dans sa publication de 1960, et, plus complètement, dans ses publications de 1964, Solomonoff a sérieusement révisé cette définition de la probabilité. Il a appelé cette nouvelle forme de probabilité « probabilité algorithmique » et a montré comment l'utiliser pour la prédiction dans sa théorie de l'inférence inductive. Dans le cadre de ce travail, il a posé les bases philosophiques de l'utilisation de la règle de causalité de Bayes pour la prédiction.

Le théorème de base de ce qui fut plus tard appelé la complexité de Kolmogorov faisait partie de sa théorie générale. En 1960, il écrit : « Considérons une très longue séquence de symboles… Nous considérerons une telle séquence de symboles comme « simple » et ayant une probabilité a priori élevée, s’il existe une description très brève de cette séquence – en utilisant, bien sûr, une sorte de méthode de description stipulée. Plus exactement, si nous n’utilisons que les symboles 0 et 1 pour exprimer notre description, nous attribuerons la probabilité 2 ^{− N} à une séquence de symboles si sa description binaire la plus courte possible contient N chiffres. »

La probabilité est en référence à une machine de Turing universelle particulière . Solomonoff a montré et prouvé en 1964 que le choix de la machine, bien qu'il puisse ajouter un facteur constant, ne changerait pas beaucoup les rapports de probabilité. Ces probabilités sont indépendantes de la machine.

En 1965, le mathématicien russe Kolmogorov a publié des idées similaires de manière indépendante . Lorsqu'il a pris connaissance des travaux de Solomonoff, il a reconnu Solomonoff, et pendant plusieurs années, les travaux de Solomonoff ont été mieux connus en Union soviétique que dans le monde occidental. Le consensus général dans la communauté scientifique était cependant d'associer ce type de complexité à Kolmogorov, qui était plus préoccupé par le caractère aléatoire d'une séquence. La probabilité algorithmique et l'induction universelle (de Solomonoff) ont été associées à Solomonoff, qui se concentrait sur la prédiction - l'extrapolation d'une séquence.

Plus tard dans la même publication de 1960, Solomonoff décrit son extension de la théorie du code le plus court. Il s'agit de la probabilité algorithmique. Il déclare : « Il semblerait que s'il existe plusieurs méthodes différentes pour décrire une séquence, chacune de ces méthodes devrait avoir un certain poids pour déterminer la probabilité de cette séquence. » Il montre ensuite comment cette idée peut être utilisée pour générer la distribution de probabilité universelle a priori et comment elle permet l'utilisation de la règle de Bayes dans l'inférence inductive. L'inférence inductive, en additionnant les prédictions de tous les modèles décrivant une séquence particulière, en utilisant des poids appropriés basés sur les longueurs de ces modèles, obtient la distribution de probabilité pour l'extension de cette séquence. Cette méthode de prédiction est depuis connue sous le nom d' induction de Solomonoff .

Il a élargi sa théorie en publiant un certain nombre de rapports menant aux publications de 1964. Les articles de 1964 donnent une description plus détaillée de la probabilité algorithmique et de l'induction de Solomonoff, présentant cinq modèles différents, y compris le modèle communément appelé la distribution universelle.

D'autres scientifiques présents à la conférence d'été de Dartmouth en 1956 (comme Newell et Simon ) développaient la branche de l'intelligence artificielle qui utilisait des machines régies par des règles de type « si-alors », basées sur des faits. Solomonoff développait la branche de l'intelligence artificielle axée sur les probabilités et les prédictions ; sa vision spécifique de l'IA décrivait des machines régies par la distribution de probabilité algorithmique. La machine génère des théories ainsi que leurs probabilités associées, pour résoudre des problèmes, et à mesure que de nouveaux problèmes et de nouvelles théories se développent, elle met à jour la distribution de probabilité sur les théories.

En 1968, il a trouvé une preuve de l'efficacité de la probabilité algorithmique , mais principalement en raison du manque d'intérêt général à l'époque, il ne l'a publiée que 10 ans plus tard. Dans son rapport, il a publié la preuve du théorème de convergence.

Dans les années qui ont suivi sa découverte de la probabilité algorithmique, il s'est concentré sur la manière d'utiliser cette probabilité et l'induction de Solomonoff dans la prédiction réelle et la résolution de problèmes pour l'IA. Il souhaitait également comprendre les implications plus profondes de ce système de probabilité.

Un aspect important de la probabilité algorithmique est qu’elle est complète et incalculable.

Dans son rapport de 1968, il montre que la probabilité algorithmique est complète ; c'est-à-dire que s'il existe une régularité descriptible dans un ensemble de données, la probabilité algorithmique découvrira éventuellement cette régularité, en nécessitant un échantillon relativement petit de ces données. La probabilité algorithmique est le seul système de probabilité connu à être complet de cette manière. En conséquence nécessaire de sa complétude, elle est incalculable . L'incomputabilité est due au fait que certains algorithmes - un sous-ensemble de ceux qui sont partiellement récursifs - ne peuvent jamais être évalués complètement car cela prendrait trop de temps. Mais ces programmes seront au moins reconnus comme des solutions possibles. D'un autre côté, tout système calculable est incomplet . Il y aura toujours des descriptions en dehors de l'espace de recherche de ce système, qui ne seront jamais reconnues ou prises en compte, même dans un laps de temps infini. Les modèles de prédiction calculables cachent ce fait en ignorant ces algorithmes.

Dans plusieurs de ses articles, il a décrit comment rechercher des solutions aux problèmes et, dans les années 1970 et au début des années 1980, il a développé ce qu'il considérait comme la meilleure façon de mettre à jour la machine.

L’utilisation des probabilités en IA n’a cependant pas été un parcours sans heurts. Dans les premières années de l’IA, la pertinence des probabilités était problématique. De nombreux membres de la communauté de l’IA pensaient que les probabilités n’étaient pas utilisables dans leur travail. Le domaine de la reconnaissance de formes utilisait une forme de probabilité, mais comme il n’existait pas de théorie générale sur la manière d’intégrer les probabilités dans un domaine de l’IA, la plupart des domaines ne l’utilisaient pas du tout.

Il y avait cependant des chercheurs comme Pearl et Peter Cheeseman qui soutenaient que les probabilités pouvaient être utilisées en intelligence artificielle.

Vers 1984, lors d'une réunion annuelle de l'Association américaine pour l'intelligence artificielle (AAAI), il a été décidé que la probabilité n'était en aucun cas pertinente pour l'IA

Un groupe de protestation s'est formé et, l'année suivante, un atelier a été organisé lors de la réunion de l'AAAI, consacré à « Probabilité et incertitude en IA ». Cet atelier annuel se poursuit jusqu'à aujourd'hui.

Dans le cadre de la protestation lors du premier atelier, Solomonoff a présenté un article sur la manière d'appliquer la distribution universelle aux problèmes d'IA Il s'agissait d'une première version du système qu'il a développé depuis lors.

Dans ce rapport, il décrit la technique de recherche qu'il a développée. Dans les problèmes de recherche, le meilleur ordre de recherche est le temps , où est le temps nécessaire pour tester l'essai et est la probabilité de succès de cet essai. Il appelle cela la « taille de saut conceptuel » du problème. La technique de recherche de Levin se rapproche de cet ordre, et Solomonoff, qui avait étudié le travail de Levin, a donc appelé cette technique de recherche Lsearch.

Dans d'autres articles, il a étudié comment limiter le temps nécessaire à la recherche de solutions, en écrivant sur la recherche limitée par les ressources. L'espace de recherche est limité par le temps disponible ou le coût de calcul plutôt que par la suppression de l'espace de recherche comme cela se fait dans d'autres méthodes de prédiction, telles que la longueur minimale de description.

Tout au long de sa carrière, Solomonoff s'est préoccupé des avantages et des dangers potentiels de l'IA, dont il a parlé dans plusieurs de ses rapports publiés. En 1985, il a analysé une évolution probable de l'IA, en donnant une formule prédisant quand elle atteindrait le « point d'infini ». Ce travail s'inscrit dans l'histoire de la pensée sur une possible singularité technologique .

À l'origine, les méthodes d'induction algorithmique extrapolaient des séquences ordonnées de chaînes de caractères. Des méthodes étaient nécessaires pour traiter d'autres types de données.

Un rapport de 1999, généralise la distribution universelle et les théorèmes de convergence associés aux ensembles de chaînes non ordonnés et un rapport de 2008, aux paires de chaînes non ordonnées.

En 1997, 2003 et 2006, il a montré que l'incomputabilité et la subjectivité sont des caractéristiques à la fois nécessaires et souhaitables de tout système à induction haute performance.

En 1970, il fonde sa propre entreprise, Oxbridge Research, et y poursuit ses recherches, à l'exception de périodes passées dans d'autres institutions telles que le MIT, l'Université de Sarre en Allemagne et l'Institut Dalle Molle d'intelligence artificielle à Lugano, en Suisse. En 2003, il est le premier lauréat du prix Kolmogorov décerné par le Computer Learning Research Center du Royal Holloway de l'Université de Londres, où il donne la conférence inaugurale Kolmogorov. Solomonoff était récemment professeur invité au CLRC.

En 2006, il a pris la parole à AI@50 , « Conférence sur l'intelligence artificielle de Dartmouth : les cinquante prochaines années », commémorant le cinquantième anniversaire du groupe d'étude d'été original de Dartmouth. Solomonoff était l'un des cinq participants originaux à y assister.

En février 2008, il a prononcé le discours d'ouverture de la conférence « Tendances actuelles dans la théorie et l'application de l'informatique » (CTTACS), qui s'est tenue à l'Université Notre Dame au Liban. Il a ensuite donné une courte série de conférences et a commencé des recherches sur de nouvelles applications de la probabilité algorithmique.

La probabilité algorithmique et l'induction de Solomonoff présentent de nombreux avantages pour l'intelligence artificielle. La probabilité algorithmique donne des estimations de probabilité extrêmement précises. Ces estimations peuvent être révisées par une méthode fiable afin qu'elles continuent d'être acceptables. Elle utilise le temps de recherche de manière très efficace. En plus des estimations de probabilité, la probabilité algorithmique « a pour l'IA une autre valeur importante : sa multiplicité de modèles nous donne de nombreuses façons différentes de comprendre nos données ;

Une description de la vie et du travail de Solomonoff avant 1997 est disponible dans « The Discovery of Algorithmic Probability », Journal of Computer and System Sciences, Vol 55, No. 1, pp 73–88, août 1997. L'article, ainsi que la plupart des autres mentionnés ici, sont disponibles sur son site Web à la page des publications.

Dans un article publié l'année de sa mort, un article de journal disait de Solomonoff : « Un scientifique très conventionnel comprend sa science en utilisant un seul « paradigme actuel » – la manière de comprendre la plus en vogue à l'heure actuelle. Un scientifique plus créatif comprend sa science de très nombreuses façons et peut plus facilement créer de nouvelles théories, de nouvelles façons de comprendre, lorsque le « paradigme actuel » ne correspond plus aux données actuelles ».