#### Document Type

Technical Report

#### Publication Date

1997-01-01

#### DOI:

10.7936/K747482M

#### Technical Report Number

WUCS-97-18

#### 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.

#### Recommended Citation

Bshouty, Nader H.; Goldman, Sally A.; and Mathias, H. David, "Noise-Tolerant Parallel Learning of Geometric Concepts" Report Number: WUCS-97-18 (1997). *All Computer Science and Engineering Research.*

https://openscholarship.wustl.edu/cse_research/434

## Comments

Permanent URL: http://dx.doi.org/10.7936/K747482M