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.

本研究针对极端分类，基于 Sandwich 定理构建了一个样本压缩方案，其尺寸等于其 VC 维度，并提出了一些有关极端分类的组合结构和无标签压缩方案存在性的问题。