A Geometric Approach to Sample Compression

zbMath1283.68301arXiv0911.3633MaRDI QIDQ5405160

Benjamin I. P. Rubinstein, Joachim Hyam Rubinstein

Publication date: 1 April 2014

Full work available at URL: https://arxiv.org/abs/0911.3633

zbMATH Keywords

hyperplane arrangementssample compressionhyperbolic and piecewise-linear geometryone-inclusion graphs

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Unlabeled sample compression schemes and corner peelings for ample and maximum classes, What convex geometries tell about shattering-extremal systems, Vapnik-Chervonenkis density on indiscernible sequences, stability, and the maximum property, Compression schemes for concept classes induced by three types of discrete undirected graphical models, Teaching and Compressing for Low VC-Dimension, Sign rank versus Vapnik-Chervonenkis dimension, Some new maximum VC classes, Unnamed Item, Order compression schemes, The complexity of exact learning of acyclic conditional preference networks from swap examples, Bounding Embeddings of VC Classes into Maximum Classes, Labeled Compression Schemes for Extremal Classes