The Complexity of Learning with Supportvector Machines - A Statistical Physics Study
Supportvector Machines (SVMs) have been introduced in recent years by V. Vapnik [ 1, 2] and his collaborators as a novel approach in machine learning (for detailed reviews, see e.g. [3-5]. SVMs seem to have a variety of advantages over otherlearning machines which make them an important alternative to neural networks. E.g., the training of SVMs is performed by minimizing a cost function which has a single minimum only. Despite the mathematical simplicity and elegance of SVM training, SVMs are able to learn tasks of high complexity. In fact, unlike neural networks, which have a fixed number of adjustable parameters, the flexibility of an SVM is not fixed in advance but can grow with the data. This seems like a very pleasant feature because it allows SVMs to memorize arbitrary sets of examples perfectly. However, such an unbounded flexibility could present also a potential danger. For practical applications, when the number of training examples grows large, we would like the learning process to converge to a solution which makes the machine able to generalize well on data that it has not observed before An SVM on the other hand, observing an increasing number of examples might generate hypotheses about the learning task which become more and more complex by exploring more and more of its unbounded learning capabilities. Can we expect that such a process will actually converge to a satisfactory solution when the actual task to be learnt is of .finite (but unknown) complexity? To address this question, we present results of an analysis which is based on a theoretical approach from Statistical Physics. As discussed in the contributions of Michael Biehl and Wolfgang Kinzel in this volume, the method has been already applied successfully to a variety of neural network learning problems (for a detailed review of methods and results, see e.g [6, 7]). It provided exact results for the performance of such machines in controlled analytical experiments on statistical ensembles of typical learning tasks. The approach will allow us to study the generalization performance of SVMs in an important limit where the dimensionality of the space of input features grows large.