Computational Intelligence, SS08
2 VO 442.070 + 1 RU 708.070 last updated:
General
Course Notes (Skriptum)
Online Tutorials
Practical Course Slides
Homework
Assignments
Scores
Guidelines
Archive
Exams
Animated Algorithms
Interactive Tests
Key Definitions
Downloads
Literature and Links
News
mailto:webmaster

Homework 49: VC dimension



[Points: 12.5; Issued: 2007/05/14; Deadline: 2007/06/12; Tutor: Gerhard Neumann; Infohour: 2007/06/08, 15:15-16:15, HSi11; Einsichtnahme: 2007/06/22, 15:15-16:15, HSi11; Download: pdf; ps.gz]





VC dimension of rectangles [4 points]

Consider the case of the Hypothesis class of a single, axis parallel rectangle, where you can additionally choose wether to classify class 1 inside or outside the rectangle. Whats the best lower bound for the VC-dimension you can proof ? What is the best lower bound if you can use 2 rectangles instead of one ?

VC dimension of disjoint hypothesis classes [8.5 points]

Prove or disprove the following assumption: For every $ n \in \mathbf{N}$ it is true that if $ \mathcal{H}_1\subseteq\mathcal{H}$ and $ \mathcal{H}_2\subseteq\mathcal{H}$ are disjoint hypothesis classes out of the space $ \mathcal{H}$ of all possible hypothesis $ \{0,1\}^n \rightarrow \{0,1\}$, then VC-dim( $ \mathcal{H}_1\cup\mathcal{H}_2$) = VC-dim( $ \mathcal{H}_1$) + VC-dim( $ \mathcal{H}_2$).

All proofs should be clearly structured, and consist of complete sentences in perspicuous logical relationship.