We present an efficient algorithm for PAC-learning a very general class of
geometric concepts over R-d for fixed d. More specifically, let T be any se
t of s halfspaces. Let x = (x(1),...,x(d)) be an arbitrary point in R-d. Wi
th each t is an element of 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, C-
s(d), that we study consists of all concepts formed by any Boolean function
over I-t1, ..., I-ts for t(i) is an element of T. This class is much more
general than any geometric concept class known to be PAC-learnable. Our res
ults can be extended easily to learn efficiently any Boolean combination of
a polynomial number of concepts selected from any concept class C over R-d
given that the VC-dimension of C has dependence only on d and there is a p
olynomial time algorithm to determine if there is a concept from C consiste
nt with a given set of labeled examples. We also present a statistical quer
y Version of our algorithm that can tolerate random classification noise. F
inally we present a generalization of the standard epsilon-net result of Ha
ussler and Welzl [1987] and apply it to give an alternative noise-tolerant
algorithm for d = 2 based on geometric subdivisions.