2010 · Theory & algorithms
PAC learning gave machine learning a precise language for generalisation.
Visual guide
Observe labelled examples.
Choose a hypothesis.
Bound likely error on new examples.
The guarantees rely on stated assumptions about the examples, hypothesis class and data distribution.
01 · The idea
Leslie Valiant developed the probably approximately correct model of learning, alongside major contributions to counting complexity, algebraic computation and parallel computing. PAC learning asks when examples can lead to a hypothesis that is likely to make only a small error on new data from the same distribution.
A mathematical learning model helps separate assumptions about data, sample size and computational efficiency.
02 · The people
Leslie Valiant developed mathematical models for understanding what computers can learn and compute efficiently. His probably approximately correct learning framework made learning from examples a precise subject of complexity theory. He also contributed to counting complexity and parallel computation. At Harvard, his research connected algorithms, artificial intelligence, and models of the brain, asking which capabilities can emerge under realistic limits on time and information.
Read the biography ↗03 · Read further
Original explanations based on the official award record. The subject label is an editorial navigation aid.
Complexity theory connected random choices with some of computation’s deepest limits.
The story
Numerical libraries connect mathematical algorithms with changing hardware.
The story