Back to Search
Start Over
Unlabeled sample compression schemes and corner peelings for ample and maximum classes
- Source :
- Journal of Computer and System Sciences, Journal of Computer and System Sciences, 2022, 127, pp.1-28, Leibniz International Proceedings in Informatics, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 2019, Patras, Greece. pp.34:1--34:15, ⟨10.4230/LIPIcs.ICALP.2019.34⟩, HAL
- Publication Year :
- 2022
- Publisher :
- HAL CCSD, 2022.
-
Abstract
- International audience; We examine connections between combinatorial notions that arise in machine learning and topological notions in cubical/simplicial geometry. These connections enable to export results from geometry to machine learning. Our first main result is based on a geometric construction by Tracy Hall (2004) of a partial shelling of the cross-polytope which can not be extended. We use it to derive a maximum class of VC dimension 3 that has no corners. This refutes several previous works in machine learning from the past 11 years. In particular, it implies that all previous constructions of optimal unlabeled sample compression schemes for maximum classes are erroneous. On the positive side we present a new construction of an unlabeled sample compression scheme for maximum classes. We leave as open whether our unlabeled sample compression scheme extends to ample (a.k.a. lopsided or extremal) classes, which represent a natural and far-reaching generalization of maximum classes. Towards resolving this question, we provide a geometric characterization in terms of unique sink orientations of the 1-skeletons of associated cubical complexes.
- Subjects :
- Computational Geometry (cs.CG)
FOS: Computer and information sciences
Computer Science - Machine Learning
General Computer Science
Discrete Mathematics (cs.DM)
Computer Networks and Communications
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
Theoretical Computer Science
Machine Learning (cs.LG)
unique sink orientation
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
FOS: Mathematics
Mathematics - Combinatorics
[MATH.MATH-MG]Mathematics [math]/Metric Geometry [math.MG]
000 Computer science, knowledge, general works
Applied Mathematics
ample/extremal class
Sauer-Shelah-Perles lemma
VC-dimension
maximum class
corner peeling
Computational Theory and Mathematics
Sandwich lemma
sample compression
Computer Science
Computer Science - Computational Geometry
Combinatorics (math.CO)
Computer Science - Discrete Mathematics
Subjects
Details
- Language :
- English
- ISSN :
- 00220000 and 10902724
- Database :
- OpenAIRE
- Journal :
- Journal of Computer and System Sciences, Journal of Computer and System Sciences, 2022, 127, pp.1-28, Leibniz International Proceedings in Informatics, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 2019, Patras, Greece. pp.34:1--34:15, ⟨10.4230/LIPIcs.ICALP.2019.34⟩, HAL
- Accession number :
- edsair.doi.dedup.....36c1f65ed2968da8ffa5df991e2d8892