Training versus Testing: Infinitely Many Lines, Only a Few Kinds | NTU Hsuan-Tien Lin Machine Learning Foundations Lecture 5
The guarantee from the previous lecture contains the number of hypotheses M, and the perceptron has infinitely many lines, so M is infinite. This lecture instead counts how many ○× patterns (dichotomies) those lines can produce on N data points, and takes the maximum over all placements to get the growth function m_H(N): N+1 for positive rays, ½N²+½N+1 for positive intervals, 2ᴺ for convex sets, and at most 14 for 2D perceptrons on 4 points. The first number of points at which the growth function falls short of 2ᴺ is called a break point; the handout conjectures that it forces the growth function down to a polynomial, and leaves the proof to the next lecture.