Source: http://andrewback.com/webpapers/svm/index.php
Timestamp: 2019-04-22 00:02:14+00:00

Document:
RIKEN Brain Science Institute, Wako-shi, Saitama, Japan.
Historically, classifiers have been determined by choosing a structure1, and then selecting a parameter estimation algorithm used to optimize some cost function. The structure chosen fixes the best achievable generalization error, while the parameter estimation algorithm optimizes the cost function with respect to the empirical risk.
The model structure needs to be selected in some manner. If this is not done correctly, then even with zero empirical risk, it is still possible to have a large generalization error .
If we wish to avoid the problem of overfitting, as indicated by the above problem, by choosing a smaller model size or order, then it may be difficult to fit the training data (and hence minimize the empirical risk).
Determining a suitable learning algorithm for minimizing the empirical risk may still be quite difficult. It may be very hard or impossible to guarantee that the correct set of parameters.
The support vector method is a recently developed technique which is designed for efficient multidimensional function approximation . The basic idea of support vector machines (SVMs) is to determine a classifier or regression machine which minimizes the empirical risk (that is, the training set error) and the confidence interval (which corresponds to the generalization or test set error) .
In SVMs, the idea is to fix the empirical risk associated with an architecture and then to use a method to minimize the generalization error. The primary advantage of SVMs as adaptive models for binary classification and regression is that they provide a classifier with minimal VC dimension which implies low expected probability of generalization errors. SVMs can be used to classify linearly separable data and nonlinearly separable data. They can be used as nonlinear classifiers and regression machines by mapping the input space to a high dimensional feature space. In this high dimensional feature space, linear classification can be performed.
In the last few years, a significant amount of research has been performed in SVMs. Learning algorithms and training methods are examined in . Methods for determining the data to use in support vector methods has been considered in . Decision rules have been considered in .
Applications of support vector machines to speaker identification are considered in . Time series prediction applications of support vector machines have been considered in .
Support vector machines have been shown to have a relationship with other recent nonlinear classification and modeling techniques such as: radial basis function networks , sparse approximation , PCA and regularization . Support vector machines have been used to choose radial basis function centers .
The key to understanding SVMs is to see how they introduce optimal hyperplanes to separate classes of data in the classifiers. We review the main concepts of SVMs in the next section.
where w = [ w1w2�wm] T, w � W � Rm.
The concept of an optimal hyperplane was proposed by Vapnik . For the case where the training data is linearly separable, an optimal hyperplane separates the data without error and the distance between the hyperplane and the closest training points is maximal.
A canonical hyperplane is a hyperplane (in this case we consider the optimal hyperplane) in which the parameters are normalized in a particular manner .
where y � [ -1,1].
This implies that the minimum distance between two classes i and j is at least [2/( || w|| )] [6,15].
Normally, to find the parameters, we would minimize the training error and there are no constraints on w,b. However, in this case, we seek to satisfy the inequality in (3). Thus, we need to solve the constrained optimization problem in which we seek a set of weights which separates the classes in the usually desired manner and also minimizing J(w), so that the margin between the classes is also maximized. Thus, we obtain a classifier with optimally separating hyperplanes.
where ai are the Lagrange multipliers and ai > 0.
and in each case a0i > 0, i = 1,..,n.
These are properties of the optimal hyperplane specified by ( w0,b0). From (14) we note that given the Lagrange multipliers, the desired weight vector solution can be found directly in terms of the training vectors.
The training vectors for which this is the case, are called support vectors.
This means, that since the Lagrangian multipliers a0i are nonzero with only the support vectors as defined in (16), the expansion of w0 in (14) is with regard to the support vectors only.
where S is the set of all support vectors in the training set. To obtain the Lagrangian multipliers a0i, we need to maximize (15) only over the support vectors, subject to the constraints a0i > 0, i = 1,..,n and that given in (13). This is a quadratic programming problem and can be readily solved . Having obtained the Lagrangian multipliers, the weights w0 can be found from (18).
For some problems, improved classification results can be obtained using a nonlinear classifier. Consider (20) which is a linear classifier. A nonlinear classifier can be obtained using support vector machines as follows.
The classifer is obtained by the inner product xiTx where i � S, the set of support vectors. However, it is not necessary to use the explicit input data to form the classifer. Instead, all that is needed is to use this inner products between the support vectors and the vectors of the feature space .
where s is a sigmoid function.
Support vector machines offer an extremely powerful method of obtaining models for classification. They provide a mechanism for choosing the model structure in a natural manner which gives low generalization error and empirical risk.
G.E.P. Box and G.M. Jenkins. Time Series Analysis: Forecasting and Control. T. Holden-Day, San Francisco, 1976.
C. Burges, F. Girosi, P. Niyogi, T. Poggio, B. Schölkopf, K.K. Sung, and V. Vapnik. Choosing RBF centers with the support vector algorithm. A.I. Memo, MIT Artificial Intelligence Lab., Cambridge, MA, 1995.
C.J.C. Burges. Simplified support vector decision rules, 1996.
C. Cortes and V. Vapnik. Support vector networks. Machine Learning, 20:1-25, 1995.
F. Girosi. An equivalence between sparse approximation and Support Vector Machines. Neural Computation, 1997. (in press).
S. Gunn. Support vector machines for classification and regression. ISIS technical report, Image Speech & Intelligent Systems Group, University of Southampton, 1997.
K.-R. Müller, A.J. Smola, G. Rätsch, B. Schölkopf, J. Kohlmorgen and V. Vapnik. Predicting time series with support vector machines. 1997. (in press).
M.Kurtz. Handbook of Applied Mathematics for Engineers and Scientists. McGraw Hill, New York, 1991.
S. Mukherjee, E. Osuna, and F. Girosi. Nonlinear prediction of chaotic time series using support vector machines. In IEEE Workshop on Neural Networks and Signal Processing (in press), Amelia Island, FL, September 1997.
E. Osuna, R. Freund, and F. Girosi. An improved training algorithm for support vector machines. In IEEE Workshop on Neural Networks and Signal Processing (in press), Amelia Island, FL, September 1997.
E. Osuna, R. Freund, and F. Girosi. Support vector machines: Training and applications. A.I. Memo (in press) 1602, MIT A. I. Lab., 1997.
E. Osuna, R. Freund, and F. Girosi. Training support vector machines: an application to face detection. In Proc. Computer Vision and Pattern Recognition, Puerto Rico, June 16-20 1997.
T. Poggio and F. Girosi. Notes on PCA, Regularization, Support Vector Machines and Sparsity. A.I. Memo (in press), MIT Artificial Intelligence Laboratory, 1997.
M. Schmidt. Identifying speakers with support vectors networks. In Proceedings of Interface '96, Sydney, July 1996.
B. Scholkopf. Support Vector Learning. PhD thesis, Technical University of Berlin, 1997.
B. Schölkopf, C. Burges, and V. Vapnik. Extracting support data for a given task. In U.M. Fayyad and R. Uthurusamy, editors, Proceedings of the First International Conference on Knowledge Discovery and Data Mining, Menlo Park, CA, 1995. AAAI Press.
B. Schölkopf, K. Sung, C. Burges, F. Girosi, P. Niyogi, T. Poggio, and V. Vapnik. Comparing support vector machines with gaussian kernels to radial basis function classifiers. IEEE Trans. Sign. Processing, 45:2758 - 2765, 1997.
V. Vapnik. The Nature of Statistical Learning Theory. Springer, New York, 1995.
V. Vapnik, S.E. Golowich, and A. Smola. Support vector method for function approximation, regression estimation, and signal processing. In Advances in Neural Information Processings Systems 9, pages 281-287, San Mateo, CA, 1997. Morgan Kaufmann Publishers.
1 This same approach has also been used for time series modelling .
File translated from TEX by TTH, version 1.57.

References: V. 
 V. 
 V. 
 V. 
 V. 

V. 

V.