On learning a union of half spaces

DOI10.1016/0885-064X(90)90012-3zbMath0702.68089MaRDI QIDQ915490

Eric B. Baum

Publication date: 1990

Published in: Journal of Complexity (Search for Journal in Brave)

zbMATH Keywords

polynomial timelearning from exampleslearnabilitycredit assignment problemlower bounds on the number of examples

Mathematics Subject Classification ID

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

Related Items (9)

An algorithmic theory of learning: robust concepts and random projection ⋮ Learning an intersection of a constant number of halfspaces over a uniform distribution ⋮ Almost optimal set covers in finite VC-dimension ⋮ Complexity of network training for classes of Neural Networks ⋮ Learning convex bodies under uniform distribution ⋮ An algorithmic theory of learning: Robust concepts and random projection ⋮ Noise-tolerant parallel learning of geometric concepts ⋮ Learning fixed-dimension linear thresholds from fragmented data ⋮ On the limits of efficient teachability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• On the complexity of loading shallow neural networks
• On the complexity of polyhedral separability
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• Convergence of stochastic processes

This page was built for publication: On learning a union of half spaces