Noise-tolerant parallel learning of geometric concepts
We present several efficient parallel algorithms for PAC-learning geometric concepts in a constantdimensional 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... Read complete abstract on page 2.