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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.