In our course, we are dealing with a d-dimensional classification problem ($\chi = \mathbb{R}^{d}$ as our input space, and $y = \{-1,+1\}$). Our hypothesis class $H$ consists of all hypotheses of the following form: $h(x) = a\cdot \text{sign}(x_i - b)$, where $i = \{1,2,\dots,d\}$, $a \in \{-1,+1\}$, and $b\in\mathbb{R}$.

We have already shown that the growth function $m_{H}(3) = 2^3$ for $d=2$ by showing all 8 possible dichotomies for three chosen points. We further know that for a $d$-dimensional linear perceptron, the VC-dimension is always equal to $d+1$.

We know want to show that for $d=6$, $m_{H}(7) < 2^7$, i.e. that the VC-dimension of our hypothesis class is lower than 7.

Could you help us out with this? Thanks a lot!


1 Answer 1


Suppose we have $n$ points in $\chi$. We have $d$ choices of $i$, two choices of $a$, and at most $n+1$ effective choices of $b$ so the number of possible combinations of outputs on those $n$ points is at most $2d(n+1)$. I'm sure you can take it from here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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