(67577) Introduction to Machine Learning Lecture 1 Introduction and Gentle Start Lecture 2 Bias Complexity Tradeoff Lecture 3(a) Mdl Lecture 3(b) Validation Lecture 3(c) Compression Bounds
In the previous lectures we saw how to express prior knowledge by restricting ourselves to a finite hypothesis classes or by defining an order over countable hypothesis classes. In this lecture we show how one can learn even uncountable hypothesis classes by deriving compression bounds. Roughly speaking, we shall see that if a learning algorithm can express the output hypothesis using a small subset of the training set, then the error of the hypothesis on the rest of the examples estimates its generalization error. To motivate the results, let us first consider the following learning protocol. First, we sample a sequence of k examples denoted T Based on these examples, we construct a hypothesis denoted hT Now we would like to estimate the performance of hT so we sample a fresh sequence of m k examples, denoted V and calculate the error of hT on V Since V and T are independent, we immediately get the following from Bernstein's inequality (as you saw in home exercise)