School Seminars and Colloquia

Representing maximum classes and sample compression


by Professor Hyam Rubinstein

Institution: The University of Melbourne
Date: Tue 19th August 2008
Time: 12:00 PM
Location: Russell Love Theatre, Richard Berry Bldg, Uni of Melbourne

Abstract: This is joint work with Ben Rubinstein.

In statistical learning theory, the aim is to predict a concept from amongst an appropriate class, choosing the best fit to a given sample. A classical result is that a concept class is learnable (in the sense of Valiant) if and only if it has finite "VC dimension", which is a measure of complexity. An interesting question is whether learnability is also equivalent to having a finite size compression scheme. Ben and I have recently shown that every maximum concept class can be represented by a simple hyperplane arrangement, answering a conjecture of Kuzmin and Warmuth. This gives a nice geometric way of showing that maximum classes have compression schemes and the background to it will be described in a talk suitable for a general audience, covering ideas from combinatorics, geometry and topology.

For More Information: Paul Norbury

Colloquium Website