Measurability Aspects of the Compactness Theorem for Sample Compression Schemes
This work resolves a measurability gap in sample compression theory, which is crucial for ensuring learnability in machine learning contexts, though it is incremental as it builds on existing compactness results.
The paper addresses the issue of measurability in sample compression schemes derived from the compactness theorem, showing that for a standard Borel space with a d-maximum and universally separable concept class, there exists a sample compression scheme of size d with universally Borel measurable hypotheses, and introduces a new variant called copy sample compression scheme.
It was proved in 1998 by Ben-David and Litman that a concept space has a sample compression scheme of size d if and only if every finite subspace has a sample compression scheme of size d. In the compactness theorem, measurability of the hypotheses of the created sample compression scheme is not guaranteed; at the same time measurability of the hypotheses is a necessary condition for learnability. In this thesis we discuss when a sample compression scheme, created from com- pression schemes on finite subspaces via the compactness theorem, have measurable hypotheses. We show that if X is a standard Borel space with a d-maximum and universally separable concept class C, then (X,C) has a sample compression scheme of size d with universally Borel measurable hypotheses. Additionally we introduce a new variant of compression scheme called a copy sample compression scheme.