PAC Learning

PAC learning (Probably Approximately Correct learning) is the theoretical framework introduced by Leslie Valiant in 1984 that gave machine learning its mathematical foundations. A concept class C is PAC-learnable if there exists an efficient algorithm that, given access to labeled examples drawn from any unknown distribution D, produces (with probability at least 1−δ) a hypothesis whose error on D is at most ε—using a number of examples and a running time that are both polynomial in 1/ε, 1/δ, and the description length of the concept. PAC learning transformed vague intuitions about “learning from examples” into a complexity statement with the same precision as circuit complexity or polynomial-time solvability: a concept class is either PAC-learnable (in which case there is a provably efficient algorithm) or it is not (in which case no algorithm can learn it efficiently from examples alone). The framework gives the field what it most needs and most lacks: a way to distinguish the claim that a system has genuinely learned a concept from