X is uniform on [0, 1] and P(Y = 1 | X = x) = r(x) is known, so the true error L(h) of any classifier can be computed exactly. The class Hk contains every rule that predicts 1 on a union of at most k intervals whose ends lie on a grid of 500 cells. Empirical risk minimisation picks the rule in Hk with the fewest training mistakes (found exactly by dynamic programming). As k grows the training error falls, but the true error does not follow: the gap is the price of choosing from a large class. Hoeffding's inequality with the union bound (Theorem 22.17) and the Vapnik–Chervonenkis theorem (Theorem 22.19) bound the largest gap over the whole class; compare them with the actual largest gap, computed exactly.
The finite class Hk has mk = ∑j≤k C(501, 2j) members. The VC bound is for all unions of k intervals (VC dimension 2k), with the exact shatter coefficient s(n) = ∑j≤k C(n + 1, 2j); it contains Hk, so it applies too. Data sets come from a seeded generator.
code/ch22_classification.py (sample_intervals, r_cells, runs_dp, erm_runs, sup_deviation, intervals_experiment, intervals_repeat).