Leslie Gabriel Valiant (* 28. März 1949) ist ein britisch-amerikanischer Informatiker und Theoretiker der Informatik, derzeit T. Jefferson Coolidge Professor für Informatik und Angewandte Mathematik an der Harvard University. Bekannt wurde er vor allem durch die Einführung des Probably-Approximately-Correct-Modells (PAC) des Lernens, das das Feld der Theorie des maschinellen Lernens begründete und eine theoretische Grundlage für maschinelles Lernen schuf. Er führte außerdem das Konzept der #P-Vollständigkeit in der Komplexitätstheorie und das Bulk-Synchronous-Parallel-Modell (BSP) für paralleles Rechnen ein. Die Association for Computing Machinery verlieh ihm 2010 den A.M. Turing Award und beschrieb ihn als "heroische Figur" der theoretischen Informatik für seine "beeindruckende Kombination aus Tiefe und Breite" bei der Bearbeitung tiefgreifender ungelöster Probleme in der Wissenschaft.
Valiant wurde als Sohn eines Chemieingenieurs und einer Übersetzerin geboren. Er absolvierte seine höhere Ausbildung am King's College in Cambridge, am Imperial College London und an der University of Warwick, wo er 1974 in Informatik promovierte. Bevor er 1982 nach Harvard wechselte, hatte er akademische Positionen an der University of Edinburgh, der University of Leeds und der Carnegie Mellon University inne.
Komplexitätstheorie und #P-Vollständigkeit
1977 führte Valiant die Komplexitätsklasse #P (Sharp-P) ein, um Zähl- und Aufzählungsprobleme zu klassifizieren, wie die Berechnung der Permanenten einer Matrix oder das Zählen von Matchings in einem Graphen. Seine Arbeit etablierte die #P-Vollständigkeit als grundlegendes Konzept in der Komplexitätstheorie und erklärte, warum viele Zuverlässigkeits- und Aufzählungsprobleme rechnerisch unlösbar sind, obwohl es sich um Entscheidungsprobleme handelt, die leicht zu verifizieren sind. Dieser Beitrag veränderte das Verständnis von Theoretikern darüber, wie schwierig Probleme über einfache Entscheidungsaufgaben hinaus sind.
PAC-Lernen und Theorie des maschinellen Lernens
1984 definierte Valiant einen Rahmen für induktives Lernen, der rechnerische Machbarkeit mit der Anwendbarkeit auf nicht-triviale Klassen logischer Regeln verband. Dieser Rahmen, später als Probably Approximately Correct (PAC)-Lernen bezeichnet, formalisierte, wie ein Lernender aus einer begrenzten Anzahl von Stichproben verallgemeinern kann, während eine kleine Fehlerwahrscheinlichkeit toleriert wird. PAC-Lernen lieferte eine theoretische Grundlage für maschinelles Lernen und behandelte Fragen zur Stichprobenkomplexität und rechnerischen Durchführbarkeit. Sein Buch Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World aus dem Jahr 2013 erweiterte diese Ideen und argumentierte, dass Lernalgorithmen nicht nur dem Rechnen, sondern auch der Evolution und Kognition zugrunde liegen. In dem Buch vertrat er die Ansicht, dass die Evolutionsbiologie keine angemessene Erklärung für die Geschwindigkeit der Evolution und ihre Fähigkeit, unter sich verändernden Umgebungen komplexe Mechanismen zu entwickeln, bietet, obwohl Darwins Schema insgesamt korrekt ist.
Ausbildung und frühe Karriere
Valiant studierte am King's College in Cambridge und am Imperial College London, bevor er 1974 an der University of Warwick in Informatik promovierte. Seine frühen Arbeiten zur Automatentheorie führten zu einem Algorithmus für kontextfreies Parsing, der bis heute der asymptotisch schnellste bekannte ist. Er war auch ein Pionier bei der Verwendung von Grapheneigenschaften zur Analyse von Berechnungen und verband strukturelle Graphentheorie mit algorithmischer Effizienz.
Beiträge zur Berechnung
Valiants Forschung umfasst mehrere Bereiche der theoretischen Informatik. Er führte das Konzept der #P-Vollständigkeit ein, um zu erklären, warum Aufzählungs- und Zuverlässigkeitsprobleme unlösbar sind, wobei die erste Anwendung die permanente Funktion der Matrix war. 1984 schlug er das PAC-Lernmodell vor, das eine rigorose Definition des Lernens aus Beispielen lieferte und grundlegend für künstliche Intelligenz wurde. Er entwickelte auch holografische Algorithmen, die von der Quantenberechnung inspiriert waren, und leistete frühe Beiträge zur Automatentheorie mit einem Algorithmus für kontextfreies Parsing, der bis heute der asymptotisch schnellste bekannte ist. In den 1990er Jahren formulierte Valiant das Bulk-Synchronous-Parallel-Modell (BSP), das analog zum Von-Neumann-Modell, aber für parallele Architekturen ist; es hat Systeme wie Googles Pregel und Beam sowie Open-Source-Projekte wie Hadoop und Spark beeinflusst.
Ausbildung und akademische Karriere
Valiant studierte am King's College in Cambridge, dann am Imperial College London und erhielt 1974 seinen Doktortitel in Informatik von der University of Warwick. Er lehrte an der University of Edinburgh und dann an der Carnegie Mellon University, bevor er 1982 an die Harvard University wechselte, wo er seitdem geblieben ist. In Harvard arbeitete er in der theoretischen Informatik und der computergestützten Neurowissenschaft, mit Schwerpunkt auf dem Verständnis von Gedächtnis- und Lernprozessen.
PAC-Lernen und maschinelles Lernen
Valiants Einführung des PAC-Modells im Jahr 1984 formalisierte die Bedingungen, unter denen ein Lernender aus einer endlichen Menge von Beispielen verallgemeinern kann. Dieser Rahmen versöhnte rechnerische Machbarkeit mit dem Lernen logischer Regeln - er wurde zu einem Eckpfeiler der Theorie des maschinellen Lernens und beeinflusste die Entwicklung praktischer Systeme der künstlichen Intelligenz. Sein Buch Probably Approximately Correct aus dem Jahr 2013 erweiterte diese Ideen auf Biologie und Evolution und argumentierte, dass die aktuelle Evolutionstheorie die Geschwindigkeit des evolutionären Fortschritts nicht angemessen erklärt und dass die Lerntheorie nützliche Analogien bietet.
Paralleles und verteiltes Rechnen
Valiants Bulk-Synchronous-Parallel-Modell, eingeführt 1990, bietet eine Brücke zwischen Hardware und Software für parallele Berechnungen, indem es die Ausführung in Supersteps mit Barrierensynchronisation organisiert. Das Modell beeinflusste verteilte Verarbeitungssysteme wie Googles Pregel und die Open-Source-Projekte Apache Giraph, Apache Hama, Apache Beam und Dask. Seine früheren Arbeiten in Kontexten rund um Xerox PARC und spätere akademische Forschung legten den Grundstein für skalierbare Graphanalyse-Engines, die in modernen Rechenzentren verwendet werden.
Auszeichnungen und Ehrungen
Valiant erhielt 1986 den Nevanlinna-Preis, 1997 den Knuth-Preis, 2008 den EATCS-Preis und 2010 den A.M. Turing Award. Er wurde 1997 zum Fellow der Royal Society (FRS) und zum Mitglied der National Academy of Sciences der Vereinigten Staaten gewählt. Die Begründung für seinen Turing Award würdigte seine transformativen Beiträge zur Theorie des PAC-Lernens, zur Komplexität von Aufzählungs- und algebraischen Berechnungen sowie zur Theorie des parallelen und verteilten Rechnens.
Persönliches Leben
Valiant ist verheiratet und hat zwei Söhne, Gregory Valiant und Paul Valiant, die beide Informatiker sind. Gregory arbeitet an Algorithmen und Statistik an der Stanford University, und Paul arbeitet an rechnerischer Komplexität und Kryptographie. Valiants Familie teilt seine Hingabe zur theoretischen Informatik, wobei beide Söhne mit ihrer eigenen Forschung zum Feld beitragen.