3
$\begingroup$

(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?

$[00]0$, $[01]0$, $[10]0$, $[11]0$, $[00]1$, $[01]1$, $[10]1$, $[11]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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – shimao
    Aug 17, 2018 at 2:13
  • $\begingroup$ @shimao thanks, could you maybe show me with an example? $\endgroup$ Aug 17, 2018 at 9:36

1 Answer 1

8
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Awesome! I can't actually upvote your answer yet, but it makes sense. Thank you! $\endgroup$ Aug 18, 2018 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.