We discuss how to extend the same ideas to algorithms that do not calculate a function, but learn a function

PAC Learnability

We discuss the synonym of Uncomputability in learning algorithms.

• For computational tasks, we talked about whether the task was computable/decidable or not.
• In Learning Algorithms we talk about whether they are Learnable or not

Then we discuss the synonym of Complexity in learning algorithms.

• For computational tasks, we talked about whether the task was efficient to solve.
• In Learning Algorithms we talk about whether they are efficient to learn

Then we discuss Representation classes, prove that CNFs are efficiently PAC learnable and (by providing a Polynomial algorithm) and discuss that 3DNFs are NOT efficiently PAC learnable

Occam's Razor

We first talk about Consistent learning algorithms. Then discuss Occam's Razor to help choose between consistent models.

VC Dimension

We finally discuss the expressive power of learning algorithms using VC Dimension, and prove that all a if a problem has a finite VC-Dimension, it is PAC Learnable and if it has infinite VCD, it's NOT PAC Learnable