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 Sherman-Morrison-Woodbury 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 appli-cation 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 reformu-lation 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 Sherman-Morrison-Woodbury 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 2-norm squared instead of the conventional 1-norm. 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 consider-ably 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 equa-tions. By invoking the Sherman-Morrison-Woodbury (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 ten-fold 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 re-lated to our work. Numerous software packages available to the community do support vector regression [6], [11]–[15]. The Sherman-Morrison-Woodbury 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 reg-ularization 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 1045-9227/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_Musicant-Dave_ActiveSetSupportVectorRegression.pdf; 008_Musicant-Dave_ActiveSetSupportVectorRegression.pdf |
Rights Management | This document is authorized for self-archiving 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 Sherman-Morrison-Woodbury 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 appli-cation 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 reformu-lation 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 Sherman-Morrison-Woodbury 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 2-norm squared instead of the conventional 1-norm. 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 consider-ably 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 equa-tions. By invoking the Sherman-Morrison-Woodbury (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 ten-fold 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 re-lated to our work. Numerous software packages available to the community do support vector regression [6], [11]–[15]. The Sherman-Morrison-Woodbury 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 reg-ularization 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 1045-9227/04$20.00 c 2004 IEEE |