I am studying ML and I got a bit confused about what Hypothesis set (Hypothesis space) is, because there are various definitions given by various people.

Short version:

  • What is a Hypothesis set and does it depend on ML algorithm? (if possible, please provide links to academic sources).
  • How to find Hypothesis set size (cardinality)?

Long version:

  1. According to this answer to similar question, hypothesis space $\mathcal{H}$ is a set of all possible mappings from input space to {0, 1} (in binary classification case); indeed, if we have 4 features each having values {0, 1} and 1 response variable having values {0, 1}, we can create $2^{2^4}=2^{16}=65536$ possible mappings or in other words possible hypotheses. So this answer claims that in the described case, $\mathcal{H} =$ {$h_1, h_2,\dots, h_{65536}$} and $|\mathcal{H}| = 65536$, and this solely depends on input space and possible responses, but does not depend on ML algorithm used..

  2. However, another answer, albeit talking about $\mathcal{H}$ being "set of all candidate formulas that could possibly explain the training examples", states that "the hypothesis test $\mathcal{H}$ is related the learning algorithm $\mathcal{A}$." This makes more sense: 2nd degree polynomial should have lesser $\mathcal{H}$ than 10th degree polynomial, as far as I understand it. According to this response, it's far from certain that $\mathcal{H} =$ {$h_1, h_2,\dots, h_{65536}$}; it rather depends on a specific chosen ML algorithm. Like, for algorithm $\mathcal{A}_1$ it's $\mathcal{H_1}$, for $\mathcal{A}_2$ it's $\mathcal{H_2}$, and $\mathcal{H_1}$ can be very different from $\mathcal{H_2}$.

And so, does $\mathcal{H}$ depend on learning algorithm, or is it just a set of all possible mappings from input space to responses which does not change from algorithm to algorithm?

As far as I understand $\mathcal{H}$ does depend on used algorithm because some algorithms physically cannot produce some hypotheses, thus their hypothesis set should be smaller than just "all possible mappings from inputs to responses", but I may be mistaken.

However, here another question arises. This article states that "hypothesis space used by a machine learning system is the set of all hypotheses that might possibly be returned by it". Well, it claims that $\mathcal{H}$ does depend on algorithm, but when we think about how many of "all possible hypotheses" there are, we can say it's infinitely many. Isn't that so? Here, let's look at classification and regression:

  1. Classification. Let's say we have 2 linearly separable classes, {-1, 1}. Let's use a Perceptron learning algorithm; to remind you, it learns and returns hypothesis in the form of $h($x$) = sign(\sum_{i=1}^{d}w_ix_i)$ where x is $d$-dimensional input vector. PLA returns us a line which separates between classes. Look at this picture (sorry for low quality as I now only have access to online paint so I had to draw by hand): onemore How many straight lines can be drawn between red and blue dots that separate them into 2 classes? Yes - infinitely many! So does that mean that hypothesis set of Perceptron is infinitely big ($|\mathcal{H}| = \mathfrak{c}$)?

  2. Regression. It's even simpler: any given input vector x can be mapped not to just 2 values like in classification, but to any real number possible, which again makes $\mathcal{H}$ infinitely large. A linear regression can map an input vector to any real number, so does this mean that hypothesis set of Linear Regression is infinitely big?

This is what confuses me. I know that people compare hypothesis sets of various algorithms, saying that some $\mathcal{H_1}$ is small and $\mathcal{H}_2$ is big. So $\mathcal{H}$ has to be finite. But how can it be finite if you can draw infinite number of lines between 2 linearly separable sets of dots like in the picture above? You can yield infinite amount of different hypothese, doesn't it make Hypothesis set infinite?

The only thing I can think of is that $\mathcal{H}$ depends not only on learning algorithm but also on a particular parameters (i.e. choice of initial weights) and particular training set $\mathcal{D}$. If parameters and train set are fixed, then hypothesis set should be finite?..

So, how do you determine cardinality of a particular $\mathcal{H}$?

Simple examples of what is hypothesis set and how to find out its size are more than welcome..


Browse other questions tagged or ask your own question.