### Abstract

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over ℛ^{d} for fixed d. More specifically, let ℑ be any set of s halfspaces. Let x = (x_{1}, ... , xd) be an arbitrary point in ℛ^{d}. With each t ∈ script T sign we associate a boolean indicator function I,(x) which is 1 if and only if x is in the halfspace t. The concept class, script c sign_{s}^{d} that we study consists of all concepts formed by any Boolean function over I_{t1}, ..., I_{ts} for t_{i} ∈ script T sign. This class is much more general than any geometric concept class known to be PAC-learnable. Our results can be extended easily to learn efficiently any Boolean combination of a polynomial number of concepts selected from any concept class script c sign over ℛ^{d} given that the VC-dimension of script c sign has dependence only on d and there is a polynomial time algorithm to determine if there is a concept from script c sign consistent with a given set of labeled examples. We also present a statistical query version of our algorithm that can tolerate random classification noise. Finally we present a generalization of the standard ∈-net result of Haussler and Welzl [1987] and apply it to give an alternative noise-tolerant algorithm for d = 2 based on geometric subdivisions.

Original language | English |
---|---|

Pages (from-to) | 863-890 |

Number of pages | 28 |

Journal | Journal of the ACM |

Volume | 45 |

Issue number | 5 |

DOIs | |

Publication status | Published - Sep 1998 |

### Keywords

- Algorithms
- Computational learning
- F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
- Geometric concepts
- Theory

## Fingerprint Dive into the research topics of 'Noise-Tolerant Distribution-Free Learning of General Geometric Concepts'. Together they form a unique fingerprint.

## Cite this

*Journal of the ACM*,

*45*(5), 863-890. https://doi.org/10.1145/290179.290184