Leslie Gabriel Valiant (nascut el 28 de març de 1949) és un científic informàtic i teòric computacional britànic-estatunidenc, actualment professor T. Jefferson Coolidge d'Informàtica i Matemàtiques Aplicades a la Universitat de Harvard. És conegut principalment per introduir el model d'aprenentatge Probablement Aproximadament Correcte (PAC), que va fundar el camp de la teoria de l'aprenentatge computacional i es va convertir en una base teòrica per a l'aprenentatge automàtic. També va introduir el concepte de #P-completesa en teoria de la complexitat i el model Bulk Synchronous Parallel (BSP) per a la computació paral·lela. L'Association for Computing Machinery li va atorgar el Premi Turing A.M. 2010, descrivint-lo com una "figura heroica" en informàtica teòrica per la seva "combinació sorprenent de profunditat i amplitud" en abordar problemes profunds no resolts en la ciència.
Valiant va néixer d'un pare enginyer químic i una mare traductora. Va cursar estudis superiors al King's College de Cambridge, l'Imperial College de Londres i la Universitat de Warwick, on va obtenir un doctorat en informàtica el 1974. Abans d'incorporar-se a Harvard el 1982, va ocupar càrrecs acadèmics a la Universitat d'Edimburg, la Universitat de Leeds i la Universitat Carnegie Mellon.
Teoria de la complexitat i #P-completesa
El 1977, Valiant va introduir la classe de complexitat #P (Sharp-P) per classificar problemes de comptatge i enumeració, com ara calcular el permanent d'una matriu o comptar aparellaments en un graf. El seu treball va establir la #P-completesa com una noció fonamental en teoria de la complexitat, explicant per què molts problemes de fiabilitat i enumeració són computacionalment intractables tot i ser problemes de decisió fàcils de verificar. Aquesta contribució va remodelar com els teòrics entenen la dificultat dels problemes més enllà de les simples tasques de decisió.
Aprenentatge PAC i teoria de l'aprenentatge computacional
El 1984, Valiant va definir un marc per a l'aprenentatge inductiu que combinava la viabilitat computacional amb l'aplicabilitat a classes de regles lògiques no trivials. Aquest marc, anomenat posteriorment aprenentatge Probablement Aproximadament Correcte (PAC), va formalitzar com un aprenent pot generalitzar a partir d'un nombre limitat de mostres tot tolerant una petita probabilitat d'error. L'aprenentatge PAC va proporcionar una base teòrica per a l'aprenentatge automàtic, abordant qüestions sobre la complexitat de mostres i la tractabilitat computacional. El seu llibre de 2013 Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World va estendre aquestes idees, argumentant que els algoritmes d'aprenentatge sustenten no només la informàtica sinó també l'evolució i la cognició. En el llibre, va sostenir que la biologia evolutiva no té un relat adequat de la taxa d'evolució i de la seva capacitat per desenvolupar mecanismes complexos sota entorns canviants, malgrat la correcció general de l'esquema de Darwin.
Educació i carrera inicial
Valiant va estudiar al King's College de Cambridge i a l'Imperial College de Londres abans de completar un doctorat en informàtica a la Universitat de Warwick el 1974. El seu treball inicial en teoria d'autòmats va produir un algoritme per a l'anàlisi sintàctica lliure de context que continua sent el més ràpid asimptòticament conegut. També va ser pioner en l'ús de propietats de grafs per analitzar càlculs, vinculant la teoria estructural de grafs amb l'eficiència algorítmica.
Contribucions a la computació
La recerca de Valiant abasta múltiples àrees de la informàtica teòrica. Va introduir la noció de #P-completesa per explicar per què els problemes d'enumeració i fiabilitat són intractables, amb la primera aplicació sent la funció permanent de matrius. El 1984 va proposar el model d'aprenentatge PAC, que va proporcionar una definició rigorosa de l'aprenentatge a partir d'exemples i es va convertir en fonamental per a la intel·ligència artificial. També va desenvolupar algoritmes hologràfics, inspirats en la computació quàntica, i va fer contribucions primerenques a la teoria d'autòmats amb un algoritme d'anàlisi sintàctica lliure de context que continua sent el més ràpid asimptòticament conegut. Als anys noranta, Valiant va formular el model Bulk Synchronous Parallel (BSP), anàleg al model de von Neumann però per a arquitectures paral·leles; ha influït en sistemes com Pregel i Beam de Google, i projectes de codi obert com Hadoop i Spark.
Educació i carrera acadèmica
Valiant va estudiar al King's College de Cambridge, després a l'Imperial College de Londres, i va rebre el seu doctorat en informàtica de la Universitat de Warwick el 1974. Va ensenyar a la Universitat d'Edimburg i després a la Universitat Carnegie Mellon abans d'incorporar-se a la Universitat de Harvard el 1982, on ha romàs des d'aleshores. A Harvard, ha treballat en informàtica teòrica i neurociència computacional, centrant-se en comprendre els processos de memòria i aprenentatge.
Aprenentatge PAC i aprenentatge automàtic
La introducció del model PAC per part de Valiant el 1984 va formalitzar les condicions sota les quals un aprenent pot generalitzar a partir d'un conjunt finit d'exemples. Aquest marc va reconciliar la viabilitat computacional amb l'aprenentatge de regles lògiques - es va convertir en una pedra angular de la teoria de l'aprenentatge computacional i va influir en el desenvolupament de sistemes pràctics de intel·ligència artificial. El seu llibre de 2013 Probably Approximately Correct va estendre aquestes idees a la biologia i l'evolució, argumentant que la teoria evolutiva actual no explica adequadament la taxa de progrés evolutiu i que la teoria de l'aprenentatge ofereix analogies útils.
Computació paral·lela i distribuïda
El model Bulk Synchronous Parallel de Valiant, introduït el 1990, proporciona un pont entre maquinari i programari per a la computació paral·lela organitzant l'execució en superpassos amb sincronització de barrera. El model va influir en sistemes de processament distribuït com Pregel de Google i els projectes de codi obert Apache Giraph, Apache Hama, Apache Beam i Dask. El seu treball anterior en contextos adjacents a Xerox PARC i la recerca acadèmica posterior van establir les bases per a motors d'anàlisi de grafs escalables utilitzats en centres de dades moderns.
Premis i honors
Valiant va rebre el Premi Nevanlinna el 1986, el Premi Knuth el 1997, el Premi EATCS el 2008 i el Premi Turing A.M. el 2010. Va ser elegit Fellow de la Royal Society (FRS) el 1997 i membre de l'Acadèmia Nacional de Ciències dels Estats Units. La seva citació del Premi Turing va reconèixer les seves contribucions transformadores a la teoria de l'aprenentatge PAC, la complexitat de l'enumeració i el càlcul algebraic, i la teoria de la computació paral·lela i distribuïda.
Vida personal
Valiant està casat i té dos fills, Gregory Valiant i Paul Valiant, tots dos informàtics. Gregory treballa en algoritmes i estadística a la Universitat de Stanford, i Paul treballa en complexitat computacional i criptografia. La família de Valiant comparteix la seva dedicació a la informàtica teòrica, ambdós fills contribuint al camp amb la seva pròpia recerca.