Active Set Support Vector Regression

              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