Theory of Generalization: How One Break Point Makes the Growth Function Polynomial | NTU Hsuan-Tien Lin Machine Learning Foundations Lecture 6
Once a hypothesis set has a break point k, the largest number of dichotomies it can produce on N points, B(N, k), satisfies B(N, k) ≤ B(N−1, k) + B(N−1, k−1). That gives B(N, k) ≤ C(N, 0) + … + C(N, k−1), whose highest term is N to the power k−1. Three more steps put the growth function into Hoeffding and yield the VC bound: the probability of the bad event is at most 4·m_H(2N)·exp(−ε²N/8). The break point of 2D perceptrons is 4, so they can learn.