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

computational geometrycombinatorial problemsVC dimension

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• Enumeration of Seven-Argument Threshold Functions
• Geometric measure theory.
• Measure Theory and Probability Theory
• On Vapnik‐Chervonenkis density over indiscernible sequences
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the density of families of sets
• 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
• dp-rank and forbidden configurations

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)