Noise-tolerant distribution-free learning of general geometric concepts
Authors:
Open Access
- 1 September 1998
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 45 (5) , 863-890
Abstract
We present an efficient algorithm for PAC-learning a very general class of geometric concepts over ℛ d for fixed d . More specifically, let 𝒯 be any set of s halfspaces. Let x =(x 1 , …, x d ) be an arbitrary point in ℛ d . With each t ∈ 𝒯 we associate a boolean indicator function I t (x) which is 1 if and only if x is in the halfspace t . The concept class, 𝒞 d s , that we study consists of all concepts formed by any Boolean function over I t1 , …, I ts for t i ∈ 𝒯. This class is much more general than any geometric concept class known to be PAC-learnable. Our results can be extended easily to learn efficiently any Boolean combination of a polynomial number of concepts selected from any concept class 𝒞 over ℛ d given that the VC-dimension of 𝒞 has dependence only on d and there is a polynomial time algorithm to determine if there is a concept from 𝒞 consistent with a given set of labeled examples. We also present a statistical query version of our algorithm that can tolerate random classification noise. Finally we present a generalization of the standard ε-net result of Haussler and Welzl [1987] and apply it to give an alternative noise-tolerant algorithm for d = 2 based on geometric subdivisions.Keywords
This publication has 21 references indexed in Scilit:
- Noise-Tolerant Parallel Learning of Geometric ConceptsInformation and Computation, 1998
- Exact Learning of Discretized Geometric ConceptsSIAM Journal on Computing, 1998
- Efficient NC algorithms for set cover with applications to learning and geometryJournal of Computer and System Sciences, 1994
- The Perceptron Algorithm is Fast for Nonmalicious DistributionsNeural Computation, 1990
- On learning a union of half spacesJournal of Complexity, 1990
- Learnability and the Vapnik-Chervonenkis dimensionJournal of the ACM, 1989
- Learning From Noisy ExamplesMachine Learning, 1988
- Queries and Concept LearningMachine Learning, 1988
- Occam's RazorInformation Processing Letters, 1987
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979