Hsuan-Tien Lin's ML Foundations L5–L6: Infinitely Many Hypotheses, So Why Does Learning Still Generalize? Growth Functions and Break Points

TL;DRThe Hoeffding guarantee from L4 carries an M, the number of hypotheses. Perceptrons have infinitely many lines, so M blows up. L5 stops counting hypotheses and counts how many ○× patterns (dichotomies) they can produce on N data points instead; the maximum is the growth function m_H(N). 2D perceptrons produce at most 14 patterns on 4 points, fewer than 2⁴ = 16, so 4 is their break point. L6, marked optional by the course, proves that any break point caps m_H(N) by a polynomial, which is what makes the VC bound work.

#ntu #machine-learning #learning-theory #ai-course #course-guide

Series: Reading NTU Hsuan-Tien Lin Machine Learning Foundations & Techniques (3 / 19)

Reading Hsuan-Tien Lin's ML Foundations: Is Learning Feasible? Hoeffding and "Outside the Data"Hsuan-Tien Lin's ML Foundations L7–L8: How the VC Dimension Measures Model Complexity, and What Noise and Error Measures Change

🌏 中文版

This is part 3 of the Reading NTU Hsuan-Tien Lin Machine Learning Foundations & Techniques series. It follows Is Learning Feasible? Hoeffding and Learning Beyond the Data. It covers Lecture 5, Training versus Testing, and Lecture 6, Theory of Generalization, from Machine Learning Foundations. Together they open the course's second big question: "Why Can Machines Learn?"

The lectures are taught in Mandarin. The slides are in English.

Official materials used:

MOOC slides 05_handout.pdf (L5) and 06_handout.pdf (L6), plus the Fall 2026 05e_handout.pdf (3 pages of extended slides for L5).
Videos 18–25 of the Foundations YouTube playlist, listed below.
Textbook Learning from Data (LFD): 2.0 and 2.1.1 for L5, 2.1.2 for L6, per the Fall 2024 course page.
Practice: Fall 2024 HW2.

Access level: videos and slides alone are A2. Add the Fall 2024 homework PDFs and this stretch reaches A3, but there are no official solutions and Gradescope grading is for enrolled students only. The grading scale is defined in the global AI/CS course map.

L6 is optional, so here is how this post handles it

Both semesters mark L6 as not required. The Fall 2026 course page lists the four L6 videos under W4 (09/30) as "suggested watching (anytime)", while the L5 videos are "required watching (before class)". The Fall 2024 page files L6 under "optional" and offers two versions side by side: Yaser Abu-Mostafa's English Lecture 6 at Caltech, and Lin's four-part Mandarin version.

So the main text covers the L5 concepts plus the result of L6: a break point squeezes the growth function down to a polynomial. Every proof step lives in a collapsible block. Readers who skip them will not miss anything later posts rely on.

The problem: M is infinite

L4 concluded that with a finite hypothesis set (|H| = M) and enough data N,

P[|E_in(g) − E_out(g)| > ε] ≤ 2 · M · exp(−2ε²N)

L5 opens by splitting learning into two questions (slide 3):

Is E_out(g) close enough to E_in(g)?
Can we make E_in(g) small enough?

M pulls these in opposite directions. A small M guarantees the first but leaves too few choices for the second. A large M does the reverse. And the perceptron from L2 has infinitely many lines, so M = ∞ and the inequality says nothing.

Slides 7–8 trace where M comes from. To let the algorithm pick any hypothesis, we bound the chance that any hypothesis hits a BAD event. That uses the union bound, which assumes the BAD events never overlap and simply adds their probabilities. But two nearby lines h₁ ≈ h₂ have the same E_in on most data sets, so their BAD events overlap heavily. The union bound counts that overlap again and again, infinitely many times.

The L5 idea: similar hypotheses fail together, so group them by kind and count kinds.

From counting lines to counting dichotomies

How many lines, as seen from one point?

The plane holds infinitely many lines. Seen from a single input x₁, though, there are only two kinds: lines that label x₁ as ○ and lines that label it ×. Two points give 4 kinds. Three points in general position give 8, and three collinear points give only 6. Four points? Slide 13: however you place them, at most 14, which is less than 2⁴ = 16.

The two missing patterns are the XOR shape: one diagonal gets the same label, the other diagonal gets the opposite one. No single line can do that.

This "maximum number of kinds" is the effective number of lines. If it can stand in for M, and it is much smaller than 2^N, then infinitely many lines are still learnable.

Dichotomies and the growth function

Slides 16–17 generalize the idea:

