Machine Learning course- Shai Ben-David: Lecture 8

CS 485/685, University of Waterloo. Jan 30, 2015.
The relationship of VC dimension and learning: Statement of the "fundamental theorem of statistical machine learning" and a proof of the non-learnability of classes of infinite VC-dimension.

[dhanajit]

11:04 No Free Lunch (NFL) Theorem
46:00 Infinite VCdim => not PAC learnable
57:31 The Fundamental Theorem of Statistical Learning
1:11:54 Class of linear predictors

[RahulMadhavan]

@40:23 I think the row example may need another argument. What Prof has shown: there exists a row (labelling function) such that over all columns (samples), the average error is atleast a quarter.

But in my opinion, we don't need to look at average over all samples. Given a learner A, which is given a fixed s, the output is A(s), the hypothesis of the learner. This is compared with the labels f.

So what we need to show - in each column, there exists a row where the error is greater than 1/4. But this is clear as average of each column is 1/4. Therefore there exists atleast 1 row (f labelling) in each column (corresponding with A(s)) with value greater than 1/4

[qizhang]

This video contains the basic idea for the proof of No-Free-Lunch Thm

[xudongsun]

39 min 52 second there exist a labeling function that will fail for all distributions

[chryszification]

Around 34:10, what does the professor mean by grouping together in blocks functions with the same behavior on a given sample? I mean, the sequence of labels predicted by those functions should differ and if they differ how can they agree on a given sample?

[pavelsinha]

Around time 44:59, when professor explains the no-free-lunch theorem, I have a question: What in the case when 1 function is bad, say error along the row is 1 and rest of the functions (along the row) have very low error per row. Then can we not mark that function as bad and not let the algorithm pick that particular bad function? Can such a case exist, if so then won't my error reduce? Sorry if my question is vague.