nips nips2000 nips2000-52 knowledge-graph by maker-knowledge-mining

52 nips-2000-Fast Training of Support Vector Classifiers

Source: pdf

Author: Fernando Pérez-Cruz, Pedro Luis Alarcón-Diana, Angel Navia-Vázquez, Antonio Artés-Rodríguez

Abstract: In this communication we present a new algorithm for solving Support Vector Classifiers (SVC) with large training data sets. The new algorithm is based on an Iterative Re-Weighted Least Squares procedure which is used to optimize the SVc. Moreover, a novel sample selection strategy for the working set is presented, which randomly chooses the working set among the training samples that do not fulfill the stopping criteria. The validity of both proposals, the optimization procedure and sample selection strategy, is shown by means of computer experiments using well-known data sets. 1 INTRODUCTION The Support Vector Classifier (SVC) is a powerful tool to solve pattern recognition problems [13, 14] in such a way that the solution is completely described as a linear combination of several training samples, named the Support Vectors. The training procedure for solving the SVC is usually based on Quadratic Programming (QP) which presents some inherent limitations, mainly the computational complexity and memory requirements for large training data sets. This problem is typically avoided by dividing the QP problem into sets of smaller ones [6, 1, 7, 11], that are iteratively solved in order to reach the SVC solution for the whole set of training samples. These schemes rely on an optimizing engine, QP, and in the sample selection strategy for each sub-problem, in order to obtain a fast solution for the SVC. An Iterative Re-Weighted Least Squares (IRWLS) procedure has already been proposed as an alternative solver for the SVC [10] and the Support Vector Regressor [9], being computationally efficient in absolute terms. In this communication, we will show that the IRWLS algorithm can replace the QP one in any chunking scheme in order to find the SVC solution for large training data sets. Moreover, we consider that the strategy to decide which training samples must j oin the working set is critical to reduce the total number of iterations needed to attain the SVC solution, and the runtime complexity as a consequence. To aim for this issue, the computer program SV cradit have been developed so as to solve the SVC for large training data sets using IRWLS procedure and fixed-size working sets. The paper is organized as follows. In Section 2, we start by giving a summary of the IRWLS procedure for SVC and explain how it can be incorporated to a chunking scheme to obtain an overall implementation which efficiently deals with large training data sets. We present in Section 3 a novel strategy to make up the working set. Section 4 shows the capabilities of the new implementation and they are compared with the fastest available SVC implementation, SV Mlight [6]. We end with some concluding remarks. 2 IRWLS-SVC In order to solve classification problems, the SVC has to minimize Lp = ~llwI12+CLei- LJliei- LQi(Yi(¢(xifw+b)-l+ei) (1) i i i with respectto w, band ei and maximize it with respectto Qi and Jli, subject to Qi, Jli ~ 0, where ¢(.) is a nonlinear transformation (usually unknown) to a higher dimensional space and C is a penalization factor. The solution to (1) is defined by the Karush-Kuhn-Tucker (KKT) conditions [2]. For further details on the SVC, one can refer to the tutorial survey by Burges [2] and to the work ofVapnik [13, 14]. In order to obtain an IRWLS procedure we will first need to rearrange (1) in such a way that the terms depending on ei can be removed because, at the solution C - Qi - Jli = 0 Vi (one of the KKT conditions [2]) must hold. Lp = 1 Qi(l- Yi(¢T(Xi)W + b)) 211wl12 + L i = (2) where The weighted least square nature of (2) can be understood if ei is defined as the error on each sample and ai as its associated weight, where! IIwl1 2 is a regularizing functional. The minimization of (2) cannot be accomplished in a single step because ai = ai(ei), and we need to apply an IRWLS procedure [4], summarized below in tree steps: 1. Considering the ai fixed, minimize (2). 2. Recalculate ai from the solution on step 1. 3. Repeat until convergence. In order to work with Reproducing Kernels in Hilbert Space (RKHS), as the QP procedure does, we require that w = Ei (JiYi¢(Xi) and in order to obtain a non-zero b, that Ei {JiYi = O. Substituting them into (2), its minimum with respect to {Ji and b for a fixed set of ai is found by solving the following linear equation system l (3) IThe detailed description of the steps needed to obtain (3) from (2) can be found in [10]. where y = [Yl, Y2, ... Yn]T (4) 'r/i,j = 1, ... ,n 'r/i,j = 1, ... ,n (H)ij = YiYj¢T(Xi)¢(Xj) = YiyjK(Xi,Xj) (Da)ij = aio[i - j] 13 = [,81, ,82, ... (5) (6) (7) , ,8n]T and 0[·] is the discrete impulse function. Finally, the dependency of ai upon the Lagrange multipliers is eliminated using the KKT conditions, obtaining a, ai 2.1 ={~ ei Yi' eiYi < Yt.et. > - ° ° (8) IRWLS ALGORITHMIC IMPLEMENTATION The SVC solution with the IRWLS procedure can be simplified by dividing the training samples into three sets. The first set, SI, contains the training samples verifying < ,8i < C, which have to be determined by solving (3). The second one, S2, includes every training sample whose,8i = 0. And the last one, S3, is made up of the training samples whose ,8i = C. This division in sets is fully justified in [10]. The IRWLS-SVC algorithm is shown in Table 1. ° 0. Initialization: SI will contain every training sample, S2 = 0 and S3 = 0. Compute H. e_a = y, f3_a = 0, b_a = 0, G 13 = Gin, a = 1 and G b3 = G bi n . 1 Solve [ (H)Sb S1 + D(al S1 . =° = e-lt a, 3. ai = { ~ (13) S2 2. e ° 1[ (Y)Sl (f3)Sl ] (y ) ~1 b and (13) Ss = C DyH(f3 - f3_a) - (b - b_a)1 =[1- G 13 ] G b3 ' °. eiYi < e- _ > O'r/Z E SI U S2 U S3 tYt 4. Sets reordering: a. Move every sample in S3 with eiYi < to S2. b. Move every sample in SI with ,8i = C to S3. c. Move every sample in SI with ai = to S2 . d. Move every sample in S2 with ai :I to SI. 5. e_a = e, f3_a = 13, G 13 = (H)Sl,SS (f3)ss + (G in )Sl' b-lt = band Gb3 = -y~s (f3)ss + Gbin · 6. Go to step 1 and repeat until convergence. ei Yi ' ° ° ° Table 1: IRWLS-SVC algorithm. The IRWLS-SVC procedure has to be slightly modified in order to be used inside a chunk:ing scheme as the one proposed in [8, 6], such that it can be directly applied in the one proposed in [1]. A chunking scheme is needed to solve the SVC whenever H is too large to fit into memory. In those cases, several SVC with a reduced set of training samples are iteratively solved until the solution for the whole set is found. The samples are divide into a working set, Sw, which is solved as a full SVC problem, and an inactive set, Sin. If there are support vectors in the inactive set, as it might be, the inactive set modifies the IRWLSSVC procedure, adding a contribution to the independent term in the linear equation system (3) . Those support vectors in S in can be seen as anchored samples in S3, because their ,8i is not zero and can not be modified by the IRWLS procedure. Then, such contribution (Gin and G bin ) will be calculated as G 13 and G b3 are (Table 1, 5th step), before calling the IRWLS-SVC algorithm. We have already modified the IRWLS-SVC in Table 1 to consider Gin and G bin , which must be set to zero if the Hessian matrix, H, fits into memory for the whole set of training samples. The resolution of the SVC for large training data sets, employing as minimization engine the IRWLS procedure, is summarized in the following steps: 1. Select the samples that will form the working set. 2. Construct Gin = (H)Sw,Sin (f3)s.n and G bin = -yIin (f3)Sin 3. Solve the IRWLS-SVC procedure, following the steps in Table 1. 4. Compute the error of every training sample. 5. If the stopping conditions Yiei < C eiYi> -c leiYil < C 'Vii 'Vii 'Vii (Ji = 0 (Ji = C 0 < (Ji < C (9) (10) (11) are fulfilled, the SVC solution has been reached. The stopping conditions are the ones proposed in [6] and C must be a small value around 10 - 3 , a full discussion concerning this topic can be found in [6]. 3 SAMPLE SELECTION STRATEGY The selection of the training samples that will constitute the working set in each iteration is the most critical decision in any chunking scheme, because such decision is directly involved in the number of IRWLS-SVC (or QP-SVC) procedures to be called and in the number of reproducing kernel evaluations to be made, which are, by far, the two most time consuming operations in any chunking schemes. In order to solve the SVC efficiently, we first need to define a candidate set of training samples to form the working set in each iteration. The candidate set will be made up, as it could not be otherwise, with all the training samples that violate the stopping conditions (9)-(11); and we will also add all those training samples that satisfy condition (11) but a small variation on their error will make them violate such condition. The strategies to select the working set are as numerous as the number of problems to be solved, but one can think three different simple strategies: • Select those samples which do not fulfill the stopping criteria and present the largest Iei I values. • Select those samples which do not fulfill the stopping criteria and present the smallest Iei I values. • Select them randomly from the ones that do not fulfill the stopping conditions. The first strategy seems the more natural one and it was proposed in [6]. If the largest leil samples are selected we guanrantee that attained solution gives the greatest step towards the solution of (1). But if the step is too large, which usually happens, it will cause the solution in each iteration and the (Ji values to oscillate around its optimal value. The magnitude of this effect is directly proportional to the value of C and q (size of the working set), so in the case ofsmall C (C < 10) and low q (q < 20) it would be less noticeable. The second one is the most conservative strategy because we will be moving towards the solution of (1) with small steps. Its drawback is readily discerned if the starting point is inappropriate, needing too many iterations to reach the SVC solution. The last strategy, which has been implemented together with the IRWLS-SVC procedure, is a mid-point between the other two, but if the number of samples whose 0 < (3i < C increases above q there might be some iterations where we will make no progress (working set is only made up of the training samples that fulfill the stopping condition in (11)). This situation is easily avoided by introducing one sample that violates each one of the stopping conditions per class. Finally, if the cardinality of the candidate set is less than q the working set is completed with those samples that fulfil the stopping criteria conditions and present the least leil. In summary, the sample selection strategy proposed is 2 : 1. Construct the candidate set, Se with those samples that do not fulfill stopping conditions (9) and (10), and those samples whose (3 obeys 0 < (3i < C. 2. IfISel < ngot05. 3. Choose a sample per class that violates each one of the stopping conditions and move them from Se to the working set, SW. 4. Choose randomly n - ISw I samples from Se and move then to SW. Go to Step 6. 5. Move every sample form Se to Sw and then-ISwl samples that fulfill the stopping conditions (9) and (10) and present the lowest leil values are used to complete SW . 6. Go on, obtaining Gin and Gbin. 4 BENCHMARK FOR THE IRWLS-SVC We have prepared two different experiments to test both the IRWLS and the sample selection strategy for solving the SVc. The first one compares the IRWLS against QP and the second one compares the samples selection strategy, together with the IRWLS, against a complete solving procedure for SVC, the SV Mlight. In the first trial, we have replaced the LOQO interior point optimizer used by SV M1ig ht version 3.02 [5] by the IRWLS-SVC procedure in Table 1, to compare both optimizing engines with equal samples selection strategy. The comparison has been made over a Pentium ill-450MHz with 128Mb running on Window98 and the programs have been compiled using Microsoft Developer 6.0. In Table 2, we show the results for two data sets: the first q 20 40 70 Adult44781 CPU time Optimize Time LOQO IRWLS LOQO IRWLS 21.25 20.70 0.61 0.39 20.60 19.22 1.01 0.17 21.15 18.72 2.30 0.46 Splice 2175 CPU time Optimize Time LOQO IRWLS LOQO IRWLS 46.19 30.76 21.94 4.77 71.34 24.93 46.26 8.07 53.77 20.32 34.24 7.72 Table 2: CPU Time indicates the consume time in seconds for the whole procedure. The Optimize Time indicates the consume time in second for the LOQO or IRWLS procedure. one, containing 4781 training samples, needs most CPU resources to compute the RKHS and the second one, containing 2175 training samples, uses most CPU resources to solve the SVC for each Sw, where q indicates the size of the working set. The value of C has 2In what follows, I . I represents absolute value for numbers and cardinality for sets been set to 1 and 1000, respectively, and a Radial Basis Function (RBF) RKHS [2] has been employed, where its parameter a has been set, respectively, to 10 and 70. As it can be seen, the SV M1ig ht with IRWLS is significantly faster than the LOQO procedure in all cases. The kernel cache size has been set to 64Mb for both data sets and for both procedures. The results in Table 2 validates the IRWLS procedure as the fastest SVC solver. For the second trial, we have compiled a computer program that uses the IRWLS-SVC procedure and the working set selection in Section 3, we will refer to it as svcradit from now on. We have borrowed the chunking and shrinking ideas from the SV Mlight [6] for our computer program. To test these two programs several data sets have been used. The Adult and Web data sets have been obtained from 1. Platt's web page http://research.microsoft.comr jplatt/smo.html/; the Gauss-M data set is a two dimensional classification problem proposed in [3] to test neural networks, which comprises a gaussian random variable for each class, which highly overlap. The Banana, Diabetes and Splice data sets have been obtained from Gunnar Ratsch web page http://svm.first.gmd.der raetschl. The selection of C and the RKHS has been done as indicated in [11] for Adult and Web data sets and in http://svm.first.gmd.derraetschl for Banana, Diabetes and Splice data sets. In Table 3, we show the runtime complexity for each data set, where the value of q has been elected as the one that reduces the runtime complexity. Database Dim Adult6 Adult9 Adult! Web 1 Web7 Gauss-M Gauss-M Banana Banana Diabetes Splice 123 123 123 300 300 2 2 2 2 8 69 N Sampl. 11221 32562 1605 2477 24693 4000 4000 400 4900 768 2175 C a SV 1 1 1000 5 5 1 100 316.2 316.2 10 1000 10 10 10 10 10 1 1 1 1 2 70 4477 12181 630 224 1444 1736 1516 80 1084 409 525 q CPU time radit light radit light 150 130 100 100 150 70 100 40 70 40 150 40 70 10 10 10 10 10 70 40 10 20 118.2 1093.29 25.98 2.42 158.13 12.69 61.68 0.33 22.46 2.41 14.06 124.46 1097.09 113.54 2.36 124.57 48.28 3053.20 0.77 1786.56 6.04 49.19 Table 3: Several data sets runtime complexity, when solved with the short, and SV Mlight, light for short. s v c radit , radit for One can appreciate that the svcradit is faster than the SV M1ig ht for most data sets. For the Web data set, which is the only data set the SV Mlight is sligthly faster, the value of C is low and most training samples end up as support vector with (3i < C. In such cases the best strategy is to take the largest step towards the solution in every iteration, as the SV Mlig ht does [6], because most training samples (3i will not be affected by the others training samples (3j value. But in those case the value of C increases the SV c radit samples selection strategy is a much more appropriate strategy than the one used in SV Mlight. 5 CONCLUSIONS In this communication a new algorithm for solving the SVC for large training data sets has been presented. Its two major contributions deal with the optimizing engine and the sample selection strategy. An IRWLS procedure is used to solve the SVC in each step, which is much faster that the usual QP procedure, and simpler to implement, because the most difficult step is the linear equation system solution that can be easily obtained by LU decomposition means [12]. The random working set selection from the samples not fulfilling the KKT conditions is the best option if the working is be large, because it reduces the number of chunks to be solved. This strategy benefits from the IRWLS procedure, which allows to work with large training data set. All these modifications have been concreted in the svcradit solving procedure, publicly available at http://svm.tsc.uc3m.es/. 6 ACKNOWLEDGEMENTS We are sincerely grateful to Thorsten Joachims who has allowed and encouraged us to use his SV Mlight to test our IRWLS procedure, comparisons which could not have been properly done otherwise. References [1] B. E. Boser, I. M . Guyon, and V. Vapnik. A training algorithm for optimal margin classifiers. In 5th Annual Workshop on Computational Learning Theory, Pittsburg, U.S.A., 1992. [2] C. J. C. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2(2):121-167, 1998. [3] S. Haykin. Neural Networks: A comprehensivefoundation. Prentice-Hall, 1994. [4] P. W. Holland and R. E. Welch. Robust regression using iterative re-weighted least squares. Communications of Statistics Theory Methods, A6(9):813-27, 1977. [5] T. Joachims. http://www-ai.infonnatik.uni-dortmund.de/forschung/verfahren Isvmlight Isvmlight.eng.html. Technical report, University of Dortmund, Informatik, AI-Unit Collaborative Research Center on 'Complexity Reduction in Multivariate Data', 1998. [6] T. Joachims. Making Large Scale SVM Learning Practical, In Advances in Kernel Methods- Support Vector Learning, Editors SchOlkopf, B., Burges, C. 1. C. and Smola, A. 1., pages 169-184. M.I.T. Press, 1999. [7] E. Osuna, R. Freund, and F. Girosi. An improved training algorithm for support vector machines. In Proc. of the 1997 IEEE Workshop on Neural Networks for Signal Processing, pages 276-285, Amelia Island, U.S.A, 1997. [8] E. Osuna and F. Girosi. Reducing the run-time complexity of support vector machines. In ICPR'98, Brisbane, Australia, August 1998. [9] F. Perez-Cruz, A. Navia-Vazquez

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 Tecnologias de las comunicaciones, Escuela Politecnica Superior, Universidad Carlos ill de Madrid, Avda. [sent-14, score-0.106]

2 Abstract In this communication we present a new algorithm for solving Support Vector Classifiers (SVC) with large training data sets. [sent-16, score-0.192]

3 The new algorithm is based on an Iterative Re-Weighted Least Squares procedure which is used to optimize the SVc. [sent-17, score-0.159]

4 Moreover, a novel sample selection strategy for the working set is presented, which randomly chooses the working set among the training samples that do not fulfill the stopping criteria. [sent-18, score-1.101]

5 The validity of both proposals, the optimization procedure and sample selection strategy, is shown by means of computer experiments using well-known data sets. [sent-19, score-0.315]

6 1 INTRODUCTION The Support Vector Classifier (SVC) is a powerful tool to solve pattern recognition problems [13, 14] in such a way that the solution is completely described as a linear combination of several training samples, named the Support Vectors. [sent-20, score-0.198]

7 The training procedure for solving the SVC is usually based on Quadratic Programming (QP) which presents some inherent limitations, mainly the computational complexity and memory requirements for large training data sets. [sent-21, score-0.402]

8 This problem is typically avoided by dividing the QP problem into sets of smaller ones [6, 1, 7, 11], that are iteratively solved in order to reach the SVC solution for the whole set of training samples. [sent-22, score-0.331]

9 These schemes rely on an optimizing engine, QP, and in the sample selection strategy for each sub-problem, in order to obtain a fast solution for the SVC. [sent-23, score-0.382]

10 An Iterative Re-Weighted Least Squares (IRWLS) procedure has already been proposed as an alternative solver for the SVC [10] and the Support Vector Regressor [9], being computationally efficient in absolute terms. [sent-24, score-0.15]

11 In this communication, we will show that the IRWLS algorithm can replace the QP one in any chunking scheme in order to find the SVC solution for large training data sets. [sent-25, score-0.312]

12 Moreover, we consider that the strategy to decide which training samples must j oin the working set is critical to reduce the total number of iterations needed to attain the SVC solution, and the runtime complexity as a consequence. [sent-26, score-0.641]

13 To aim for this issue, the computer program SV cradit have been developed so as to solve the SVC for large training data sets using IRWLS procedure and fixed-size working sets. [sent-27, score-0.479]

14 In Section 2, we start by giving a summary of the IRWLS procedure for SVC and explain how it can be incorporated to a chunking scheme to obtain an overall implementation which efficiently deals with large training data sets. [sent-29, score-0.376]

15 We present in Section 3 a novel strategy to make up the working set. [sent-30, score-0.258]

16 Section 4 shows the capabilities of the new implementation and they are compared with the fastest available SVC implementation, SV Mlight [6]. [sent-31, score-0.032]

17 2 IRWLS-SVC In order to solve classification problems, the SVC has to minimize Lp = ~llwI12+CLei- LJliei- LQi(Yi(¢(xifw+b)-l+ei) (1) i i i with respectto w, band ei and maximize it with respectto Qi and Jli, subject to Qi, Jli ~ 0, where ¢(. [sent-33, score-0.228]

18 The solution to (1) is defined by the Karush-Kuhn-Tucker (KKT) conditions [2]. [sent-35, score-0.109]

19 For further details on the SVC, one can refer to the tutorial survey by Burges [2] and to the work ofVapnik [13, 14]. [sent-36, score-0.027]

20 In order to obtain an IRWLS procedure we will first need to rearrange (1) in such a way that the terms depending on ei can be removed because, at the solution C - Qi - Jli = 0 Vi (one of the KKT conditions [2]) must hold. [sent-37, score-0.32]

21 Lp = 1 Qi(l- Yi(¢T(Xi)W + b)) 211wl12 + L i = (2) where The weighted least square nature of (2) can be understood if ei is defined as the error on each sample and ai as its associated weight, where! [sent-38, score-0.233]

22 The minimization of (2) cannot be accomplished in a single step because ai = ai(ei), and we need to apply an IRWLS procedure [4], summarized below in tree steps: 1. [sent-40, score-0.229]

23 In order to work with Reproducing Kernels in Hilbert Space (RKHS), as the QP procedure does, we require that w = Ei (JiYi¢(Xi) and in order to obtain a non-zero b, that Ei {JiYi = O. [sent-46, score-0.121]

24 Substituting them into (2), its minimum with respect to {Ji and b for a fixed set of ai is found by solving the following linear equation system l (3) IThe detailed description of the steps needed to obtain (3) from (2) can be found in [10]. [sent-47, score-0.114]

25 Finally, the dependency of ai upon the Lagrange multipliers is eliminated using the KKT conditions, obtaining a, ai 2. [sent-61, score-0.16]

26 > - ° ° (8) IRWLS ALGORITHMIC IMPLEMENTATION The SVC solution with the IRWLS procedure can be simplified by dividing the training samples into three sets. [sent-64, score-0.471]

27 The first set, SI, contains the training samples verifying < ,8i < C, which have to be determined by solving (3). [sent-65, score-0.31]

28 The second one, S2, includes every training sample whose,8i = 0. [sent-66, score-0.217]

29 And the last one, S3, is made up of the training samples whose ,8i = C. [sent-67, score-0.263]

30 This division in sets is fully justified in [10]. [sent-68, score-0.057]

31 Initialization: SI will contain every training sample, S2 = 0 and S3 = 0. [sent-71, score-0.141]

32 The IRWLS-SVC procedure has to be slightly modified in order to be used inside a chunk:ing scheme as the one proposed in [8, 6], such that it can be directly applied in the one proposed in [1]. [sent-91, score-0.215]

33 A chunking scheme is needed to solve the SVC whenever H is too large to fit into memory. [sent-92, score-0.188]

34 In those cases, several SVC with a reduced set of training samples are iteratively solved until the solution for the whole set is found. [sent-93, score-0.386]

35 The samples are divide into a working set, Sw, which is solved as a full SVC problem, and an inactive set, Sin. [sent-94, score-0.384]

36 If there are support vectors in the inactive set, as it might be, the inactive set modifies the IRWLSSVC procedure, adding a contribution to the independent term in the linear equation system (3) . [sent-95, score-0.15]

37 Those support vectors in S in can be seen as anchored samples in S3, because their ,8i is not zero and can not be modified by the IRWLS procedure. [sent-96, score-0.234]

38 Then, such contribution (Gin and G bin ) will be calculated as G 13 and G b3 are (Table 1, 5th step), before calling the IRWLS-SVC algorithm. [sent-97, score-0.04]

39 We have already modified the IRWLS-SVC in Table 1 to consider Gin and G bin , which must be set to zero if the Hessian matrix, H, fits into memory for the whole set of training samples. [sent-98, score-0.163]

40 The resolution of the SVC for large training data sets, employing as minimization engine the IRWLS procedure, is summarized in the following steps: 1. [sent-99, score-0.161]

41 Select the samples that will form the working set. [sent-100, score-0.306]

42 If the stopping conditions Yiei < C eiYi> -c leiYil < C 'Vii 'Vii 'Vii (Ji = 0 (Ji = C 0 < (Ji < C (9) (10) (11) are fulfilled, the SVC solution has been reached. [sent-108, score-0.268]

43 The stopping conditions are the ones proposed in [6] and C must be a small value around 10 - 3 , a full discussion concerning this topic can be found in [6]. [sent-109, score-0.24]

44 In order to solve the SVC efficiently, we first need to define a candidate set of training samples to form the working set in each iteration. [sent-111, score-0.491]

45 The candidate set will be made up, as it could not be otherwise, with all the training samples that violate the stopping conditions (9)-(11); and we will also add all those training samples that satisfy condition (11) but a small variation on their error will make them violate such condition. [sent-112, score-0.869]

46 The strategies to select the working set are as numerous as the number of problems to be solved, but one can think three different simple strategies: • Select those samples which do not fulfill the stopping criteria and present the largest Iei I values. [sent-113, score-0.689]

47 • Select those samples which do not fulfill the stopping criteria and present the smallest Iei I values. [sent-114, score-0.487]

48 • Select them randomly from the ones that do not fulfill the stopping conditions. [sent-115, score-0.278]

49 The first strategy seems the more natural one and it was proposed in [6]. [sent-116, score-0.153]

50 If the largest leil samples are selected we guanrantee that attained solution gives the greatest step towards the solution of (1). [sent-117, score-0.399]

51 But if the step is too large, which usually happens, it will cause the solution in each iteration and the (Ji values to oscillate around its optimal value. [sent-118, score-0.098]

52 The magnitude of this effect is directly proportional to the value of C and q (size of the working set), so in the case ofsmall C (C < 10) and low q (q < 20) it would be less noticeable. [sent-119, score-0.134]

53 The second one is the most conservative strategy because we will be moving towards the solution of (1) with small steps. [sent-120, score-0.181]

54 Its drawback is readily discerned if the starting point is inappropriate, needing too many iterations to reach the SVC solution. [sent-121, score-0.026]

55 This situation is easily avoided by introducing one sample that violates each one of the stopping conditions per class. [sent-123, score-0.345]

56 Finally, if the cardinality of the candidate set is less than q the working set is completed with those samples that fulfil the stopping criteria conditions and present the least leil. [sent-124, score-0.636]

57 In summary, the sample selection strategy proposed is 2 : 1. [sent-125, score-0.321]

58 Construct the candidate set, Se with those samples that do not fulfill stopping conditions (9) and (10), and those samples whose (3 obeys 0 < (3i < C. [sent-126, score-0.718]

59 Choose a sample per class that violates each one of the stopping conditions and move them from Se to the working set, SW. [sent-130, score-0.519]

60 Choose randomly n - ISw I samples from Se and move then to SW. [sent-132, score-0.242]

61 Move every sample form Se to Sw and then-ISwl samples that fulfill the stopping conditions (9) and (10) and present the lowest leil values are used to complete SW . [sent-135, score-0.672]

62 4 BENCHMARK FOR THE IRWLS-SVC We have prepared two different experiments to test both the IRWLS and the sample selection strategy for solving the SVc. [sent-138, score-0.339]

63 The first one compares the IRWLS against QP and the second one compares the samples selection strategy, together with the IRWLS, against a complete solving procedure for SVC, the SV Mlight. [sent-139, score-0.432]

64 In the first trial, we have replaced the LOQO interior point optimizer used by SV M1ig ht version 3. [sent-140, score-0.063]

65 02 [5] by the IRWLS-SVC procedure in Table 1, to compare both optimizing engines with equal samples selection strategy. [sent-141, score-0.418]

66 The comparison has been made over a Pentium ill-450MHz with 128Mb running on Window98 and the programs have been compiled using Microsoft Developer 6. [sent-142, score-0.074]

67 In Table 2, we show the results for two data sets: the first q 20 40 70 Adult44781 CPU time Optimize Time LOQO IRWLS LOQO IRWLS 21. [sent-144, score-0.026]

68 72 Table 2: CPU Time indicates the consume time in seconds for the whole procedure. [sent-168, score-0.076]

69 The Optimize Time indicates the consume time in second for the LOQO or IRWLS procedure. [sent-169, score-0.044]

70 one, containing 4781 training samples, needs most CPU resources to compute the RKHS and the second one, containing 2175 training samples, uses most CPU resources to solve the SVC for each Sw, where q indicates the size of the working set. [sent-170, score-0.418]

71 I represents absolute value for numbers and cardinality for sets been set to 1 and 1000, respectively, and a Radial Basis Function (RBF) RKHS [2] has been employed, where its parameter a has been set, respectively, to 10 and 70. [sent-172, score-0.095]

72 As it can be seen, the SV M1ig ht with IRWLS is significantly faster than the LOQO procedure in all cases. [sent-173, score-0.219]

73 The kernel cache size has been set to 64Mb for both data sets and for both procedures. [sent-174, score-0.108]

74 The results in Table 2 validates the IRWLS procedure as the fastest SVC solver. [sent-175, score-0.153]

75 For the second trial, we have compiled a computer program that uses the IRWLS-SVC procedure and the working set selection in Section 3, we will refer to it as svcradit from now on. [sent-176, score-0.457]

76 We have borrowed the chunking and shrinking ideas from the SV Mlight [6] for our computer program. [sent-177, score-0.102]

77 To test these two programs several data sets have been used. [sent-178, score-0.113]

78 The Adult and Web data sets have been obtained from 1. [sent-179, score-0.083]

79 html/; the Gauss-M data set is a two dimensional classification problem proposed in [3] to test neural networks, which comprises a gaussian random variable for each class, which highly overlap. [sent-183, score-0.055]

80 The Banana, Diabetes and Splice data sets have been obtained from Gunnar Ratsch web page http://svm. [sent-184, score-0.193]

81 The selection of C and the RKHS has been done as indicated in [11] for Adult and Web data sets and in http://svm. [sent-188, score-0.175]

82 In Table 3, we show the runtime complexity for each data set, where the value of q has been elected as the one that reduces the runtime complexity. [sent-192, score-0.188]

83 2 10 1000 10 10 10 10 10 1 1 1 1 2 70 4477 12181 630 224 1444 1736 1516 80 1084 409 525 q CPU time radit light radit light 150 130 100 100 150 70 100 40 70 40 150 40 70 10 10 10 10 10 70 40 10 20 118. [sent-197, score-0.218]

84 19 Table 3: Several data sets runtime complexity, when solved with the short, and SV Mlight, light for short. [sent-219, score-0.185]

85 s v c radit , radit for One can appreciate that the svcradit is faster than the SV M1ig ht for most data sets. [sent-220, score-0.408]

86 For the Web data set, which is the only data set the SV Mlight is sligthly faster, the value of C is low and most training samples end up as support vector with (3i < C. [sent-221, score-0.404]

87 In such cases the best strategy is to take the largest step towards the solution in every iteration, as the SV Mlig ht does [6], because most training samples (3i will not be affected by the others training samples (3j value. [sent-222, score-0.889]

88 But in those case the value of C increases the SV c radit samples selection strategy is a much more appropriate strategy than the one used in SV Mlight. [sent-223, score-0.621]

89 5 CONCLUSIONS In this communication a new algorithm for solving the SVC for large training data sets has been presented. [sent-224, score-0.249]

90 Its two major contributions deal with the optimizing engine and the sample selection strategy. [sent-225, score-0.245]

91 An IRWLS procedure is used to solve the SVC in each step, which is much faster that the usual QP procedure, and simpler to implement, because the most difficult step is the linear equation system solution that can be easily obtained by LU decomposition means [12]. [sent-226, score-0.304]

92 The random working set selection from the samples not fulfilling the KKT conditions is the best option if the working is be large, because it reduces the number of chunks to be solved. [sent-227, score-0.584]

93 This strategy benefits from the IRWLS procedure, which allows to work with large training data set. [sent-228, score-0.241]

94 All these modifications have been concreted in the svcradit solving procedure, publicly available at http://svm. [sent-229, score-0.113]

95 A tutorial on support vector machines for pattern recognition. [sent-249, score-0.116]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('irwls', 0.524), ('svc', 0.471), ('samples', 0.172), ('sv', 0.165), ('stopping', 0.159), ('working', 0.134), ('loqo', 0.132), ('strategy', 0.124), ('procedure', 0.121), ('fulfill', 0.119), ('qp', 0.119), ('mlight', 0.109), ('radit', 0.109), ('chunking', 0.102), ('gin', 0.094), ('selection', 0.092), ('training', 0.091), ('ei', 0.09), ('cpu', 0.089), ('banana', 0.087), ('eiyi', 0.087), ('rkhs', 0.087), ('web', 0.084), ('sample', 0.076), ('table', 0.075), ('move', 0.07), ('sw', 0.068), ('runtime', 0.068), ('splice', 0.068), ('ai', 0.067), ('madrid', 0.066), ('svcradit', 0.066), ('universidad', 0.066), ('ht', 0.063), ('support', 0.062), ('ji', 0.059), ('sets', 0.057), ('solution', 0.057), ('diabetes', 0.056), ('jli', 0.056), ('kkt', 0.056), ('de', 0.053), ('conditions', 0.052), ('adult', 0.051), ('ss', 0.051), ('se', 0.051), ('every', 0.05), ('solve', 0.05), ('solving', 0.047), ('engine', 0.044), ('inactive', 0.044), ('candidate', 0.044), ('compiled', 0.044), ('consume', 0.044), ('escuela', 0.044), ('jiyi', 0.044), ('leil', 0.044), ('politecnica', 0.044), ('respectto', 0.044), ('violate', 0.044), ('si', 0.042), ('step', 0.041), ('qi', 0.04), ('bin', 0.04), ('select', 0.04), ('burges', 0.038), ('optimize', 0.038), ('cardinality', 0.038), ('osuna', 0.038), ('criteria', 0.037), ('http', 0.036), ('scheme', 0.036), ('faster', 0.035), ('solved', 0.034), ('iei', 0.034), ('optimizing', 0.033), ('whole', 0.032), ('fastest', 0.032), ('sl', 0.03), ('programs', 0.03), ('avoided', 0.03), ('dividing', 0.03), ('proposed', 0.029), ('yi', 0.029), ('largest', 0.028), ('communication', 0.028), ('reproducing', 0.028), ('violates', 0.028), ('workshop', 0.028), ('vector', 0.027), ('tutorial', 0.027), ('iterations', 0.026), ('complexity', 0.026), ('data', 0.026), ('resources', 0.026), ('obtaining', 0.026), ('lp', 0.026), ('page', 0.026), ('kernel', 0.025), ('scholkopf', 0.024)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000004 52 nips-2000-Fast Training of Support Vector Classifiers

Author: Fernando Pérez-Cruz, Pedro Luis Alarcón-Diana, Angel Navia-Vázquez, Antonio Artés-Rodríguez

2 0.084040061 12 nips-2000-A Support Vector Method for Clustering

Author: Asa Ben-Hur, David Horn, Hava T. Siegelmann, Vladimir Vapnik

Abstract: We present a novel method for clustering using the support vector machine approach. Data points are mapped to a high dimensional feature space, where support vectors are used to define a sphere enclosing them. The boundary of the sphere forms in data space a set of closed contours containing the data. Data points enclosed by each contour are defined as a cluster. As the width parameter of the Gaussian kernel is decreased, these contours fit the data more tightly and splitting of contours occurs. The algorithm works by separating clusters according to valleys in the underlying probability distribution, and thus clusters can take on arbitrary geometrical shapes. As in other SV algorithms, outliers can be dealt with by introducing a soft margin constant leading to smoother cluster boundaries. The structure of the data is explored by varying the two parameters. We investigate the dependence of our method on these parameters and apply it to several data sets.

3 0.080643103 70 nips-2000-Incremental and Decremental Support Vector Machine Learning

Author: Gert Cauwenberghs, Tomaso Poggio

Abstract: An on-line recursive algorithm for training support vector machines, one vector at a time, is presented. Adiabatic increments retain the KuhnTucker conditions on all previously seen training data, in a number of steps each computed analytically. The incremental procedure is reversible, and decremental

4 0.075084709 54 nips-2000-Feature Selection for SVMs

Author: Jason Weston, Sayan Mukherjee, Olivier Chapelle, Massimiliano Pontil, Tomaso Poggio, Vladimir Vapnik

Abstract: We introduce a method of feature selection for Support Vector Machines. The method is based upon finding those features which minimize bounds on the leave-one-out error. This search can be efficiently performed via gradient descent. The resulting algorithms are shown to be superior to some standard feature selection algorithms on both toy data and real-life problems of face recognition, pedestrian detection and analyzing DNA micro array data.

5 0.074170083 130 nips-2000-Text Classification using String Kernels

Author: Huma Lodhi, John Shawe-Taylor, Nello Cristianini, Christopher J. C. H. Watkins

Abstract: We introduce a novel kernel for comparing two text documents. The kernel is an inner product in the feature space consisting of all subsequences of length k. A subsequence is any ordered sequence of k characters occurring in the text though not necessarily contiguously. The subsequences are weighted by an exponentially decaying factor of their full length in the text, hence emphasising those occurrences which are close to contiguous. A direct computation of this feature vector would involve a prohibitive amount of computation even for modest values of k, since the dimension of the feature space grows exponentially with k. The paper describes how despite this fact the inner product can be efficiently evaluated by a dynamic programming technique. A preliminary experimental comparison of the performance of the kernel compared with a standard word feature space kernel [6] is made showing encouraging results. 1

6 0.070337549 75 nips-2000-Large Scale Bayes Point Machines

7 0.068311185 133 nips-2000-The Kernel Gibbs Sampler

8 0.063079976 22 nips-2000-Algorithms for Non-negative Matrix Factorization

9 0.062968321 128 nips-2000-Support Vector Novelty Detection Applied to Jet Engine Vibration Spectra

10 0.061625779 120 nips-2000-Sparse Greedy Gaussian Process Regression

11 0.05301217 4 nips-2000-A Linear Programming Approach to Novelty Detection

12 0.05185245 31 nips-2000-Beyond Maximum Likelihood and Density Estimation: A Sample-Based Criterion for Unsupervised Learning of Complex Models

13 0.051758334 58 nips-2000-From Margin to Sparsity

14 0.050711937 18 nips-2000-Active Support Vector Machine Classification

15 0.050264563 76 nips-2000-Learning Continuous Distributions: Simulations With Field Theoretic Priors

16 0.04764051 145 nips-2000-Weak Learners and Improved Rates of Convergence in Boosting

17 0.047462713 9 nips-2000-A PAC-Bayesian Margin Bound for Linear Classifiers: Why SVMs work

18 0.04743379 110 nips-2000-Regularization with Dot-Product Kernels

19 0.045821756 138 nips-2000-The Use of Classifiers in Sequential Inference

20 0.045523047 73 nips-2000-Kernel-Based Reinforcement Learning in Average-Cost Problems: An Application to Optimal Portfolio Choice

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.164), (1, 0.079), (2, -0.003), (3, -0.015), (4, -0.037), (5, 0.039), (6, -0.002), (7, 0.004), (8, -0.027), (9, 0.068), (10, -0.036), (11, 0.042), (12, 0.046), (13, -0.007), (14, 0.018), (15, -0.038), (16, -0.032), (17, -0.099), (18, -0.016), (19, -0.06), (20, 0.036), (21, -0.034), (22, -0.059), (23, -0.057), (24, -0.069), (25, -0.223), (26, -0.069), (27, 0.233), (28, -0.157), (29, -0.003), (30, 0.04), (31, 0.216), (32, -0.127), (33, -0.073), (34, 0.088), (35, -0.019), (36, 0.068), (37, -0.097), (38, 0.084), (39, 0.133), (40, 0.098), (41, -0.088), (42, 0.052), (43, 0.008), (44, 0.014), (45, -0.013), (46, 0.193), (47, 0.042), (48, -0.069), (49, -0.058)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95259249 52 nips-2000-Fast Training of Support Vector Classifiers

Author: Fernando Pérez-Cruz, Pedro Luis Alarcón-Diana, Angel Navia-Vázquez, Antonio Artés-Rodríguez

2 0.7215265 70 nips-2000-Incremental and Decremental Support Vector Machine Learning

Author: Gert Cauwenberghs, Tomaso Poggio

3 0.44857299 54 nips-2000-Feature Selection for SVMs

Author: Jason Weston, Sayan Mukherjee, Olivier Chapelle, Massimiliano Pontil, Tomaso Poggio, Vladimir Vapnik

4 0.42319575 18 nips-2000-Active Support Vector Machine Classification

Author: Olvi L. Mangasarian, David R. Musicant

Abstract: An active set strategy is applied to the dual of a simple reformulation of the standard quadratic program of a linear support vector machine. This application generates a fast new dual algorithm that consists of solving a finite number of linear equations, with a typically large dimensionality equal to the number of points to be classified. However, by making novel use of the Sherman-MorrisonWoodbury formula , a much smaller matrix of the order of the original input space is inverted at each step. Thus, a problem with a 32-dimensional input space and 7 million points required inverting positive definite symmetric matrices of size 33 x 33 with a total running time of 96 minutes on a 400 MHz Pentium II. The algorithm requires no specialized quadratic or linear programming code, but merely a linear equation solver which is publicly available. 1

5 0.41157591 5 nips-2000-A Mathematical Programming Approach to the Kernel Fisher Algorithm

Author: Sebastian Mika, Gunnar R채tsch, Klaus-Robert M체ller

Abstract: We investigate a new kernel-based classifier: the Kernel Fisher Discriminant (KFD). A mathematical programming formulation based on the observation that KFD maximizes the average margin permits an interesting modification of the original KFD algorithm yielding the sparse KFD. We find that both, KFD and the proposed sparse KFD, can be understood in an unifying probabilistic context. Furthermore, we show connections to Support Vector Machines and Relevance Vector Machines. From this understanding, we are able to outline an interesting kernel-regression technique based upon the KFD algorithm. Simulations support the usefulness of our approach.

6 0.39899433 22 nips-2000-Algorithms for Non-negative Matrix Factorization

7 0.36846811 93 nips-2000-On Iterative Krylov-Dogleg Trust-Region Steps for Solving Neural Networks Nonlinear Least Squares Problems

8 0.36200359 12 nips-2000-A Support Vector Method for Clustering

9 0.34075621 120 nips-2000-Sparse Greedy Gaussian Process Regression

10 0.33084753 133 nips-2000-The Kernel Gibbs Sampler

11 0.3243688 128 nips-2000-Support Vector Novelty Detection Applied to Jet Engine Vibration Spectra

12 0.31427896 130 nips-2000-Text Classification using String Kernels

13 0.3104893 116 nips-2000-Sex with Support Vector Machines

14 0.30668035 73 nips-2000-Kernel-Based Reinforcement Learning in Average-Cost Problems: An Application to Optimal Portfolio Choice

15 0.28065544 143 nips-2000-Using the Nyström Method to Speed Up Kernel Machines

16 0.27364162 1 nips-2000-APRICODD: Approximate Policy Construction Using Decision Diagrams

17 0.26955894 75 nips-2000-Large Scale Bayes Point Machines

18 0.2658233 29 nips-2000-Bayes Networks on Ice: Robotic Search for Antarctic Meteorites

19 0.25815591 127 nips-2000-Structure Learning in Human Causal Induction

20 0.24994211 68 nips-2000-Improved Output Coding for Classification Using Continuous Relaxation

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.215), (10, 0.019), (17, 0.087), (26, 0.012), (27, 0.073), (32, 0.018), (33, 0.044), (55, 0.04), (62, 0.04), (65, 0.025), (67, 0.054), (75, 0.023), (76, 0.049), (79, 0.016), (81, 0.018), (90, 0.091), (91, 0.013), (97, 0.049)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.81200218 52 nips-2000-Fast Training of Support Vector Classifiers

Author: Fernando Pérez-Cruz, Pedro Luis Alarcón-Diana, Angel Navia-Vázquez, Antonio Artés-Rodríguez

2 0.78425729 8 nips-2000-A New Model of Spatial Representation in Multimodal Brain Areas

Author: Sophie Denève, Jean-René Duhamel, Alexandre Pouget

Abstract: Most models of spatial representations in the cortex assume cells with limited receptive fields that are defined in a particular egocentric frame of reference. However, cells outside of primary sensory cortex are either gain modulated by postural input or partially shifting. We show that solving classical spatial tasks, like sensory prediction, multi-sensory integration, sensory-motor transformation and motor control requires more complicated intermediate representations that are not invariant in one frame of reference. We present an iterative basis function map that performs these spatial tasks optimally with gain modulated and partially shifting units, and tests it against neurophysiological and neuropsychological data. In order to perform an action directed toward an object, it is necessary to have a representation of its spatial location. The brain must be able to use spatial cues coming from different modalities (e.g. vision, audition, touch, proprioception), combine them to infer the position of the object, and compute the appropriate movement. These cues are in different frames of reference corresponding to different sensory or motor modalities. Visual inputs are primarily encoded in retinotopic maps, auditory inputs are encoded in head centered maps and tactile cues are encoded in skin-centered maps. Going from one frame of reference to the other might seem easy. For example, the head-centered position of an object can be approximated by the sum of its retinotopic position and the eye position. However, positions are represented by population codes in the brain, and computing a head-centered map from a retinotopic map is a more complex computation than the underlying sum. Moreover, as we get closer to sensory-motor areas it seems reasonable to assume Spksls 150 100 50 o Figure 1: Response of a VIP cell to visual stimuli appearing in different part of the screen, for three different eye positions. The level of grey represent the frequency of discharge (In spikes per seconds). The white cross is the fixation point (the head is fixed). The cell's receptive field is moving with the eyes, but only partially. Here the receptive field shift is 60% of the total gaze shift. Moreover this cell is gain modulated by eye position (adapted from Duhamel et al). that the representations should be useful for sensory-motor transformations, rather than encode an

3 0.74976712 60 nips-2000-Gaussianization

Author: Scott Saobing Chen, Ramesh A. Gopinath

Abstract: High dimensional data modeling is difficult mainly because the so-called

4 0.54570937 7 nips-2000-A New Approximate Maximal Margin Classification Algorithm

Author: Claudio Gentile

Abstract: A new incremental learning algorithm is described which approximates the maximal margin hyperplane w.r.t. norm p ~ 2 for a set of linearly separable data. Our algorithm, called ALMAp (Approximate Large Margin algorithm w.r.t. norm p), takes 0 ((P~21;;2) corrections to separate the data with p-norm margin larger than (1 - 0:) ,,(, where,,( is the p-norm margin of the data and X is a bound on the p-norm of the instances. ALMAp avoids quadratic (or higher-order) programming methods. It is very easy to implement and is as fast as on-line algorithms, such as Rosenblatt's perceptron. We report on some experiments comparing ALMAp to two incremental algorithms: Perceptron and Li and Long's ROMMA. Our algorithm seems to perform quite better than both. The accuracy levels achieved by ALMAp are slightly inferior to those obtained by Support vector Machines (SVMs). On the other hand, ALMAp is quite faster and easier to implement than standard SVMs training algorithms.

5 0.54325002 128 nips-2000-Support Vector Novelty Detection Applied to Jet Engine Vibration Spectra

Author: Paul M. Hayton, Bernhard Schölkopf, Lionel Tarassenko, Paul Anuzis

Abstract: A system has been developed to extract diagnostic information from jet engine carcass vibration data. Support Vector Machines applied to novelty detection provide a measure of how unusual the shape of a vibration signature is, by learning a representation of normality. We describe a novel method for Support Vector Machines of including information from a second class for novelty detection and give results from the application to Jet Engine vibration analysis.

6 0.54289579 74 nips-2000-Kernel Expansions with Unlabeled Examples

7 0.53657943 81 nips-2000-Learning Winner-take-all Competition Between Groups of Neurons in Lateral Inhibitory Networks

8 0.52745676 21 nips-2000-Algorithmic Stability and Generalization Performance

9 0.5272128 4 nips-2000-A Linear Programming Approach to Novelty Detection

10 0.52569652 111 nips-2000-Regularized Winnow Methods

11 0.52462733 106 nips-2000-Propagation Algorithms for Variational Bayesian Learning

12 0.52276903 3 nips-2000-A Gradient-Based Boosting Algorithm for Regression Problems

13 0.51994938 79 nips-2000-Learning Segmentation by Random Walks

14 0.51892167 40 nips-2000-Dendritic Compartmentalization Could Underlie Competition and Attentional Biasing of Simultaneous Visual Stimuli

15 0.51618499 119 nips-2000-Some New Bounds on the Generalization Error of Combined Classifiers

16 0.51614958 122 nips-2000-Sparse Representation for Gaussian Process Models

17 0.51455581 69 nips-2000-Incorporating Second-Order Functional Knowledge for Better Option Pricing

18 0.51030844 104 nips-2000-Processing of Time Series by Neural Circuits with Biologically Realistic Synaptic Dynamics

19 0.50885743 107 nips-2000-Rate-coded Restricted Boltzmann Machines for Face Recognition

20 0.50686377 75 nips-2000-Large Scale Bayes Point Machines