DATA-DEPENDENT GENERALIZATION ERROR BOUNDS FOR (NOISY) CLASSIFICATION: A PAC-BAYESIAN APPROACH
The common method to understand and improve classification rules is to prove bounds on the generalization error. Here we provide localized data-based PAC-bounds for the difference between the risk of any two randomized estimators. We derive from these bounds two types of algorithms: the first one uses combinatorial technics and is related to compression schemes whereas the second one involves Gibbs estimators. We also recover some of the results of the Vapnik-Chervonenkis theory and improve them by taking into account the variance term measured by the pseudo-distance (f1, f2) 7→ [f1(X) 6= f2(X)]. Finally, we present different ways of localizing the results in order to improve the bounds and make them less dependent on the choice of the prior. For some classes of functions (such as VC-classes), this will lead to gain a logN factor (without using the chaining technique (see [1] for more details)).