Your complimentary articles

You’ve read one of your four complimentary articles for this month.

You can read four articles free per month. To have complete access to the thousands of philosophy articles on this site, please

SUBSCRIBE NOW

Books

Probably Approximately Correct by Leslie Valiant

Joshua Schrier is approximately correct, probably.

“All by nature desire to know,” said Aristotle, in one of his less contentious remarks. Epistemology is the study of the validity and scope of methods aiming to satisfy that desire to know, including how one distinguishes between knowledge and mere opinion. Being able to make reliable inferences and deductions is quite useful, so epistemology has been central not only to the Western tradition of philosophy but to philosophy globally (For classic non-Western examples, see the Nyaya Sutras, or the works of Dignaga). Also, philosophers of mind as well as religious apologists debate how the capacity to learn (or for that matter, any rational faculties) could possibly emerge from an entirely undirected, that is, irrational, evolutionary process. Computer science may provide new insights into all these philosophical problems, by discovering fundamental limits to the sorts of processes by which a system can learn to predict its environment. I’m not talking about the recent computer programs that can outperform human experts at chess, Go, poker, diagnosing illnesses, or predicting chemical reactions. It has been quipped that computer science is neither about computers (the electronic gadgets themselves) nor a science (no laboratory). Rather, theoretical computer science is more akin to mathematics and formal logic, consisting of formal proofs of how processes behave, independent of any particular hardware or software implementation. In this book, Leslie Valiant, the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University, presents a readable introduction to his work on ‘probably approximately correct’ learning algorithms – PACs.

The robots are still coming.
Robot © Marcin Wichary 2009

Most decision-making algorithms are carefully designed to never make mistakes. In contrast, PACs are less stringent, allowing for noisy input data and somewhat faulty, ‘good enough’ outputs. ‘Probably approximately correct’ quantifies the extent to which a learning process with no underlying theory about the problem, finite computational resources and limited access to data, can make inferences. PAC systems also allow one to diagnose how a learner can fail. For instance, a given task may be fundamentally too random to be learned; or it may be too complex to extract a prediction even in principle, even if there were perfect information; or the learner may be using the wrong algorithm or data. Moreover, what PACs tell us is not limited to the particular physical or biological mechanism by which the learning process occurs. Instead it can place bounds on the types of problems any physical system with finite resources can perform, including human brains. Evolution is by its nature theoryless (as Valiant puts it, one can find a mate without having a theory of mating), so the PAC model lends itself to studying evolutionary ‘ecorithms’.

One of Valiant’s major scholarly contributions (and the topic of Chapter 6) is indeed the description of evolution as a restricted class of probably approximately correct learning algorithms in or by which a population learns to respond to its environment. The limited types of evolutionary processes each individual can perform (for example, having reproductive success, or not dying), and ways populations can learn from the environment (for example, through mutations in DNA), limit the types of learning tasks that evolution can perform. Framing evolution as a computational problem enables proofs that rely only on very general limits concerning the computational complexity of what organisms can perform and the types of feedback they can receive. Valiant’s conclusions are more general than typical biological treatments of evolution, as they do not rely upon any particular physical mechanisms.

Chapter 7 focuses on the classical epistemological topics of deduction and induction as viewed through this ‘probably approximately correct’ lens. Valiant argues that deductive logic, including probabilistic modelling and computer programming, is fragile. In other words, there is no guarantee that the answer will be correct if the underlying theoretical model is incorrect. In contrast, inductive learning – that is, learning from repeated experience – can occur in the absence of any theory. PAC-style induction can quantify the uncertainty of the predictions one generates from experience, and can even provide some guide to its own predictive accuracy for theoryless problems. This provides an interesting twist on Hume’s critique of induction as having no ultimate theoretical justification (although Valiant does not pursue this).

Chapter 8 makes some appropriately cautious speculations about the implications of PAC for human cognition. Probably approximately correct learning algorithms can establish a continuum of learning (or broadly characterised, ‘thinking’) capabilities that encompasses the whole natural world, through what Aristotelian or Scholastic philosophers would have called the vegetative and animal faculties, up to rational human capabilities. Valiant even claims that he can use PAC to establish the mathematical inevitability of materialistic, undirected evolutionary processes resulting in a rational faculty. Moreover, the limits on energy, time, and memory in a PAC process also give insight into the origins of the cognitive biases and logical fallacies so prevalent in human thinking.

Why might this book be interesting for philosophers? Valiant engages with epistemology and theory of mind only in passing, making a few nods towards the usual suspects – Sextus Empiricus, Aristotle’s Posterior Analytics, and Ockham’s Razor – without drawing out many of the philosophical implications. However, a philosophically inclined reader will find many other ways PAC might illuminate classic problems. For example, Valiant criticizes philosophical thought experiments on the grounds that probably approximately correct learning only works if the data one learns from is generally representative of what one is trying to predict. Thought experiments violate this condition by generally considering unusual cases; therefore PAC predicts human reason to perform poorly on them. For instance, consider the famous sorites problem: how many grains make a heap? Since our previous experiences of heap- and not-heap-like piles are very distinct, attempting to classify an intermediate pile is ill-defined: it violates the ‘representative data’ assumption.

Although unmentioned by Valiant, seeing evolution as a learning process provides a novel perspective on entire schools of philosophical thought. For instance, the PAC theory of evolution might reduce Schopenhauer’s ‘will to life’ to a more fundamental ‘will to learn’. The ‘turning of the will upon itself’ – the development of rational capacities whereby the will critiques itself – occurs merely accidentally in Schopenhauer’s theory, but is an almost inevitable consequence of PAC. Predicting the future by using a PAC process is moreover how organisms exert power over the world; and thus the ‘will to learn’ also encompasses Nietzsche’s ‘will to power’. Perhaps the closest philosophical connection is seen in Michel Foucault’s inaugural College de France 1970-1971 lecture series, which framed a legal perspective on a ‘will to know’, connecting the Aristotelian desire to know to Nietzsche’s desire for power. Is legal process – that bureaucratic Leviathan – a consequence of a probably approximately correct learning algorithm for human societies?

This is an enjoyable, well-written book for a general audience describing a comprehensive mathematical theory of adaptation, evolution, learning, and cognition. It is accessible to such an audience, while providing sufficient references into the primary literature for further study. The essential points are illustrated with conceptual and pictorial examples of simplified versions of the algorithms, and example problems that demonstrate the logical underpinnings, without getting bogged down in formal mathematical proofs. The book also provides interesting material for philosophically speculation. The conclusions may be simplistic, but they’re probably, approximately, correct.

Joshua Schrier is Kim B. and Stephen E. Bepler Chair Professor of Chemistry at Fordham University in New York.

• Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World, Leslie Valiant, New York, Basic Books, 2013, x+195 pages, $26.99, ISBN 978-0-465-03271-6