
Subsections
Prove that the VCdimension of the class
H_{n} of halhspaces
in n dimensions is
n+1.
(H_{n} is the set
of functions
, where
w_{0},...,w_{n}
are realvalued.) We will use the following definition: the
convex hull of a set of points
S is the set of all convex
combinations of points S; this is
the set of all points that can be written as
, where
, and
.
It is not hard to see that if a halfspace has all points from a set
S on one side, then the entire
convex hull of S must be on that
side as well.
Prove that
VCdim(H_{n})
by presenting a set of
n + 1 points in
ndimensional space such that one
can partition that set with halfspaces in all possible ways. (And,
show how one can partition the set in any desires way.)
One good set of n+1 points is:
The origin and all points with a 1 in one coordinate and zeros in
the rest (i.e., all neighbors of the origin on the Boolean cube).
Let p_{i} be the
point with a 1 in the ith
coordinate. Suppose we wish to partition this set into two pieces
S_{1} and
S_{2} with a hyperplane
(and, say the origin is in
S_{1}). Then just choose
the hyperplane:
The following is ''Radon's Theorem''.
Theorem. Let S be a set
of n+2 points in
n dimensions. Then
S can be partitioned into two
(disjoint) subsets S_{1}
and S_{2} whose convex
hulls intersect.
Show that Radon's Theorem implies that the VCdimension of
halfspaces is at most n+1.
Conclude that
VCdim(H_{n}) =
n+1.
If S is a set of
n+2 points, then by Radon's
theorem we may partition S into
sets S_{1} and
S_{2} whose convex hulls
intersect. Let be a point in that intersection. Assume
there exist a hyperplane
so that
which is contradicted by
So no set of
n+2 points can be shattered and
VCdim(H_{n}) =
n+1.
Prove Radon's Theorem. As a first step show
the following. For a set of n+2
points
x_{1},...,x_{n+2}
in ndimensional space, there
exist
not all zero
such that
and
.
(This is called affine dependence.)
We first prove the affine dependence.Let
v_{1},...,v_{n+2}
be defined as
.
So {v_{i}} is linearly
dependent. And so there exist a set of scalares
, not all zero, so
that
. These
satisfy
the required conditions.
Further
and
.
So
Define
Consider the point
This point lies in the convex hull of both
S_{1} and
S_{2}.
