Leslie Valiant and PAC Learning

Abstract

Leslie Valiant (born 1949), a Budapest-born British computer scientist at Harvard since 1982, gave machine learning its first mathematical definition. His 1984 paper “A Theory of the Learnable” defined probably approximately correct (PAC) learning: an algorithm learns a concept if, from a number of examples and an amount of computation that grow only polynomially, it produces a rule that is, with high probability, approximately right on new examples. Colleagues at first asked him whether he was serious; the definition became the foundation of computational learning theory. Before that, Valiant had shown in 1979 that counting can be far harder than deciding, defining the complexity class #P and proving that computing the permanent of a matrix is as hard as any counting problem. In 1990 he proposed the bulk synchronous parallel model for programming parallel computers. He received the Turing Award for 2010.

Leslie Valiant at the ACM Turing Centenary Celebration, June 2012. Image: Dennis Hamilton, CC BY 2.0, via Wikimedia Commons.

Budapest, London, Cambridge

Leslie Gabriel Valiant was born in Budapest on 28 March 1949. His father was a chemical engineer and his mother, who was good at languages, worked as a translator; he has an older sister who became a physicist. The family moved to England, and his schooling was divided between the north-east, at Tynemouth High School in North Shields, and London, where he finished at Latymer Upper School in Hammersmith. His parents, he recalled in 2017, never gave him directions or even suggestions, “but I think they made it clear what they respected.”

As a boy he built transistor radios, model planes and rockets, and a thermometer from a bottle, a little tube and a drop of water, fascinated that the experiment worked however he built it. In a five-month gap before his final school examinations, a teacher found him a job in a medical physics laboratory at a London medical school. He decided there that he did not want to be an experimental physicist, and in his last two weeks he wrote his first program, probably in ALGOL, on green punched paper tape, to compute correlations. “It didn’t strike me as what I was going to do for the rest of my life.”

He read mathematics at King’s College, Cambridge, graduating in 1970. Turing had been a student and fellow at King’s, but Valiant never heard of him there; years later he found Sara Turing’s book about her son in a library and was shocked to read on the first page that he had gone to King’s. After a one-year diploma in computing at Imperial College London, he read a paper by Mike Paterson on computability and discovered, he said, “the depth of Turing’s computability theory,” which struck him as “a rather particularly novel and staggering comment on the limits of our intellectual capabilities.” He went to the University of Warwick, where Paterson became his supervisor, and wrote a doctoral thesis in 1974 on deciding whether two deterministic pushdown automata, the stack machines used in compilers, accept the same language. He never resolved it and proved special cases, which he later considered good training: there was no stock of techniques, and he had to develop his own.

Faster Than Cubic

After a year as a visiting assistant professor at Carnegie Mellon (1973–74), a lectureship at Leeds and a move to Edinburgh in the mid-1970s (he became a reader there in 1981), Valiant made his first widely noticed discovery. Volker Strassen had shown in 1969 that matrices can be multiplied faster than the schoolbook method by using identities invented for the purpose. Valiant saw that the problem of recognizing whether a string belongs to a context-free language, the kind of grammar used to define programming languages, could be reduced to matrix multiplication. His 1975 paper “General Context-Free Recognition in Less than Cubic Time” gave the asymptotically fastest known algorithm for the problem, and it still is.

He remembered the moment vividly. “This is like poetry, but it’s more constrained,” he thought: one had to create a new image within tight rules. He had drawn a diagram from just the right angle; and for several days afterwards he was unsure whether the result was right at all.

Counting

The question that occupied Valiant in the mid-1970s was why linear algebra, which can apparently do an exponential number of things at once, cannot solve NP-complete problems (see P vs NP and Complexity Theory). Its central object is the determinant of a matrix, which can be computed quickly by Gaussian elimination. The permanent is defined by almost the same formula, with all the minus signs replaced by plus signs, and nobody knew a fast way to compute it. At a workshop around 1976 the combinatorialist Dominic Welsh told him that a fast reduction of the permanent to the determinant would be publishable. Valiant went the other way.

In “The Complexity of Computing the Permanent” (Theoretical Computer Science, 1979) and “The Complexity of Enumeration and Reliability Problems” (SIAM Journal on Computing, 1979) he defined #P (“sharp P”), the class of problems that ask not whether a solution exists but how many solutions there are, and showed that computing the permanent of a 0-1 matrix is #P-complete, as hard as any problem in the class. The permanent of such a matrix counts the perfect matchings of a bipartite graph, so the result had a startling consequence: deciding whether a graph has a perfect matching is easy, but counting its perfect matchings is as hard as counting the solutions of any NP problem. Until then complexity theorists had assumed that the decision version of a problem captured its difficulty. When Valiant explained the result to a well-known colleague on a train to a conference, the reply was: “Oh, something must be wrong here.”

Counting turned out to be everywhere. Computing the reliability of a network, the probability of an event, or an integral in many dimensions are counting problems. Approximate counting and random sampling became a field of their own, connecting computer science with statistics and statistical physics, and Seinosuke Toda later showed that a polynomial-time machine that can consult a #P oracle solves every problem in the entire polynomial hierarchy. With his student Carl Sturtivant, Valiant also noticed that the permanent is the function that describes the quantum state of a set of bosons in physics, a physical quantity that is #P-hard to compute, years before anyone spoke of quantum computers. In 1986 he and Vijay Vazirani showed that NP is no easier when a problem is promised to have at most one solution.

Routing and BSP

