Exact Learning of Discretized Geometric Concepts

DOI10.1137/S0097539794274246zbMath0915.68087OpenAlexW2013631630MaRDI QIDQ4210170

Nader H. Bshouty, Paul W. Goldberg, Sally A. Goldman, H. David Mathias

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794274246

zbMATH Keywords

computational learningexact learninggeometric conceptsmembership and equivalence queries

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Related Items

Invariants for time-series constraints, Intrinsic complexity of learning geometrical concepts from positive data, The bounded injury priority method and the learnability of unions of rectangles, Learning convex partitions and computing game-theoretic equilibria from best response queries, An optimal algorithm for proper learning of unions of two rectangles with queries, Inferring Symbolic Automata, A hybrid classifier based on boxes and nearest neighbors, Agnostic learning of geometric patterns, Analysis of a multi-category classifier, Learning fixed-dimension linear thresholds from fragmented data

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bound methods and separation results for on-line learning models
• Testing geometric objects
• Efficient learning with virtual threshold gates
• Probing polygons minimally is hard
• Fast identification of geometric objects with membership queries
• Testing simple polygons.
• Learning in the Presence of Malicious Errors
• Learnability and the Vapnik-Chervonenkis dimension
• A Greedy Heuristic for the Set-Covering Problem
• Covering Polygons Is Hard
• Decision Trees for Geometric Models