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

Axis Parallel Rectangles

What is the VC-dimension of axis parallel rectangles in the plane $\mathbb{R}^2$? The target function is specified by a rectangle, and labels any example positive iff it lies inside that rectangle.

VC-dim = 4. For instance the set of points {(1,0),(0.1),(-1,0),(0,-1)} can be shattered, but if you draw the smallest enclosing box around 5 points it is not possible to label the point inside the box - and the remaining points on the edges +.