In parallel computing, Valiant’s first contribution was about communication. If many processors exchange packets over a network in which each wire can carry one packet at a time, the time until the last packet arrives determines when the next step can start. His solution, published in 1982 as “A Scheme for Fast Parallel Communication,” was to randomize: send each packet first to a random intermediate node, then to its destination. Once stated, he said, the idea seemed so obvious that one wondered why nobody had thought of it; he had reached it by a long series of technical steps.

The second came from frustration. At a meeting on parallel computing in California in late 1988 he felt that all the important things had been said but nobody had put them together, and the field was crowded with competing models of parallel machines. Writing a survey chapter for the Handbook of Theoretical Computer Science, he tried to find efficient simulations between the models, and one model kept appearing in the middle. In “A Bridging Model for Parallel Computation” (Communications of the ACM, August 1990) he described it as bulk synchronous parallel (BSP) computation: processors compute locally, exchange messages, and then all wait at a barrier before the next “superstep,” with the machine characterized by a few parameters for communication bandwidth and synchronization cost. He meant it to play the role for parallel computers that the von Neumann model plays for sequential ones: a pragmatic standard between hardware and software that survives changes of technology. The model had wide influence on how parallel computation is conceptualized and carried out (see Concurrency and Parallelism).

A Theory of the Learnable

Valiant arrived at Harvard in 1982 as Gordon McKay Professor of Computer Science and Applied Mathematics. In the year or two before his best-known paper, he became intensely interested in cognition. Looking at the proceedings of an artificial intelligence conference, with its sessions on planning, search, reasoning and learning, he asked which of these was fundamental, and decided that it was learning. The learning studied in AI at the time, in the tradition of Newell and Simon (see Newell and Simon: The Thinking Machines), was mostly not statistical: a program compiled its past experience to do the same thing better next time. Statistics, on the other hand, had a theory of inference but said nothing about computation. “Why isn’t statistics enough?” was how Valiant put the question to himself. What was missing was a quantitative answer to the questions: when do you have enough data, and when enough computation?

“A Theory of the Learnable,” presented at the ACM Symposium on Theory of Computing in 1984 and published in Communications of the ACM in November 1984, answered with a definition. A learner sees examples drawn at random from some unknown distribution, each labelled according to an unknown rule from a known class (for example, all Boolean formulas of a certain form). The class is PAC-learnable if there is an algorithm that, for any distribution and any target rule, uses a number of examples and an amount of computation polynomial in the problem size and in 1/ε and 1/δ, and outputs a rule that, with probability at least 1 − δ, disagrees with the target on at most a fraction ε of future examples. “Probably” refers to δ, “approximately” to ε. The definition made learning a problem of computational complexity: whether a class can be learned depends on both the number of examples and the computation needed.

The paper’s proofs were deliberately elementary, the kind of argument that people outside the theory community could follow. “In my mathematical papers, the interest is in the proof,” Valiant said, “but in some of these, the interest is in the definitions.” The reception was sceptical. At the conference where he presented it, a friendly colleague came up to show that he was on Valiant’s side and asked: “Are you serious?” In the theory community, Valiant recalled, a rigorous theory of learning had been thought absurd.

The definition did what he had hoped. A group of theoretical computer scientists took it up, and the research area it founded is now called computational learning theory; the model was extended by others into a tool for practical applications. In 2017 Valiant said that the deep-learning systems that now fill the newspapers are good “exactly” at supervised learning in the statistical sense of PAC, though nobody yet understands why their particular algorithms work so well (see Geoffrey Hinton and Deep Learning).

The Brain and Evolution

Soon after the PAC paper Valiant turned the same approach to the brain. His book Circuits of the Mind (1994) asked how a network of neurons with realistic numbers of connections and synaptic strengths could store new memories and associations at the speed people do. The constraint he found most useful was communication: long-distance signalling in the brain is stylized, spikes travelling along axons, while local computation in neurons and synapses is very diverse. Even with a simple learning rule, he noted, nobody knows whether yesterday’s lunch is remembered by ten neurons or a million.

In 2009 he published “Evolvability” in the Journal of the ACM, treating Darwinian evolution as a restricted form of learning, in which variation is a randomized algorithm and selection acts only on aggregate performance, and asked which kinds of functions could evolve in realistic numbers of generations. His popular book Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World (2013) brought the two themes together for a general readership. In 2004 he had also introduced holographic algorithms, which solve some counting problems in polynomial time through cancellations reminiscent of quantum interference.

Recognition

Valiant received the Nevanlinna Prize of the International Mathematical Union in 1986, was elected a Fellow of the Royal Society in 1991 and of the American Association for Artificial Intelligence in 1992, received the Knuth Prize in 1997, was elected to the US National Academy of Sciences in 2001 and became T. Jefferson Coolidge Professor at Harvard the same year, and received the European Association for Theoretical Computer Science Award in 2008. The ACM gave him the Turing Award for 2010 “for transformative contributions to the theory of computation, including the theory of probably approximately correct (PAC) learning, the complexity of enumeration and of algebraic computation, and the theory of parallel and distributed computing.” Both of his sons, Gregory and Paul Valiant, became theoretical computer scientists.

Asked in 2017 whether PAC learning had been the first attempt to bring the theory of computation to bear on a natural phenomenon, Valiant answered that it was probably at least the second. Before Turing, he said, computing had been a human activity that nobody thought could be formalized; Turing’s definition was so successful that “now we forget even what ‘computing’ meant before his time.” He had thought that learning was ripe for the same treatment.