Probably approximately correct learning formalizes learning as a two-parameter guarantee. With probability at least over the training random sample and any learner randomness, the returned hypothesis must have true prediction error at most . In the realizable distribution-free setting, this must hold for every input probability distribution and every target in the specified concept class, using an appropriate polynomial number of examples; efficient PAC learning also requires polynomial running time.
“Probably” refers to the chance of obtaining a good hypothesis; “approximately” refers to that hypothesis's error on a fresh observation. For example, and require a 95% chance of returning a predictor whose error is at most 1%, rather than a claim that 95% of individual predictions are right. For finite realizable classes, the sample complexity bound follows by excluding every high-error rule that could have survived the observations.[ref]
Articles by others on the same topic
Probably Approximately Correct (PAC) learning is a framework in computational learning theory that formalizes the concept of learning from examples. Introduced by Leslie Valiant in 1984, PAC learning provides a mathematical foundation for understanding how well a learning algorithm can generalize from a finite set of training data to unseen data. ### Key Concepts: 1. **Hypothesis Space**: This is the set of all possible hypotheses (or models) that a learning algorithm can consider.