Dictionary of Applied Machine Learning: 114 machine-learning terms, each with a definition, a figure, citations and a Python demo · All terms · Demos · Start here

hypothesis space

Updated on 2026-10-29

Readiness 100/100

▶ Run the Python demo Open in Colab Typeset PDF LaTeX source Markdown Cite this entry

See also hypothesis model empirical risk minimization

A hypothesis space $\mathcal{H}$ is a set of hypothesis maps $h: \mathcal{X} \rightarrow \mathcal{Y}$ from a feature space into a label space. Every machine learning (ML) method uses an underlying hypothesis space, which is a subset of the set $\mathcal{Y}^{\mathcal{X}}$ of all possible maps from $\mathcal{X}$ into $\mathcal{Y}$. Available computational resources limit the size of $\mathcal{H}$, which in turn determines the method's computational cost and generalization gap. The hypothesis space typically carries geometric structure: real-valued hypotheses can be compared via the deviation in their predictions on a reference dataset, and a parametric model inherits a geometric structure from the underlying parameter space $\mathcal{W}$.

Figure produced by the Python demo of the entry hypothesis space
Figure written by the entry's Python demo hypospace.py, which recomputes what the entry states: the script block by block · open in Colab

Definition

P-defA weather service predicting tomorrow's maximum daytime temperature from today's morning temperature must commit to a set of candidate prediction maps: for example, all linear functions of the morning temperature. This set of candidates is the hypothesis space of the method; more generally, every machine learning (ML) method commits to a specific hypothesis space $\mathcal{H}$, the set from which it learns a single hypothesis $\widehat{h}$. Formally, $\mathcal{H}$ is a subset of the set $\mathcal{Y}^{\mathcal{X}}$ of all possible maps from the feature space into the label space (see Fig. 1).

Figure 1 of the entry hypospace
Figure 1: Hypothesis space $\hypospace$ of an ML method as a restricted subset of the much larger set $\labelspace^{\featurespace}$ of all possible maps from the feature space $\featurespace$ into the label space $\labelspace$
Linear regression and other linear methods use the linear model as $\mathcal{H}$, i.e., the set of all linear maps $\mathbb{R}^{d} \rightarrow \mathbb{R}$ (Shalev-Shwartz and Ben-David, 2014, Ch. 2). Another canonical example is the set of input–output maps realizable by an artificial neural network (ANN) of fixed architecture, as the model parameters vary.

P-examplesThe same $\mathcal{H}$ can be used by different ML algorithms, such as empirical risk minimization (ERM) on a fixed training set, online learning on a stream of data points, or Bayesian inference that returns a posterior distribution over $\mathcal{H}$ rather than a single hypothesis (Bishop, 2006, Sect. 1.2.3).

P-designThe choice of $\mathcal{H}$ is a central design decision for an ML method. From an ML engineering perspective, it is guided by two factors. The first is the available computational resources, such as memory, processing time, and communication bandwidth. The second factor is the number of available data points, which limits the maximum size of $\mathcal{H}$ that can be effectively trained without overfitting. In principle, $\mathcal{H}$ could be as large as $\mathcal{Y}^{\mathcal{X}}$ itself. The size of $\mathcal{H}$ allows the anticipation of generalization before any training is carried out. A small $\mathcal{H}$ typically incurs a small generalization gap, while a large $\mathcal{H}$ is more prone to overfitting. For a finite $\mathcal{H}$, the effective size is its cardinality. For an infinite $\mathcal{H}$, an effective size can be quantified by the Vapnik–Chervonenkis dimension (VC dimension) or the Rademacher complexity.

P-sizeThe word space (rather than set) reflects the fact that $\mathcal{H}$ typically carries some geometric structure. In general, $\mathcal{H}$ is not a vector space: the sum of two hypotheses in $\mathcal{H}$ need not belong to $\mathcal{H}$. What is more, there are hypothesis spaces that are not equipped with an algebraic structure at all, i.e., there is no meaningful way to add two hypotheses in $\mathcal{H}$ or to multiply a hypothesis by a scalar.

