Some new maximum VC classes

DOI10.1016/J.IPL.2014.01.006MaRDI QIDQ2446573zbMATH OpenOpenAlexFDO

Authors Hunter Johnson

Publication date 17 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial problemscomputational geometryVC dimension

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial optimization (90C27)

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.

Recommendations

• Some new Vapnik-Chervonenkis classes
• VC-dimensions of random function classes
• Density and dimension
• On the complexity of constrained VC-classes
• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• A compression approach to support vector model selection
• A geometric approach to sample compression
• Balls in \(\mathbb{R}^k\) do not cut all subsets of \(k+2\) points
• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• dp-rank and forbidden configurations
• Enumeration of Seven-Argument Threshold Functions
• Geometric measure theory.
• scientific article; zbMATH DE number 1817650 (Why is no real title available?)
• scientific article; zbMATH DE number 46153 (Why is no real title available?)
• scientific article; zbMATH DE number 67631 (Why is no real title available?)
• Measure Theory and Probability Theory
• On the density of families of sets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On Vapnik‐Chervonenkis density over indiscernible sequences
• Ordinary differential equations. A first course
• Shattering All Sets of ‘k’ Points in “General Position” Requires (k — 1)/2 Parameters
• Some special Vapnik-Chervonenkis classes
• Uniform Central Limit Theorems
• Unlabeled compression schemes for maximum classes
• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements

Cited in

(7)

• A note on the richness of convex hulls of VC classes
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
• Free resolutions of function classes via order complexes
• On the complexity of constrained VC-classes
• Comment: The Two Styles of VC Bounds
• VC bounds on the cardinality of nearly orthogonal function classes
• VC-dimensions of random function classes

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)