Intrinsic complexity of learning geometrical concepts from positive data

DOI10.1016/S0022-0000(03)00067-9zbMath1114.68432OpenAlexW2761450214MaRDI QIDQ1877693

Sanjay Jain, E. B. Kinber

Publication date: 19 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(03)00067-9

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Related Items

Intrinsic complexity of partial learning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Comparison of identification criteria for machine inductive inference
• Noise-tolerant parallel learning of geometric concepts
• On-line learning of rectangles and unions of rectangles
• Language learning from texts: Degrees of intrinsic complexity and their characterizations
• The learnability of unions of two rectangles in the two-dimensional discretized space
• Language learning from texts: Mindchanges, limited memory and monotonicity
• The intrinsic complexity of language identification
• A theoretical and empirical study of a noise-tolerant algorithm to learn geometric patterns
• On the intrinsic complexity of learning
• Learnability and the Vapnik-Chervonenkis dimension
• On the complexity of inductive inference
• Exact Learning of Discretized Geometric Concepts
• The Power of Vacillation in Language Learning
• LEARNING RECURSIVE LANGUAGES WITH BOUNDED MIND CHANGES
• The structure of intrinsic complexity of learning
• Criteria of language learning
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Some decidability results on grammatical inference and complexity
• Language identification in the limit
• Agnostic learning of geometric patterns