What exactly is a hypothesis space in machine learning?

Question

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

Answer 1

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.

For more information browse Abu-Mostafa's presentaton slides: https://work.caltech.edu/textbook.html

Answer 2

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

• A Few Useful Things to Know About ML

Answer 3

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).