Combinatorial variability of vapnik-chervonenkis classes with applications to sample compression schemes Original Research Article

We define embeddings between concept classes that are meant to reflect certain aspects of their combinatorial structure. Furthermore, we introduce a notion of universal concept classes - classes into which any member of a given family of classes can be embedded. These universal classes play a role similar to that played in computational complexity by languages that are hard for a given complexity class. We show that classes of half-spaces in Rn are universal with respect to families of algebraically defined classes.