《模式识别》课程教学资源（书籍文献）Sequential Minimal Optimization - A Fast Algorithm for Training Support Vector Machines（John C. Platt）.pdf

Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines John C.Platt Microsoft Research iplatt@microsoft.com Technical Report MSR-TR-98-14 April 21,1998 1998 John Platt ABSTRACT This paper proposes a new algorithm for training support vector machines:Sequential Minimal Optimization,or SMO.Training a support vector machine requires the solution of a very large quadratic programming(QP)optimization problem.SMO breaks this large QP problem into a series of smallest possible QP problems.These small QP problems are solved analytically,which avoids using a time-consuming numerical QP optimization as an inner loop.The amount of memory required for SMO is linear in the training set size, which allows SMO to handle very large training sets.Because matrix computation is avoided,SMO scales somewhere between linear and quadratic in the training set size for various test problems,while the standard chunking SVM algorithm scales somewhere between linear and cubic in the training set size.SMO's computation time is dominated by SVM evaluation,hence SMO is fastest for linear SVMs and sparse data sets.On real- world sparse data sets,SMO can be more than 1000 times faster than the chunking algorithm. 1.INTRODUCTION In the last few years,there has been a surge of interest in Support Vector Machines(SVMs)[19] [20][4].SVMs have empirically been shown to give good generalization performance on a wide variety of problems such as handwritten character recognition [12],face detection [15],pedestrian detection [14],and text categorization [9]. However,the use of SVMs is still limited to a small group of researchers.One possible reason is that training algorithms for SVMs are slow,especially for large problems.Another explanation is that SVM training algorithms are complex,subtle,and difficult for an average engineer to implement. This paper describes a new SVM learning algorithm that is conceptually simple,easy to implement,is generally faster,and has better scaling properties for difficult SVM problems than the standard SVM training algorithm.The new SVM learning algorithm is called Sequential Minimal Optimization(or SMO).Instead of previous SVM learning algorithms that use numerical quadratic programming(QP)as an inner loop,SMO uses an analytic QP step This paper first provides an overview of SVMs and a review of current SVM training algorithms. The SMO algorithm is then presented in detail,including the solution to the analytic QP step

1 Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines John C. Platt Microsoft Research jplatt@microsoft.com Technical Report MSR-TR-98-14 April 21, 1998 © 1998 John Platt ABSTRACT This paper proposes a new algorithm for training support vector machines: Sequential Minimal Optimization, or SMO. Training a support vector machine requires the solution of a very large quadratic programming (QP) optimization problem. SMO breaks this large QP problem into a series of smallest possible QP problems. These small QP problems are solved analytically, which avoids using a time-consuming numerical QP optimization as an inner loop. The amount of memory required for SMO is linear in the training set size, which allows SMO to handle very large training sets. Because matrix computation is avoided, SMO scales somewhere between linear and quadratic in the training set size for various test problems, while the standard chunking SVM algorithm scales somewhere between linear and cubic in the training set size. SMO’s computation time is dominated by SVM evaluation, hence SMO is fastest for linear SVMs and sparse data sets. On realworld sparse data sets, SMO can be more than 1000 times faster than the chunking algorithm. 1. INTRODUCTION In the last few years, there has been a surge of interest in Support Vector Machines (SVMs) [19] [20] [4]. SVMs have empirically been shown to give good generalization performance on a wide variety of problems such as handwritten character recognition [12], face detection [15], pedestrian detection [14], and text categorization [9]. However, the use of SVMs is still limited to a small group of researchers. One possible reason is that training algorithms for SVMs are slow, especially for large problems. Another explanation is that SVM training algorithms are complex, subtle, and difficult for an average engineer to implement. This paper describes a new SVM learning algorithm that is conceptually simple, easy to implement, is generally faster, and has better scaling properties for difficult SVM problems than the standard SVM training algorithm. The new SVM learning algorithm is called Sequential Minimal Optimization (or SMO). Instead of previous SVM learning algorithms that use numerical quadratic programming (QP) as an inner loop, SMO uses an analytic QP step. This paper first provides an overview of SVMs and a review of current SVM training algorithms. The SMO algorithm is then presented in detail, including the solution to the analytic QP step

