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


What is the VC-dimension of circles in the plane $\mathbb{R}^2$? I.e., examples are points in $\mathbb{R}^2, C=\{c_{p,r}:p\in \mathbb{R}^2,r\in \mathbb{R}\}$ and cp,r=1 if x is within distance r of p. Or, in words, a legal target function is specified by a circle, and labels any example positive iff it lies inside that circle.

VC-dim = 3. It is easy to see the VC-dimension is at least 3 since any 3 points that make up a non-degenerate triangle can be shattered.It is a bit trickier to prove that the VC-dimension is less than 4. Given 4 points, the easy case is when one is inside the convex hull of th others. In that case, because circles are convex, it is not possible to label the inside point - and the outside points +. Otherwise, call the points a,b,c,d in clockwise order. the claim is that it is not possible for one circle c1 to achieve labeling +,-,+,- and for some other c2 to achieve labeling -,+,-,+,-. If such c1, c2 existed, then their symmetric difference would consist of 4 disjoint regions, which is impossible for circles.