A new composition theorem for learning algorithms
Nader H. Bshouty · 1998
Abotractwe present a new approach to the composition of learning algorithmo (in various models) for classes of constant VC-dimension into learning algorithms for more complicated classes.We prove thnt if a class C is learnable in time t from a hypothesis class 7f of constant VC-dimension then the class C* of all functions F of the form F = f(gr,,,.,gm),where f is any function and gr , , , , , gm E C, is learnable in time polynomial in t and m .We alao use n simple argument to prove that the composition theorem cannot be extended to classes with a nonconstant VC-dimension.A composition theorem for the exact learning model (withequivnlcnce queries only) is proven in [BBK97] on1y for classes C of constant VC-dimension that have conrlant space learning algorithms.Constant space algorithms are hard to find and have large complexity, Our algorithm is simple and has a complexity lower than the algorithm in [BBK97].WC then show how to change a PAC.-learning algorithm of C from '#I! to an SQ-learning algorithm and to a PAC-learning algorllhm for C" with malicious noise that achieves the optimal error rate v/(1 -pl) + /3 for any p.This, in particular, shows that if a class of constant VC-dimension is PAC-learnable from a class of conotnnt VC-dimension then it is SQ-learnable and PAC-learnable with mnlicious noise.We apply this result for SQ-learning and PAC-lenming with malicious noise a general class of geometric objects, Thls class includes the set of all geometric objects in the constant dimensional space that are bounded by m algebraic surfaces of constant degree (for example, hyperplanes, spheres, etc.).This result generalizes nil the results known from the literature about lcnming geometric objects in the SQ-learning and PAC-learning models with malicious noise.