Skip navigation.
Home

Book Review: Probably Approximately Correct by Leslie Valiant

How does life prosper in a complex and erratic world? We know that it does, but how, exactly? In this book Dr. Valiant attempts to sketch out an answer to this question.

A core meme presented here is the idea of an "ecorithm" - a portmanteau combining "ecology" and "algorithm." An ecorithm is therefore an algorithm that operates in ecological environments - described here as an environment unknown to the algorithm or its designer - but which learns how to prosper in the environment by interacting with it. An ecorithm acquires expertise extracted from the environment it operates in as opposed to more conventional algorithms which have expertise designed in.

Valient proposes a model of how these ecorithms learn which he labels the Probably Approximately Correct (PAC) model and argues "that such learning mechanisms impose and determine the character of life on Earth."

Note what is being claimed here - that computation (specifically algorithmic learning) forms the underpinning of our intelligence, learning, and evolution itself. Evolution is driven by computation. This perspective is probably easier for computer scientists (and electrical engineers such as myself!) to appreciate than say a philosopher or artist.

Much of life is what the author describes as 'theoryless' - for example there is no theory that tells us how to navigate social situations, but most us manage to muddle through anyhow. By contrast, much of science is 'theoryful' - such as Einstein's theory of relativity. A good theory predicts the behavior of some set of actions. Theoryless life, by contrast, has no theory to operate on, but it does have experience.

The 'theoryful' domain is seen to be relatively simple, often expressible as a mathematical formula. By contrast, the area of interest that is 'theoryless' is often very complex, with no underlying or understood structure to help us navigate it. And yet, we manage - which leads to the concept so central to the book of being Probably Approximately Correct.

If intelligence, learning, and evolution are fundamentally computation then we need to understand computation at its most basic level. The author reviews the pivotal contributions of Alan Turing, who provided us with the needed insight. Turing revolutionized our understanding of computation, introducing the Turing machine, (a simple model of computation that can compute anything that is, in fact, computable), and the shocking truth that some even well defined programs will never terminate - thus defining "noncomputability."

The book shows that even among computable problems there is a practicality constraint that we need to consider - how many steps are needed to reach an answer? If we are dealing with N items and a computation takes on the order of N**k steps (written as O[N**k]) the computation is termed polynomial in time. If it takes O(k**N) the computation is termed exponential in time. Computations that are exponential in time are not practical for even modest N - a computer performing a trillion steps per second would take 30 billion years to perform 10**30 steps. The class of problems that can be computed in polynomial time is the class of practical problems - meaning that whatever the details of the Probably Approximately Correct algorithms might be, they must certainly be at least as efficient as polynomial in time.

Although the book has no examples of Probably Approximately Correct ecorithms, it does outline the characteristics that such algorithms would have to have, such as being polynomial in time and not requiring an overly complex substrate to perform the computations.

Until humans came on the scene life evolved subject to a balance or equilibrium between Darwinian evolution and the (limited) learning algorithms (ecorithms) of organisms. Evolution remained the principal source of adaptations to the world and environment. Humans have shifted the equilibrium in favor of ecorithms - which are now hastening the speed of change and having a much larger impact than the plodding pace of Darwinian evolution. We preserve the creations and knowledge of each generation, and use that inheritance to build on in the next - creating an exponential rate of change.

Darwinian evolution offers a truly grand view of life on Earth - life that has resulted from a simple evolutionary mechanism. When and if we gain an understanding of the ecorithms that, according to the author, underpin life and evolution itself, the view will be grander yet, for we will begin to bring our very nature into the realm of science.

Recommended.