PAC learning
Probably Approximately Correct learning: a theoretical framework defining when an algorithm has successfully learned from examples—namely when it can predict future examples accurately with a moderate (polynomial) amount of effort, with accuracy improving in proportion to effort.
As defined in 272 | Leslie Valiant on Learning and Educability in Computers and People
Where it comes up · 1
Most important claims · 7 of 7Search all claims for “PAC learning” →
- Learning systems offer a promise that predictions averaged over many cases will be good, but for any single case the promise is very weak; therefore using AI for safety-critical applications is dangerous because in your particular case the guarantee is minimal.272 | Leslie Valiant on Learning and Educability in Computers and People
- The PAC (Probably Approximately Correct) model defines learning success as accurately predicting future examples from past examples, while requiring that the effort to reach that prediction is moderate (polynomial time) and that increased effort yields proportionally better accuracy, formalized as the error being a constant exponent of the effort.272 | Leslie Valiant on Learning and Educability in Computers and People
- The philosophical problem of induction, which goes back to the Greeks and which philosophers abandoned without resolving, has been solved by computer science in the specific, understandable sense in which the problem is meant—the PAC framework gives a rigorous meaning to when inductive generalization is justified.272 | Leslie Valiant on Learning and Educability in Computers and People
- Darwinian evolution can be formulated as a PAC learning process in which the genome is the rule being learned, mutation is the learning algorithm, and survival provides the labeling feedback from the world instead of an external labeler—making evolution and human cognition instances of the same learning phenomenon.272 | Leslie Valiant on Learning and Educability in Computers and People
- Among the topics studied in AI, learning is the most fundamental, because a theory of computation is worthless if it cannot address the basic problems of the mind, and learning turned out to be the entry point that was computationally feasible whereas logical reasoning proved computationally intractable.272 | Leslie Valiant on Learning and Educability in Computers and People
- Educability, the proposed feature distinguishing humans, is the integration of three capabilities: learning from experience (PAC learning), chaining together pieces of knowledge learned in different contexts (a basic form of reasoning), and absorbing explicit theories handed over directly by others without personal experience.272 | Leslie Valiant on Learning and Educability in Computers and People
- The PAC model correctly anticipated modern large language models: it promised that the computation needed to learn well would be large but still polynomial-time and therefore doable, which is borne out by LLMs costing millions of dollars to train.272 | Leslie Valiant on Learning and Educability in Computers and People