P-algosFor real-valued hypotheses, two $h, h' \in \mathcal{H}$ can be compared by their average squared prediction deviation on a reference dataset $\mathcal{D} = \{{\mathbf x}^{(1)}, \ldots, {\mathbf x}^{(m)}\}$, \[ \frac{1}{m} \sum_{r=1}^{m} \big(h({\mathbf x}^{(r)}) - h'({\mathbf x}^{(r)})\big)^{2} \text{.} \] Fig. 2 illustrates this comparison: the two hypotheses are evaluated at the feature values of the data points in $\mathcal{D}$ and the squared differences in their predictions are averaged, which yields a distance between the two. This construction is not meaningful for hypotheses with a finite label space, as used in classification methods. Instead, two such hypotheses can be compared by their disagreement rate on $\mathcal{D}$.

Figure 2 of the entry hypospace
Figure 2: Comparing two hypotheses $\hypothesis$ (red) and $\hypothesis'$ (blue) by their predictions at four scalar features $\feature^{(1)},\ldots,\feature^{(4)}$. The dashed segments mark the gap $\hypothesis(\feature^{(\sampleidx)}) - \hypothesis'(\feature^{(\sampleidx)})$ for each data point; the average of its square defines the distance $d_{\dataset}(\hypothesis,\hypothesis')$ between $\hypothesis$ and $\hypothesis'$
A parametric model $\mathcal{H} = \{h^{({\mathbf w})} : {\mathbf w} \in \mathcal{W}\}$ inherits a geometric structure from the underlying parameter space $\mathcal{W} \subseteq \mathbb{R}^{d}$. A norm on $\mathbb{R}^{d}$ induces the candidate distance $d(h^{({\mathbf w})},h^{({\mathbf w}')}) := \Vert {{\mathbf w} - {\mathbf w}'} \Vert$ on $\mathcal{H}$. When the parameterization ${\mathbf w} \mapsto h^{({\mathbf w})}$ is injective, distinct weight vectors give distinct hypotheses, and this candidate distance is a metric. The linear model $\mathcal{H} = \{h^{({\mathbf w})}({\mathbf x}) = {\mathbf w}^{\top} {\mathbf x} : {\mathbf w} \in \mathbb{R}^{d}\}$ is a canonical example of an injective parameterization: distinct weight vectors ${\mathbf w}$ produce distinct linear maps, so $\Vert {{\mathbf w} - {\mathbf w}'} \Vert$ is a metric on $\mathcal{H}$. When the parameterization is not injective, two distinct weight vectors ${\mathbf w} \neq {\mathbf w}'$ can represent the same hypothesis $h^{({\mathbf w})} = h^{({\mathbf w}')}$. The distance $\Vert {{\mathbf w} - {\mathbf w}'} \Vert$ is then strictly positive even though the two hypotheses coincide, so it is only a pseudo-metric. Permuting the hidden units of an ANN, for instance, changes ${\mathbf w}$ but leaves $h^{({\mathbf w})}$ unchanged.

Synonyms: hypothesis class, model.

See also: hypothesis, model, linear model, parametric model, parameter space, Vapnik–Chervonenkis dimension, Rademacher complexity, empirical risk minimization.

References

  1. Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press. doi.org/10.1017/cbo9781107298019
  2. Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media. doi.org/10.1007/978-0-387-45528-0

Cite this entry

Published version: doi.org/10.1007/978-981-92-2012-0_6-1, in Dictionary of Applied Machine Learning (Springer Nature Singapore). Please cite that version. This page corresponds to version 1 of that entry.

@incollection{dictml_hypospace,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {hypothesis space},
  booktitle = {Dictionary of Applied Machine Learning},
  publisher = {Springer Nature Singapore},
  year = {2026},
  doi = {10.1007/978-981-92-2012-0_6-1},
  isbn = {978-981-92-2012-0},
  url = {https://doi.org/10.1007/978-981-92-2012-0_6-1}
}