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 6: VC-dimension of decision trees of depth 2



[Points: 10; Issued: 2003/04/04; Deadline: 2003/05/09; Tutor: Thomas Pock; Infohour: 2003/05/07, 14:00-15:00, Seminarraum IGI; Einsichtnahme: 2003/05/21, 14:00-15:00, Seminarraum IGI; Download: pdf; ps.gz]





Prove an upper and a lower bound for VC-dim( $ \mathcal{H}$) for the hypothesis class $ \mathcal{H}$ consisting of all decision trees of depth $ \langle 2$ for the data type $ \{0,1\}^n \times \{0,1\}$.

Remarks

  • I.e. a desicion tree $ T \in \mathcal{H}$ has a depth of maximum 2 and represents a specific function $ T:\{0,1\}^n T_\mathit{output}\{0,1\}$.