Noise-Tolerant Distribution-Free Learning of General Geometric Concepts

Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, Hisao Tamaki

Research output: Contribution to journalArticle

11 Citations (Scopus)


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 = (x1, ... , 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 signsd that we study consists of all concepts formed by any Boolean function over It1, ..., Its for ti ∈ 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 languageEnglish
Pages (from-to)863-890
Number of pages28
JournalJournal of the ACM
Issue number5
Publication statusPublished - Sep 1998


  • 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