The Hypothesis Space: The Universe of Possible Models

When we say a machine learning algorithm 'learns' a model, what does that actually mean? What are the possible things it could learn? How does it decide which one to pick?

These questions lead us to one of the most fundamental concepts in machine learning theory: the hypothesis space.

The hypothesis space is the set of all possible functions that a learning algorithm is allowed to consider. It's the universe within which learning takes place. Understanding hypothesis spaces illuminates:

• Why some algorithms work well for certain problems and poorly for others
• The fundamental tradeoff between expressiveness and learnability
• Why overfitting occurs and how to prevent it
• The theoretical foundations that underpin all of machine learning

This is where machine learning moves from practical engineering to rigorous mathematics—and understanding this transition is essential for developing principled intuition about ML.

Let's establish the formal vocabulary.

Definition: Hypothesis

A hypothesis $h$ is a function that maps inputs to outputs:

$$h: \mathcal{X} \rightarrow \mathcal{Y}$$

where $\mathcal{X}$ is the input space (feature space) and $\mathcal{Y}$ is the output space (label space).

For classification: $h(\mathbf{x})$ predicts a class label For regression: $h(\mathbf{x})$ predicts a real value

Definition: Hypothesis Space (or Hypothesis Class)

The hypothesis space $\mathcal{H}$ is the set of all hypotheses that the learning algorithm considers:

$$\mathcal{H} = {h : \mathcal{X} \rightarrow \mathcal{Y}}$$

This set is determined by the choice of algorithm and any constraints we impose. The learning problem becomes: find the hypothesis $h^ \in \mathcal{H}$ that best fits the training data and generalizes well.*

Example: Linear Classifiers in 2D

Consider binary classification with 2D inputs $\mathbf{x} = [x_1, x_2]^T$.

A linear classifier hypothesis takes the form:

$$h_{\mathbf{w},b}(\mathbf{x}) = \text{sign}(w_1 x_1 + w_2 x_2 + b) = \text{sign}(\mathbf{w}^T \mathbf{x} + b)$$

The hypothesis space of all linear classifiers in 2D is:

$$\mathcal{H}{linear} = {h{\mathbf{w},b} : \mathbf{w} \in \mathbb{R}^2, b \in \mathbb{R}}$$

This is parameterized by 3 real numbers: $w_1$, $w_2$, and $b$. Each setting of these parameters defines a different hypothesis (a different line in 2D that separates classes).

What's NOT in This Hypothesis Space?

• Circular decision boundaries (nonlinear)
• XOR patterns (requires non-convex regions)
• Complex shapes that cannot be linearly separated

If the true pattern requires a circular boundary, no linear classifier will ever find it—it's outside the hypothesis space.

Different machine learning algorithms define different hypothesis spaces. Understanding what each algorithm can and cannot represent is crucial for algorithm selection.

Parametric vs Non-Parametric Models:

Parametric models have a fixed-size hypothesis space regardless of training data size:

• Linear regression: always $d + 1$ parameters
• Logistic regression: always $d + 1$ parameters
• Fixed-architecture neural networks: fixed number of weights

Advantage: Efficient inference, doesn't grow with data Disadvantage: May not capture complex patterns

Non-parametric models have hypothesis complexity that grows with data:

• k-NN: stores all training examples
• Kernel SVM: support vectors grow with data
• Decision trees: can grow to fit any configuration
• Gaussian Processes: one weight per training point

Advantage: Can capture arbitrarily complex patterns Disadvantage: Complexity grows, can overfit easily

Learning can be viewed as a search problem: given training data $\mathcal{D}$, find the hypothesis $h^* \in \mathcal{H}$ that best explains the data and will generalize well.

The Learning Objective:

Define a loss function $L(h, \mathcal{D})$ that measures how poorly hypothesis $h$ fits the data. Learning seeks:

$$h^* = \arg\min_{h \in \mathcal{H}} L(h, \mathcal{D})$$

How the Search Works Depends on $\mathcal{H}$:

1. Finite Hypothesis Spaces: Can enumerate all possibilities (though often infeasible)

   • Decision stumps (single-split trees): finite number of possible splits
   • Enumerate and select the best

2. Continuous, Convex Hypothesis Spaces: Gradient descent finds global optimum

   • Linear regression, logistic regression
   • Follow the gradient to the minimum

3. Continuous, Non-Convex Hypothesis Spaces: Local optimization, hope for good local minima

   • Neural networks, mixture models
   • Gradient descent finds A minimum, not necessarily THE minimum

4. Discrete, Combinatorial Spaces: Heuristic search, approximations

   • Decision tree structure
   • Greedy algorithms, beam search

Here's a fundamental tension in machine learning:

Larger hypothesis spaces → More expressive, can fit more patterns But also → More risk of fitting noise, worse generalization

This isn't just intuitive—it's mathematically formalized in learning theory.

