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 24: Relationship between the true error of a hypothesis and its error on the training set.



[Points: 8; Issued: 2005/03/18; Deadline: 2005/04/28; Tutor: Stefan Rath; Infohour: 2005/04/25, 12:00-13:00, Seminarraum IGI; Einsichtnahme: 2005/05/16, 12:00-13:00, Seminarraum IGI; Download: pdf; ps.gz]





Construct for every $ k\in \mathbb{N}$ a probability measure $ P_k$ on $ \mathbb{R}^2\times\{0,1\}$ and a class $ {\cal H}_k$ of hypotheses $ H:\mathbb{R}^2\rightarrow \{0,1\}$ for which you can prove: for every $ k\in \mathbb{N}$ there exists a nonempty list $ L_k$ of examples $ \langle \mathbf{a},b\rangle \in \mathbb{R}^2 times \{0,1\}$ with $ P_k(\langle \mathbf{a},b\rangle )>0$ for all $ \langle \mathbf{a},b\rangle $ in $ L_k$ and a hypothesis $ H_k\in{\cal H}_k$ so that $ error_{L_k}(H_k)>0$ and $ error_{P_k}(H_k)>k\cdot error_{L_k}(H_k)$. The construction and the proof should be clearly structured, and consist of complete sentences in perspicuous logical relationship.

Note:

You can get up to 2 extra $ *$-points if you can arrange your construction so that the same $ P_k$ and the same $ {\cal H}_k$ can be chosen for all $ k\in \mathbb{N}$.