Support-Vector Networks

n## Abstract

Abstract

The support-vector network is a new learning machine for two-group classification problems. The machine conceptually implements the following idea: input vectors are non-linearly mapped to a very high-dimension feature space. In this feature space a linear decision surface is constructed. Special properties of the decision surface ensures high generalization ability of the learning machine. The idea behind the support-vector network was previously implemented for the restricted case where the training data can be separated without errors. We here extend this result to non-separable training data.

High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated. We also compare the performance of the support-vector network to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.

Notes

1. Introduction

Gaussian class models

For an input and class label , the two populations are modelled by class-conditional Gaussian distributions:

The mean locates class ; its covariance matrix describes the joint spread of its coordinates. Under zero–one loss, the Bayes rule chooses the larger posterior probability.

• Separate covariance matrices yield quadratic discriminant analysis (QDA), with a generally quadratic boundary.
• A shared covariance yields linear discriminant analysis (LDA): the terms cancel. With equal class priors, the score favouring class is

The score is affine in , and is an affine hyperplane when the means differ. Unequal priors add to the offset.

Equation (1) as printed

The Gaussian log-density derivation gives the class--minus-class- score

The printed equation reverses the quadratic difference and gives the determinant term without the factor . Reversing the whole score would swap class labels, but would also reverse the determinant term. These notes use the density-derived score above, which reduces to equation (2) for shared covariance and equal priors.

Why prefer a linear rule with limited data?

The passage counts the adjustable boundary coefficients after removing an irrelevant overall scale:

See A Simpler Boundary Can Be Easier to Estimate for the coefficient count and the distinction between boundary parameters and Gaussian-model parameters. The simpler family can have less estimation error, even when the population-optimal boundary is curved. The suggestion that fewer than roughly observations may be inadequate is a heuristic, not a universal sample-size theorem.

A shared covariance is also a modelling choice

The proposed linear rule can use a shared matrix

even when the actual class covariances differ. In practice the matrices must be estimated; sample-size-weighted pooling is one conventional choice of weights. The rule can also be used for non-Gaussian classes, but its Gaussian Bayes-optimality guarantee then no longer applies.

Figure 1: a feature map followed by a linear output

The multilayer perceptron has layer sizes . Its hidden layers construct a feature representation:

The final score is linear in the hidden representation , not necessarily in the original input . Non-linear hidden activations make the composite map a non-linear feature map; dot-products alone would not do so. This gives the same structural separation used by support-vector networks: construct features, then place a linear decision boundary in their space.