jmlr jmlr2012 jmlr2012-3 jmlr2012-3-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Benjamin I.P. Rubinstein, J. Hyam Rubinstein
Abstract: The Sample Compression Conjecture of Littlestone & Warmuth has remained unsolved for a quarter century. While maximum classes (concept classes meeting Sauer’s Lemma with equality) can be compressed, the compression of general concept classes reduces to compressing maximal classes (classes that cannot be expanded without increasing VC dimension). Two promising ways forward are: embedding maximal classes into maximum classes with at most a polynomial increase to VC dimension, and compression via operating on geometric representations. This paper presents positive results on the latter approach and a first negative result on the former, through a systematic investigation of finite maximum classes. Simple arrangements of hyperplanes in hyperbolic space are shown to represent maximum classes, generalizing the corresponding Euclidean result. We show that sweeping a generic hyperplane across such arrangements forms an unlabeled compression scheme of size VC dimension and corresponds to a special case of peeling the one-inclusion graph, resolving a recent conjecture of Kuzmin & Warmuth. A bijection between finite maximum classes and certain arrangements of piecewise-linear (PL) hyperplanes in either a ball or Euclidean space is established. Finally we show that d-maximum classes corresponding to PL-hyperplane arrangements in Rd have cubical complexes homeomorphic to a d-ball, or equivalently complexes that are manifolds with boundary. A main result is that PL arrangements can be swept by a moving hyperplane to unlabeled d-compress any finite maximum class, forming a peeling scheme as conjectured by Kuzmin & Warmuth. A corollary is that some d-maximal classes cannot be embedded into any maximum class of VC-dimension d + k, for any constant k. The construction of the PL sweeping involves Pachner moves on the one-inclusion graph, corresponding to moves of a hyperplane across the intersection of d other hyperplanes. This extends the well known Pachner moves for triangulations to c
N. Alon. On the density of sets of vectors. Discrete Mathematics, 46(2):199–202, 1983. S. Ben-David and A. Litman. Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes. Discrete Applied Mathematics, 86(1):3–25, 1998. A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the VapnikChervonenkis dimension. Journal of the ACM, 36(4):929–965, 1989. R. M. Dudley. The structure of some Vapnik-Chervonenkis classes. In L.M. Le Cam and R.A. Olshen, editors, Proceedings of the Berkeley Conference in Honor of Jerzy Neyman, volume II, pages 495–507. Wadsworth, 1985. H. Edelsbrunner. Algorithms in Combinatorial Geometry, volume 10 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1987. S. Floyd. Space-bounded learning and the Vapnik-Chervonenkis dimension. Technical Report TR-89-061, ICSI, UC Berkeley, 1989. P. Frankl. On the trace of finite sets. Journal of Combinatorial Theory (A), 34(1):41–45, 1983. M. Freedman. The topology of four-dimensional manifolds. Journal of Differential Geometry, 17: 357–454, 1982. B. G¨ rtner and E. Welzl. Vapnik-Chervonenkis dimension and (pseudo-) hyperplane arrangements. a Discrete and Computational Geometry, 12:399–432, 1994. 1259 RUBINSTEIN AND RUBINSTEIN D. Haussler. Sphere packing numbers for subsets of the boolean n-cube with bounded VapnikChervonenkis dimension. Journal of Combinatorial Theory (A), 69:217–232, 1995. D. Haussler, N. Littlestone, and M. K. Warmuth. Predicting {0, 1} functions on randomly drawn points. Information and Computation, 115(2):284–293, 1994. L. Hellerstein, 28 June 2006. pers. comm. D. Helmbold, R. Sloan, and M. K. Warmuth. Learning integer lattices. SIAM Journal on Computing, 21(2):240–266, 1992. D. Kuzmin and M. K. Warmuth. Unlabeled compression schemes for maximum classes. Journal of Machine Learning Research, 8(Sep):2047–2081, 2007. N. Littlestone and M. K. Warmuth. Relating data compression and learnability. Unpublished manuscript http://www.cse.ucsc.edu/˜manfred/pubs/lrnk-olivier.pdf, 1986. M. Marchand and J. Shawe-Taylor. The decision list machine. In Advances in Neural Information Processing Systems 15, pages 921–928, 2003. B. Mazur. A note on some contractible 4-manifolds. Annals of Mathematics, 73:221–228, 1961. T. Neylon. Sparse Solutions for Linear Prediction Problems. PhD thesis, NYU, 2006. U. Pachner. Konstruktionsmethoden und das kombinatorische Hom¨ omorphieproblem f¨ r Triano u gulationen kompakter semilinearer Mannigfaltigkeiten. (german) [Construction methods and the combinatorial homeomorphism problem for triangulations of compact semilinear manifolds]. Abhandlungen aus dem Mathematischen Seminar der Universit¨ t Hamburg, 57:69–86, 1987. a G. Perelman. Finite extinction time for the solutions to the Ricci flow on certain 3-manifolds, 2002. http://arXiv.org/math.DG/0211159v1. J. G. Ratcliffe. Foundations of Hyperbolic Manifolds. Springer-Verlag, 1994. C. Rourke and B. Sanderson. Introduction to Piecewise-Linear Topology. Springer-Verlag, 1982. B. I. P. Rubinstein and J. H. Rubinstein. Geometric & topological representations of maximum classes with applications to sample compression. In Proceedings of the 21st Annual Conference on Learning Theory (COLT’08), pages 299–310, 2008. B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein. Shifting, one-inclusion mistake bounds and tight multiclass expected risk bounds. In Advances in Neural Information Processing Systems 19, pages 1193–1200, 2007. B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein. Shifting: one-inclusion mistake bounds and sample compression. Journal of Computer and System Sciences: Special Issue on Learning Theory 2006, 75(1):37–59, 2009. N. Sauer. On the density of families of sets. Journal of Combinatorial Theory (A), 13:145–147, 1972. 1260 A G EOMETRIC A PPROACH TO S AMPLE C OMPRESSION S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247–261, 1972. S. Smale. Generalized Poincar´ conjecture in dimensions greater than four. Annals of Mathematics, e 74:391–406, 1961. V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264–280, 1971. U. von Luxburg, O. Bousquet, and B. Sch¨ lkopf. A compression approach to support vector model o selection. Journal of Machine Learning Research, 5:293–323, 2004. M. K. Warmuth. Compressing to VC dimension many points. In Proceedings of the 16th Annual Conference on Learning Theory, 2003. E. Welzl. Complete range spaces. Unpublished notes, 1987. 1261