# Growth function of a 6-dimensional linear classifier

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!

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.