Noise-Tolerant Parallel Learning of Geometric Concepts

AbstractWe 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εandδdoes not depend ond. 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 define a complexity measure of any setSof (d−1)-dimensional surfaces that we call thevariantofSand prove that the class of geometric concepts defined by surfaces of polynomial variant can be efficiently 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 single surface of variant one is ∞. Finally, we give an efficient, parallel, noise-tolerant algorithm to PAC-learn any 2-dimensional geometric concept defined by a setSof 1-dimensional surfaces of polynomial length under a uniform distribution