Hyperplane arrangements and compression schemes
by Hyam Rubinstein
Abstract: This is joint work with Ben Rubinstein. A concept class is a subset of binary strings of fixed finite length n. The VC dimension d is the largest subcube of the binary cube that a concept class projects onto. Sauer's lemma gives an upper bound for the cardinality of a concept class with fixed VC dimension. Classes which achieve this upper bound are called maximum. It is known that such classes admit d-compression schemes- roughly speaking they can be described by d pieces of information for each element of the class. Warmuth and Kuzmin conjectured that there was a geometric interpretation of such compression schemes. We will sketch a proof of this conjecture by representing the concept class as a Piecewise Linear hyperplane arrangement and finding a compression scheme using a sweeping or height function on the arrangement. If time permits, a sketch will be given of a concept class of VC dimension d which cannot be embedded in a maximum class of VC dimension 2d-1 but does embed in such a class of dimension 2d. This is based on an extension of Sauer's lemma.