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 28: VC dimension



[Points: 8; Issued: 2003/05/06; Deadline: 2005/06/01; Tutor: Peter Bliem; Infohour: 2005/05/30, 12:00-13:00, HSi12; Einsichtnahme: 2005/06/20, 12:00-13:00, HSi12; Download: pdf; ps.gz]





a)
Consider the hypothesis class $ \mathcal{H}_{sin}$ of sinusoidal classifers $ H_w(x) := sign(\sin(w x))$ over the real line, i.e. $ x \in \mathbb{R}$, with $ w>0$. What is the VC dimension of $ \mathcal{H}_{sin}$? [4 points]
b)
Prove or disprove that for every hypothesis class of boolean functions $ F$ that has finite size and is defined over a finite domain $ X$ the VC dimension has a lower bound of $ VC(F) \ge \log(\vert F\vert)/\log(\vert X\vert)$. ($ \vert F\vert$ denotes the number of different functions in $ F$.) [4 points]