The Generalization Bound (Informal):

With probability at least $1 - \delta$, for any hypothesis $h \in \mathcal{H}$:

$$\text{True Error}(h) \leq \text{Training Error}(h) + \text{Complexity Term}(|\mathcal{H}|, n, \delta)$$

where:

• True Error = error on unseen data (what we care about)
• Training Error = error on training data (what we observe)
• Complexity Term = penalty that grows with hypothesis space complexity
• $n$ = number of training examples

The complexity term depends on measures like:

• VC dimension (for classification): Roughly, the largest set of points the hypothesis class can shatter
• Rademacher complexity: How well the hypothesis class can fit random noise
• Number of parameters: Crude but often useful proxy

Implications:

1. Simpler hypothesis spaces generalize better (all else equal)

   • If two hypothesis spaces both contain the true function, the smaller one will typically generalize better

2. More training data allows larger hypothesis spaces

   • The complexity term shrinks with $n$, so you can afford more expressiveness

3. Regularization shrinks the effective hypothesis space

   • Even if $\mathcal{H}$ is large, regularization restricts which hypotheses are reachable

4. The right hypothesis space matches the problem complexity

   • Too small: can't capture the pattern (underfitting)
   • Too large: captures noise along with pattern (overfitting)

Every learning algorithm embodies inductive biases—assumptions about what kinds of hypotheses are preferred. Without these biases, learning would be impossible.

Why Bias is Necessary:

Consider a classification problem with 10 training examples. There are infinitely many hypotheses consistent with these 10 points:

• One that classifies exactly these 10 correctly (and labels everything else positive)
• Another that classifies these 10 correctly (and labels everything else negative)
• Infinitely many more with arbitrary behavior outside the training points

All have zero training error. How do we choose? We need preferences—biases—about which hypotheses are more likely to generalize.

Common Inductive Biases:

Matching Bias to Problem:

The art of machine learning includes choosing algorithms whose inductive biases match the problem structure:

When the inductive bias matches the problem, learning is efficient and generalization is good. When it doesn't, even vast amounts of data may not help.

Learning theory distinguishes two settings based on whether the true function is in our hypothesis space.

Realizable Setting:

The true function $f^*$ that generated the data is contained in $\mathcal{H}$:

$$f^* \in \mathcal{H}$$

In this setting:

• There exists a hypothesis with zero true error
• Learning can find a perfect predictor (with enough data)
• Theoretical guarantees are strongest

Agnostic Setting:

We make no assumption that $f^* \in \mathcal{H}$:

The best we can hope for is to find the hypothesis $h^*$ that minimizes error among all $h \in \mathcal{H}$:

$$h^* = \arg\min_{h \in \mathcal{H}} \text{True Error}(h)$$

In this setting:

• Even the best hypothesis has nonzero error (approximation error)
• We compete against the best-in-class, not perfection
• More realistic for complex real-world problems

Decomposing Error:

In the agnostic setting, the error of a learned hypothesis $\hat{h}$ can be decomposed:

$$\text{Error}(\hat{h}) = \underbrace{\text{Error}(h^)}_{\text{Approximation Error}} + \underbrace{(\text{Error}(\hat{h}) - \text{Error}(h^)}_{\text{Estimation Error}}$$

where:

• Approximation Error: Error of the best hypothesis in $\mathcal{H}$. This is zero in the realizable case. Reduced by making $\mathcal{H}$ larger.
• Estimation Error: Difference between the learned hypothesis and the best-in-class. Reduced by getting more data or making $\mathcal{H}$ smaller.

This is the essence of the bias-variance tradeoff viewed through hypothesis spaces:

• Large $\mathcal{H}$: Low approximation error, high estimation error (variance)
• Small $\mathcal{H}$: High approximation error (bias), low estimation error

Given the tradeoff between expressiveness and generalization, how do we effectively restrict the hypothesis space? Several mechanisms work together:

1. Architecture Choice:

The structure of the model defines $\mathcal{H}$:

• A 2-layer neural network defines a different $\mathcal{H}$ than a 5-layer one
• A decision tree with max depth 3 is in a smaller $\mathcal{H}$ than one with max depth 10
• A polynomial of degree 2 is simpler than degree 20

2. Regularization:

Penalizing certain hypotheses makes them effectively unreachable:

• L2 regularization (Ridge): penalizes large weights → encourages simpler, smoother functions
• L1 regularization (Lasso): penalizes non-zero weights → encourages sparse solutions
• Dropout: randomly dropping neurons → encourages distributed representations
• Early stopping: stop before full convergence → limits hypothesis complexity

3. Hyperparameter Settings:

• Learning rate: affects which minima are reachable
• Batch size: larger batches can lead to sharper minima
• Tree depth: limits decision tree expressiveness
• k in k-NN: higher k means smoother decision boundaries