Computational Learning Theory

The conditions for learnability of a task by a computer algorithm provide guidance for understanding their performance and guidance for selecting the appropriate learning algorithm for a particular task. In this chapter, we present the main theoretical frameworks for machine learning algorithms: probably approximately correct (PAC) and Vapnik–Chervonenkis (VC) dimension. In addition, we discuss the new underlying principles of deep learning. These frameworks allow us to answer questions such as which learning process we should select, what is the learning capacity of the algorithm selected, and under which conditions is successful learning possible or impossible. Practical methods for selecting proper model complexity are presented using techniques based on information theory and statistical resampling.