Growth function of a 6-dimensional linear classifier

Question

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!

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.