PAC learning intersections of halfspaces with membership queries

DOI10.1007/PL00013834MaRDI QIDQ1271191zbMATH OpenOpenAlexFDO

Authors K. Appert

Publication date 11 November 1998

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00013834

zbMATH Keywords

POLLYrandomized learning algorithm

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• A random-sampling-based algorithm for learning intersections of halfspaces
• Learning an intersection of a constant number of halfspaces over a uniform distribution
• Learning intersections and thresholds of halfspaces
• On the hardness of learning intersections of two halfspaces

Cited in

(17)

• Cryptographic hardness for learning intersections of halfspaces
• The hardest halfspace
• A characterization of 2-threshold functions via pairs of prime segments
• Noise-tolerant distribution-free learning of general geometric concepts
• On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle
• Learning Theory
• On learning a union of half spaces
• Learning unions of high-dimensional boxes over the reals
• Exact learning from an honest teacher that answers membership queries
• New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries
• Characterizing PAC-learnability of semilinear sets
• Learning Boolean halfspaces with small weights from membership queries
• Learning Theory
• Learning intersections and thresholds of halfspaces
• On the limits of efficient teachability
• Unconditional lower bounds for learning intersections of halfspaces
• Learning intersections of halfspaces with a margin

This page was built for publication: PAC learning intersections of halfspaces with membership queries

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