2015/05/30 by Shay Moran, Moran, Shay, Manfred K. Warmuth +1 · 3 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #cs.DM #cs.LG #math.CO
paper · pdf · doi:10.48550/arxiv.1506.00165
21 pages, 4 figures
arxiv created 2016/07/22 · arxiv updated 2016/07/25
It is a long-standing open problem whether there always exists a compression scheme whose size is of the order of the Vapnik-Chervonienkis (VC) dimension d. Recently compression schemes of size exponential in d have been found for any concept class of VC dimension d. Previously, compression schemes of size d have been given for maximum classes, which are special concept classes whose size equals an upper bound due to Sauer-Shelah. We consider a generalization of maximum classes called extremal classes. Their definition is based on a powerful generalization of the Sauer-Shelah bound called the Sandwich Theorem, which has been studied in several areas of combinatorics and computer science. The key result of the paper is a construction of a sample compression scheme for extremal classes of size equal to their VC dimension. We also give a number of open problems concerning the combinatorial structure of extremal classes and the existence of unlabeled compression schemes for them.