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 it is true that if and are disjoint hypothesis classes out of the space of all possible hypothesis , then VC-dim( ) = VC-dim( ) + VC-dim( ).

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