Noise-tolerant distribution-free learning of general geometric concepts
We present an efficient algorithm for PAC-learning a very general class of geometric concepts over {fancy R superscript d} for fixed d. More specifically, let {T} be any set of s halfspaces. Let x = (x1,...,xd) be an arbitrary point in {fancy R superscript d}. With each t {lying in} T we associate a boolean indicator function I{sub t}(x) which is 1 if and only if x is in the halfspace t. The concept class C{super script d, subscript s} that we study consists of all concepts formed by any boolean function over It1, ...Its for ti {lying in} T. 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 C over {fancy R superscript d} given that the VC-dimension of C has dependence only on d and there is a polynomial time algorithm to determine if there is a concept from C consistent with a... Read complete abstract on page 2.