A Generalized Model of PAC Learning and its Applicability

We combine a new data model, where the random classification is subjected to rather weak restrictions which in turn are based on the Mammen-Tsybakov (1999, 2004) small margin conditions, andthe statistical query (SQ) model due to Kearns (1998) to what we refer to as PAC + SQ model. We generalize the class conditional constant noise (CCCN) model introduced by Decatur (1997) to the noise model orthogonal to a set of query functions. We show that every polynomial time PAC+SQ learning algorithm can be efficiently simulated provided that the random noise rate is orthogonal to the query functions used by the algorithm given the target concept. Furthermore, we extend the constant-partition classification noise (CPCN) model due to Decatur (1997) to what we call the constant- partition piecewise orthogonal (CPPO) noise model. We show how statistical queries can be simulated in the CPPO scenario, given the partition is known to the learner. We show how to practically use PAC + SQ simulators in the noise model orthogonal to the query space by presenting two examples from bioinformatics and software engineering. That way we demonstrate that our new noise model is a realistic one.