Scale-sensitive dimensions and skeleton estimates for classification

DOI10.1016/S0166-218X(98)00013-4MaRDI QIDQ1265744zbMATH OpenOpenAlexFDO

Authors Márta Horváth, Gábor Lugosi

Publication date 27 April 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(98)00013-4

zbMATH Keywords

binary classificationempirical riskregression functionsskeletons

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Review text

The classical binary classification problem is investigated when it is known in advance that the posterior probability function (or regression function) belongs to some class of functions. The authors introduce and analyze methods which effectively exploit this knowledge. These methods are based on minimizing the empirical risk over a carefully selected ``skeleton of the class of regression functions. The skeletons are coverings of the class based on metrics, especially fitted for classification. A new scale-sensitive dimension is introduced which is more suitable for the studied classification problem than other, previously defined, dimension measures. This fact is demonstrated by performance bounds for the skeleton estimates in terms of the new dimension.

Recommendations

• Classifier selection from a totally bounded class of functions
• Efficiency of classification methods based on empirical risk minimization
• A general approach to classification problems
• Scale adjustments for classifiers in high-dimensional, low sample size settings
• Local Rademacher complexities

Cites work

• A metric entropy bound is not sufficient for learnability
• A result of Vapnik with applications
• Adaptive model selection using empirical complexities
• Convergence of stochastic processes
• Covering numbers for real-valued function classes
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Efficient agnostic learning of neural networks with bounded fan-in
• Efficient distribution-free learning of probabilistic concepts
• Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
• Fat-shattering and the learnability of real-valued functions
• Function Learning from Interpolation
• scientific article; zbMATH DE number 3738628 (Why is no real title available?)
• scientific article; zbMATH DE number 89080 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• Learnability and the Vapnik-Chervonenkis dimension
• Learning by canonical smooth estimation. I. Simultaneous estimation
• Learning by canonical smooth estimation. II. Learning and choice of model complexity
• On the density of families of sets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Scale-sensitive dimensions, uniform convergence, and learnability

Cited in

(1)

• Optimal aggregation of classifiers in statistical learning.

This page was built for publication: Scale-sensitive dimensions and skeleton estimates for classification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1265744)