Separating formal bounds from practical performance in learning systems
David A. Cohn · 1992
Learning theory has attempted to establish, among other things, bounds on the generalization performance of machine learning systems, that is, how well a learning system will perform when tested on data that was not in its training set. Although such bounds have been derived for a variety of problems [Vap82, Val84, BEHW89], it is unclear whether or not they are relevant to problems actually of interest to machine learning practitioners. The work described in this dissertation attempts to establish a link between the formal bounds and the practical performance of learning systems. I describe two empirical studies that quantify the generalization performance of learning systems trained by random sampling, and then describe a theoretically-motivated algorithm that improves generalization by "selectively...