Scale-sensitive dimensions and skeleton estimates for classification
type: Item
instance of: scholarly article
title: Scale-sensitive dimensions and skeleton estimates for classification
zbMATH Open document ID: 0934.62065
DOI: 10.1016/S0166-218X(98)00013-4
author: Márta Horváth
author: Gábor Lugosi
published in: Discrete Applied Mathematics
publication date: 2000-04-27T00:00:00Z
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.
Mathematics Subject Classification ID: 62H30
zbMATH DE Number: 1202585
zbMATH Keywords: binary classification
zbMATH Keywords: empirical risk
zbMATH Keywords: regression functions
zbMATH Keywords: skeletons
reviewed by: Arjun K. Gupta
MaRDI profile type: Publication
cites work: Scale-sensitive dimensions, uniform convergence, and learnability
cites work: Function Learning from Interpolation
cites work: A result of Vapnik with applications
cites work: Covering numbers for real-valued function classes
cites work: Fat-shattering and the learnability of real-valued functions
cites work: Learnability and the Vapnik-Chervonenkis dimension
cites work: Learning by canonical smooth estimation. I. Simultaneous estimation
cites work: Learning by canonical smooth estimation. II. Learning and choice of model complexity
cites work: Q4881152
cites work: A metric entropy bound is not sufficient for learnability
cites work: Decision theoretic generalizations of the PAC model for neural net and other learning applications
cites work: Efficient distribution-free learning of probabilistic concepts
cites work: Efficient agnostic learning of neural networks with bounded fan-in
cites work: Adaptive model selection using empirical complexities
cites work: Q4016646
cites work: Convergence of stochastic processes
cites work: On the density of families of sets
cites work: Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
cites work: Q3924912
full work available at URL: s0166-218x(98)00013-4
OpenAlex ID: W1988355994
description: scientific article; zbMATH DE number 1202585