Leslie Gabriel Valiant (né le 28 mars 1949) est un informaticien et théoricien de la computation britannico-américain, actuellement professeur T. Jefferson Coolidge d'informatique et de mathématiques appliquées à l'université Harvard. Il est surtout connu pour avoir introduit le modèle d'apprentissage Probably Approximately Correct (PAC), qui a fondé le domaine de la théorie de l'apprentissage computationnel et est devenu une base théorique pour apprentissage automatique. Il a également introduit le concept de #P-complétude en théorie de la complexité et le modèle Bulk Synchronous Parallel (BSP) pour le calcul parallèle. L'Association for Computing Machinery lui a décerné le prix A.M. Turing 2010, le décrivant comme une « figure héroïque » de l'informatique théorique pour sa « combinaison frappante de profondeur et d'ampleur » dans l'adresse de problèmes profonds non résolus en science.
Valiant est né d'un père ingénieur chimiste et d'une mère traductrice. Il a poursuivi ses études supérieures au King's College de Cambridge, à l'Imperial College de Londres et à l'université de Warwick, où il a obtenu un doctorat en informatique en 1974. Avant de rejoindre Harvard en 1982, il a occupé des postes académiques à l'université d'Édimbourg, à l'université de Leeds et à Carnegie Mellon University.
Théorie de la complexité et #P-complétude
En 1977, Valiant a introduit la classe de complexité #P (Sharp-P) pour classer les problèmes de comptage et d'énumération, tels que le calcul du permanent d'une matrice ou le comptage des couplages dans un graphe. Ses travaux ont établi la #P-complétude comme une notion fondamentale en théorie de la complexité, expliquant pourquoi de nombreux problèmes de fiabilité et d'énumération sont computationnellement intraîtables malgré le fait qu'ils soient des problèmes de décision faciles à vérifier. Cette contribution a remodelé la façon dont les théoriciens comprennent la difficulté des problèmes au-delà des simples tâches de décision.
Apprentissage PAC et théorie de l'apprentissage computationnel
En 1984, Valiant a défini un cadre pour l'apprentissage inductif qui combinait la faisabilité computationnelle avec l'applicabilité à des classes de règles logiques non triviales. Ce cadre, appelé plus tard apprentissage Probably Approximately Correct (PAC), a formalisé comment un apprenant peut généraliser à partir d'un nombre limité d'échantillons tout en tolérant une petite probabilité d'erreur. L'apprentissage PAC a fourni une base théorique pour apprentissage automatique, abordant des questions sur la complexité des échantillons et la traîtabilité computationnelle. Son livre de 2013 Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World a étendu ces idées, soutenant que les algorithmes d'apprentissage sous-tendent non seulement l'informatique mais aussi l'évolution et la cognition. Dans ce livre, il a soutenu que la biologie évolutive manque d'un compte rendu adéquat du taux d'évolution et de sa capacité à développer des mécanismes complexes sous des environnements changeants, malgré l'exactitude globale du schéma de Darwin.
Éducation et début de carrière
Valiant a étudié au King's College de Cambridge et à l'Imperial College de Londres avant de compléter un doctorat en informatique à l'université de Warwick en 1974. Ses premiers travaux en théorie des automates ont produit un algorithme pour l'analyse syntaxique hors contexte qui reste le plus rapide asymptotiquement connu. Il a également été un pionnier dans l'utilisation des propriétés des graphes pour analyser les calculs, reliant la théorie structurelle des graphes à l'efficacité algorithmique.
Contributions au calcul
Les recherches de Valiant couvrent plusieurs domaines de l'informatique théorique. Il a introduit la notion de #P-complétude pour expliquer pourquoi les problèmes d'énumération et de fiabilité sont intraîtables, avec la première application étant la fonction permanente de matrice. En 1984, il a proposé le modèle d'apprentissage PAC, qui a fourni une définition rigoureuse de l'apprentissage à partir d'exemples et est devenu fondamental pour intelligence artificielle. Il a également développé des algorithmes holographiques, inspirés du calcul quantique, et a fait des contributions précoces à la théorie des automates avec un algorithme d'analyse syntaxique hors contexte qui reste le plus rapide asymptotiquement connu. Dans les années 1990, Valiant a formulé le modèle Bulk Synchronous Parallel (BSP), analogue au modèle de von Neumann mais pour les architectures parallèles ; il a influencé des systèmes tels que Google's Pregel et Beam, et des projets open source comme Hadoop et Spark.
Éducation et carrière académique
Valiant a étudié au King's College de Cambridge, puis à l'Imperial College de Londres, et a reçu son doctorat en informatique de l'université de Warwick en 1974. Il a enseigné à l'université d'Édimbourg puis à Carnegie Mellon University avant de rejoindre l'université Harvard en 1982, où il est resté depuis. À Harvard, il a travaillé en informatique théorique et en neurosciences computationnelles, se concentrant sur la compréhension des processus de mémoire et d'apprentissage.
Apprentissage PAC et apprentissage automatique
L'introduction du modèle PAC par Valiant en 1984 a formalisé les conditions sous lesquelles un apprenant peut généraliser à partir d'un ensemble fini d'exemples. Ce cadre a réconcilié la faisabilité computationnelle avec l'apprentissage de règles logiques - il est devenu une pierre angulaire de la théorie de l'apprentissage computationnel et a influencé le développement de systèmes pratiques d'intelligence artificielle. Son livre de 2013 Probably Approximately Correct a étendu ces idées à la biologie et à l'évolution, soutenant que la théorie évolutive actuelle n'explique pas adéquatement le taux de progrès évolutif et que la théorie de l'apprentissage offre des analogies utiles.
Calcul parallèle et distribué
Le modèle Bulk Synchronous Parallel de Valiant, introduit en 1990, fournit un pont entre le matériel et le logiciel pour le calcul parallèle en organisant l'exécution en super-étapes avec synchronisation par barrière. Le modèle a influencé les systèmes de traitement distribué tels que Pregel de Google et les projets open source Apache Giraph, Apache Hama, Apache Beam et Dask. Ses travaux antérieurs au Xerox PARC dans des contextes adjacents et ses recherches académiques ultérieures ont posé les bases des moteurs d'analyse de graphes évolutifs utilisés dans les centres de données modernes.
Prix et distinctions
Valiant a reçu le prix Nevanlinna en 1986, le prix Knuth en 1997, le prix EATCS en 2008 et le prix A.M. Turing en 2010. Il a été élu Fellow de la Royal Society (FRS) en 1997 et membre de l'Académie nationale des sciences des États-Unis. Sa citation pour le prix Turing a reconnu ses contributions transformatrices à la théorie de l'apprentissage PAC, à la complexité de l'énumération et du calcul algébrique, et à la théorie du calcul parallèle et distribué.
Vie personnelle
Valiant est marié et a deux fils, Gregory Valiant et Paul Valiant, tous deux informaticiens. Gregory travaille sur les algorithmes et les statistiques à l'université Stanford, et Paul travaille sur la complexité computationnelle et la cryptographie. La famille de Valiant partage son dévouement à l'informatique théorique, avec les deux fils contribuant au domaine dans leurs propres recherches.