Order compression schemes

Sample compression schemes are schemes for “encoding” a set of examples in a small subset of examples. The long-standing open sample compression conjecture states that, for any concept class CC of VC-dimension d  , there is a sample compression scheme in which samples for concepts in CC are compressed to samples of size at most d.We show that every order over CC induces a special type of sample compression scheme for CC, which we call order compression scheme. It turns out that order compression schemes can compress to samples of size at most d   if CC is maximum, intersection-closed, a Dudley class, or of VC-dimension 1 – and thus in most cases for which the sample compression conjecture is known to be true.Since order compression schemes are much simpler than sample compression schemes in general, their study seems to be a promising step towards resolving the sample compression conjecture. We reveal a number of fundamental properties of order compression schemes, which are helpful in such a study. In particular, order compression schemes exhibit interesting graph-theoretic properties as well as connections to the theory of learning from teachers.To obtain small compressed sets, order compression schemes for a concept class CC must often use a proper superset H⊃CH⊃C as a hypothesis space. We thus further compare order compression schemes for CC to order compression schemes for such hypothesis spaces, leading to a study of a number of mutually related combinatorial parameters specifying compressibility.