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 triangles in the plane $\mathbb{R}^2$? I.e., a legal target function is specified by a triangle, and labels any example positive iff it lies inside that triangle.

VC-dim = 7. Given 7 points on a circle, they can be labeled in any desired way because in any labeling, the negative examples form at most 3 contiguous blocks. Therefore one edge of the triangle can be used to cut off each block. However, no set of 8 points can be shattered. If one of the points is inside the convex hull of the rest, then it is not possible to label that point negative and the rest positive. Otherwise, it is not possible to label them in alternating +,-,+,-,+,-,+,- order.