In machine learning, selecting a model class involves a fundamental trade-off. More flexible, or higher variance, model classes can perfectly fit the training data but carry a significant risk of overfitting and poor generalization. Conversely, more rigid, or higher bias, model classes generalize predictably but may underfit, failing to capture the underlying patterns in either the training or test data.

Trade-off Between Model Flexibility and Rigidity

The Vapnik-Chervonenkis (VC) dimension is a metric that quantifies the complexity or flexibility of a model class. It is defined as the maximum number of data points for which the model class can perfectly classify any arbitrary binary labeling; that is, for any possible assignment of labels to these points, there exists some classifier $$f$$ in the class that correctly matches that labeling.

Vapnik-Chervonenkis (VC) Dimension

In machine learning, models with continuously valued parameters, such as linear models, belong to an infinite class of functions (denoted as $$|\mathcal{F}| = \infty$$). Because the set of possible classifiers is infinite, it is impossible to simply test every function to guarantee that its empirical error matches its true population error without risking false discovery. This mathematical complexity directly motivates the need for advanced statistical learning theories, such as uniform convergence and the VC dimension, to bound the generalization gap.

Infinite Class of Functions

Statistical learning theory is the mathematical subfield of machine learning that aims to elucidate the fundamental principles explaining why and when models trained on empirical data can generalize to unseen data. A primary objective is to bound the generalization gap by relating the properties of the chosen model class to the dataset size.

Claude

Because the true population error $$\epsilon(f)$$ of a classifier cannot be observed directly in most practical scenarios, it must be estimated using samples. When a test dataset $$\mathcal{D}$$ is statistically representative of the underlying population, the empirical error $$\epsilon_\mathcal{D}(f)$$ serves as a statistical estimator for the population error $$\epsilon(f)$$. Since the empirical error is a sample average and the population error is its expectation, this reduces to a classical mean estimation problem.

Estimation of Population Error via Empirical Error

Dive into Deep Learning

In the context of estimating classification error, the event of a classifier $$f$$ making an error on a single instance, $$\mathbf{1}(f(X) 
eq Y)$$, can be modeled as a Bernoulli random variable. It takes the value $$1$$ (error) with probability equal to the true population error rate $$\epsilon(f)$$, and $$0$$ (correct) otherwise. Consequently, its variance is $$\epsilon(f)(1-\epsilon(f))$$, which reaches its maximum when the true error rate is exactly $$0.5$$ and decreases as the error approaches $$0$$ or $$1$$. This implies that the asymptotic standard deviation of the empirical error estimate cannot exceed $$\sqrt{0.25/n}$$ for a sample size $$n$$.

Classification Error as a Bernoulli Random Variable

By the central limit theorem, as the size $$n$$ of a test dataset grows toward infinity, the empirical test error $$\epsilon_\mathcal{D}(f)$$ approaches the true population error $$\epsilon(f)$$ at an asymptotic convergence rate of $$\mathcal{O}(1/\sqrt{n})$$. This $$\mathcal{O}(1/\sqrt{n})$$ rate reveals that improving the precision of the error estimate is computationally expensive; for instance, estimating the test error twice as precisely requires collecting four times as many samples.

Asymptotic Convergence Rate of Test Error

Statistical Learning Theory

When evaluating a machine learning model, the empirical error measured on a test dataset provides an unbiased estimate of the underlying population error. To formally quantify the uncertainty of this point estimate, researchers construct confidence intervals around the test error. These boundaries can be formulated as approximate confidence intervals based on exact asymptotic distributions—such as the central limit theorem—or as strictly valid, albeit more conservative, finite sample confidence intervals derived from finite sample guarantees like Hoeffding's inequality.

Learn Before

Related

Learn After