Document Open Access Logo

Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes

Authors Jérémie Chalopin , Victor Chepoi , Shay Moran , Manfred K. Warmuth

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2019.34.pdf
  • Filesize: 0.64 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
  • Theory of computation → Machine learning theory
  • Theory of computation → Computational geometry
Keywords
  • VC-dimension
  • sample compression
  • Sauer-Shelah-Perles lemma
  • Sandwich lemma
  • maximum class
  • ample/extremal class
  • corner peeling
  • unique sink orientation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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 H. 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 the previous constructions of optimal unlabeled compression schemes for maximum classes are erroneous.
On the positive side we present a new construction of an optimal unlabeled compression scheme for maximum classes. We leave as open whether our unlabeled 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.

Cite As Get BibTex

Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.34

Author Details

Jérémie Chalopin
  • CNRS, Aix-Marseille Université, Université de Toulon, LIS, Marseille, France
Victor Chepoi
  • Aix-Marseille Université, CNRS, Université de Toulon, LIS, Marseille, France
Shay Moran
  • Department of Computer Science, Princeton University, Princeton, USA
Manfred K. Warmuth
  • Computer Science Department, University of California, Santa Cruz, USA

Funding

The research of J.C. and V.C. is supported by the ANR project DISTANCIA (ANR-17-CE40-0015). The research of S.M. is supported by the Simons Foundation and the NSF; part of this project was carried while S.M. was at the Institute for Advanced Study and was supported by the National Science Foundation under agreement No. CCF-1412958. The research of M.W. is supported by the NSF grant IIS-1619271.

Acknowledgements

The authors are grateful to Olivier Bousquet for insightful discussions and to the anonymous referees for useful remarks that helped improving the presentation of this work.