3 where xi is the ith training example, and yi is the correct output of the SVM for the ith training example. The value yi is +1 for the positive examples in a class and –1 for the negative examples. Using a Lagrangian, this optimization problem can be converted into a dual form which is a QP problem where the objective function Ψ is solely dependent on a set of Lagrange multipliers αi, min ( ) min ( ) , r r r r r α α Ψ= ⋅ − α αα α = = = ∑ ∑ ∑ 1 2 1 1 1 yy x x i j N i N j i j ij i i N (4) (where N is the number of training examples), subject to the inequality constraints, α i ≥ 0, , ∀i (5) and one linear equality constraint, yi i N i = ∑ = 1 α 0. (6) There is a one-to-one relationship between each Lagrange multiplier and each training example. Once the Lagrange multipliers are determined, the normal vector r w and the threshold b can be derived from the Lagrange multipliers: r r rr w y x b wx y i i N = =⋅ − > ii k k = ∑ 1 α α , . for some 0 k (7) Because r w can be computed via equation (7) from the training data before use, the amount of computation required to evaluate a linear SVM is constant in the number of non-zero support vectors. Of course, not all data sets are linearly separable. There may be no hyperplane that splits the positive examples from the negative examples. In the formulation above, the non-separable case would correspond to an infinite solution. However, in 1995, Cortes & Vapnik [7] suggested a modification to the original optimization statement (3) which allows, but penalizes, the failure of an example to reach the correct margin. That modification is: min || || ( ) , , , , r r r rr w b i i N w C y wx b i ii i ξ ξ ξ 1 2 2 1 + ⋅ − ≥− ∀ 1 = ∑ subject to (8) where ξi are slack variables that permit margin failure and C is a parameter which trades off wide margin with a small number of margin failures. When this new optimization problem is transformed into the dual form, it simply changes the constraint (5) into a box constraint: 0 ≤≤∀ α i C, .i (9) The variables ξi do not appear in the dual formulation at all. SVMs can be even further generalized to non-linear classifiers [2]. The output of a non-linear SVM is explicitly computed from the Lagrange multipliers:

立，aK,-b, u= (10) where K is a kernel function that measures the similarity or distance between the input vector X and the stored training vector ,Examples of K include Gaussians,polynomials,and neural network non-linearities [4].If K is linear,then the equation for the linear SVM(1)is recovered The Lagrange multipliers o are still computed via a quadratic program.The non-linearities alter the quadratic form,but the dual objective function Y is still quadratic in o: mna=mn之立yK民，天)a,-立a i=l jl 0≤a,≤C,i, (11) 立ya=0 The QP problem in equation(11),above,is the QP problem that the SMO algorithm will solve. In order to make the QP problem above be positive definite,the kernel function K must obey Mercer's conditions [4]. The Karush-Kuhn-Tucker(KKT)conditions are necessary and sufficient conditions for an optimal point of a positive definite QP problem.The KKT conditions for the QP problem(11) are particularly simple.The QP problem is solved when,for all i: 0,=0台y,4≥1， 0<C,<C台y4,=1, (12) ,=C台y,4≤1. where 4;is the output of the SVM for the ith training example.Notice that the KKT conditions can be evaluated on one example at a time,which will be useful in the construction of the SMO algorithm. 1.2 Previous Methods for Training Support Vector Machines Due to its immense size,the QP problem (11)that arises from SVMs cannot be easily solved via standard QP techniques.The quadratic form in (11)involves a matrix that has a number of elements equal to the square of the number of training examples.This matrix cannot be fit into 128 Megabytes if there are more than 4000 training examples. Vapnik [19]describes a method to solve the SVM QP,which has since been known as "chunking."The chunking algorithm uses the fact that the value of the quadratic form is the same if you remove the rows and columns of the matrix that corresponds to zero Lagrange multipliers. Therefore,the large QP problem can be broken down into a series of smaller QP problems,whose ultimate goal is to identify all of the non-zero Lagrange multipliers and discard all of the zero Lagrange multipliers.At every step,chunking solves a QP problem that consists of the following examples:every non-zero Lagrange multiplier from the last step,and the M worst examples that violate the KKT conditions(12)[4],for some value of M(see figure 2).If there are fewer than M examples that violate the KKT conditions at a step,all of the violating examples are added in. Each QP sub-problem is initialized with the results of the previous sub-problem.At the last step

4 u y Kx x b j j N = − j j = ∑ 1 α ( ,) , r r (10) where K is a kernel function that measures the similarity or distance between the input vector r x and the stored training vector r x j . Examples of K include Gaussians, polynomials, and neural network non-linearities [4]. If K is linear, then the equation for the linear SVM (1) is recovered. The Lagrange multipliers αi are still computed via a quadratic program. The non-linearities alter the quadratic form, but the dual objective function Ψ is still quadratic in α: min ( ) min ( , ) , , , . r r r r r α α α αα α α α Ψ= − ≤ ≤∀ = = = = = ∑ ∑ ∑ ∑ 1 2 1 1 1 1 0 0 yyK x x C i y ij i j i j j N i N i i N i i i i N (11) The QP problem in equation (11), above, is the QP problem that the SMO algorithm will solve. In order to make the QP problem above be positive definite, the kernel function K must obey Mercer’s conditions [4]. The Karush-Kuhn-Tucker (KKT) conditions are necessary and sufficient conditions for an optimal point of a positive definite QP problem. The KKT conditions for the QP problem (11) are particularly simple. The QP problem is solved when, for all i: α α α i ii i ii i ii y u C yu C yu =⇔ ≥ < <⇔ = =⇔ ≤ 0 1 0 1 1 , , . (12) where ui is the output of the SVM for the ith training example. Notice that the KKT conditions can be evaluated on one example at a time, which will be useful in the construction of the SMO algorithm. 1.2 Previous Methods for Training Support Vector Machines Due to its immense size, the QP problem (11) that arises from SVMs cannot be easily solved via standard QP techniques. The quadratic form in (11) involves a matrix that has a number of elements equal to the square of the number of training examples. This matrix cannot be fit into 128 Megabytes if there are more than 4000 training examples. Vapnik [19] describes a method to solve the SVM QP, which has since been known as “chunking.” The chunking algorithm uses the fact that the value of the quadratic form is the same if you remove the rows and columns of the matrix that corresponds to zero Lagrange multipliers. Therefore, the large QP problem can be broken down into a series of smaller QP problems, whose ultimate goal is to identify all of the non-zero Lagrange multipliers and discard all of the zero Lagrange multipliers. At every step, chunking solves a QP problem that consists of the following examples: every non-zero Lagrange multiplier from the last step, and the M worst examples that violate the KKT conditions (12) [4], for some value of M (see figure 2). If there are fewer than M examples that violate the KKT conditions at a step, all of the violating examples are added in. Each QP sub-problem is initialized with the results of the previous sub-problem. At the last step

