Exact Learning of Discretized Geometric Concepts

DOI10.1137/S0097539794274246MaRDI QIDQ4210170zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 2095981
• scientific article; zbMATH DE number 1256730
• Noise-tolerant parallel learning of geometric concepts
• Intrinsic complexity of learning geometrical concepts from positive data
• scientific article; zbMATH DE number 1804103
• Noise-tolerant distribution-free learning of general geometric concepts
• Algorithms and lower bounds for on-line learning of geometrical concepts

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• Covering Polygons Is Hard
• Decision Trees for Geometric Models
• Efficient learning with virtual threshold gates
• Fast identification of geometric objects with membership queries
• scientific article; zbMATH DE number 67634 (Why is no real title available?)
• scientific article; zbMATH DE number 193511 (Why is no real title available?)
• Learnability and the Vapnik-Chervonenkis dimension
• Learning in the Presence of Malicious Errors
• Lower bound methods and separation results for on-line learning models
• Probing polygons minimally is hard
• Testing geometric objects
• Testing simple polygons.

Cited in

(21)

• Learning boxes in high dimension
• Composite geometric concepts and polynomial predictability
• 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
• Learning unions of high-dimensional boxes over the reals
• scientific article; zbMATH DE number 2089369 (Why is no real title available?)
• Noise-tolerant distribution-free learning of general geometric concepts
• Behavioral shaping for geometric concepts
• scientific article; zbMATH DE number 67634 (Why is no real title available?)
• scientific article; zbMATH DE number 1256730 (Why is no real title available?)
• scientific article; zbMATH DE number 1559548 (Why is no real title available?)
• Preference-based teaching of unions of geometric objects
• 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 union of integer hypercubes with queries (with applications to monadic decomposition)

This page was built for publication: Exact Learning of Discretized Geometric Concepts

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