1、A Simple Introduction to Support Vector Machines,Martin Law Lecture for CSE 802 Department of Computer Science and Engineering Michigan State University,10/9/2018,CSE 802. Prepared by Martin Law,2,Outline,A brief history of SVM Large-margin linear classifier Linear separable Nonlinear separable Crea
2、ting nonlinear classifiers: kernel trick A simple example Discussion on SVM Conclusion,10/9/2018,CSE 802. Prepared by Martin Law,3,History of SVM,SVM is related to statistical learning theory 3 SVM was first introduced in 1992 1 SVM becomes popular because of its success in handwritten digit recogni
3、tion 1.1% test error rate for SVM. This is the same as the error rates of a carefully constructed neural network, LeNet 4. See Section 5.11 in 2 or the discussion in 3 for details SVM is now regarded as an important example of “kernel methods”, one of the key area in machine learning Note: the meani
4、ng of “kernel” is different from the “kernel” function for Parzen windows,1 B.E. Boser et al. A Training Algorithm for Optimal Margin Classifiers. Proceedings of the Fifth Annual Workshop on Computational Learning Theory 5 144-152, Pittsburgh, 1992. 2 L. Bottou et al. Comparison of classifier method
5、s: a case study in handwritten digit recognition. Proceedings of the 12th IAPR International Conference on Pattern Recognition, vol. 2, pp. 77-82. 3 V. Vapnik. The Nature of Statistical Learning Theory. 2nd edition, Springer, 1999.,10/9/2018,CSE 802. Prepared by Martin Law,4,What is a good Decision
6、Boundary?,Consider a two-class, linearly separable classification problem Many decision boundaries! The Perceptron algorithm can be used to find such a boundary Different algorithms have been proposed (DHS ch. 5) Are all decision boundaries equally good?,10/9/2018,CSE 802. Prepared by Martin Law,5,E
7、xamples of Bad Decision Boundaries,Class 1,Class 2,Class 1,Class 2,10/9/2018,CSE 802. Prepared by Martin Law,6,Large-margin Decision Boundary,The decision boundary should be as far away from the data of both classes as possible We should maximize the margin, m Distance between the origin and the lin
8、e wtx=k is k/|w|,Class 1,Class 2,m,10/9/2018,CSE 802. Prepared by Martin Law,7,Finding the Decision Boundary,Let x1, ., xn be our data set and let yi 1,-1 be the class label of xi The decision boundary should classify all points correctly The decision boundary can be found by solving the following c
9、onstrained optimization problemThis is a constrained optimization problem. Solving it requires some new tools Feel free to ignore the following several slides; what is important is the constrained optimization problem above,10/9/2018,CSE 802. Prepared by Martin Law,8,Recap of Constrained Optimizatio
10、n,Suppose we want to: minimize f(x) subject to g(x) = 0 A necessary condition for x0 to be a solution:a: the Lagrange multiplier For multiple constraints gi(x) = 0, i=1, , m, we need a Lagrange multiplier ai for each of the constraints,10/9/2018,CSE 802. Prepared by Martin Law,9,Recap of Constrained
11、 Optimization,The case for inequality constraint gi(x)0 is similar, except that the Lagrange multiplier ai should be positive If x0 is a solution to the constrained optimization problemThere must exist ai0 for i=1, , m such that x0 satisfyThe function is also known as the Lagrangrian; we want to set
12、 its gradient to 0,10/9/2018,CSE 802. Prepared by Martin Law,10,Back to the Original Problem,The Lagrangian isNote that |w|2 = wTwSetting the gradient of w.r.t. w and b to zero, we have,10/9/2018,CSE 802. Prepared by Martin Law,11,The Dual Problem,If we substitute to , we have Note that This is a fu
13、nction of ai only,10/9/2018,CSE 802. Prepared by Martin Law,12,The Dual Problem,The new objective function is in terms of ai only It is known as the dual problem: if we know w, we know all ai; if we know all ai, we know w The original problem is known as the primal problem The objective function of
14、the dual problem needs to be maximized! The dual problem is therefore:,Properties of ai when we introduce the Lagrange multipliers,The result when we differentiate the original Lagrangian w.r.t. b,10/9/2018,CSE 802. Prepared by Martin Law,13,The Dual Problem,This is a quadratic programming (QP) prob
15、lem A global maximum of ai can always be foundw can be recovered by,10/9/2018,CSE 802. Prepared by Martin Law,14,Characteristics of the Solution,Many of the ai are zero w is a linear combination of a small number of data points This “sparse” representation can be viewed as data compression as in the
16、 construction of knn classifier xi with non-zero ai are called support vectors (SV) The decision boundary is determined only by the SV Let tj (j=1, ., s) be the indices of the s support vectors. We can write For testing with a new data z Compute and classify z as class 1 if the sum is positive, and
17、class 2 otherwise Note: w need not be formed explicitly,10/9/2018,CSE 802. Prepared by Martin Law,15,The Quadratic Programming Problem,Many approaches have been proposed Loqo, cplex, etc. (see http:/www.numerical.rl.ac.uk/qp/qp.html) Most are “interior-point” methods Start with an initial solution t
18、hat can violate the constraints Improve this solution by optimizing the objective function and/or reducing the amount of constraint violation For SVM, sequential minimal optimization (SMO) seems to be the most popular A QP with two variables is trivial to solve Each iteration of SMO picks a pair of
19、(ai,aj) and solve the QP with these two variables; repeat until convergence In practice, we can just regard the QP solver as a “black-box” without bothering how it works,10/9/2018,CSE 802. Prepared by Martin Law,16,a6=1.4,A Geometrical Interpretation,Class 1,Class 2,a1=0.8,a2=0,a3=0,a4=0,a5=0,a7=0,a
20、8=0.6,a9=0,a10=0,10/9/2018,CSE 802. Prepared by Martin Law,17,Non-linearly Separable Problems,We allow “error” xi in classification; it is based on the output of the discriminant function wTx+bxi approximates the number of misclassified samples,10/9/2018,CSE 802. Prepared by Martin Law,18,Soft Margi
21、n Hyperplane,If we minimize ixi, xi can be computed byxi are “slack variables” in optimization Note that xi=0 if there is no error for xi xi is an upper bound of the number of errors We want to minimizeC : tradeoff parameter between error and margin The optimization problem becomes,10/9/2018,CSE 802
22、. Prepared by Martin Law,19,The Optimization Problem,The dual of this new constrained optimization problem isw is recovered asThis is very similar to the optimization problem in the linear separable case, except that there is an upper bound C on ai now Once again, a QP solver can be used to find ai,
23、10/9/2018,CSE 802. Prepared by Martin Law,20,Extension to Non-linear Decision Boundary,So far, we have only considered large-margin classifier with a linear decision boundary How to generalize it to become nonlinear? Key idea: transform xi to a higher dimensional space to “make life easier” Input sp
24、ace: the space the point xi are located Feature space: the space of f(xi) after transformation Why transform? Linear operation in the feature space is equivalent to non-linear operation in input space Classification can become easier with a proper transformation. In the XOR problem, for example, add
25、ing a new feature of x1x2 make the problem linearly separable,10/9/2018,CSE 802. Prepared by Martin Law,21,Transforming the Data (c.f. DHS Ch. 5),Computation in the feature space can be costly because it is high dimensional The feature space is typically infinite-dimensional! The kernel trick comes
26、to rescue,f(.),Feature space,Input space,Note: feature space is of higher dimension than the input space in practice,10/9/2018,CSE 802. Prepared by Martin Law,22,The Kernel Trick,Recall the SVM optimization problemThe data points only appear as inner product As long as we can calculate the inner pro
27、duct in the feature space, we do not need the mapping explicitly Many common geometric operations (angles, distances) can be expressed by inner products Define the kernel function K by,10/9/2018,CSE 802. Prepared by Martin Law,23,An Example for f(.) and K(.,.),Suppose f(.) is given as followsAn inne
28、r product in the feature space isSo, if we define the kernel function as follows, there is no need to carry out f(.) explicitlyThis use of kernel function to avoid carrying out f(.) explicitly is known as the kernel trick,10/9/2018,CSE 802. Prepared by Martin Law,24,Kernel Functions,In practical use
29、 of SVM, the user specifies the kernel function; the transformation f(.) is not explicitly stated Given a kernel function K(xi, xj), the transformation f(.) is given by its eigenfunctions (a concept in functional analysis) Eigenfunctions can be difficult to construct explicitly This is why people on
30、ly specify the kernel function without worrying about the exact transformation Another view: kernel function, being an inner product, is really a similarity measure between the objects,10/9/2018,CSE 802. Prepared by Martin Law,25,Examples of Kernel Functions,Polynomial kernel with degree dRadial bas
31、is function kernel with width sClosely related to radial basis function neural networks The feature space is infinite-dimensional Sigmoid with parameter k and q It does not satisfy the Mercer condition on all k and q,10/9/2018,CSE 802. Prepared by Martin Law,26,Modification Due to Kernel Function,Ch
32、ange all inner products to kernel functions For training,Original,With kernel function,10/9/2018,CSE 802. Prepared by Martin Law,27,Modification Due to Kernel Function,For testing, the new data z is classified as class 1 if f 0, and as class 2 if f 0,Original,With kernel function,10/9/2018,CSE 802.
33、Prepared by Martin Law,28,More on Kernel Functions,Since the training of SVM only requires the value of K(xi, xj), there is no restriction of the form of xi and xj xi can be a sequence or a tree, instead of a feature vector K(xi, xj) is just a similarity measure comparing xi and xj For a test object
34、 z, the discriminat function essentially is a weighted sum of the similarity between z and a pre-selected set of objects (the support vectors),10/9/2018,CSE 802. Prepared by Martin Law,29,More on Kernel Functions,Not all similarity measure can be used as kernel function, however The kernel function
35、needs to satisfy the Mercer function, i.e., the function is “positive-definite” This implies that the n by n kernel matrix, in which the (i,j)-th entry is the K(xi, xj), is always positive definite This also means that the QP is convex and can be solved in polynomial time,10/9/2018,CSE 802. Prepared
36、 by Martin Law,30,Example,Suppose we have 5 1D data points x1=1, x2=2, x3=4, x4=5, x5=6, with 1, 2, 6 as class 1 and 4, 5 as class 2 y1=1, y2=1, y3=-1, y4=-1, y5=1 We use the polynomial kernel of degree 2 K(x,y) = (xy+1)2 C is set to 100 We first find ai (i=1, , 5) by,10/9/2018,CSE 802. Prepared by
37、Martin Law,31,Example,By using a QP solver, we get a1=0, a2=2.5, a3=0, a4=7.333, a5=4.833 Note that the constraints are indeed satisfied The support vectors are x2=2, x4=5, x5=6 The discriminant function isb is recovered by solving f(2)=1 or by f(5)=-1 or by f(6)=1, as x2 and x5 lie on the line and
38、x4 lies on the line All three give b=9,10/9/2018,CSE 802. Prepared by Martin Law,32,Example,Value of discriminant function,1,2,4,5,6,class 2,class 1,class 1,10/9/2018,CSE 802. Prepared by Martin Law,33,Why SVM Work?,The feature space is often very high dimensional. Why dont we have the curse of dime
39、nsionality? A classifier in a high-dimensional space has many parameters and is hard to estimate Vapnik argues that the fundamental problem is not the number of parameters to be estimated. Rather, the problem is about the flexibility of a classifier Typically, a classifier with many parameters is ve
40、ry flexible, but there are also exceptions Let xi=10i where i ranges from 1 to n. The classifiercan classify all xi correctly for all possible combination of class labels on xi This 1-parameter classifier is very flexible,10/9/2018,CSE 802. Prepared by Martin Law,34,Why SVM works?,Vapnik argues that
41、 the flexibility of a classifier should not be characterized by the number of parameters, but by the flexibility (capacity) of a classifier This is formalized by the “VC-dimension” of a classifier Consider a linear classifier in two-dimensional space If we have three training data points, no matter
42、how those points are labeled, we can classify them perfectly,10/9/2018,CSE 802. Prepared by Martin Law,35,VC-dimension,However, if we have four points, we can find a labeling such that the linear classifier fails to be perfectWe can see that 3 is the critical number The VC-dimension of a linear clas
43、sifier in a 2D space is 3 because, if we have 3 points in the training set, perfect classification is always possible irrespective of the labeling, whereas for 4 points, perfect classification can be impossible,10/9/2018,CSE 802. Prepared by Martin Law,36,VC-dimension,The VC-dimension of the nearest
44、 neighbor classifier is infinity, because no matter how many points you have, you get perfect classification on training data The higher the VC-dimension, the more flexible a classifier is VC-dimension, however, is a theoretical concept; the VC-dimension of most classifiers, in practice, is difficul
45、t to be computed exactly Qualitatively, if we think a classifier is flexible, it probably has a high VC-dimension,10/9/2018,CSE 802. Prepared by Martin Law,37,Structural Risk Minimization (SRM),A fancy term, but it simply means: we should find a classifier that minimizes the sum of training error (e
46、mpirical risk) and a term that is a function of the flexibility of the classifier (model complexity) Recall the concept of confidence interval (CI) For example, we are 99% confident that the population mean lies in the 99% CI estimated from a sample We can also construct a CI for the generalization
47、error (error on the test set),10/9/2018,CSE 802. Prepared by Martin Law,38,Structural Risk Minimization (SRM),Increasing error rate,CI of test error for classifier 1,Training error,CI of test error for classifier 2,Training error,SRM prefers classifier 2 although it has a higher training error, beca
48、use the upper limit of CI is smaller,10/9/2018,CSE 802. Prepared by Martin Law,39,Structural Risk Minimization (SRM),It can be proved that the more flexible a classifier, the “wider” the CI is The width can be upper-bounded by a function of the VC-dimension of the classifier In practice, the confide
49、nce interval of the testing error contains 0,1 and hence is trivial Empirically, minimizing the upper bound is still useful The two classifiers are often “nested”, i.e., one classifier is a special case of the other SVM can be viewed as implementing SRM because i xi approximates the training error; |w|2 is related to the VC-dimension of the resulting classifier See http:/www.svms.org/srm/ for more details,
