Combinatorial Theory of Overfitting

In Combinatorial Theory of Overfitting the problem of bounding generalization ability of a learning algorithm is considered in a following discrete framework. Given a binary error matrix with rows corresponding to objects and columns corresponding to hypotheses. The “one” in a matrix cell means that a given hypothesis is wrong for a given object. One tries to find a hypothesis that makes errors as few as possible provided that only a subset of rows is observable. All partitions of an object set into an observable training sample and a hidden testing sample of fixed lengths are assumed to be equiprobable. This only probabilistic assumption is sufficient to bound the probability of overfitting and the complete cross-validation functional. Combinatorial approach enables to capture information from error matrix in most explicit and exhaustive way, thus resulting to very tight and in some cases exact generalization bounds. Some applications of combinatorial generalization bounds to learning algorithm design are