= Probably approximately correct learning
<Probably approximately correct learning> formalizes learning as a two-parameter guarantee. With probability at least $1-\delta$ over the training <random sample> and any learner randomness, the returned <hypothesis> must have true prediction error at most $\epsilon$. 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, $\epsilon=0.01$ and $\delta=0.05$ 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.<Learnability and VC Dimension in MIT 6.790>[PAC learning and sample complexity]{ref}
Back to article page
