Generalisation Error Bounds for Classifiers Trained with Interdependent Data

Nicolas Usunier, Massih-Reza Amini, Patrick Gallinari
Laboratoire d'Informatique Paris 6
8, rue du capitaine scott
75015 Paris

In this paper we propose a general framework to study the generalisation properties of binary classifiers trained with data which may be dependent, but are deterministically generated upon a sample of independent samples. It provides generalisation bounds for binary classification and some cases of ranking problems, and clarifies the relationship between these learning tasks.