Find the number of distinct hypotheses within hypothesis space

120 Views Asked by At

Suppose that for given instance space $X=\{0,1\}^3$ we're observing the following model H which consists of hypotheses $h(x|\theta) = x_1\theta_1 + x_2\theta_2 + x_3\theta_3 + \theta_4$, such that $h(x|\theta)<0$, $x = (x_1, x_2, x_3)$, $x_i \in \{0,1\}, i = 1, 2, 3,$ $\theta = [\theta_1, \theta_2, \theta_3, \theta_4]$, $\theta_j \in \mathbb{R}, j = 1, 2, 3, 4.$

Prove that the dimension of hypothesis space H is equal to 4, and that the number of distinct hypotheses that exist in that space is 104.

I am familiar with the following corollary:

The VC dimension of the set of oriented hyperplanes in $\mathbb{R^n}$ is $n+1$.

Therefore it's clear to me that $VC(H) = 4$. However, I do not know how to prove that the number of distinct hypotheses that exist in that space is 104.

Any help would be appreciated!