
[Points: 12.5; Issued: 2007/05/14; Deadline: 2007/06/12; Tutor:
Gerhard Neumann; Infohour: 2007/06/08, 15:1516:15,
HSi11; Einsichtnahme: 2007/06/22, 15:1516:15, HSi11; Download:
pdf; ps.gz]
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 VCdimension you can proof ? What is the best
lower bound if you can use 2 rectangles instead of one ?
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 VCdim(
) = VCdim(
) +
VCdim(
).
All proofs should be clearly structured, and consist of complete
sentences in perspicuous logical relationship.
