A Training Algorithm for Optimal Margin Classifiers

Problem and background

*A Training Algorithm for Optimal Margin Classifiers* is a paper by Bernhard E. Boser, Isabelle M. Guyon and Vladimir N. Vapnik, listed by ACM's Digital Library as published on 1 July 1992.^[1] It appears on pages 144 to 152 of the COLT 1992 proceedings, the fifth annual workshop on Computational Learning Theory.^[1] The paper concerns the training of classifiers: given training patterns and a decision boundary, how should the boundary be chosen? Its abstract states the aim directly: the algorithm maximizes the margin between the training patterns and the decision boundary.^[1] In a margin-based view, a classifier is not judged only by whether it separates training patterns, but also by how much room it leaves around the boundary. The paper places that margin objective at the center of the training procedure.^[1]

Method

The abstract describes a technique intended to apply to a wide variety of classification functions, including Perceptrons, polynomials and Radial Basis Functions.^[1] This breadth matters: the algorithm is not presented as tied to one function family. Another stated property is that the effective number of parameters is adjusted automatically to match the complexity of the problem.^[1] In other words, the training procedure is described as adapting the capacity of the solution to the data rather than requiring the user to set that number directly. The abstract also gives the form of the solution: it is expressed as a linear combination of supporting patterns, defined as the subset of training patterns closest to the decision boundary.^[1] These supporting patterns are the training examples nearest the boundary, so the solution is organized around that subset rather than around an arbitrary fixed formula.

The abstract adds that bounds on generalization performance are given, based on the leave-one-out method and VC-dimension.^[1] These are tools for reasoning about how well a learned classifier may perform beyond the training set; VC-dimension, for example, is a capacity measure for function classes. The paper connects its training rule to such generalization bounds.^[1]

Results

The abstract reports experiments on optical character recognition problems. In those experiments the method demonstrated good generalization compared with other learning algorithms.^[1] The result is stated as a comparison of generalization, not merely training error. Together with the generalization bounds, this gives the paper two kinds of evidence: a formal discussion of generalization performance and an empirical test on character-recognition data.^[1]

Why it matters

The paper's stated contributions fit together as one picture. Margin maximization defines what the training procedure is trying to achieve; the solution in terms of supporting patterns describes what the learned classifier depends on; automatic adjustment of the effective number of parameters describes how complexity is handled; and the leave-one-out and VC-dimension bounds describe how generalization is analyzed.^[1] The technique's applicability to Perceptrons, polynomials and Radial Basis Functions extends the discussion beyond a single model family.^[1] For readers, the abstract therefore presents not only an algorithm but a way to connect training, representation and expected performance.

Bibliographic record

ACM's Digital Library lists the paper as published on 1 July 1992 and places it on pages 144 to 152 of the COLT 1992 proceedings, the fifth annual workshop on Computational Learning Theory.^[1] The title identifies it as a training algorithm for optimal margin classifiers.^[1]