Dichotomy: look at hypothesis h only through its outputs on x₁…x_N, giving a ○× vector (h(x₁), …, h(x_N)). All the dichotomies H can produce on those N points are written H(x₁, …, x_N), and there are at most 2^N of them.
Growth function m_H(N): the dichotomy count depends on where the inputs sit, so take the maximum over all possible sets of N inputs to remove that dependence.

Four examples

Slides 18–23 work out four hypothesis sets. They come back all the way through L7.

Hypothesis set	Shape	m_H(N)	break point
positive rays	1D, h(x) = sign(x − a)	N + 1	2
positive intervals	1D, +1 inside an interval	½N² + ½N + 1	3
convex sets	2D, +1 inside a convex region	2^N	none
2D perceptrons	lines in the plane	< 2^N for some N	4

The convex-sets argument is worth remembering. Put N points on a big circle. Any ○× pattern can then be realized by a convex region traced slightly outside the ○ points. When some set of N points admits all 2^N patterns like this, H shatters those points.

The 05e extended slides add two more examples. For 1D positive-and-negative rays (the decision stump), m_H(N) = 2N: positive rays give N + 1 patterns, negative rays give another N + 1 by symmetry, and the all-○ and all-× patterns are counted twice, so subtract 2. Origin-passing 2D perceptrons also give 2N. The trick is to normalize the points onto a unit half-circle, then sweep the angle, which reduces the problem to decision stumps.

Try this: draw 4 points on paper and find, by hand, the two patterns a line cannot produce. It is the most concrete picture in the whole VC story.

Break point: where the growth function stops growing exponentially

Slide 24 defines it: if no set of k inputs can be shattered by H, then k is a break point of H, meaning m_H(k) < 2^k. If k is a break point, so are k + 1, k + 2, and so on. The course only discusses the smallest.

Watch the quantifiers. For 2D perceptrons, some set of 3 points can be shattered (three points in general position). For 4 points, no arrangement can be. So the break point is 4.

Slide 25 draws a conjecture from the table:

No break point: m_H(N) = 2^N. That part is certain.
Break point k: m_H(N) = O(N^k−1).

Positive rays (k = 2) are O(N) and positive intervals (k = 3) are O(N²), so both fit. If the conjecture holds, plugging m_H(N) into Hoeffding in place of M works: the polynomial eventually loses to exp(−2ε²N). L6 proves exactly this.

L6: how a break point caps the growth function

L6 has four videos: Restriction of Break Point, Bounding Function: Basic Cases, Bounding Function: Inductive Cases, and A Pictorial Proof. The result fits in two sentences:

Define the bounding function B(N, k): the largest m_H(N) can possibly be, given break point k. It is a purely combinatorial quantity that ignores what H looks like. Positive intervals and 1D perceptrons both have break point 3, for example, so B(N, 3) bounds both.
One can prove B(N, k) ≤ Σ_i=0^k−1 C(N, i), whose highest-order term is N^k−1. So whenever a break point exists, m_H(N) is polynomial in N.

Putting m_H back into the BAD-event probability gives the Vapnik–Chervonenkis (VC) bound (slide 25):

P[∃h ∈ H such that |E_in(h) − E_out(h)| > ε] ≤ 4 · m_H(2N) · exp(−ε²N / 8)

Compared with 2 · M · exp(−2ε²N), M becomes m_H(2N) and the constants get worse. For 2D perceptrons, the break point is 4 and m_H(N) is O(N³), so learning with 2D perceptrons is feasible. This is the moment the PLA from L2 gets its theoretical footing.

Proof 1: the B(N, k) table and recurrence (slides 6–19)

Boundary cases (slides 8–10):

B(N, 1) = 1. The set cannot shatter even one point, so every column holds a single symbol. Once the first dichotomy is in, no other fits.
B(N, k) = 2^N when N < k. There are not yet enough points to hit the break point, so every pattern is allowed.
B(N, k) = 2^N − 1 when N = k. Removing any one pattern is enough to avoid shattering k points.

Inductive case (slides 12–17), using B(4, 3). After checking all 2^2⁴ sets of dichotomies, the maximum is 11. Group those 11 by their first three coordinates (x₁, x₂, x₃):

α groups appear in pairs, identical on the first three points with x₄ = ○ in one and × in the other (2α dichotomies in total).
β dichotomies appear only once.

So B(4, 3) = 2α + β. Two observations follow:

α + β are dichotomies on (x₁, x₂, x₃), and they still cannot shatter any 3 points. So α + β ≤ B(3, 3).
If the α part could shatter any 2 of the first three points, pairing with x₄ would shatter 3 points, a contradiction. So α ≤ B(3, 2).

In general this gives B(N, k) ≤ B(N − 1, k) + B(N − 1, k − 1), and induction yields B(N, k) ≤ Σ_i=0^k−1 C(N, i). Slide 18 notes that the "≤" is actually "=", and leaves the proof to math lovers. The bonus problem Q13 of Fall 2024 HW3 asks for exactly that ≥ direction.

