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 5: VC-Dimension and Proofs

[Points: 12.5; Issued: 2008/05/09; Deadline: 2008/05/30; Tutor: Gerhard Neumann; Infohour: 2008/05/23, 15:30-16:30, HS i11; Einsichtnahme: 2008/06/13, 15:30-16:30, HS i11; Download: pdf; ps.gz]

## Threshold circuits [8.5 points]

Prove that each Boolean function can be computed by a threshold circuit (Schwellenschaltkreis) of depth 2.

### Remarks

• You can use the fact (without proving it) that there exists for each Boolean function a Boolean formula in disjunctive normal form (DNF); see definition 1.1.5 of Grundbegriffe der Aussagenlogik'' for the precise definition of the DNF.
• Hence you just have to prove that there exists for each Boolean formula in DNF a circuit of threshold gates (of depth 2) which outputs for each binary input vector 1 if the DNF formula is true and outputs 0 if the DNF formulae is false for the corresponding truth assignment.

## VC-dimension [4 points]

• Consider the case of the hypothesis class of axis parallel rectangles. The VC-dimension of a single rectangle is 4. Find the best lower bound if you can use 2 rectangles instead of one !
• 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 ?