The Probably Approximately Correct Learning Model in Computational Learning Theory

Leslie Valiant's 1984 paper "A Theory of the Learnable" [Val84], reproduced in this volume, has the unusual distinction of having changed the course of several scientific disciplines. Within theoretical computer science it was one of the key works giving rise to the field now known as computational learning theory, which may loosely be defined as the rigorous study of learning processes and phenomena from the computer science perspective of efficient algorithms and computational complexity. In the decades since the publication of [Val84], computational learning theory has grown into a rich field with strong connections to many other theoretical disciplines such as mathematical probability and statistics, information theory, decision theory and more. Beyond the realm of theory, Valiant's paper and the Probably Approximately Correct (PAC) model which he introduced in it have also had a great impact on the subsequent development of machine learning, a field which has already transformed many aspects of science and human society and seems certain to have an even greater influence in the future. This chapter gives an overview of the Probably Approximately Correct learning model that Valiant introduced in [Val84], explaining some of the major results and directions that the field has taken in the years since that work.