A quiz on slide 11 makes one more point: for 2D perceptrons m_H(4) = 14, while B(4, 4) = 15. The bounding function can be loose.

Proof 2: the three-step pictorial proof of the VC bound (slides 21–25)

The goal is to turn "infinitely many E_out values" into "finitely many cases".

Replace E_out with E′_in. Draw a second, "ghost" data set D′ of size N and compute E′_in on it. If h is BAD between E_in and E_out, it is probably also BAD between E_in and E′_in. This step turns ε into ε/2 and adds a factor of 2 in front.
Decompose H by kind. Now only the 2N points of D and D′ matter, and on them the hypotheses fall into at most m_H(2N) kinds. Apply the union bound over those finitely many kinds.
Hoeffding without replacement. Treat the 2N examples as a small bin. Draw N at random for E_in and use the rest for E′_in. |E_in − E′_in| > ε/2 is equivalent to |E_in − (E_in + E′_in)/2| > ε/4, and for a fixed h the without-replacement version of Hoeffding applies.

Together the three steps give 4 · m_H(2N) · exp(−ε²N / 8). The quiz on slide 26 plugs in positive rays with ε = 0.1 and N = 10,000 and gets a bound of about 0.298. Even with ten thousand examples, the bound on the BAD probability is not small. L7 returns to that looseness.

L5 (required before class in Fall 2026):

L6 (optional in both semesters):

English counterpart: in Caltech's Learning from Data, Lecture 5 is also called Training versus Testing and Lecture 6 is Theory of Generalization. It uses the same textbook. The Fall 2024 NTU course page links Abu-Mostafa's Lecture 6 right next to Lin's Mandarin version.

Practice: Fall 2024 HW2

HW2 was released on 2024-09-23 and due 10/07. It is worth 200 points plus 20 bonus points and spans L4 to L7. The problems tied to this post:

Q1: the growth function of 2D perceptrons restricted to slope 1 or −1, for N ≥ 4.
Q3: the growth function of 2D perceptrons that must pass through the point (11, 26). The 05e page on reducing origin-passing perceptrons to decision stumps is a good warm-up.
Q4: the tightest upper bound on the VC dimension of a finite set of 6211 fixed perceptrons. It uses the L7 definition, but the idea is "how many patterns can finitely many hypotheses produce?"
Q10–12: decision stumps. Q10 asks you to prove that under the given noisy data distribution E_out(h_s,θ) = u + v·|θ|. Q11 has you implement the 1D decision stump algorithm, run it 2000 times with N = 12 and 15% noise, and plot (E_in, E_out). Q12 repeats this with a randomly chosen hypothesis.
Q13 (bonus): an upper bound on the VC dimension of multi-dimensional decision stumps.

Q2, Q6 and Q7 are the L4 multi-bin sampling problems, covered in the previous post. The Q13 bonus of Fall 2024 HW3 asks for the lower bound on B(N, k); see Proof 1 above.

Try this: Q11 and Q12 need no data set, since the code generates its own data. Put the two scatter plots side by side and compare the median E_out − E_in for "pick the lowest-E_in hypothesis" against "pick any hypothesis". That gap is exactly what this post is about. With no official solutions, you can check your simulation against the E_out formula you derive in Q10.

Per the course schedule, Fall 2026 hw2 comes out on 10/07. As of 2026-09-30 it is not yet public.

The next post, VC Dimension, Noise and Error Measures, gives "the largest non-break point" its formal name, the VC dimension d_VC. It proves that d-dimensional perceptrons have d_VC = d + 1, then extends the theory to noisy data.

Further reading: the Stanford CS229 generalization chapter guide approaches the same question by a different route.

Hsuan-Tien Lin's ML Foundations L5–L6: Infinitely Many Hypotheses, So Why Does Learning Still Generalize? Growth Functions and Break Points

L6 is optional, so here is how this post handles it

The problem: M is infinite

From counting lines to counting dichotomies

How many lines, as seen from one point?

Dichotomies and the growth function

Four examples

Break point: where the growth function stops growing exponentially

L6: how a break point caps the growth function

Practice: Fall 2024 HW2

Next

References

Hsuan-Tien Lin's ML Foundations L5–L6: Infinitely Many Hypotheses, So Why Does Learning Still Generalize? Growth Functions and Break Points

L6 is optional, so here is how this post handles it

The problem: M is infinite

From counting lines to counting dichotomies

How many lines, as seen from one point?

Dichotomies and the growth function

Four examples

Break point: where the growth function stops growing exponentially

L6: how a break point caps the growth function

Video list

Practice: Fall 2024 HW2

Next

References

Related