Chromatic PAC-Bayes Bounds for Non-IID Data: Applications to Ranking and\n Stationary $\\beta$-Mixing Processes

Pac-Bayes bounds are among the most accurate generalization bounds for\nclassifiers learned from independently and identically distributed (IID) data,\nand it is particularly so for margin classifiers: there have been recent\ncontributions showing how practical these bounds can be either to perform model\nselection (Ambroladze et al., 2007) or even to directly guide the learning of\nlinear classifiers (Germain et al., 2009). However, there are many practical\nsituations where the training data show some dependencies and where the\ntraditional IID assumption does not hold. Stating generalization bounds for\nsuch frameworks is therefore of the utmost interest, both from theoretical and\npractical standpoints. In this work, we propose the first - to the best of our\nknowledge - Pac-Bayes generalization bounds for classifiers trained on data\nexhibiting interdependencies. The approach undertaken to establish our results\nis based on the decomposition of a so-called dependency graph that encodes the\ndependencies within the data, in sets of independent data, thanks to graph\nfractional covers. Our bounds are very general, since being able to find an\nupper bound on the fractional chromatic number of the dependency graph is\nsufficient to get new Pac-Bayes bounds for specific settings. We show how our\nresults can be used to derive bounds for ranking statistics (such as Auc) and\nclassifiers trained on data distributed according to a stationary {\\ss}-mixing\nprocess. In the way, we show how our approach seemlessly allows us to deal with\nU-processes. As a side note, we also provide a Pac-Bayes generalization bound\nfor classifiers learned on data from stationary $\\varphi$-mixing distributions.\n