Thesis (Ph. D.)--University of Rochester. Dept. of Computer Science, 1995. Simultaneously published in the Technical Report series.
Training a learning machine from examples is accomplished by minimizing a quantitative error measure, the training error defined over a training set. A low error on the training set does not, however, guarantee a low expected error on any future example presented to the learning machine---that is, a low generalization error. The main goal of the dissertation is to merge theory and practice: to develop theoretically based but experimentally adapted tools that allow an accurate prediction of the generalization error of an arbitrarily arbitrarily complex classifier. This goal is reached through experimental and theoretical studies of the relationship between the training and generalization error for a variety of learning machines. The result is the introduction of a practical and principled method for predicting the generalization error. The power and accuracy of the predictive procedure is illustrated from application to real-life problems. Theoretical inspiration for the model arises from calculations of of the expected difference between the training and generalization error for some simple learning machines. Novel computations of this character are included in the dissertation. Experimental studies yield experience with the performance ability of real-life classifiers, and result in new capacity measures for a set of classifiers. The dissertation also presents a new classification algorithm, the Soft Margin Classifier algorithm, for learning with errors on the training set. The algorithm is an extension of the Optimal Margin Classifier algorithm, and is consistently found to outperform its predecessor because it absorbs out-lying and erroneous patterns in flexible margins.
