What is the PAC learning model?

The purpose of this post is to learn about the Probably Approximately Correct Learning model introduced by Valiant in “A Theory of the Learnable.” This model is relevant because it is the first formal framework to study the process of learning from a computational viewpoint. Computability theory and complexity theory became possible once we had a rigorous model of the phenomenon of mechanical calculations (Turing Machines) that could be used to explain the phenomenon and was valuable to study for its own sake. In this line, the phenomenon of learning is also very relevant and needs a model that is valuable for its own sake and also explains the process of learning and its limits. Valiant defines that a program to perform a task has been acquired by learning if it has been acquired by any means different to explicit programming.

Read More