Sample complexity for computational classification problems

DOI10.1007/S00453-007-0037-ZMaRDI QIDQ2461637zbMATH OpenOpenAlexFDO

Authors Daniil Ryabko

Publication date 28 November 2007

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://doc.rero.ch/record/310183/files/453_2007_Article_37.pdf

zbMATH Keywords

labelling function

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Computational learning theory (68Q32) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Algorithmic Learning Theory
• Computational Sample Complexity
• On limited nondeterminism and the complexity of the V-C dimension
• Results on learnability and the Vapnik-Chervonenkis dimension
• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions

Cited in

(7)

• Learning figures with the Hausdorff metric by fractals -- towards computable binary classification
• Some Sufficient Conditions on an Arbitrary Class of Stochastic Processes for the Existence of a Predictor
• Algorithmic Learning Theory
• Computational Sample Complexity
• Classification of binary vectors by stochastic complexity.
• Computational sample complexity and attribute-efficient learning
• Sample Complexity of Classifiers Taking Values in ℝ^Q, Application to Multi-Class SVMs

This page was built for publication: Sample complexity for computational classification problems

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