# What exactly is a hypothesis space in machine learning?

Whilst I understand the term conceptually, I'm struggling to understand it operationally. Could anyone help me out by providing an example?

• A space where we can predict output by a set of some legal hypothesis (or function) and function is represented in terms of features. Aug 9, 2019 at 17:03

Lets say you have an unknown target function $$f:X \rightarrow Y$$ that you are trying to capture by learning. In order to capture the target function you have to come up with some hypotheses, or you may call it candidate models denoted by H $$h_1,...,h_n$$ where $$h \in H$$. Here, $$H$$ as the set of all candidate models is called hypothesis class or hypothesis space or hypothesis set.

• This answer conveys absolutely no information! What is the intended relationship between $f$, $h$, and $H$? What is meant by "hypothesis set"?
– whuber
Nov 28, 2015 at 20:50
– whuber
Nov 28, 2015 at 20:57
• The answer says very clear, h learns to capture target function f. H is the space where h1, h2,..hn got defined. Nov 29, 2018 at 21:47
• @whuber I hope this is clearer Aug 6, 2021 at 8:51
• @pentanol You have succeeded in providing a different name for "hypothesis space," but without a definition or description of "candidate model," it doesn't seem to add any information to the post. What would be useful is information relevant to the questions that were posed, which concern "understand[ing] operationally" and a request for an example.
– whuber
Aug 6, 2021 at 13:55

Suppose an example with four binary features and one binary output variable. Below is a set of observations:

x1 x2 x3 x4 | y
---------------
0  0  0  1 | 0
0  1  0  1 | 0
1  1  0  0 | 1
0  0  1  0 | 1


This set of observations can be used by a machine learning (ML) algorithm to learn a function f that is able to predict a value y for any input from the input space.

We are searching for the ground truth f(x) = y that explains the relation between x and y for all possible inputs in the correct way.

The function f has to be chosen from the hypothesis space.

To get a better idea: The input space is in the above given example $$2^4$$, its the number of possible inputs. The hypothesis space is $$2^{2^4}=65536$$ because for each set of features of the input space two outcomes (0 and 1) are possible.

The ML algorithm helps us to find one function, sometimes also referred as hypothesis, from the relatively large hypothesis space.

References

• Just a small note on your answer: the size of the hypothesis space is indeed 65,536, but the a more easily explained expression for it would be $2^{(2^4)}$, since, there are $2^4$ possible unique samples, and thus $2^{(2^4)}$ possible label assignments for the entire input space. Jan 10, 2018 at 9:52
– So S
Jan 10, 2018 at 21:00
• @SoS That one function is called classifier??
– user125163
Aug 22, 2018 at 16:26
• @Arjun Hedge: Not the one, but one function that you learned is the classifier. The classifier could be (and that's your aim) the one function.
– So S
Aug 22, 2018 at 16:50

The hypothesis space is very relevant to the topic of the so-called Bias-Variance Tradeoff in maximum likelihood. That's if the number of parameters in the model(hypothesis function) is too small for the model to fit the data(indicating underfitting and that the hypothesis space is too limited), the bias is high; while if the model you choose contains too many parameters than needed to fit the data the variance is high(indicating overfitting and that the hypothesis space is too expressive).

As stated in So S' answer, if the parameters are discrete we can easily and concretely calculate how many possibilities are in the hypothesis space(or how large it is), but normally under realy life circumstances the parameters are continuous. Therefore generally the hypothesis space is uncountable.

Here is an example I borrowed and modified from the related part in the classical machine learning textbook: Pattern Recognition And Machine Learning to fit this question:

We are selecting a hypothesis function for an unknown function hidding in the training data given by a third person named CoolGuy living in an extragalactic planet. Let's say CoolGuy knows what the function is, because the data cases are provided by him and he just generated the data using the function. Let's call it(we only have the limited data and CoolGuy has both the unlimited data and the function generating them) the ground truth function and denote it by $$y(x, w)$$. The green curve is the $$y(x,w)$$, and the little blue circles are the cases we have(they are not actually the true data cases transmitted by CoolGuy because of the it would be contaminated by some transmission noise, for example by macula or other things).

We thought that that hidden function would be very simple then we make an attempt at a linear model(make a hypothesis with a very limited space): $$g_1(x, w)=w_0 + w_1 x$$ with only two parameters: $$w_0$$ and $$w_1$$, and we train the model use our data and we obtain this: We can see that no matter how many data we use to fit the hypothesis it just doesn't work because it is not expressive enough.

So we try a much more expressive hypothesis: $$g_9=\sum_j^9 w_j x^j$$ with ten adaptive paramaters $$w_0, w_1\cdots , w_9$$, and we also train the model and then we get: We can see that it is just too expressive and fits all data cases. We see that a much larger hypothesis space(since $$g_2$$ can be expressed by $$g_9$$ by setting $$w_2, w_3, \cdots, w_9$$ as all 0) is more powerful than a simple hypothesis. But the generalization is also bad. That is, if we recieve more data from CoolGuy and to do reference, the trained model most likely fails in those unseen cases.

Then how large the hypothesis space is large enough for the training dataset? We can find an aswer from the textbook aforementioned:

One rough heuristic that is sometimes advocated is that the number of data points should be no less than some multiple (say 5 or 10) of the number of adaptive parameters in the model.

And you'll see from the textbook that if we try to use 4 parameters, $$g_3=w_0+w_1 x + w_2 x^2 + w_3 x^3$$, the trained function is expressive enough for the underlying function $$y=\sin(2\pi x)$$. It's kind a black art to find the number 3(the appropriate hypothesis space) in this case.

Then we can roughly say that the hypothesis space is the measure of how expressive you model is to fit the training data. The hypothesis that is expressive enough for the training data is the good hypothesis with an expressive hypothesis space. To test whether the hypothesis is good or bad we do the cross validation to see if it performs well in the validation data-set. If it is neither underfitting(too limited) nor overfititing(too expressive) the space is enough(according to Occam Razor a simpler one is preferable, but I digress).

• This approach looks relevant, but your explanation does not agree with that on p. 5 of your first reference: "A function $h:X\to\{0,1\}$ is called [an] hypothesis. A set $H$ of hypotheses among which the approximation function $y$ is searched is called [the] hypothesis space." (I would agree the slide is confusing, because its explanation implicitly requires that $C=\{0,1\}$, whereas that is generically labeled "classes" in the diagram. But let's not pass along that confusion: let's rectify it.)
– whuber
Sep 24, 2016 at 15:33
• @whuber I updated my answer just now more than two years later after I have learned more knowledge on the topic. Please help check if I can rectify it in a better way. Thanks. Feb 5, 2019 at 11:41