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 <inline-equation><f><sc>R</sc></f> </inline-equation><supscrpt>d</supscrpt> for fixed <italic>d</italic>. More specifically, let <inline-equation><f><sc>T</sc></f> </inline-equation> be any set of <italic>s</italic> halfspaces. Let <italic>x</italic> =(x<subscrpt>1</subscrpt>, …, <italic>x</italic><subscrpt>d</subscrpt>) be an arbitrary point in <inline-equation><f><sc>R</sc></f> </inline-equation><supscrpt>d</supscrpt>. With each <italic>t</italic><inline-equation><f>∈<sc>T</sc></f> </inline-equation> we associate a boolean indicator function <italic>I<subscrpt>t</subscrpt>(x)</italic> which is 1 if and only if <italic>x</italic> is in the halfspace <italic>t</italic>. The  concept class, <inline-equation><f><sc>C</sc><sup>d</sup><inf>s</inf></f> </inline-equation>, that we study consists of all  concepts formed by any Boolean function over <italic>I<subscrpt>t1</subscrpt>, …, I<subscrpt>ts</subscrpt></italic> for   <italic>t<subscrpt>i</subscrpt></italic> <inline-equation><f>∈<sc>T</sc></f> </inline-equation>. 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 <inline-equation><f><sc>C</sc></f> </inline-equation> over <inline-equation><f><sc>R</sc></f> </inline-equation> given that the VC-dimension of <inline-equation><f><sc>C</sc></f> </inline-equation> has dependence only on <italic>d</italic> and there is a polynomial time algorithm to determine if there is a concept from  <inline-equation><f><sc>C</sc></f> </inline-equation> 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  <italic>d</italic> = 2 based on geometric subdivisions.