# Size of the Hypothesis Space

(I'm asking the same question as the one linked below, I simply don't have enough reputation to comment yet, but hopefully, this one will more clearly explain what me and the other asker both mean)

Let's say I have 2 possible binary features, $$x_0$$ and $$x_1$$. Each of them can take on 2 values, either a $$0$$ or a $$1$$. Finally, I have 2 possible labels: $$y$$ can either be a $$0$$ or a $$1$$.

This means there are 4 possible data points: $$00$$ , $$01$$ , $$10$$ , $$11$$ ,

And there are 2 possible labels: $$0$$ or $$1$$

The equation for the hypothesis space I've often seen says the size of it would be: $$2^4$$, since there are 2 possible labels and 4 possible data points.

But that doesn't make any sense, shouldn't we multiply the number of possible data points by the number of possible labels instead, leaving us with a hypothesis space of 8 and not 16?

$$0$$, $$0$$, $$0$$, $$0$$, $$1$$, $$1$$, $$1$$, $$1$$

Look at the cited question to see what I mean (but it's not just the cited question that says this, I've seen it everywhere)

abeltre1, How to calculate hypothesis space, URL (version: 2017-09-13): https://stats.stackexchange.com/q/303002

• the list of 8 input output pairs you have listed are just that: input output pairs. A hypothesis is more than that: it is a mapping from inputs to outputs Aug 17, 2018 at 2:13
• @shimao thanks, could you maybe show me with an example? Aug 17, 2018 at 9:36

A hypothesis is a function $h:\mathcal{X} \to \mathcal{Y}$, where $\mathcal{X}$ is the feature space (the set of all possible inputs) and $\mathcal{Y}$ is the label space (the set of all possible outputs). In your example, \begin{align} \mathcal{X} & = \{0,1\}^2 = \{(0,0), (0,1), (1,0), (1,1)\}, \\ \mathcal{Y} & = \{0,1\}. \end{align} So a single hypothesis $h$ needs to assign a binary label to all 4 points in $\mathcal{X}$. This means that you can identify a particular hypothesis by a 4-digit binary number. For example, the hypothesis $h_{1011}$ would assign 1 to (0,0), 0 to (0,1), 1 to (1,0), and 1 to (1,1). It should be clear that the total number of hypotheses is equal to the number of 4-digit binary strings, which is $2^4$.