How to calculate hypothesis space I'm trying to calculate the size of the hypothesis space of a function F. This function takes $N$ binary inputs and outputs a single binary classification.
With $N$ binary inputs, then the size of the domain must be $2^N$. Then, I would think that for each of these possible $2^N$ instances there must be two hypotheses (one for each output). This would make the total number of hypotheses equal to $2 \times (2^N)$.
I have read from other sources that the correct number of hypotheses is actually $2^{(2^N)}$. What is the mistake in my thinking?
 A: In general, whenever we have a function $f: \mathcal{D} \rightarrow \mathcal{C}$, the function can be considered as an element of the set $\mathcal{C}^\mathcal{D}$ (called the function space).  The set of all possible functions with domain $\mathcal{D}$ and codomain $\mathcal{C}$ is the full function space $\mathcal{C}^\mathcal{D}$.  Each function in the space can be considered as a list of outputs for each of the inputs --- the list has $|\mathcal{D}|$ elements and each element takes on one of $|\mathcal{C}|$ possible outputs.  Consequently, using a simple application of the multiplication principle of counting, we have:
$$\begin{align}
\text{No. of possible functions with domain } \mathcal{D} \text{ and codomain } \mathcal{C} 
&= \underbrace{|\mathcal{C}| \times \cdots \times |\mathcal{C}|}_{|\mathcal{D}| \text{ times}} \\[12pt]
&= |\mathcal{C}|^{|\mathcal{D}|}. \\[6pt]
\end{align}$$
Now, you have already correctly determined that there are $2^n$ possible inputs in the domain of the function, so we have $\mathcal{D} = 2^n$ in the present case.  For every possible input in the domain the function output takes on one of two binary values, so we have $|\mathcal{C}| = 2$.  Consequently, in this case we have:
$$\text{No. of possible functions with domain } \mathcal{D} \text{ and codomain } \mathcal{C} = |\mathcal{C}|^{|\mathcal{D}|} = 2^{2^n}. $$
A: Think of the output as being a lock (0 closed, 1 opened) that is potentially opened by keys. That is, there might be no combination that can open the lock, or as many as $2^n$ keys that can open it. If the lock can be opened by only one key, then counting in binary it is some number between $0000\dots0000$ and $1111\dots1111$ for a binary number of length $n$, and there are $2^n$ of those. Next we ask how may combinations of two keys can open the lock and there are $\left(\begin{array}{c}2^n\\2\end{array}\right)$ of those.
In general, we are adding up combinations
$$\left(\begin{array}{c}2^n\\0\end{array}\right)+\left(\begin{array}{c}2^n\\1\end{array}\right)+\left(\begin{array}{c}2^n\\2\end{array}\right)+\dots+\left(\begin{array}{c}2^n\\2^n-1\end{array}\right)+\left(\begin{array}{c}2^n\\2^n\end{array}\right).$$
Finally, as order does not matter, we can use the binomial theorem (see e.g., here) to get
$${m \choose 0} + {m \choose 1} + {m \choose 2} + \dots + {m \choose m} = 2^m,$$ which substituting $m=2^n$ leads us to $2^{2^n}$, which is the answer you read.
A: To calculate the Hypothesis Space: 

if we have the given image above we can then figure it out the following way. 


*

*Count the number of attributes or features. In this case, we have four features or (4). 

*Analyze or if given what are the values corresponding to each feature (e.g. binary, or many different inputs). In this particular case, we have binary values (0/1).
Hence, 2^4 = 16. 


*So for each of the 2^4 attributes, the outputs can take 0 or 1. 
Therefore, 2^(2^4) = 65536 ways. 

