Noise-tolerant parallel learning of geometric concepts
Nader H. Bshouty, Sally A. Goldman, H. David Mathias · 1995
We present several efficient parallel algorithms for PAC-learning geometric concepts in a constantdimensional space that are robust even against malicious misclassification noise of any rate less than 1/2.In particular we consider the class of geometric concepts defined by a polynomial number of (d -1)-dimensional hyperplanes against an arbitrary distributionwhere each hyperplane has a slope from a set of known slopes, and the class of geometric concepts defined by a polynomial number of (d -1)-dimensional hyperplanes (of unrestricted slopes) against a product distribution.Next we define 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 efficiently learned in parallel under a product distribution (even under malicious misclassification noise).Finally, we describe how boosting techniques can be used so that our algorithms' dependence one and 6 does not depend on d.