Proximal support vector machine classifiers.
Instead of a standard support vector machine (SVM) that classifies points by assigning them to one of two disjoint half-spaces, points are classified by assigning them to the closest of two parallel planes (in input or feature space) that are pushed apart as far as possible. This formulation, which can also be interpreted as regularized least squares and considered in the much more general context of regularized networks [8, 9], leads to an extremely fast and simple algorithm for generating a linear or nonlinear classifier that merely requires the solution of a single system of linear equations. In contrast, standard SVMs solve a quadratic or a linear program that require considerably longer computational time. Computational results on publicly available datasets indicate that the proposed proximal SVM classifier has comparable test set correctness to that of standard SVM classifiers, but with considerably faster computational time that can be an order of magnitude faster. The linear proximal SVM can easily handle large datasets as indicated by the classification of a 2 million point 10-attribute set in 20.8 seconds. All computational results are based on 6 lines of MATLAB code.
INTRODUCTION
Standard support vector machines (SVMs) [36, 6, 3, 5,
20], which are powerful tools for data classification, classify
points by assigning them to one of two disjoint halfspaces.
These halfspaces are either in the original input space of
the problem for linear classifiers, or in a higher dimensional
feature space for nonlinear classifiers [36, 6, 20]. Such standard
SVMs require the solution of either a quadratic or a
linear program which require specialized codes such as [7].
In contrast we propose here a proximal SVM (PSVM) which
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
KDD 2001 San Francisco CA USA
classifies points depending on proximity to one of two parallel
planes that are pushed as far apart as possible. In fact our
geometrically motivated proximal formulation has been considered
in the much more general context of regularization
networks [8, 9]. These results, which give extensive theoretical
and statistical justification for the proximal approach,
do not contain the extensive computational implementation
and results given here. Furthermore, our specific formulation
leads to a strongly convex objective function which is
not always the case in [8, 9]. Strong convexity plays a key
role in the simple proximal code provided here as well the
very fast computational times obtained. Obtaining a linear
or nonlinear PSVM classifier requires nothing more sophisticated
than solving a single system of linear equations. Efficient
and fast linear equation solvers are freely available [1]
or are part of standard commercial packages such as MATLAB
[26], and can solve large systems very fast.
We briefly summarize the contents of the paper now. In
Section 2 we introduce the proximal linear support vector
machine, give the Linear Proximal Algorithm 2.1 and an explicit
expression for the leave-one-out-correctness in terms of
problem data (16). In Section 3 we introduce the proximal
kernel-based nonlinear support vector machine, the corresponding
nonlinear classifier (28) and the Nonlinear Proximal
Algorithm 3.1. Section 3 contains many numerical testing
results for both the linear and nonlinear classifiers based
on an extremely simple MATLAB [26] code of 6 lines for
both the linear and nonlinear PSVM. The results surpass
all other algorithms compared to in speed and give very
comparable testing set correctness.
A word about our notation and background material. All
vectors will be column vectors unless transposed to a row
vector by a prime superscript # . For a vector x in the n-dimensional
real space R n , the step function step(x) is defined
as
n. The scalar (inner) product of two vectors
x and y in the n-dimensional real space R n will be denoted
by x # y and the 2-norm of x will be denoted by #x#. For a
matrix A # R m-n , A i is the ith row of A which is a row
vector in R n , while A -j is the jth column of A. A column
vector of ones of arbitrary dimension will be denoted by e.
For A # R m-n and B # R n-k , the kernel K(A,B) maps
R m-n
-R n-k into R m-k . In particular, if x and y are column
vectors in R n then, K(x # , y) is a real number, K(x # , A # )
is a row vector in R m and K(A,A # ) is an m-m matrix. The
base of the natural logarithm will be denoted by #. We will
make use of the following Gaussian kernel [36, 6, 20] that is
frequently used in the SVM literature:
(1)
where A # R m-n , B # R n-k and - is a positive constant.
The identity matrix of arbitrary dimension will be denoted
by I.
2. THE LINEAR PROXIMAL SUPPORT VECTOR
We consider the problem, depicted in Figure 1, of classifying
m points in the n-dimensional real space R n , represented
by the m - n matrix A, according to membership of each
point A i in the class A+ or A- as specified by a given m-m
diagonal matrix D with plus ones or minus ones along its
diagonal. For this problem, the standard support vector machine
with a linear kernel [35, 6] is given by the following
quadratic program with parameter # > 0:
min
(w,#,y)#R n+1+m
(2)
As depicted in Figure 1, w is the normal to the bounding
planes:
that bound most of the sets A+ and A- respectively. The
constant # determines their location relative to the origin.
When the two classes are strictly linearly separable, that is
when the error variable in (2) (which is not the case
shown in Figure 1), the plane x # all of the
class A+ points, while the plane x #
the class A- points as follows:
Consequently, the plane:
midway between the bounding planes (3), is a separating
plane that separates A+ from A- completely if
only approximately as depicted in Figure 1. The quadratic
term in (2), which is twice the reciprocal of the square of
the 2-norm distance 2
#w# between the two bounding planes
of (3) (see

Figure

1), maximizes this distance, often called
the "margin". Maximizing the margin enhances the generalization
capability of a support vector machine [35, 6]. If
the classes are linearly inseparable, which is the case shown
in

Figure

1, then the two planes bound the two classes with
a "soft margin" (i.e. bound approximately with some error)
determined by the nonnegative error variable y, that is:
The 1-norm of the error variable y is minimized parametrically
with weight # in (2) resulting in an approximate separating
plane (5) as depicted in Figure 1. This plane acts as
a linear classifier as follows:
< 0, then x # A-,
Our point of departure is similar to that of [23, 24], where
the optimization problem (2) is replaced by the following
problem:
min
(w,#,y)#R n+1+m
Note that no explicit nonnegativity constraint is needed on
y, because if any component y i is negative then the objective
function can be decreased by setting that y
still satisfying the corresponding inequality constraint. Note
further that the 2-norm of the error vector y is minimized
instead of the 1-norm, and the margin between the bounding
planes is maximized with respect to both orientation w
and relative location to the origin #. Extensive computational
experience, as in [22, 23, 24, 18, 17] indicates that
this formulation is just as good as the classical formulation
(2) with some added advantages such as strong convexity of
the objective function. Our key idea in this present paper is
to make a very simple, but very fundamental change in the
formulation (8), namely replace the inequality constraint by
an equality as follows:
min
(w,#,y)#R n+1+m
This modification, even though very simple, changes the nature
of optimization problem significantly. In fact it turns
out that we can write an explicit exact solution to the problem
in terms of the problem data as we show below, whereas
it is impossible to do that in the previous formulations because
of their combinatorial nature. Geometrically the formulation
is depicted in Figure 2 which can be interpreted
as follows. The planes x # w -1 are not bounding
planes anymore, but can be thought of as "proximal"
planes, around which the points of each class are clustered
and which are pushed as far apart as possible by the term
(w in the objective function which is nothing other
than the reciprocal of the 2-norm distance squared between
the two planes in the (w, #) space of R n+1 .
x
A-
x
x
x
x
x
x
x
PSfrag replacements
#w#
Separating Plane: x #

Figure

1: The Standard Support Vector Machine
Classifier in the w-space of R n : The approximately
bounding planes of equation (3) with a soft (i.e. with
some error) margin 2
#w# , and the plane of equation
approximately separating A+ from A-.
x
x
x
x
x
A-
x
x
x
x
x
x
x
PSfrag replacements
Separating Plane: x # w

Figure

2: The Proximal Support Vector Machine
Classifier in the (w, #)-space of R n+1 : The planes
which points of the sets A+
and A- cluster and which are pushed apart by the
optimization problem (9).
We note that our formulation (9) can be also interpreted
as a regularized least squares solution [34] of the system of
linear equations D(Aw - e, that is finding an approximate
solution (w, #) with least 2-norm. Similarly the
standard SVM formulation (2) can be interpreted, by using
linear programming perturbation theory [21], as a least 2-
norm approximate solution to the system of linear inequalities
e. Neither of these interpretations,
however, is based on the idea of maximizing the margin,
the distance between the parallel planes (3), which is a key
feature of support vector machines [36, 6, 20].
The Karush-Kuhn-Tucker (KKT) necessary and su#cient
optimality conditions [19, p. 112] for our equality constrained
problem are obtained by setting equal to zero
the gradients with respect to (w, #, y, u) of the Lagrangian:
L(w, #, y,
Here, u is the Lagrange multiplier associated with the
equality constraint of (9). Setting the gradients of L equal
to zero gives the following KKT optimality conditions:
The first three equations of (11) give the following expressions
for the original problem variables (w, #, y) in terms of
the Lagrange multiplier u:
. (12)
Substituting these expressions in the last equality of (11)
allows us to obtain an explicit expression for u in terms of
the problem data A and D as follows:
I
I
where H is defined as:
Having u from (13), the explicit solution (w, #, y) to our
problem (9) is given by (12). Because the solution (13) for
u entails the inversion of a possibly massive m-m matrix,
we make immediate use of the Sherman-Morrison-Woodbury
formula [14, p. 51] for matrix inversion, as was done in [23,
10, 24], which results in:
I
This expression, as well as another simple expression (29)
for
below, involve the inversion of a much smaller dimensional
matrix of order (n completely
solves the classification problem. For concreteness we explicitly
state our very simple algorithm.
Algorithm 2.1. Linear Proximal SVM Given m data
points in R n represented by the m - n matrix A and a diagonal
matrix D of -1 labels denoting the class of each row
of A, we generate the linear classifier (7) as follows:
(i) Define H by (14) where e is an m - 1 vector of ones
and compute u by (15) for some positive #. Typically
# is chosen by means of a tuning (validating) set.
(ii) Determine (w, #) from (12).
(iii) Classify a new x by using (7).
For standard SVMs, support vectors consist of all data
points which are the complement of the data points that
can be dropped from the problem without changing the separating
plane (5) [36, 20]. Thus, for the standard SVM formulation
(2), support vectors correspond to data points for
which the Lagrange multipliers are nonzero because, solving
(2) with these data points only will give the same answer as
solving it with the entire dataset. In our proximal formulation
however, the Lagrange multipliers u are merely a
multiple of the error vector y: #y as given by (12). Con-
sequently, because all components of y are typically nonzero
since none of the data points usually lie on the proximal
planes x # the concept of support vectors needs to
be modified as follows. Because (w, # R n+1 are given as
linear functions of y by (11), it follows by the basis theorem
for linear equations [13, Theorem 2.11][25, Lemma 2.1],
applied to the last equality of (11) for a fixed value of the
error vector y, that at most n+ 1 linearly independent data
points are needed to determine the basic nonzero components
of (w, # R n+1 . Guided by this fact that only a
small number of data points can characterize any specific
(w, #), we define the concept of #-support vectors as those
data points A i for which error vector y i is less than # in
absolute value. We typically pick # small enough such that
about 1% of the data are #-support vectors. Re-solving our
proximal SVM problem (9) with these data points and a #
adjusted (typically upwards) by a tuning set gives test set
correctness that is essentially identical to that obtained by
using the entire dataset.
We note that with explicit expressions (w, #, y, u) in terms
of problem data given by (12) and (15), we are able to get
also an explicit expression for the leave-one-out-correctness
looc [32], that is the fraction of correctly classified data
points if each point in turn is left out of the PSVM formulation
and then is classified by the classifier (7). Omitting
some algebra, we have the following leave-one-out-correctness:
where the "step" function is defined in the Introduction, and
I
Here, H is defined by (14), H i denotes row i of H, while H i
denotes H with row H i removed from H, and u i is defined
by (15) with H replaced by H i . Similarly, D i denotes row i
of D.
We extend now some of the above results to nonlinear
proximal support vector machines.
3. NONLINEAR PROXIMAL SUPPORT VECTOR
MACHINES
To obtain our nonlinear proximal classifier we modify our
equality constrained optimization problem (9) as in [20, 18]
by replacing the primal variable w by its dual equivalent
# Du from (12) to obtain:
min
e,
where the objective function has also been modified to minimize
weighted 2-norm sums of the problem variables (u, #, y).
If we now replace the linear kernel AA # by a nonlinear kernel
defined in the Introduction, we obtain:
min
Using the shorthand notation:
the Lagrangian for (19) can be written similarly to (10) as:
L(u, #, y,
Here, v # R m is the Lagrange multiplier associated with
the equality constraint of (19). Setting the gradients of this
Lagrangian with respect to (u, #, y, v) equal to zero gives the
following KKT optimality conditions:
The first three equations of (22) give the following expressions
for (u, #, y) in terms of the Lagrange multiplier v:
. (23)
Substituting these expressions in the last equality of (22)
gives an explicit expression for v in terms of the problem
data A and D as follows:
I
I
e, (24)
where G is defined as:
Note the similarity between G above and H as defined in
(14). This similarity allows us to obtain G from the expression
replacing A by K in (14). This can be
taken advantage of in the MATLAB code 4.1 of Algorithm
2.1 which is written for the linear classifier (7). Thus, to generate
a nonlinear classifier by Algorithm 3.1 merely replace
A by K in the algorithm.
Having the solution v from (24), the solution (u, #, y) to
our problem (19) is given by (23). Unlike the situation with
linear kernels, the Sherman-Morrison-Woodbury formula is
useless here because the kernel matrix
square so the inversion must take place in
a potentially high-dimensional R m . However, the reduced
kernel techniques of [17] can be utilized to reduce the m-
m dimensionality of the kernel to a much
smaller m-
m dimensionality of a rectangular kernel
m is as small as 1% of m and -
A is an
random submatrix of of A. Such reduced kernels not
only make most large problems tractable, but they also often
lead to improved generalization by avoiding data overfitting.
The e#ectiveness of these reduced kernels is demonstrated
by means of a numerical test problem in the next section of
the paper.
The nonlinear separating surface corresponding to the kernel
Equation (8.1)] and can be deduced from
the linear separating surface (5) and
as follows:
If we replace x # A # by the corresponding kernel expression
substitute from (23) for u and #:
we obtain the nonlinear separating surface:
The corresponding nonlinear classifier to this nonlinear separating
surface is then:
< 0, then x # A-,
We now give an explicit statement of our nonlinear classifier
algorithm.
Algorithm 3.1. Nonlinear Proximal SVM Given m
data points in R n represented by the m- n matrix A and a
diagonal matrix D of -1 labels denoting the class of each row
of A, we generate the nonlinear classifier (28) as follows:
(i) Choose a kernel function K(A,A # ), typically the Gaussian
kernel (1).
(ii) Define G by (25) where is an
vector of ones. Compute v by (24) for some
positive #. (Typically # is chosen by means of a tuning
set.)
(iii) The nonlinear surface (27) with the computed v constitutes
the nonlinear classifier (28) for classifying a
new point x.
The nonlinear classifier (28), which is a direct generalization
of the linear classifier (7), works quite e#ectively as indicated
by the numerical examples presented in the next section.
4. NUMERICAL IMPLEMENTATION AND COMPARISON

Most of our computations were performed on the University
of Wisconsin Data Mining Institute "locop1" machine,
which utilizes a 400 Mhz Pentium II and allows a maximum
of 2 Gigabytes of memory for each process. This computer
runs on Windows NT server 4.0, with MATLAB 6 installed.
Even though "locop1" is a multiprocessor machine, only one
processor was used for all the experiments since MATLAB
is a single threaded application and does not distribute any
load across processors [26]. Our algorithms require the solution
of a single square system of linear equations of the
size of the number of input attributes n in the linear case,
and of the size of the number of data points m in the non-linear
case. When using a rectangular kernel [18], the size
of the problem can be reduced from m to k with k << m
for the nonlinear case. Because of the simplicity of our algo-
rithm, we give below the actual MATLAB implementation
that was used in our experiments and which consists of 6
lines of native MATLAB code:
-226
Figure

3: The spiral dataset consisting of 97 black
points and 97 white points intertwined as two spirals
in 2-dimensional space. PSVM with a Gaussian kernel
generated a sharp nonlinear spiral-shaped separating
Code 4.1. PSVM MATLAB Code
function
% PSVM:linear and nonlinear classification
Note that the command line in the MATLAB code above:
computes directly the factor ( I
of (15). This is much more economical and stable
than computing the inverse ( I
explicitly then
multiplying it by H # e. The calculations H # e and A # s involve
the transpose of typically large matrices which can be time
consuming. Instead, we calculate r=sum(H)' and w=(s'*A)'
respectively, the transposes of these vectors.
We further note that the MATLAB code above not only
works for a linear classifier, but also for a nonlinear classifier
as well. In the nonlinear case, the matrix K(A,A # ) is used
as input instead of A, [20, Equations (1), (10)], and the pair
returned instead of (w, #).
The nonlinear separating surface is then given by (27) as:
Rectangular kernels [17] can also be handled by this code.
The input then is the rectangular matrix K(A, -
A # R m-k , k << m and the given output is the pair (-u, #)
with -
D and - u are the D and u
associated with the reduced matrix -
A.
A final note regarding a further simplification of PSVM.
If we substitute the expression (15) for u in (12), we obtain
after some algebra the following simple expression for w and
# in terms of the problem data:
I
E)
This direct explicit solution of our PSVM problem
be written as the following single line of MATLAB code,
which also does not perform the explicit matrix inversion
I
E) -1 , and is slightly faster than the above MATLAB
code:
Here, according to MATLAB commands, diag(D) is an m-1
vector generated from the diagonal of the matrix D. Computational
testing results using this one-line MATLAB code
are slightly better than those obtained with Code 4.1
and are the ones reported in the tables below. We comment
further that the solution (29) can also be obtained directly
from (9) by using the equality constraint to eliminate y from
the problem and solving the resulting unconstrained minimization
problem in the variables w and # by setting to zero
the gradients with respect to w and #. We turn now to our
computations.
The datasets used for our numerical tests were the following

. Seven publicly available datasets from the UCI Machine
Learning Repository [28]: WPBC, Ionosphere,
Cleveland Heart, Pima Indians, BUPA Liver, Mush-
room, Tic-Tac-Toe.
. The Census dataset is a version of the US Census Bureau
"Adult" dataset, which is publicly available from
the Silicon Graphics website [4].
. The Galaxy Dim dataset used in galaxy discrimination
with neural networks from [30]
. Two large datasets (2 million points and 10 attributes)
created using David Musicant's NDC Data Generator
[29].
. The Spiral dataset proposed by Alexis Wieland of the
MITRE Corporation and available from the CMU Artificial
Intelligence Repository [37].
We outline our computational results now in five groups
as follows.
1.

Table

1: Comparison of seven di#erent methods
on the Adult dataset In this experiment we
compared the performance of seven di#erent methods
for linear classification on di#erent sized versions of
the Adult dataset. Reported results on the SOR [22],
SMO [31] and SVM light [16] are from [22]. Results for
LSVM [24] results were computed here using "locop1",
whereas SSVM [18] and RLP [2] are from [18]. The
SMO experiments were run on a 266 MHz Pentium II
processor under Windows NT 4 using Microsoft's Visual
C++ 5.0 compiler. The SOR experiments were
run on a 200 MHz Pentium Pro with 64 megabytes
of RAM, also under Windows NT 4 and using Visual
C++ 5.0. The SVM light experiments were run on the
same hardware as that for SOR, but under the Solaris
5.6 operating system. Bold type indicates the
best result and a dash (-) indicates that the results
were not available from [22]. Although the timing comparisons
are approximate because of the di#erent machines
used, they do indicate that PSVM has a distinct
edge in speed, e.g. solving the largest problem in 7.4
seconds, which is much faster than any other method.
Times and ten-fold testing correctness are shown in

Table

1. Times are for the ten-folds.
2.

Table

4: Comparative performances of LSVM
[24] and PSVM on a large dataset
Two large datasets consisting of 2 million points and
attributes were created using the NDC Data Generator
[29]. One of them is called NDC-easy because it
is highly linearly separable (around 90%). The other
one is called NDC-hard since it has linear separability
of around 70%. As is shown in Table 4 the linear classifiers
obtained using both methods performed almost
identically. Despite the 2 million size of the datasets,
PSVM solved the problems in about 20 seconds each
compared to LSVM's times of over 650 seconds. In
contrast, SVM light [16] failed on this problem [24].
3.

Table

3: Comparison of PSVM, SSVM and
LSVM and SVM light , using a Linear Classifier
In this experiment we compared four methods: PSVM,
SSVM, LSVM and SVM light on seven publicly available
datasets from UCI Machine Learning Repository
[28] and [30]. As shown in Table 3, the correctness of
the four methods were very similar but the execution
time including ten-fold cross validation for PSVM was
smaller by as much as one order of magnitude or more
than the other three methods tested. Since LSVM,
SSVM and PSVM are all based on similar formulations
of the classification problem the same value of #
was used for all of them. For SVM light the trade-o#
between trading error and margin is represented by a
parameter C. The value of C was chosen by tuning.
A paired t-test [27] at 95% confidence level was performed
to compare the performance of PSVM and the
other algorithms tested. The p-values obtained show
that there is no significant di#erence between PSVM
and the other methods tested.
4.

Figure

3: PSVM on the Spiral Dataset
We used a Gaussian kernel in order to classify the spiral
dataset. This dataset consisting of 194 black and
white points intertwined in the shape of a spiral is a
synthetic dataset [37]. However, it apparently is a di#-
cult test case for data mining algorithms and is known
to give neural networks severe problems [15]. In con-
trast, a sharp separation was obtained using PSVM as
can be seen in Figure 3.
5.

Table

2: Nonlinear Classifier Comparison using
PSVM, SSVM and LSVM
For this experiment we chose four datasets from the
UCI Machine Learning Repository for which it is known
that a nonlinear classifier performs significantly better
that a linear classifier. We used PSVM, SSVM and
LSVM in order to find a Gaussian-kernel-based non-linear
classifier to classify the data. In all datasets
tested, the three methods performed similarly as far
as ten-fold cross validation is concerned. However, execution
time of PSVM was much smaller than that
of other two methods. Note that for the mushroom
dataset that consists of points with
attributes each, the square 8124 - 8124 kernel matrix
does not fit into memory. In order to address this prob-
lem, we used a rectangular kernel with -
A # R 215-8124
instead, as described in [17]. In general, our algorithm
performed particularly well with a rectangular kernel
since the system solved is of size k - k, with k << m
and where k is the much smaller number of rows of -
A.
In contrast with a full square kernel matrix the system
solved is of size m - m. A paired t-test [27] at 95%
confidence level was performed to compare the performance
of PSVM and the other algorithms tested. The
p-values obtained show that there is no significant difference
between PSVM and the other methods tested
as far as ten-fold testing correctness is concerned.
5. CONCLUSION AND FUTURE WORK
We have proposed an extremely simple procedure for generating
linear and nonlinear classifiers based on proximity to
one of two parallel planes that are pushed as far apart as pos-
sible. This procedure, a proximal support vector machine
(PSVM), requires nothing more sophisticated than solving
a simple nonsingular system of linear equations, for either a
linear or nonlinear classifier. In contrast, standard support
vector machine classifiers require a more costly solution of a
linear or quadratic program. For a linear classifier, all that
is needed by PSVM is the inversion of a small matrix of the
order of the input space dimension, typically of the order of
100 or less, even if there are millions of data points to clas-
sify. For a nonlinear classifier, a linear system of equations
of the order of the number of data points needs to be solved.
This allows us to easily classify datasets with as many as a
few thousand of points. For larger datasets, data selection
and reduction methods such as [11, 17, 12] can be utilized as
indicated by some of our numerical results and will be the
subject of future work. Our computational results demonstrate
that PSVM classifiers obtain test set correctness statistically
comparable to that of standard of SVM classifiers
at a fraction of the time, sometimes an order of magnitude
less.
Another avenue for future research is that of incremental
classification for large datasets. This appears particularly
promising in view of the very simple explicit solutions
and (24) for the linear and nonlinear PSVM classifiers
that can be updated incrementally as new data points come
streaming in.
To sum up, the principal contribution of this work, is a
very e#cient classifier that requires no specialized software.
PSVM can be easily incorporated into all sorts of data mining
applications that require a fast, simple and e#ective classifier

Acknowledgements

The research described in this Data Mining Institute Report
01-02, February 2001, was supported by National Science
Foundation Grants CCR-9729842 and CDA-9623632, by Air
Force O#ce of Scientific Research Grant F49620-00-1-0085
and by the Microsoft Corporation. We are grateful to Professor
C.-J. Lin of National Taiwan University who pointed
out reference [33], upon reading the original version of this
paper. Least squares are also used in [33] to construct an
SVM, but with the explicit requirement of Mercer's positive
definiteness condition [35], which is not needed here. Fur-
thermore, the objective function of the quadratic program
of [33] is not strongly convex like ours. This important feature
of PSVM influences its speed as evidenced by the many
numerical comparisons given here but not in [33].
6.



--R

LAPACK User's Guide.
Robust linear programming discrimination of two linearly inseparable sets.
Massive data discrimination via linear support vector machines.
US Census Bureau.
A tutorial on support vector machines for pattern recognition.
Learning from Data - Concepts
CPLEX Optimization Inc.
Regularization networks and support vector machines.
Regularization networks and support vector machines.
Interior point methods for massive support vector machines.
Data selection for support vector machine classification.

The Theory of Linear Economic Models.
Matrix Computations.
Data mining with sparse grids.
Making large-scale support vector machine learning practical
RSVM: Reduced support vector machines.
SSVM: A smooth support vector machine.
Nonlinear Programming.
Generalized support vector machines.
Nonlinear perturbation of linear programs.
Successive overrelaxation for support vector machines.
Active support vector machine classification.
Lagrangian support vector machines.
Lipschitz continuity of solutions of linear inequalities
The MathWorks
Machine Learning.
UCI repository of machine learning databases
NDC: normally distributed clustered datasets
Automated star/galaxy discrimination with neural networks.
Sequential minimal optimization: A fast algorithm for training support vector machines.
Advances in Large Margin Classifiers.
Least squares support vector machine classifiers.
Solutions of Ill-Posed Problems
The Nature of Statistical Learning Theory.
The Nature of Statistical Learning Theory.
Twin spiral dataset.
--TR
Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems
The nature of statistical learning theory
Matrix computations (3rd ed.)
Making large-scale support vector machine learning practical
Fast training of support vector machines using sequential minimal optimization
Least Squares Support Vector Machine Classifiers
Data selection for support vector machine classifiers
Machine Learning
Learning from Data
A Tutorial on Support Vector Machines for Pattern Recognition
Lagrangian support vector machines

--CTR
Wenye Li , Kin-Hong Lee , Kwong-Sak Leung, Large-scale RLSC learning without agony, Proceedings of the 24th international conference on Machine learning, p.529-536, June 20-24, 2007, Corvalis, Oregon
Soumen Chakrabarti , Shourya Roy , Mahesh V. Soundalgekar, Fast and accurate text classification via multiple linear discriminant projections, Proceedings of the 28th international conference on Very Large Data Bases, p.658-669, August 20-23, 2002, Hong Kong, China
Tsong Song Hwang , Tsung-Ju Lee , Yuh-Jye Lee, A three-tier IDS via data mining approach, Proceedings of the 3rd annual ACM workshop on Mining network data, June 12-12, 2007, San Diego, California, USA
Simon I. Hill , Arnaud Doucet, Adapting two-class support vector classification methods to many class problems, Proceedings of the 22nd international conference on Machine learning, p.313-320, August 07-11, 2005, Bonn, Germany
Thorsten Joachims, Training linear SVMs in linear time, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Glenn Fung , Sathyakama Sandilya , R. Bharat Rao, Rule extraction from linear support vector machines, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Hwanjo Yu , Jiong Yang , Jiawei Han , Xiaolei Li, Making SVMs Scalable to Large Data Sets using Hierarchical Cluster Indexing, Data Mining and Knowledge Discovery, v.11 n.3, p.295-321, November  2005
Kristin P. Bennett , Michinari Momma , Mark J. Embrechts, MARK: a boosting algorithm for heterogeneous kernel models, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Hwanjo Yu , Jiong Yang , Jiawei Han, Classifying large data sets using SVMs with hierarchical clusters, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Tonatiuh Pea Centeno , Neil D. Lawrence, Optimising Kernel Parameters and Regularisation Coefficients for Non-linear Discriminant Analysis, The Journal of Machine Learning Research, 7, p.455-491, 12/1/2006
Yang , Ali R. Hurson, Content-aware search of multimedia data in ad hoc networks, Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 10-13, 2005, Montral, Quebec, Canada
Bin Li , Mingmin Chi , Jianping Fan , Xiangyang Xue, Support cluster machine, Proceedings of the 24th international conference on Machine learning, p.505-512, June 20-24, 2007, Corvalis, Oregon
Dacheng Tao , Xuelong Li , Xindong Wu , Weiming Hu , Stephen J. Maybank, Supervised tensor learning, Knowledge and Information Systems, v.13 n.1, p.1-42, September 2007
Hwanjo Yu , Xiaoqian Jiang , Jaideep Vaidya, Privacy-preserving SVM using nonlinear kernels on horizontally partitioned data, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
Brian Whitman , Deb Roy , Barry Vercoe, Learning word meanings and descriptive parameter spaces from music, Proceedings of the HLT-NAACL workshop on Learning word meaning from non-linguistic data, p.92-99, May 31,
Soumen Chakrabarti , Shourya Roy , Mahesh V. Soundalgekar, Fast and accurate text classification via multiple linear discriminant projections, The VLDB Journal  The International Journal on Very Large Data Bases, v.12 n.2, p.170-185, August
Glenn Fung , Murat Dundar , Jinbo Bi , Bharat Rao, A fast iterative algorithm for fisher discriminant using heterogeneous kernels, Proceedings of the twenty-first international conference on Machine learning, p.40, July 04-08, 2004, Banff, Alberta, Canada
Glenn M. Fung , O. L. Mangasarian, Multicategory Proximal Support Vector Machine Classifiers, Machine Learning, v.59 n.1-2, p.77-97, May       2005
Deepak K. Agarwal, Shrinkage estimator generalizations of Proximal Support Vector Machines, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Glenn M. Fung , Olvi L. Mangasarian , Alexander J. Smola, Minimal kernel classifiers, The Journal of Machine Learning Research, 3, p.303-321, 3/1/2003
W. A. Chaovalitwongse , P. M. Pardalos, On the time series support vector machine using dynamic time warping kernel for brain activity classification, Cybernetics and Systems Analysis, v.44 n.1, p.125-138, January   2008
Yuh-Jye Lee , Wen-Feng Hsieh , Chien-Ming Huang, epsilon-SSVR: A Smooth Support Vector Machine for epsilon-Insensitive Regression, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.678-685, May 2005

Ryan Rifkin , Aldebaro Klautau, In Defense of One-Vs-All Classification, The Journal of Machine Learning Research, 5, p.101-141, 12/1/2004
Rolando Grave de Peralta Menendez , Quentin Noirhomme , Febo Cincotti , Donatella Mattia , Fabio Aloise , Sara Gonzlez Andino, Modern electrophysiological methods for brain-computer interfaces, Computational Intelligence and Neuroscience, v.2007 n.2, p.1-11, April 2007
Rolando Grave de Peralta Menendez , Quentin Noirhomme , Febo Cincotti , Donatella Mattia , Fabio Aloise , Sara Gonzlez Andino, Modern electrophysiological methods for brain-computer interfaces, Computational Intelligence and Neuroscience, v.7 n.3, p.1-8, August 2007
support vector machines;data classification;linear equations