Some new maximum VC classes
From MaRDI portal
Publication:2446573
DOI10.1016/J.IPL.2014.01.006zbMATH Open1284.68604arXiv1309.2626OpenAlexW2059728575MaRDI QIDQ2446573FDOQ2446573
Authors: Hunter Johnson 
Publication date: 17 April 2014
Published in: Information Processing Letters (Search for Journal in Brave)
Abstract: Set systems of finite VC dimension are frequently used in applications relating to machine learning theory and statistics. Two simple types of VC classes which have been widely studied are the maximum classes (those which are extremal with respect to Sauer's lemma) and so-called Dudley classes, which arise as sets of positivity for linearly parameterized functions. These two types of VC class were related by Floyd, who gave sufficient conditions for when a Dudley class is maximum. It is widely known that Floyd's condition applies to positive Euclidean half-spaces and certain other classes, such as sets of positivity for univariate polynomials. In this paper we show that Floyd's lemma applies to a wider class of linearly parameterized functions than has been formally recognized to date. In particular we show that, modulo some minor technicalities, the sets of positivity for any linear combination of real analytic functions is maximum on points in general position. This includes sets of positivity for multivariate polynomials as a special case.
Full work available at URL: https://arxiv.org/abs/1309.2626
Recommendations
Learning and adaptive systems in artificial intelligence (68T05) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Measure Theory and Probability Theory
- Some special Vapnik-Chervonenkis classes
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- Uniform Central Limit Theorems
- Geometric measure theory.
- Title not available (Why is that?)
- Enumeration of Seven-Argument Threshold Functions
- Title not available (Why is that?)
- Balls in \(\mathbb{R}^k\) do not cut all subsets of \(k+2\) points
- Unlabeled compression schemes for maximum classes
- dp-rank and forbidden configurations
- Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
- Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
- Title not available (Why is that?)
- On Vapnik‐Chervonenkis density over indiscernible sequences
- A geometric approach to sample compression
- Ordinary differential equations. A first course
- Shattering All Sets of ‘k’ Points in “General Position” Requires (k — 1)/2 Parameters
- A compression approach to support vector model selection
Cited In (7)
- VC bounds on the cardinality of nearly orthogonal function classes
- On the complexity of constrained VC-classes
- Unlabeled sample compression schemes and corner peelings for ample and maximum classes
- A note on the richness of convex hulls of VC classes
- Comment: The Two Styles of VC Bounds
- VC-dimensions of random function classes
- Free resolutions of function classes via order complexes
This page was built for publication: Some new maximum VC classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2446573)
