Computer Science – Learning
Scientific paper
2009-11-18
Computer Science
Learning
37 pages, 18 figures, submitted to the Journal of Machine Learning Research
Scientific paper
The Sample Compression Conjecture of Littlestone & Warmuth has remained unsolved for over two decades. This paper presents a systematic geometric investigation of the compression of finite maximum concept classes. Simple arrangements of hyperplanes in Hyperbolic space, and Piecewise-Linear hyperplane arrangements, are shown to represent maximum classes, generalizing the corresponding Euclidean result. 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 cubical complexes.
Rubinstein Benjamin I. P.
Rubinstein Hyam J.
No associations
LandOfFree
A Geometric Approach to Sample Compression does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Geometric Approach to Sample Compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Geometric Approach to Sample Compression will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-241829