Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.
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.
Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.
Shashank Ahire, Melissa Guyre, et al.
CUI 2025
Ella Barkan, Ibrahim Siddiqui, et al.
Computational And Structural Biotechnology Journal
George Saon
SLT 2014