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 12: Demonstrate differences in expression power for different hypothesis classes



[Points: 8; Issued: 2004/03/04; Deadline: 2004/04/28; Tutor: Stefan Klampfl; Infohour: 2004/04/26, 12:00-13:00, Seminarraum IGI; Einsichtnahme: 2004/05/17, 12:00-13:00, Seminarraum IGI; Download: pdf; ps.gz]





Construct a probability measure $ P$ on $ \mathbf{R}^n \times \{0,1\}$ for which you can prove that there exists a hypothesis $ H:\mathbf{R}^n \rightarrow \{0,1\} $ with the following properties:

  1. $ H$ can be defined by a threshold circuit consisting of more than one gate.
  2. $ error_P(H)$ is less than the true error $ error_P(H')$ of every hypothesis $ H'$ defined by a single threshold gate.
The proof should be clearly structured and consist of complete sentences.