the entire set of non-zero Lagrange multipliers has been identified,hence the last step solves the large QP problem. Chunking seriously reduces the size of the matrix from the number of training examples squared to approximately the number of non-zero Lagrange multipliers squared.However,chunking still cannot handle large-scale training problems,since even this reduced matrix cannot fit into memory. Chunking Osuna SMO Figure 2.Three alternative methods for training SVMs:Chunking,Osuna's algorithm,and SMO.For each method,three steps are illustrated.The horizontal thin line at every step represents the training set,while the thick boxes represent the Lagrange multipliers being optimized at that step.For chunking,a fixed number of examples are added every step,while the zero Lagrange multipliers are discarded at every step.Thus,the number of examples trained per step tends to grow.For Osuna's algorithm,a fixed number ofexamples are optimized every step:the same number of examples is added to and discarded from the problem at every step.For SMO,only two examples are analytically optimized at every step,so that each step is very fast. In 1997,Osuna,et al.[16]proved a theorem which suggests a whole new set of QP algorithms for SVMs.The theorem proves that the large QP problem can be broken down into a series of smaller QP sub-problems.As long as at least one example that violates the KKT conditions is added to the examples for the previous sub-problem,each step will reduce the overall objective function and maintain a feasible point that obeys all of the constraints.Therefore,a sequence of QP sub-problems that always add at least one violator will be guaranteed to converge.Notice that the chunking algorithm obeys the conditions of the theorem,and hence will converge. Osuna,et al.suggests keeping a constant size matrix for every QP sub-problem,which implies adding and deleting the same number of examples at every step [16](see figure 2).Using a constant-size matrix will allow the training on arbitrarily sized data sets.The algorithm given in Osuna's paper [16]suggests adding one example and subtracting one example every step. Clearly this would be inefficient,because it would use an entire numerical QP optimization step to cause one training example to obey the KKT conditions.In practice,researchers add and subtract multiple examples according to unpublished heuristics [17].In any event,a numerical QP solver is required for all of these methods.Numerical QP is notoriously tricky to get right; there are many numerical precision issues that need to be addressed

5 the entire set of non-zero Lagrange multipliers has been identified, hence the last step solves the large QP problem. Chunking seriously reduces the size of the matrix from the number of training examples squared to approximately the number of non-zero Lagrange multipliers squared. However, chunking still cannot handle large-scale training problems, since even this reduced matrix cannot fit into memory. In 1997, Osuna, et al. [16] proved a theorem which suggests a whole new set of QP algorithms for SVMs. The theorem proves that the large QP problem can be broken down into a series of smaller QP sub-problems. As long as at least one example that violates the KKT conditions is added to the examples for the previous sub-problem, each step will reduce the overall objective function and maintain a feasible point that obeys all of the constraints. Therefore, a sequence of QP sub-problems that always add at least one violator will be guaranteed to converge. Notice that the chunking algorithm obeys the conditions of the theorem, and hence will converge. Osuna, et al. suggests keeping a constant size matrix for every QP sub-problem, which implies adding and deleting the same number of examples at every step [16] (see figure 2). Using a constant-size matrix will allow the training on arbitrarily sized data sets. The algorithm given in Osuna’s paper [16] suggests adding one example and subtracting one example every step. Clearly this would be inefficient, because it would use an entire numerical QP optimization step to cause one training example to obey the KKT conditions. In practice, researchers add and subtract multiple examples according to unpublished heuristics [17]. In any event, a numerical QP solver is required for all of these methods. Numerical QP is notoriously tricky to get right; there are many numerical precision issues that need to be addressed. Chunking Osuna SMO Figure 2. Three alternative methods for training SVMs: Chunking, Osuna’s algorithm, and SMO. For each method, three steps are illustrated. The horizontal thin line at every step represents the training set, while the thick boxes represent the Lagrange multipliers being optimized at that step. For chunking, a fixed number of examples are added every step, while the zero Lagrange multipliers are discarded at every step. Thus, the number of examples trained per step tends to grow. For Osuna’s algorithm, a fixed number of examples are optimized every step: the same number of examples is added to and discarded from the problem at every step. For SMO, only two examples are analytically optimized at every step, so that each step is very fast