On Overfitting of Classifiers Making a Lattice

摘要

Obtaining accurate bounds of the probability of overfitting is a fundamental question in statistical learning theory. In this paper we propose exact combinatorial bounds for the family of classifiers making a lattice. We use some lattice properties to derive the probability of overfitting for a set of classifiers represented by concepts. The extent of a concept, in turn, matches the set of objects correctly classified by the corresponding classifier. Conducted experiments illustrate that the proposed bounds are consistent with the Monte Carlo bounds.