VC Dimension

A learner sees only a finite labeled sample, but a PAC guarantee concerns performance on the entire underlying distribution. The central question is therefore whether the sample is capable of detecting every hypothesis that disagrees with the target on a sufficiently large part of that distribution. VC dimension supplies the capacity measure, while epsilon-nets supply the coverage argument that turns a sample into a guarantee.

The important feature is the universal coverage requirement. The sample is not merely likely to hit one particular high-probability set. It must hit every set in the relevant class that has probability at least epsilon. This is what allows the argument to eliminate an entire collection of bad hypotheses at once.

To apply epsilon-net coverage to classification, fix a target hypothesis c and compare every candidate h with c. For each h in H, form the set of domain points on which h and c disagree. The collection of all such disagreement sets is the class H_c.

Assume the realizable setting: the target c belongs to H, and the sample receives labels according to c. Consider a candidate h whose true error is at least epsilon. Its disagreement set with c therefore has probability at least epsilon. If the sample is an epsilon-net for H_c, the sample intersects that disagreement set, so h makes at least one error on the labeled sample.

Because c is consistent with the sample, a hypothesis that makes a sampled error cannot be an empirical-risk minimizer. Therefore, once the sample intersects every disagreement set of probability at least epsilon, every hypothesis with true error at least epsilon is excluded from being an ERM hypothesis.

A classification class is more expressive when it can realize more different labelings of data points. VC dimension measures this capacity by asking for the largest number of points that can be shattered. A set of points is shattered when every possible binary labeling of those points can be produced by some classifier in the class.

In the PAC argument, VC dimension controls the complexity of the relevant hypothesis or disagreement class. The equality between the VC dimensions of H and H_c allows the complexity of H to be carried into the epsilon-net analysis. Thus, VC dimension connects the number of distinguishable labelings to the sample size needed for a high-probability learning guarantee.

For homogeneous halfspaces in R^{^d}, the separating boundary is required to pass through the origin. Their VC dimension is exactly d.

For the upper bound, take any d+1 vectors in R^{^d}. They are linearly dependent, so there are real coefficients, not all zero, whose weighted combination is the zero vector. Separate the indices with positive coefficients from those with negative coefficients. If both groups are nonempty, a weight vector that assigns the required opposite signs would create incompatible sign conditions when applied to the dependence relation. If one group is empty, the corresponding side becomes an equality and the contradiction still follows. Therefore, no d+1 vectors can be shattered by homogeneous halfspaces.

Non-homogeneous halfspaces in R^{^d} include a bias term, so their separating boundary is not required to pass through the origin. Their VC dimension is exactly d+1.

For the lower bound, use the zero vector together with the d standard basis vectors. The source proof states that this set of d+1 vectors is shattered by non-homogeneous halfspaces, paralleling the homogeneous construction for the basis vectors.

For the upper bound, suppose d+2 vectors in R^{^d} could be shattered by non-homogeneous halfspaces. The standard reduction described in the source converts this into d+2 vectors in R^{^d+1} shattered by homogeneous halfspaces. That contradicts the homogeneous result, because homogeneous halfspaces in R^{^d+1} have VC dimension d+1 and cannot shatter d+2 vectors. Hence the non-homogeneous VC dimension is d+1.