1
$\begingroup$

Statement : A half space is set of all points on one side of a linear separator, i.e., a set of the form $\{x \mid w^{T}x \ge t\}$. The VC-dimension of half spaces in $d$-dimensions is at least $d+1$.

Proof Idea. There exists a set of size $d+1$ that can be shattered by half-spaces. Select the $d$ unit-coordinate vectors plus the origin to be the $d+1$ points. Suppose $A$ is any subset of these $d+1$ points. Without loss of generality assume that the origin is in $A$. Take $0-1$ vector $w$ which has $1$'s precisely in the coordinates corresponding to vectors not in $A$. Clearly $A$ lies in the half-space $w^{T}x\le 0$ and complement of $A$ lies in the complementary half-space.

The overall idea is to show that a set of size $d+1$ can be shattered. My understanding is that they are adding origin into the set of points. So the set size will be $d+1$ but I am not getting the last two lines:

Take $0-1$ vector $w$ which has $1$'s precisely in the coordinates corresponding to vectors not in $A$. Clearly $A$ lies in the half-space $w^{T}x\le 0$ and complement of $A$ lies in the complementary half-space.

$\endgroup$

1 Answer 1

1
$\begingroup$

Let us understand the proof by example.

Suppose $d=3$.
Select $d+1=4$ points, which are the 3 unit-coordinate vectors $(1,0,0)$, $(0,1,0)$, $(0,0,1)$ and the origin $(0,0,0)$.
Let $C$ be the set of these 4 points.

Suppose $A$ is any subset of these 4 points. There are two cases.

  • The origin is not in $A$.
    Let $0{-}1$ vector $w$ be the sum of all points (vectors) in $A$. For examples, if $A$ contains $(1,0,0), (0,0,1)$, then $w=(1,0,0) + (0,0,1)=(1,0,1)$.
    Then $A = C\cap \{x \mid w^{T}x \ge 1\}$.

  • The origin is in $A$.

    Take $0{-}1$ vector $w$ which has $1$'s precisely in the coordinates corresponding to vectors not in $A$.

    For example, if $A=\{(1,0,0\}$, then $A$ does not contain $(0,1,0)$ nor $(0,0,1)$.

    • $w$ has $1$ at second coordinate since $(0,1,0)$ is not in $A$.
    • $w$ has $1$ at third coordinate since $(0,0,1)$ is not in $A$.

    So $w=(0,1,1)$. (This construction of $w$ is the same as letting $w$ be the sum of all points not in $A$.) Check that

    Clearly $A$ lies in the half-space $w^Tx\le0$ and complement of $A$ lies in the complementary half-space.

    Note that $\{x\mid w^Tx\le0\}$ is indeed of the form $\{x \mid w^{T}x \ge t\}$ since $\{x\mid w^Tx\le0\}=\{x\mid (-w)^Tx\ge0\}$.


Without loss of generality assume that the origin is in $A$.

This "without loss of generality" does not imply that author will adapt the case of the origin not in $A$ by "adding origin into" the subset $A$.

It means "let us deal with one of the cases. The other case is more or less similar." simply.

$\endgroup$

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.