Probably Approximately Correct Learning and Decision-Theoretic Generalizations: David Haussler

Here we survey some recent theoretical results on the efficiency of machine learning algorithms. The main tool described is the notion of probably approximately correct (PAC) learning, introduced by Valiant. We define this learning model and then look at some of the results obtained in it. We then consider some criticisms of the PAC model and the extensions proposed to address these criticisms. Finally, we look briefly at other models recently proposed in computational learning theory.