Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2008 Research Summary

Properties of Maximum and Maximal VC-Classes

View Current Project Information

Benjamin I. P. Rubinstein, J. Hyam Rubinstein1 and Peter Bartlett

A compression scheme of size k for concept class C consists of a compression function that maps an n-sample consistent with C to a k-subsample and a reconstruction function that maps the subsample to a concept consistent with the original n-sample. Littlestone and Warmuth showed that having a compression scheme is sufficient for learnability [2]; whether this was necessary inspired their sample compressibility conjecture. This conjecture predicts that every concept class of finite VC-dimension d has a compression scheme of size d [2]. It has been known for some time that maximum classes (concept classes meeting Sauer's Lemma with equality) can be d-labeled compressed. Recently Kuzmin and Warmuth in [1] proposed the elegant Peeling scheme and conjectured that it is a d-unlabeled compression scheme for maximum classes. A correctness proof was conjectured, relying on a graph density upper bound and a minimum degree lower bound. In [3] we prove the density bounds (Conjecture 9.1 of [1]), while in [4-5] we disprove the conjectured degree bound (Conjectures 3.1 and 9.2). Compressing general VC classes is easily reduced to compressing maximal classes (where the addition of a single concept must increase dimension); one popular approach to d-compressing general concept classes is to embed maximal classes into maximum classes, with at most a small increase in VC-dim. We are interested in a proof of correctness for Peeling as it would imply a negative result about maximal in maximum embeddings.

In algebraic topology the natural generalization of a 1-dimensional simplicial complex (i.e., a graph) that is a tree, to d-dimensional complexes, is contractibility. In [4-5] we have generalized the characterization of VC-dimension 1 maximum classes as trees, by proving that VC-dimension d maximum classes are contractible cubical complexes. This structure is special to maximum classes and is not generally reflected by maximal classes. We are interested in finding further differences between maximum and maximal classes. In particular we are working on hyperplane arrangement characterizations of maximum classes and their relation to Peeling.

D. Kuzmin and M. K. Warmuth, "Unlabeled Compression Schemes for Maximum Classes," Journal of Machine Learning Research, Vol. 8, September 2007, pp. 2047-2081.
N. Littlestone and M. K. Warmuth, Relating Data Compression and Learnability, unpublished manuscript, 1986. http://www.cse.ucsc.edu/~manfred/pubs/lrnk-olivier.pdf.
B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein, "Shifting, One-Inclusion Mistake Bounds and Tight Multiclass Expected Risk Bounds," Advances in Neural Information Processing Systems 19, 2007, pp. 1193-1200.
B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein, Shifting: One-Inclusion Mistake Bounds and Sample Compression, UC Berkeley EECS Department, Technical Report No. UCB/EECS-2007-86, June 25, 2007.
B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein, "Shifting: One-Inclusion Mistake Bounds and Sample Compression," Journal of Computer and System Sciences Special Issue on Learning Theory 2006, (invited paper) 2007 (to appear).

1Mathematics & Statistics, Univ. Melbourne, Australia