Dictionary of Applied Machine Learning

generalization

Typeset PDF version — the authoritative form of this entry

Generalization is the ability of a machine learning (ML) method to make accurate predictions on data points that have not been used during training. Many ML methods implement training via empirical risk minimization (ERM), i.e., learning a hypothesis $\learnthypothesis$ that minimizes the empirical risk on the training set $\trainset$. The learned $\learnthypothesis$ is then used to compute predictions on new data points outside $\trainset$. A probabilistic model for data generation quantifies the prediction errors beyond $\trainset$ via the risk of $\learnthypothesis$, i.e., the expected loss incurred on a new randomly chosen data point. The difference between the risk and the empirical risk is the generalization gap. A complementary deterministic view characterizes generalization via the robustness of $\learnthypothesis$ to small perturbations of the features of a data point.

Definition

A weather forecaster trained on past data is useful only if its predictions are accurate on future unseen data points. Generalization refers to the ability of a learned hypothesis $\learnthypothesis$ to make similarly accurate predictions on data points that have not been used during training. It is the central goal of machine learning (ML): learning patterns in the features and labels of data points that extend beyond the training set.

The canonical learning technique is empirical risk minimization (ERM): the machine learning system (ML system) obtains $\learnthypothesis \in \hypospace$ by minimizing the empirical risk on the training set $\trainset$. A low empirical risk on $\trainset$ does not guarantee accurate predictions on data points outside $\trainset$. Online learning and Bayesian inference face the same generalization challenge.

Studying generalization mathematically requires formalizing the notion of unseen data points. A widely used approach is to assume a probabilistic model for the generation of data points, such as the independent and identically distributed assumption (i.i.d.\ assumption). Here, data points are interpreted as independent random variables (RVs) with an identical, fixed but unknown, probability distribution $\probdist$. Fig. 1 sketches this setup: the shaded ellipse depicts the region of typical data points under $\probdist$, and the two large filled circles are the data points of the training set that ERM fits with the learned hypothesis $\learnthypothesis$. The risk of $\learnthypothesis$ is the expected loss: \[ \risk{\learnthypothesis} = \expect \left\{ \lossfunc{\datapoint}{\learnthypothesis} \right\}. \] The difference $\risk{\learnthypothesis} - \emprisk{\learnthypothesis}{\trainset}$ is the generalization gap.

Figure 1 of the entry generalization
Figure 1: Two data points $\datapoint^{(1)}, \datapoint^{(2)}$ used as a training set to learn a hypothesis $\learnthypothesis$ via ERM. The shaded ellipse marks the region of typical data points under an assumed probability distribution $\probdist$
For any fixed hypothesis $\hypothesis \in \hypospace$, $\risk{\hypothesis}$ is a deterministic number that depends only on $\hypothesis$ and $\probdist$, whereas $\emprisk{\hypothesis}{\trainset}$ is an RV that depends on $\trainset$, which, in turn, is a realization of an independent and identically distributed (i.i.d.) sequence of RVs $\datapoint^{(1)}, \ldots, \datapoint^{(\samplesize)} \sim \probdist$. Bounding the generalization gap therefore means controlling the probability of the (undesirable) event \[ \mathcal{E}^{(\hypothesis)} \defeq \left\{ \trainset : \big| \emprisk{\hypothesis}{\trainset} - \risk{\hypothesis} \big| > \varepsilon \right\}, \] where $\varepsilon > 0$ is a user-specified tolerance for the generalization gap. Each $\hypothesis \in \hypospace$ defines a different event $\mathcal{E}^{(\hypothesis)}$ (see Fig. 2), and generalization requires low probability of $\mathcal{E}^{(\hypothesis)}$ uniformly over $\hypospace$ (Bishop, 2006, Sect. 1.5; Shalev-Shwartz and Ben-David, 2014, Ch. 4).
Figure 2 of the entry generalization
Figure 2: Consider an ML application with feature space $\featurespace=\reals$ and label space $\labelspace=\reals$. A training set of size $\samplesize$ is a point in the sample space $(\reals \times \reals)^{\samplesize}$ of all possible training sets of size $\samplesize$ (the outer region). Each hypothesis $\hypothesis \in \hypospace$ defines an event $\mathcal{E}^{(\hypothesis)} \subseteq (\reals \times \reals)^{\samplesize}$ (an inner region) collecting those training sets on which $\hypothesis$ fails to generalize. Ensuring that the ML method is likely to generalize requires the union $\bigcup_{\hypothesis \in \hypospace} \mathcal{E}^{(\hypothesis)}$ to have low probability, not just each individual $\mathcal{E}^{(\hypothesis)}$
Probability theory is not the only route to generalization. A complementary deterministic approach uses robustness: a good hypothesis $\learnthypothesis$ should not change its prediction $\learnthypothesis(\featurevec)$ much if the features $\featurevec$ of a data point $\datapoint$ are slightly perturbed. For example, an object detection system trained on smartphone photos should still detect the object even if a single pixel is changed (Su et al., 2019), and it should deliver the same result if the object in the image is rotated (Mallat, 2016). The arrows in Fig. 1 indicate small perturbations of each data point in the training set of an ML method.

See also: empirical risk minimization, empirical risk, risk, generalization gap, independent and identically distributed assumption, training set, validation error, test set, overfitting, validation, regularization, hypothesis, hypothesis space, online learning, Bayesian inference.

References

  1. Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media.
  2. Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press.
  3. Su et al. (2019). One Pixel Attack for Fooling Deep Neural Networks. IEEE Trans. Evol. Comput..
  4. Mallat (2016). Understanding deep convolutional networks. Philos. Trans. Roy. Soc. A.

Cite this entry

@misc{dictml_generalization,
  author = {Jung, Alexander},
  title = {generalization},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-08-06},
  url = {https://dictionaryofml.org/terms/generalization.html}
}