On ordinal VC-dimension and some notions of complexity

DOI10.1016/J.TCS.2006.07.041MaRDI QIDQ860824zbMATH OpenOpenAlexFDO

Authors A. K. Sharma, Frank Stephan, Éric Martin

Publication date 9 January 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.07.041

zbMATH Keywords

generalized VC-dimensioninductive inferencepredictive complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational learning theory (68Q32)

Recommendations

• On ordinal VC-dimension and some notions of complexity
• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
• Results on learnability and the Vapnik-Chervonenkis dimension
• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
• Learnability and the Vapnik-Chervonenkis dimension

Cites work

• A note on batch and incremental learnability
• A note on VC-dimension and measure of sets of reals
• A theory of the learnable
• scientific article; zbMATH DE number 1966621 (Why is no real title available?)
• scientific article; zbMATH DE number 2084839 (Why is no real title available?)
• scientific article; zbMATH DE number 1416102 (Why is no real title available?)
• Inductive inference of formal languages from positive data
• Language identification in the limit
• Learnability and the Vapnik-Chervonenkis dimension
• On the role of procrastination in machine learning
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Ordinal mind change complexity of language identification

Cited in

(1)

• On ordinal VC-dimension and some notions of complexity

This page was built for publication: On ordinal VC-dimension and some notions of complexity

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