A combinatorial approach to hypothesis similarity in generalization bounds
D. A. Kochedykov · Pattern Recognition and Image Analysis · 2011
The paper is concerned with the problem of function approximation on a finite training sample. Generalization ability of an approximation method is characterized by a probability of large deviation of a test sample error from the training sample error. We obtain upper bounds on this probability based on combinatorial inclusion-exclusion techniques and metric properties of a set A of binary error vectors induced by a given approximating family of functions on a finite population. We introduce a notion of connectivity-splitting profile of A ; accounting for a connectivity degree q in generalization bounds allows to reduce the bound by the factor exponential in q .