Noise-tolerant distribution-free learning of general geometric concepts
Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, Hisao Tamaki ยท Journal of the ACM ยท 1998
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 , โฆ, x d ) be an arbitrary point in โ d . With each t โ ๐ฏ we associate a boolean indicator function I t (x) which is 1 if and only if x is in the halfspace t . The concept class, ๐ d s , that we study consists of all concepts formed by any Boolean function over I t1 , โฆ, I ts for t i โ ๐ฏ. 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 ๐ over โ d given that the VC-dimension of ๐ has dependence only on d and there is a polynomial time algorithm to determine if there is a concept from ๐ 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.