Computational Intelligence, SS08 2 VO 442.070 + 1 RU 708.070 last updated:
General
Course Notes (Skriptum)
Online Tutorials
 Introduction to Matlab Neural Network Toolbox OCR with ANNs Adaptive Filters VC dimension Gaussian Statistics PCA, ICA, Blind Source Separation Hidden Markov Models Mixtures of Gaussians Automatic Speech Recognition
Practical Course Slides
Homework
Exams
Animated Algorithms
Interactive Tests
Key Definitions
News
mailto:webmaster

Subsections

# Halfspaces in

Prove that the VC-dimension of the class Hn of halhspaces in n dimensions is n+1. (Hn is the set of functions , where w0,...,wn are real-valued.) 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.

## Lower Bound

Prove that VC-dim(Hn) by presenting a set of n + 1 points in n-dimensional 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 pi be the point with a 1 in the ith coordinate. Suppose we wish to partition this set into two pieces S1 and S2 with a hyperplane (and, say the origin is in S1). Then just choose the hyperplane:

## Upper Bound Part I

Theorem. Let S be a set of n+2 points in n dimensions. Then S can be partitioned into two (disjoint) subsets S1 and S2 whose convex hulls intersect.

Show that Radon's Theorem implies that the VC-dimension of halfspaces is at most n+1. Conclude that VC-dim(Hn) = n+1.

If S is a set of n+2 points, then by Radon's theorem we may partition S into sets S1 and S2 whose convex hulls intersect. Let be a point in that intersection. Assume there exist a hyperplane

so that

So no set of n+2 points can be shattered and VC-dim(Hn) = n+1.

## Upper Bound Part II

Prove Radon's Theorem. As a first step show the following. For a set of n+2 points x1,...,xn+2 in n-dimensional space, there exist not all zero such that and . (This is called affine dependence.)

We first prove the affine dependence.Let v1,...,vn+2 be defined as . So {vi} 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 S1 and S2.