Shattering with halfspaces

Question

I came across the result that, for the concept class of linear predictors where the weight vector has zero-norm $k$, I am able to shatter logarithmically many points with respect to the class where $k=1$

I'm just having a lot of trouble visualizing this and trying to prove it, and have tried many different configurations of logarithmically many points to no avail. the weight vector here, with 0-norm of $1$, means that when we assign it for a given classifier, we can choose only one axis to 'activate'. I have tried arranging $\log d$ points such that they all fall on different axes, but then, with a single $w$, you are unable to achieve the labeling where, say, two points belong to the class $+1$, as, for any $i$, both points won't have a nonzero $i$-th component and hence can't both be activated by the same $w$.

I would be very much appreciative if anyone could help me determine the correct configuration of these points.

Answer 1

If the shattering number is $\Omega(\log d)$ that means you get $d=2^{O(n)}$ dimensions for $n$ points, which is a lot of dimensions. Specifically, it's enough to have one dimension for every subset of the points. List out all the subsets of $n$ points, and use binary to assign a number from $0$ to $2^n-1$ to each one.

For each, with $n=3$, writing 0 for the point not being in the set and 1 for being in the set

• 0,0,0: 0
• 0,0,1: 1
• 0,1,0: 2
• 0,1,1: 3
• 1,0,0: 4
• 1,0,1: 5
• 1,1,0: 6
• 1,1,1: 7

Now, represent the $i=1,\dots,n$th point in $\mathbb{R}^{2^n}=\mathbb{R}^8$ with a 1 for the subsets it's in and a 0 for the ones it isn't in

The first point is in subsets 4, 5, 6, and 7, so it gets $(0,0,0,0,1,1,1,1)$. The second point is in subsets 2, 3, 6, and 7 so it gets $(0,0,1,1,0,0,1,1)$, and the third point is in subsets 1, 3, 5, 7, so it gets $(0,1,0,1,0,1,0,1)$. These 8-vectors can be obtained by reading down the columns of the list above.

And finally, if you want a specific subset, you just read off it's dimensions. The empty set is dimension 1, so $\langle 1,0,0,0,0,0,0,0\rangle$; the set $\{2,3\}$ is dimension 3, so $\langle 0,0,1,0,0,0,0,0\rangle$