Sample compression, learnability, and the Vapnik-Chervonenkis dimension

摘要

Within the framework of pac-learning, we explore the learnability of concepts from samples using the paradigm of sample compression schemes. A sample compression scheme of sizek for a concept class\(C \subseteq 2^X \) consists of a compression function and a reconstruction function. The compression function receives a finite sample set consistent with some concept inC and chooses a subset ofk examples as the compression set. The reconstruction function forms a hypothesis onX from a compression set ofk examples. For any sample set of a concept inC the compression set produced by the compression function must lead to a hypothesis consistent with the whole original sample set when it is fed to the reconstruction function. We demonstrate that the existence of a sample compression scheme of fixed-size for a classC is sufficient to ensure that the classC is pac-learnable.