Page 1 
Save page Remove page  Previous  1 of 8  Next 

small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution
All (PDF)

This page
All

268 IEEE TRANSACTIONS ON NEURAL NETWORKS, VOL. 15, NO. 2, MARCH 2004 Active Set Support Vector Regression David R. Musicant and Alexander Feinberg Abstract—We present ASVR, a new active set strategy to solve a straightforward reformulation of the standard support vector regression problem. This new algorithm is based on the successful ASVM algorithm for classification problems, and consists of solving a finite number of linear equations with a typically large dimensionality equal to the number of points to be approximated. However, by making use of the ShermanMorrisonWoodbury formula, a much smaller matrix of the order of the original input space is inverted at each step. The algorithm requires no specialized quadratic or linear programming code, but merely a linear equation solver which is publicly available. ASVR is extremely fast, produces comparable generalization error to other popular algorithms, and is available on the web for download. Index Terms—regression, active set, support vector. I. INTRODUCTION SUPPORT vector regression (SVR) is a powerful technique for predictive data analysis [1], [2] with many applications to varied areas of study. For example, regression is used in biological contexts to model disease onset and intensity as influenced by various behaviors and environmental conditions [3]. Support vector regression has been used for diverse application areas such as drug discovery [4], civil engineering [5], and sunspot frequency prediction [6]. In this work, we present a new active set strategy to solve a straightforward reformulation of the standard support vector regression problem. This new algorithm, based on the successful ASVM algorithm for classification problems [7], consists of solving a finite number of linear equations with a typically large dimensionality equal to the number of points to be approximated. However, by making use of the ShermanMorrisonWoodbury formula, a much smaller matrix of the order of the original input space is inverted at each step. The algorithm requires no specialized quadratic or linear programming code, but merely a linear equation solver which is publicly available. Key to our approach are the following two changes to the standard linear SVR problem: Regularize the regression plane with respect to both orientation ( ) and location relative to the origin ( ). See (6) below. Such an approach has been successfully used in a number of classification methodologies, such as ASVM [7], LSVM [8], and SSVM [9]. Minimize the regression error ( and ) using the 2norm squared instead of the conventional 1norm. See (6). Such This work was supported by a grant from the Howard Hughes Medical Institute and by additional funding from Carleton College. c 2004 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. an approach is common in the context of traditional least squares regression [10]. These simple, but fundamental changes, lead to a considerably simpler dual problem with only nonnegativity constraints and a simple complementarity condition. In Section II of the paper we begin with the standard SVR formulation and its dual and then give our formulation and its simpler dual. We corroborate with solid computational evidence that our simpler formulation does not compromise on generalization ability as evidenced by numerical tests in Section IV on public datasets. See Table I. Section III gives our active set support vector regression (ASVR) Algorithm 1 which consists of repeatedly solving systems of linear equations. By invoking the ShermanMorrisonWoodbury (SMW) formula (1) we need only invert an matrix where is the dimensionality of the input space. This is a key feature of our approach that allows us to solve problems with millions of points by merely inverting much smaller matrices of the order of . Section IV describes our numerical results which indicate that the ASVR formulation has a tenfold testing correctness that is as good as the ordinary SVR formulation, and has the capability of quickly and accurately solving massive problems with millions of points that are difficult to solve with standard SVR methods. There is a considerable amount of previous literature related to our work. Numerous software packages available to the community do support vector regression [6], [11]–[15]. The ShermanMorrisonWoodbury formula has been used by many support vector machine approaches, such as ASVM [7], LSVM [8], and PSVM [16], as well as in an interior point approach by Ferris and Munson [17]. Williams and Seeger make use of the SMW formula in applying the Nystr¨om method to Gaussian process classification and regression [18]. In addition to our own previous work on active set methods [7], Burges has also used an active set method for the support vector classification problem [19]. We note that an active set computational strategy bears no relation to active learning. Evgeniou, Pontil, and Poggio [20] provide a general theory for considering different support vector machine formulations. Within this framework, our approach can be seen to contain elements of both standard support vector regression and regularization networks. The support vector machine regression problem differs from the support vector machine classification problem in a few fundamental ways [2], [21]. The goal of the classification problem is to make a binary decision, i.e. to choose in which of two classes a given point should be classified. The goal of the regression problem, on the other hand, is to approximate a function. The solution to a support vector regression problem is a function that accepts a data point and returns a continuous 10459227/04$20.00 c 2004 IEEE
Object Description
Collection Title  Scholarly Publications by Carleton Faculty and Staff 
Journal Title  IEEE Transactions on Neural Networks 
Article Title  Active Set Support Vector Regression 
Article Author 
Musicant, Dave Feinberg, Alexander 
Carleton Author 
Musicant, Dave 
Department  Computer Science 
Field  Science and Mathematics 
Year  2004 
Volume  15 
Publisher  IEEE 
File Name  008_MusicantDave_ActiveSetSupportVectorRegression.pdf; 008_MusicantDave_ActiveSetSupportVectorRegression.pdf 
Rights Management  This document is authorized for selfarchiving and distribution online by the author(s) and is free for use by researchers. 
RoMEO Color  RoMEO_Color_Green 
Preprint Archiving  Yes 
Postprint Archiving  Yes 
Publisher PDF Archiving  Yes 
Paid OA Option  No_Value 
Contributing Organization  Carleton College 
Type  Text 
Format  application/pdf 
Language  English 
Description
Article Title  Page 1 
FullText  268 IEEE TRANSACTIONS ON NEURAL NETWORKS, VOL. 15, NO. 2, MARCH 2004 Active Set Support Vector Regression David R. Musicant and Alexander Feinberg Abstract—We present ASVR, a new active set strategy to solve a straightforward reformulation of the standard support vector regression problem. This new algorithm is based on the successful ASVM algorithm for classification problems, and consists of solving a finite number of linear equations with a typically large dimensionality equal to the number of points to be approximated. However, by making use of the ShermanMorrisonWoodbury formula, a much smaller matrix of the order of the original input space is inverted at each step. The algorithm requires no specialized quadratic or linear programming code, but merely a linear equation solver which is publicly available. ASVR is extremely fast, produces comparable generalization error to other popular algorithms, and is available on the web for download. Index Terms—regression, active set, support vector. I. INTRODUCTION SUPPORT vector regression (SVR) is a powerful technique for predictive data analysis [1], [2] with many applications to varied areas of study. For example, regression is used in biological contexts to model disease onset and intensity as influenced by various behaviors and environmental conditions [3]. Support vector regression has been used for diverse application areas such as drug discovery [4], civil engineering [5], and sunspot frequency prediction [6]. In this work, we present a new active set strategy to solve a straightforward reformulation of the standard support vector regression problem. This new algorithm, based on the successful ASVM algorithm for classification problems [7], consists of solving a finite number of linear equations with a typically large dimensionality equal to the number of points to be approximated. However, by making use of the ShermanMorrisonWoodbury formula, a much smaller matrix of the order of the original input space is inverted at each step. The algorithm requires no specialized quadratic or linear programming code, but merely a linear equation solver which is publicly available. Key to our approach are the following two changes to the standard linear SVR problem: Regularize the regression plane with respect to both orientation ( ) and location relative to the origin ( ). See (6) below. Such an approach has been successfully used in a number of classification methodologies, such as ASVM [7], LSVM [8], and SSVM [9]. Minimize the regression error ( and ) using the 2norm squared instead of the conventional 1norm. See (6). Such This work was supported by a grant from the Howard Hughes Medical Institute and by additional funding from Carleton College. c 2004 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. an approach is common in the context of traditional least squares regression [10]. These simple, but fundamental changes, lead to a considerably simpler dual problem with only nonnegativity constraints and a simple complementarity condition. In Section II of the paper we begin with the standard SVR formulation and its dual and then give our formulation and its simpler dual. We corroborate with solid computational evidence that our simpler formulation does not compromise on generalization ability as evidenced by numerical tests in Section IV on public datasets. See Table I. Section III gives our active set support vector regression (ASVR) Algorithm 1 which consists of repeatedly solving systems of linear equations. By invoking the ShermanMorrisonWoodbury (SMW) formula (1) we need only invert an matrix where is the dimensionality of the input space. This is a key feature of our approach that allows us to solve problems with millions of points by merely inverting much smaller matrices of the order of . Section IV describes our numerical results which indicate that the ASVR formulation has a tenfold testing correctness that is as good as the ordinary SVR formulation, and has the capability of quickly and accurately solving massive problems with millions of points that are difficult to solve with standard SVR methods. There is a considerable amount of previous literature related to our work. Numerous software packages available to the community do support vector regression [6], [11]–[15]. The ShermanMorrisonWoodbury formula has been used by many support vector machine approaches, such as ASVM [7], LSVM [8], and PSVM [16], as well as in an interior point approach by Ferris and Munson [17]. Williams and Seeger make use of the SMW formula in applying the Nystr¨om method to Gaussian process classification and regression [18]. In addition to our own previous work on active set methods [7], Burges has also used an active set method for the support vector classification problem [19]. We note that an active set computational strategy bears no relation to active learning. Evgeniou, Pontil, and Poggio [20] provide a general theory for considering different support vector machine formulations. Within this framework, our approach can be seen to contain elements of both standard support vector regression and regularization networks. The support vector machine regression problem differs from the support vector machine classification problem in a few fundamental ways [2], [21]. The goal of the classification problem is to make a binary decision, i.e. to choose in which of two classes a given point should be classified. The goal of the regression problem, on the other hand, is to approximate a function. The solution to a support vector regression problem is a function that accepts a data point and returns a continuous 10459227/04$20.00 c 2004 IEEE 