Noise-Tolerant Parallel Learning of Geometric Concepts

Abstract

We present several efficient parallel algorithms for PAC-learning geometric concepts in a constant-dimensional space. The algorithms are robust even against malicious classification noise of any rate less than 1/2. We first give an efficient noise-tolerant parallel algorithm to PAC-learn the class of geometric concepts defined by a polynomial number of (d-1)-dimensional hyperplanes against an arbitrary distribution where each hyperplane has a slope from a set of known slopes. We then describe how boosting techniques can be used so that our algorithms' dependence on GREEK LETTER and DELTA does not depend on d. Next we give an efficient noise-tolerant parallel algorithm to PAC-learn the class of geometric concepts defined by a polynomial number of (d-1)-dimensional hyperplanes (of unrestricted slopes) against a uniform distribution. We then show how to extend our algorithm to learn this class against any (unknown) product distribution. Next we defined a complexity measure of any set S of (d-1)-dimensional surfaces that we call the variant of S and prove that the class of geometric concepts defined by surfaces of polynomial variant can be efficienty learned in parallel under a product distribution (even under malicious classification noise). Furthermore, we show that the VC-dimension of the class of geometric concepts defined by a set of surfaces S of variant v is at least v. Finally, we give an efficient, parallel, noise-tolerant algorithm to PAC-learn any geometric concept defined by a set S of (d-1)-dimensional surfaces of polynomial area under a uniform distribution.