References

  1. Richard P. Anstee, Lajos Rónyai, and Attila Sali. Shattering News. Graphs Combin., 18(1):59-73, 2002. URL: http://dx.doi.org/10.1007/s003730200003.
  2. Hans-Jürgen Bandelt and Victor Chepoi. Metric Graph Theory and Geometry: a Survey. In J. E. Goodman, J. Pach, and R. Pollack, editors, Surveys on Discrete and Computational Geometry: Twenty Years Later, volume 453 of Contemp. Math., pages 49-86. Amer. Math. Soc., Providence, RI, 2008. URL: http://dx.doi.org/10.1090/conm/453/08795.
  3. Hans-Jürgen Bandelt, Victor Chepoi, Andreas W. M. Dress, and Jack H. Koolen. Combinatorics of Lopsided Sets. European J. Combin., 27(5):669-689, 2006. URL: http://dx.doi.org/10.1016/j.ejc.2005.03.001.
  4. Béla Bollobás and Andrew J. Radcliffe. Defect Sauer Results. J. Combin. Theory Ser. A, 72(2):189-208, 1995. URL: http://dx.doi.org/10.1016/0097-3165(95)90060-8.
  5. Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes. arXiv preprint, 1812.02099, 2018. URL: http://arxiv.org/abs/1812.02099.
  6. Thorsten Doliwa, Gaojian Fan, Hans Ulrich Simon, and Sandra Zilles. Recursive Teaching Dimension, VC-dimension and Sample Compression. J. Mach. Learn. Res., 15(1):3107-3131, 2014. URL: http://jmlr.org/papers/v15/doliwa14a.html.
  7. Andreas W. M. Dress. Towards a Theory of Holistic Clustering. In Mathematical Hierarchies and Biology, volume 37 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 271-290. DIMACS, Amer. Math. Soc., 1996. URL: http://dx.doi.org/10.1090/dimacs/037/19.
  8. Paul H. Edelman and Robert E. Jamison. The Theory of Convex Geometries. Geom. Dedicata, 19(3):247-270, 1985. URL: http://dx.doi.org/10.1007/BF00149365.
  9. Sally Floyd. On Space Bounded Learning and the Vapnik-Chervonenkis Dimension. PhD thesis, International Computer Science Institut, Berkeley, CA, 1989. URL: https://www.icsi.berkeley.edu/icsi/node/2289.
  10. Sally Floyd and Manfred K. Warmuth. Sample Compression, Learnability, and the Vapnik-Chervonenkis Dimension. Mach. Learn., 21(3):269-304, 1995. URL: http://dx.doi.org/10.1007/BF00993593.
  11. Bernd Gärtner and Emo Welzl. Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements. Discrete Comput. Geom., 12(4):399-432, 1994. URL: http://dx.doi.org/10.1007/BF02574389.
  12. Mikhaïl Gromov. Hyperbolic Groups. In S. M. Gersten, editor, Essays in Group Theory, volume 8 of Math. Sci. Res. Inst. Publ., pages 75-263. Springer, New York, 1987. URL: http://dx.doi.org/10.1007/978-1-4613-9586-7_3.
  13. H. Tracy Hall. Counterexamples in Discrete Geometry. PhD thesis, University of California, 2004. Google Scholar
  14. Dima Kuzmin and Manfred K. Warmuth. Unlabeled Compression Schemes for Maximum Classes. J. Mach. Learn. Res., 8:2047-2081, 2007. URL: http://www.jmlr.org/papers/v8/kuzmin07a.html.
  15. James F. Lawrence. Lopsided Sets and Orthant-intersection of Convex Sets. Pacific J. Math., 104(1):155-173, 1983. URL: http://dx.doi.org/10.2140/pjm.1983.104.155.
  16. Nick Littlestone and Manfred K. Warmuth. Relating Data Compression and Learnability. Technical report, Department of Computer and Information Sciences, Santa Cruz, CA, 1986. Google Scholar
  17. Jiří Matoušek. The Number Of Unique-Sink Orientations of the Hypercube. Combinatorica, 26(1):91-99, 2006. URL: http://dx.doi.org/10.1007/s00493-006-0007-0.
  18. Tamás Mészáros and Lajos Rónyai. Shattering-Extremal Set Systems of VC Dimension at most 2. Electron. J. Combin., 21(4):P4.30, 2014. URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p30.
  19. Shay Moran. Shattering-extremal Systems. arXiv preprint, 1211.2980, 2012. URL: http://arxiv.org/abs/1211.2980.
  20. Shay Moran and Manfred K. Warmuth. Labeled Compression Schemes for Extremal Classes. In ALT 2016, volume 9925 of Lecture Notes in Comput. Sci., pages 34-49. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-46379-7_3.
  21. Shay Moran and Amir Yehudayoff. Sample Compression Schemes for VC Classes. J. ACM, 63(3):21:1-21:10, 2016. URL: http://dx.doi.org/10.1145/2890490.
  22. Mogens Nielsen, Gordon D. Plotkin, and Glynn Winskel. Petri nets, event structures and domains, part I. Theoret. Comput. Sci., 13(1):85-108, 1981. URL: http://dx.doi.org/10.1016/0304-3975(81)90112-2.
  23. Alain Pajor. Sous-espaces 𝓁₁ⁿ des Espaces de Banach. Travaux en Cours. Hermann, Paris, 1985. Google Scholar
  24. Dömötör Pálvölgyi and Gábor Tardos. Unlabeled Compression Schemes Exceeding the VC-dimension. arXiv preprint, 1811.12471, 2018. URL: http://arxiv.org/abs/1811.12471.
  25. Benjamin I. P. Rubinstein and J. Hyam Rubinstein. A Geometric Approach to Sample Compression. J. Mach. Learn. Res., 13:1221-1261, 2012. URL: http://www.jmlr.org/papers/v13/rubinstein12a.html.
  26. Michah Sageev. CAT(0) cube complexes and groups. In M. Bestvina, M. Sageev, and K. Vogtmann, editors, Geometric Group Theory, volume 21 of IAS/Park City Math. Ser., pages 6-53. Amer. Math. Soc., Inst. Adv. Study, 2012. URL: http://dx.doi.org/10.1090/pcms/021/02.
  27. Rahim Samei, Boting Yang, and Sandra Zilles. Generalizing Labeled and Unlabeled Sample Compression to Multi-label Concept Classes. In ALT 2014, volume 8776 of Lecture Notes in Comput. Sci., pages 275-290. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-11662-4_20.
  28. Norbert Sauer. On the Density of Families of Sets. J. Combin. Theory Ser. A, 13(1):145-147, 1972. URL: http://dx.doi.org/10.1016/0097-3165(72)90019-2.
  29. Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press, 2014. URL: http://dx.doi.org/10.1017/CBO9781107298019.
  30. Saharon Shelah. A Combinatorial Problem, Stability and Order for Models and Theories in Infinitary Languages. Pacific J. Math., 41(1):247-261, 1972. URL: http://dx.doi.org/10.2140/pjm.1972.41.247.
  31. Tibor Szabó and Emo Welzl. Unique Sink Orientations of Cubes. In FOCS 2001, pages 547-555. IEEE Computer Society, 2001. URL: http://dx.doi.org/10.1109/SFCS.2001.959931.
  32. Vladimir N. Vapnik and Alexey Y. Chervonenkis. On the Uniform Convergence of Relative Frequencies of Events to their Probabilities. Theory Probab. Appl., 16(2):264-280, 1971. URL: http://dx.doi.org/10.1137/1116025.
  33. Manfred K. Warmuth. Compressing to VC Dimension Many Points. In COLT/Kernel 2003, volume 2777 of Lecture Notes in Comput. Sci., pages 743-744. Springer, 2003. URL: http://dx.doi.org/10.1007/978-3-540-45167-9_60.
  34. Emo Welzl. Complete Range Spaces, 1987. Unpublished notes. Google Scholar
  35. Douglas H. Wiedemann. Hamming Geometry. PhD thesis, University of Waterloo, 1986. re-typeset July, 2006. Google Scholar
  36. Avi Wigderson. Mathematics and Computation. Princeton Univ. Press, 2019. Google Scholar
  37. Glynn Winskel. Events in Computation. PhD thesis, Edinburgh University, 1980. Google Scholar
  38. Günter M. Ziegler. Lectures on Polytopes, volume 152 of Grad. Texts in Math. Springer-Verlag, New York, 1995. URL: http://dx.doi.org/10.1007/978-1-4613-8431-1.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact