
FCT 2009
17th International Symposium on Fundamentals of Computation Theory
September 24, 2009, Wrocław, Poland
September 3, building D1, room 215

14^{00}15^{30}
Stephan Waack, Universität Göttingen,
A Generalized Model of PAC Learning and its Applicability
Abstract.
We generalize the class conditional constant noise model (CCCN) of PAC learning introduced by Decatur (1997) to what we call the transparent noise model. Statistical queries due to Kearns (1998) as well as the Mammen/Tsybakov small margin conditions are an integral parts.
We show that every concept class that is efficiently learnable from statistical queries in the sense of Kearns (1998) using query spaces of polynomially bounded size is efficiently learnable in the transparent noise model, too.
Haussler's covering method to learn monomials is our first vehicle for demonstrating how these ideas work in theory and practice.
We modify its cover phase to obtain an algorithm that can easier be applied. Having proved its consistency, we apply it to the problem of finding a powerful discriminator
between proteinprotein interfaces and random sets of pairs of protein surface residues. The hypothesis learned is convincing with respect
to the classification rate as well as to its biological interpretation.
This example gives evidence for the applicability of the transparent noise model in practice.
Finally, we draw a connection to the constantpartition classification noise (CPCN) due to Decatur (1997). We outline, how statistical queries can be utilized to devise efficient learning algorithms in Decatur's CPCN scenario. That way we give another proof of the fact that every concept class that is efficiently learnable from statistical queries is efficiently CPCN learnable.
