Exact Learning of Discretized Geometric Concepts

DOI10.1137/S0097539794274246zbMath0915.68087MaRDI 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 learning; exact learning; geometric concepts; membership and equivalence queries

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T05: Learning and adaptive systems in artificial intelligence

Related Items

Agnostic learning of geometric patterns, An optimal algorithm for proper learning of unions of two rectangles with queries, Inferring Symbolic Automata, Analysis of a multi-category classifier, Invariants for time-series constraints, Learning fixed-dimension linear thresholds from fragmented data, 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, A hybrid classifier based on boxes and nearest neighbors

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