Computational Intelligence, SS08
2 VO 442.070 + 1 RU 708.070 last updated:
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
Animated Algorithms
Interactive Tests
Key Definitions
Literature and Links


Halfspaces in $\mathbb{R}^n$

Prove that the VC-dimension of the class Hn of halhspaces in n dimensions is n+1. (Hn is the set of functions $w_1x_1 + ...+ w_nx_n \le w_0$, 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 $\sum_{x_i\in S}\lambda_i x_i$, where $\lambda_i \le 0$, and $\sum_i \lambda_i = 1$. 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) $\ge n + 1$ 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:
\begin{displaymath} \sum_{\{i:p_i \in S_2\}}x_i=1/2. \nonumber \end{displaymath}  

Upper Bound Part I

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 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 $p \in S_1$ be a point in that intersection. Assume there exist a hyperplane

$\displaystyle w \cdot x_i \le w_0, \hspace{5mm} \forall x_i \in S_1$      
$\displaystyle w \cdot x_i > w_0, \hspace{5mm} \forall x_i \in S_2$      

so that

\begin{displaymath} w \cdot p \le w_0 \end{displaymath}

which is contradicted by

\begin{displaymath} w \cdot p = \sum_{i:x_i \in S_2} \lambda_i w \cdot x_i > (\s... ..._i \in S_2}(w\cdot x_i)= \min_{i:x_i \in S_2}(w\cdot x_i)>w_0. \end{displaymath}

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 $\lambda_1,...,\lambda_{n+2}$ not all zero such that $\sum_i\lambda_i x_i = 0$ and $\sum_i \lambda_i = 0$. (This is called affine dependence.)

We first prove the affine dependence.Let v1,...,vn+2 be defined as $v_i = \langle x_i,1\rangle \in \mathbb{R}^{n+1}$. So {vi} is linearly dependent. And so there exist a set of scalares $\lambda_1,...,\lambda_{n+2}$, not all zero, so that $\sum_i\lambda_i v_i = 0$. These $\{\lambda_i\}$ satisfy the required conditions.

Further $S_1 = \{x_i\vert\lambda_i \ge 0 \}$ and $S_2 = \{x_i\vert\lambda_i < 0 \}$. So

\begin{displaymath}\lambda^* = \sum_{i:x_i \in S_1}\lambda_i=-\sum_{j:x_j \in S_2}\vert\lambda_j\vert.\end{displaymath}


\begin{displaymath} x^* = \sum_{i:x_i \in S_1}\lambda_i x_i=-\sum_{j:x_j \in S_2}\vert\lambda_j\vert x_j. \end{displaymath}

Consider the point

\begin{displaymath} \frac{x^*}{\lambda^*} = \sum_{i:x_i \in S_1}\frac{\lambda_i}... ...-\sum_{j:x_j \in S_2}\frac{\vert\lambda_j\vert}{\lambda^*}x_j. \end{displaymath}

This point lies in the convex hull of both S1 and S2.