Computable Shell Decomposition Bounds
John Langford, David McAllester; 5(May):529--547, 2004.
Abstract
Haussler, Kearns, Seung and Tishby introduced the notion of a shell
decomposition of the union bound as a means of understanding certain
empirical phenomena in learning curves such as phase transitions. Here
we use a variant of their ideas to derive an upper bound on the
generalization error of a hypothesis computable from its training
error and the histogram of training errors for the hypotheses in the
class. In most cases this new bound is significantly tighter than
traditional bounds computed from the training error and the
cardinality of the class. Our results can also be viewed as providing
a rigorous foundation for a model selection algorithm proposed by
Scheffer and Joachims.
[abs][pdf][ps.gz][ps]