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
News
mailto:webmaster

Homework 44: VC dimension

[Points: 12.5; Issued: 2007/05/8; Deadline: 2007/06/12; Tutor: Gerhard Neumann; Infohour: 2006/05/29, 13:00-14:00, HSi13; Einsichtnahme: 2006/06/12, 13:00-14:00, HSi13; 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.