情報論的学習理論テクニカルレポート 2009
Technical Report on Information-Based Induction Sciences 2009 (IBIS2009)

楕円型サポートベクターマシン
Ellipsoidal Support Vector Machines
門馬道也∗
Michinari Momma
Abstract: This paper proposes the ellipsoidal SVM (e-SVM) that uses an ellipsoid center,in the version space, to approximate the Bayes point. Since SVM approximates it bya sphere center, e-SVM provides an extension to SVM for better approximation of theBayes point. Although the idea has been mentioned before [11], no work has been done
for formulating and kernelizing the method. Starting from the maximum volume ellipsoid
problem, we successfully formulate and kernelize it by employing relaxations. The resulting
e-SVM optimization framework has much similarity to SVM; it is naturally extendable toother loss functions and other problems. A variant of the sequential minimal optimization
is provided for efficient implementation. The empirical results are shown to be consistent
with the Bayes point machines, in terms of classification performance, and difference fromother related methods is highlighted by using high dimensional datasets.
Keywords: Bayes point machines, Support vector machines

1

Introduction
The most common interpretation of the support vec-

tor machines (SVMs) [19, 12] is that it separates positive and negative examples by maximizing the margin
that is the distance between supporting hyperplanesof both examples. Another interpretation comes froma concept called the version space. The version space
is a space of consistent hypotheses, or models with noerror. SVM maximizes the inscribing hypersphere tofind the center that is the SVM weight vector w. Given
the version space, the “sphere center” completely characterizes the SVM model. The Bayes point is a point
through which all hyperplanes bisect the version spaceby half, and is shown to have better generalization ability theoretically and empirically[6, 11].
Attempts to approximately find the Bayes point havebeen done since the early studies of the version space
and the Bayes point. SVM can be considered as an
example. The Bayes point machines (BPM) [6] uses
a kernel billiard algorithm to find the center of mass
∗ NEC 共通基盤ソフトウェア研究所, 211-8653 川崎市中原区下沼部 1753, tel. 044-431-7656, e-mail m-momma@cd.jp.nec.com,
NEC Common Platform Software Research Laboratories, 1753
Shimonumabe, Nakahara-Ku, Kawasaki, Kanagawa 211-8666

in the version space. The analytic center machines(ACM) [18] approximate the Bayes point by analytic
points of linear constraints.
The idea of using an ellipsoid rather than a sphere
has been mentioned in [11], although it was neither formulated nor implemented because of its projected highcomputational cost O(n3.5 ). Then a billiard algorithm
including BPM has been developed to alleviate thecomputational challenge. However, as we have seen in
the history of SVM, seemingly expensive problem canbe made efficient by exploiting special structures in the
problem. Sequential minimal optimization (SMO) or
decomposition methods are notable examples of suchalgorithms[9, 3]. Furthermore, recent development oflarge scale linear SVMs [13, 8] impressively improves
the scalability of the quadratic optimization into practially linear order. Learning from the experience, weare encouraged to develop and study the method of ellipsoidal approximation to BPM, which we refer to as
the ellipsoidal SVM (e-SVM).
e-SVM is formulated just like SVMs. Advantages informulating in such a way include possible adaptationof theoretical characterization, optimization methods
developed for SVM. Furthermore, extensions to chang-ing loss function or application to other kind of problems should be possible. These advantages would not

optimization (SMO). The modified SMO algorithm indeed shares many convenient features with that forbe obtained if we stick to BPM that has to rely on
sampling techniques that scale poorly on a large scale

SVM, such as the closed-form solution for the minimal problem, Karush-Kuhn-Tucker (KKT) condition

dataset; In BPM, even the soft boundary formulation

violation check, etc. Although there should exist fasteris nontrivial and the kernel regularization is used afterall.

algorithm to solve depending on the type of problems,
we decide to start from the simpler SMO algorithm

The e-SVM formulation is based on the maximum
volume inscribed ellipsoid (MVIE) problem. The origi-

and study how e-SVM compares against BPM, SVM
and other related methods.

nal MVIE problem consists of second order cone (SOC)
constraints and a semidefinite constraint. Although

Section 2 formulates the e-SVM optimization problem. Section 3 describes the SMO algorithm adapted

the problem is convex and an interior point type method
can be applied for polynomial time convergence, thefor the e-SVM problem. Section 4 compares related
methods by a simple example. Section 5 gives experi-“natural” kernelization, i.e, the inner-product based
mapping, is left as a challenge. For example, the sec-

mental results. Section 6 concludes the paper.
Notation: Throughout the paper, we assume that

ond order cone program in [16] resorts to the direct
kernel method where the original data matrix is re-m data points xi in n-dimensional space and the corresponding (target) label yi ∈ {−1, 1} are given. The

placed by the kernel matrix. e-SVM uses relaxation of
SOC constraints to make the dual kernelizable. Thisbold small letters represent vectors and the capital letters represent matrices. The vector/matrix transposetechnique has not been used before to the best of ouris T . The kernel matrix is given by K with Kij as its

knowledge.
As with the MVIE problem, e-SVM has the log-

element. trA denotes the trace of a matrix A. “s.t.”
in optimization problems means “subject to”. I is andeterminant term in the objective. Similar problems
can be seen in [14, 5, 4, 16]. e-SVM problem may be in-index set of m data points: I ∈ {1, . . . , m}. kAk2 denotes the matrix 2-norm and kxk2 the L2-norm of aterpreted as a combination of the regular SVM and theminimum volume covering ellipsoid (MVCE) problem.

vector x.

Thus, when optimized separately, e-SVM becomes very
similar to ellipsoidal kernel machine (EKM) [14]. If ap-

2

Ellipsoidal support vector machine formulations

plied to one class problem, e-SVM would become similar to [5]. In other words, e-SVM can subsume other re-In this section, the e-SVM optimization problem islated methods and possesses bigger optimization problem. By changing the loss function to a strict convex

formulated starting from that of SVM in the version
space, since it is a simpler counterpart of e-SVM.

Bregman function, the Bregman’s method would beapplicable to solving e-SVM [4].

The version space is a space of error zero models. For
linear models, it is the error-zero subspace of weight

One direct interpretation of e-SVM is that it learns

vectors w. The data points are considered as hyperplanes and the classification constraints are the feasible

the Mahalanobis metric in margin. That is, e-SVM
maximizes margin by adjusting the metric. In terms ofadjusting margin, the relative margin machines (RMM)[15] address impact of data scaling on the performancein SVM. Since SVMs do not take into considerationof spread of data, a bad scaling can hurt the perfor-

region that is a polyhedron. The problem of finding amaximum hypersphere inside the polyhedron can beformulated as follows:
max ρ

ρ,w,b

s.t.


yi xTi w + b≥ ρ,
kxi k2kwk2 ≤ 1, i ∈ Imance. Although e-SVM has more degree of freedom
to adjust the margin, these two methods learn quite

which corresponds to maximization of the minimum
distance between the center and the hyperplanes, indifferent models as we will see in Section 4.
As the first step to solving the challenging e-SVM

the absence of the bias b. By allowing errors in theabove problem, we can get a soft-margin version of the

problem efficiently, we adopt the sequential minimal

allowing us to remove λ:above problem.
mX
ζimin −mρ + 1/νρ,w,b,ζ
i=1

s.t. yi xTi w + b + t2i ζi ≥ t2i ρ, kwk2 ≤ 1, i ∈ I (1)where ti is defined to be kxi k2 and ν > 0 is a given
constant. Note in the special case with ti = 1, Problem

minE,ζ ,w,bs.t.

−r log |E| + (1 − r)trE +

1X
ζi
ν


yi xTi w + b + t2i ζi ≥ kExi k2

kwk2 ≤ 1, ζi ≥ 0, i ∈ I, E  0.

(5)

1 becomes identical to the ν-SVM formulation.

This MVIE problem can be solved by using existing
techniques, including interior point methods or cut-

To better approximate the “center of models”, an
ellipsoid, instead of a hypersphere, will be used to in-ting plane based approaches. Here we relax the SOC
constraint in Problem 5 in order to ease the high com-

scribe the polyhedron. The MVIE problem is a wellknown log-determinant optimization problem, see e.g.

putational complexity. This change, as we shall see,plays a significant role in making the kernelized for-[2]. A representation of an ellipsoid centered at w is
given by E = {Eu + w | kuk2 ≤ 1, E  0}. Thus themulation possible. As the first step, assume the ma-

constraints for SVM (1) are modified as follows:
yi xTi (Eu + w) + b + t2i ζi ≥ t2i ρ, ∀u, kuk2 ≤ 1 (2)Since Equation 2 holds for any u, it suffices to use thelower bound of lhs in order to remove u:
yi xTi (Eu + w) + b + t2i ζi≥ yi xTi w + b − kExi k2 + t2i ζi ≥ t2i ρ(3)inscribing a polyhedron, the volume of the ellipsoid
should be maximized, which corresponds to maximizing the determinant of E (|E|), as the volume of anellipsoid is proportional to the determinant. In an optimization problem, log det is easier to handle and thus
adopted here as well. The resulting optimization problem is given as follows:
1X
ζi
ν

min
E,ρ,ζ ,w,b−λ (r log |E| + (1 − r)trE) − mρ +s.t.

yi xTi w + b − kExi k2 ≥ t2i ρ − t2i ζi
kwk2 ≤ 1, ζi ≥ 0, i ∈ I, E  0,

(4)

where λ > 0 is a trade-off parameter and r is a constantwhose value takes 0 < r ≤ 1. The additional term trE
is introduced to gain numerical stability as suggested
in [5].
Note the role of ρ and |E| as maximizing margin
is similar and redundant; the determinant maximization term can subsume the linear maximization of ρ1

. Hence, ρ is dropped from the problem hereafter,
1 Our preliminary study confirmed

most cases

the Taylor expansion, the SOC constraint is written
as kExi k2 = κi + κ1i xTi E 0 Bxi + O(kBk22 ) where κi isgiven by κi = kE 0 xi k2 . Using the convexity of SOC,
we get the following inequality.
kExi k2 ≥ κi + (1/κi )xTi E 0 Bxi .

yi Exi= arg minu, kuk=1 (yi xTi Eu) is used.
where − kEx
i k2
Furthermore, in order to obtain the largest ellipsoidtrix E is written as E = E 0 + B, where E 0 is thecurrent solution and B is a deviation from it. By

that ρ becomes zero in(6)

Now the SOC constraints are replaced by linear constraints that are much easier to handle. In the special
case with E 0 = cI, c → +0, the problem becomes
simple and may be used as the initial problem.
X
Ci ξi
min
−r log |B| + (1 − r)trB +B,ξ ,w,bis.t.
yi xTi w + b + ξi ≥ xTi Bxi
kwk2 ≤ 1, ξ ≥ 0, i ∈ I, B  0(7)where we define ξi = κ2i ζi and Ci = t21ν . This fori
mulates the ellipsoidal support vector machines primal
problem. Note the Taylor approximation gets less accurate when kBk2 becomes larger, which is the cost formaking the formulation feasible for kernelization donein Section 2.2.
Problem 7 has some interesting similarity with othermethods. By putting B = Σ−1 , it can be seen as avariant of MVCE problem in which the radius in theoriginal problem is modified to a prediction dependent
constraint. Hence it can be viewed as a supervised version of [14, 5]; unlike EKM, e-SVM solves the classification problem at the same time. Shivaswamy et al.’s
formulation for handling missing and uncertain data
[16] looks similar to Problem 4, where the metric in
margin is given by the uncertainty in the data point.

In e-SVM, margin is given by the B-norm, which is
optimized simultaneously.

2.1

Dual formulationr log B −1 in the objective. By the matrix determinant lemma, the following equality can be shown to
1/2
T
1−r
A1/2
hold; B −1 = I + A XX
(1−r)
r I , where X is

It can be readily shown that Problem 7 is a convex

the data matrix X = [x1 . . . xm ]T and A is a diagonal
matrix whose elements are give by Ai,i = αi . Noteoptimization problem with no duality gap. Hence thecomplementarity can be used to solve the primal andthat the last factor is a constant so it can be ignored.
By employing the kernel defined feature mapping

the dual problems, just like SVMs. The Lagrangian isgiven as follows:

x 7→ φ(x), or XX T 7→ K, we haveL =−r log |B| + (1 − r) trB +
−

X
i

X

1
I + (1−r)
A1/2 XX T A1/2

Ci ξi

i



αi yi xTi w + b − xTi Bxi − ξi+γ kwk22 − 1 − π T ξ − tr(BD),1
A1/2 KA1/2(1 − r)1
A1/2 ZZ T A1/2
= I+
(1 − r)
1= I+
Z T AZ(1 − r)7→ I +

where α, γ, π and D are the Lagrange multipliers
for the classification constraints, norm constraint on

where K is decomposed as K = ZZ T From the 2ndline to the 3rd line the Sylvester’s determinant theo-w, nonnegativity on ξ and positive semidefinitenesson B, respectively. The optimality condition gives therem, a generalization of the Matrix determinant lemma,
is used. Note also the dimensionality of I changes

following relations2 :before and after the theorem is applied. In general,
Z can be any matrix such that K = ZZ T including!
X1T
αi xi xi , D = 0(1 − r)I +
B =
r
i
X
1 X
w=
αi yi xi ,yi αi = 0, Ci − αi − πi = 0.
2γ i
i
−1

Thus using the above equations the dual problem iswritten as follows:
1 X
αi αj yi yj xTi xj − γ
4γ i,j!
XT
αi xi xi
(1 − r)I +

max
α,γ

r log B −1 −s.t.

B −1 =
X

1rtorization may be used. After removing the constantterms, the kernel e-SVM optimization problem is given
by
max

s.t.

i

yi αi = 0, 0 ≤ αi ≤ Ci , γ > 0

r log I +X
1
αi z i z i T(1 − r) i

1 X
yi yj αi αj Kij − γ
4γ i,jXyi αi = 0, 0 ≤ αi ≤ Ci , γ ≥ 0,−

A pleasant surprise is that B −1 is always positive
definite since αi ≥ 0, which is a great advantage,
allowing us to remove the constraint B −1  0 in (8).

Kernel formulation

In this subsection, we show how Problem 8 is kernelized. For notational convenience, we use the matrix

(9)

i

(8)

i

2.2

Z = K 1/2 so that a rank reduction method or sparsification method such as the incomplete Cholesky fac-with z i being the transpose of the i-th row of thematrix Z: Z = [z 1 . . . z m ]T .

3

Sequential minimal optimization

Although Problem 9 can be solved by an optimization package, a customized solver should be developed
to take advantage of its similarity to the familiar SVM

notation as well as the vector notation wherever appropriate. Note Problem 8 is very similar to the SVM

formulation; ideally an SVM solver can be modified tohandle e-SVM. For this purpose, we develop a variant

problems, with the only difference being the additionalof SMO for e-SVM.
The differences from the standard implementation

2 The log |B| term forces B to be full-rank. Thus D = 0 holds
by complementarity.

of SMO include kwk2 being normalized to one, step

size optimization formula, and KKT conditions. The
weight normalization concerns optimization with re-portant piece in SMO algorithm is to find the optimal
step size. The incremental step for αi can be expressed

spect to γ and can be done via the iterative projection.
Step size optimization and active set selection using theasαnew = αold + s (ei − yi yj ej ) ,(13)
P= 0 given αold
which satisfies the constraint i yi αnewi

KKT condition are done very similar to those for SVM.
This section focuses on describing essential differences
as a guide to implementation.

3.1

is a feasible solution. ei is a vector of zeros except for
the i-th element being unity. Consider the following
objective function, U (s), after removing any constantterms with respect to s:

Optimality conditions

SMO chooses an active set, a pair of data points,e −1 −
U (s) = r log det B

to optimize at any iteration. The selection of a paircritically affects the convergence speed. We adopt the
selection heuristic described in [9]: choose ones that
violate the KKT condition most. This subsection de-e −1BFirst, consider the dual of (9). The Lagrangian isgiven by

=
=
=

1X
1−r
αi z i z i TI+−r log
r
r i
X
1 X
yi αi
yi yj αi αj Kij + γ − η
+
4γ ij
i
X
X
δi αi +µi (αi − Ci ) .
−

αnew
αnew
yi yj Kij − γ. (14)ije old −1 + s z i z i T − yi yj z j z j T
B
" r
#
zi T
s
e old −1e old [z i yj z j ] BI+BTr −yi z j
1 + rs ωii− rs yi ωijsr yj ωij
1 − rs yi yj ωjj× conste
where ωij is defined to be ωij = z i T B

old

(15)

z i and thematrix determinant lemma is used for deriving the 2ndline. The resulting matrix is merely a 2 × 2 matrix
determinant and easily expandable.

i

Likewise, we can rewrite the second term in (14) as
follows:

Solving the optimality conditions, we havee i=0
(Fi − γ) yi − δi + µi − z i T BzsXγ=
yi yj αi αj Kij /2.

4γi,jThe first term is modified using the update formula:

rives the KKT condition and thus gives the criterion
for choosing the active set.

L =

X 1

(10)

X

(11)


P
1
e = 1−r I + P αi z i z i T −1 .
with Fi = 2γ
Kij yj αj and BirHence, by the complementarity, we have the following• For αi = 0, δi > 0, µi = 0 ⇒ (Hi − β) yi ≥ 0• For 0 < αi < Ci , δi , µi = 0, ⇒ (Hi − β) yi = 0• For αi = Ci , δi = 0, µi > 0 ⇒ (Hi − β) yi ≤ 0
e i . Note the first term Fi corwith Hi = Fi − yi z i T Bz

=

X

old
αold
i αj yi yj Kij

i,j

i,j

ij

KKT conditions:

αnew
αnew
yi yj Kijij

−4βsyi (Fi − Fj )−s2 (Kii − 2Kij + Kjj ) .

Hence by putting all the pieces together, we have thefollowing optimality condition on s.


−1
X
e
∂U (s)∂ log det B∂  1
αi αj yi yj Kij  = 0
= r
−
∂s
∂s
∂s 4γ ij
⇒ ra1 − a3 + (2ra2 − a1 a3 − a4 )s

responds to that in [9] and the second term is newly
introduced for the e-SVM problem. This means that−(a2 a3 + a1 a4 )s2 − a2 a4 s3 = 0

replacing Fi by Hi suffices to establish a version of the2with a1 = r(ωii −yi yj ωjj ), a2 = yi yj (ωij−ωii ωjj ), a3 =SMO algorithm for e-SVM and can be easily integrated
into an existing SVM solver.

ii
ij. This is merely a cubicyi (Gi − Gj ), a4 = ii 2γ
equation and can be solved analytically.

3.2

3.3

Step size computation

As explained, the KKT condition for e-SVM is easily
adopted to the existing SMO algorithm. Another im-

K +K −2KeComputing B

e is needed to calculate
At each iteration, access to B
ω’s. Specifically, the diagonal elements ωii are required

for the KKT violaiton check and ωij as well as ωii andωjj for the step size computation concerning an updateof αi and αj . Since we solve the dual α, as well as γe −1 is easily obtained, but getting B,
e in ain SMO, B

naive way, would require an inverse matrix operationthat is never done in practice.
e is to employ the
A way to efficiently compute B

rank-one update of matrix inversion and factorize thee = B 0 + P σi v i v T .
matrix in the following way: Biie
By using the Woodbury formula, B is updated at eache new =
SMO step involving update of αi and αj : B
e old + σi v i v T + σj v j v T , where v i = B
e old z i , ωii =
B
i
j

 old
s
T
e
B
+
σ
v
v
z j , σj =.
v=
z i T v i , σi = − r+sω
i
i
j
i
ii
syi yje. Note this decomposition formula on BTr−syi yj z j v jenables us to do an incremental update of ω:

new
old
ωkl
= ωkl
+ σi z i T z k z i T z l + σj z j T z k z j T z loldewhere ωkl
= zk T B

oldz l . This update formula is par-ticularly useful when exploiting efficiency; it is evident
e close to full-rank or dense isthat computing ωkl with B

overkill as SMO requires many updates. ωij ’s that arecached will be updated via the vector-vector multipli-

cations. For ωij ’s that are not in the cache may require
e is computed
the full matrix-vector multiplication, if B

and kept in memory. Otherwise, the conjugate gradient would need to be employed to calculate ωij frome −1 , see [7], for example. A recommendation is thatB
the diagonal elememts ωii are kept in memory as allof them are used in any case for the KKT condition
violation check.

4

Related methods

Recently, several methods are proposed for improving generalization ability of SVMs. Ellipsoidal kernel
machines (EKM) are ellipsoidal gap-tolerant classifiers
that have lower bound of the VC dimension than thatof SVMs. The EKM algorithm first finds the minimum
volume ellipsoid enclosing data points. Then the normal SVM is applied to the transformed space wheredata points are placed in a hypersphere.

as to reduce the effect of influence from badly scaledfeatures.

5

Experimental study

5.1

Comparison against BPM

It is important to examine the quality of e-SVM solutions to understand how the approximation and relaxation used in e-SVM affect the performance. In thispaper, we directly compare the classification performance using the standard real dataset as a delegate toan assessment from an optimization perspective, whichis left for a longer version of the paper. Also, BPM ande-SVM are compared against SVM to understand how
much performance lift can be realized.
In this regard, a wide range of datasets in the UCI
machine learning repository [1] are used. Both SVM
and e-SVM are implemented in pure MATLAB, using
the SMO. Note ν-SVM formulation is adopted in thisstudy, since e-SVM is based on ν-SVM. BPM’s implementation follow [6] and is implemented in C with an
R interface. For the experimental setting, 100 randomizations are done and the average error rates in percent
is reported in Table 1 and 2. In order to evaluate significance of statistics, the paired t-tests are conducted
for comparing BPM with SVM, and e-SVM with SVM.
SVM. Bold numbers denote the test results being significant.
Both hard and soft margin/boundary cases are examined. The training and testing splits are identicalto [10] except for sonar, iono, wisconsin-breastcancer(WISC-BC). The splits for sonar are set identical to[6] and those for iono are created randomly in advanceand identical splits are applied for all methods. For eSVM and SVM, the tolerance of KKT violation is set
to 10−3 . For BPM the tolerance parameter for convergence check is set to 10−3 . Model parameters are
selected following [10]: using five-fold cross validationon the first five set and take the median of the bestparameters. The best model parameters are fixed to
conduct the 100 repetitions. Parameters including C

Relative margin machines (RMM) addresses the issue of scale invariance in SVMs. Being motivated byand r for e-SVM, ν for SVM and λ in BPM are selectedby the cross validation, in which 10-20 parameter val-a simple example where enlarging one feature dimension can drastically change the solution of an SVM,

ues are used to cover a wide range of the search space.
For hard margin e-SVM, r is set to 1 − 10−6 . The ra-

RMM regularizes the amplitude of prediction value, or
projection of data point onto the weight vector w sodial basis function kernel is used for this experiment.

Table 1: Error rates for hard boundary/margin classifiers
Data set
thyroidheart
diabeteswave
bananawisc-bc
bupa
german
brest
sonar
iono

SVM
4.96 (.24)
25.86 (.40)
33.87 (.21)
13.19 (.12)
16.24 (.14)
4.22 (.13)
37.04 (.39)
30.07 (.22)
35.17 (.51)
14.90 (.38)
7.94 (.25)

BPM
4.24 (.22)
22.58 (.33)
31.06 (.22)
12.02 (.08)
13.70 (.10)
2.56 (.10)
34.5 (.38)
27.16 (.24)
33.04 (.48)
16.26 (.36)
11.45 (.25)

e-SVM
4.42 (.25)
20.87 (.32)
29.68 (.24)
11.59 (.07)
12.76 (.08)
3.28 (.12)
32.71 (.35)
26.34 (.27)
31.96 (.51)
16.87 (.38)
5.92 (.21)

Table 2: Error rates for soft boundary/margin classifiers
Data set
thyroidheart
diabeteswave
bananawisc-bc
bupa
germanbreast
sonar
iono

SVM
5.05 (.22)
15.58 (.30)
23.36 (.17)
9.88 (.04)
10.90 (.07)
2.70 (.10)
28.80 (.30)
23.61 (.20)
29.01 (.43)
14.93 (.38)
5.94 (.18)

BPM
4.32 (.20)
16.19 (.29)
23.12 (.18)
11.82 (.05)
10.40 (.04)
2.32 (.10)
28.37 (.30)
23.27 (.22)
26.21 (.46)
16.49 (.36)
10.16 (.23)

e-SVM
4.44 (.22)
16.17 (.32)
23.79 (.19)
10.03 (.04)
10.59 (.05)
2.77 (.09)
28.38 (.32)
23.21 (.22)
26.08 (.48)
16.12 (.36)
5.16 (.18)

The kernel width parameters are set to identical to10000

those reported in [6], except for iono, for the rest ofsimilar. This suggests that the approximations madeto formulate e-SVM do not affect the classification performance for the datasets examined. In comparison
with SVM, the hard boundary/margin classifiers significantly outperform those of SVM. For soft boundary/margin cases, however, the advantage is reduced.
Although performance of BPM and e-SVM is slightly
better than that of SVM, the difference is small, which
is a consistent observation with [6].
Scalability
The computational cost is illustrated to see how eSVM scales in comparison with BPM, using the adultdataset [1]. The entire dataset is split into training,
testing and validation. Model selection is done using
the validation set of size 1000 and fixed for the restof the experiments. The size of the training set is increased from 100 up to 4000. Test performance is observed to check if the there is no significant difference
between the methods. Obviously, e-SVM runs much
faster than BPM as the data size grows. Using the
log-log fit, e-SVM scales as m2.1 whereas BPM takes
as much as m2.7 . Note SVM takes only 30 secs for the
problem of size 4,000 (not shown); although e-SVM significantly beats BPM, there is much room to improvethe efficiency when compared with SVM.

5.2

High dimensional datasets

The datasets used in Subsection 5.1 are in relatively
low dimensions. With the ability to adjust the margin
metric, it is more interesting to see the performance

BPM
ESVM(SMO)
8000

time (sec)the datasets, those reported for SVMs in [10] are used.
The overall performance for BPM and e-SVM is very

6000

4000

2000

0
0

500

1000

1500

2000
size

2500

3000

3500

4000

Figure 1: Scalability for BPM and e-SVM
with a high dimensional dataset. We compare the eSVM with other methods mentioned in Section 4. The
20-newsgroup (20N G) and mnist [1] are used for thispurpose. EKM is implemented in MATLAB Optimization Toolbox. RMM is implemented in SDPT3 [17].
For 20N G, the number of words is limited to the top
5,000 frequent words and each data point is normalized to length one after the tf-idf weighting. There
are 11,250 data points in the training and 7,486 in thetesting set. mnist contains 60,000 observations in the
training and 10,000 in the testing set in 784 dimensions.
The one-versus-one strategy is applied to solving themulticlass problem. We set the number of training
data points to 50, 100 and 200 for each pair of classes
in training (100, 200 & 400 in training samples for bothclasses). The rest of the training data is reserved as
the validation set that is used for model selection. The
linear kernel is used for all the methods. The results
are shown in Table 3. For 20N G, e-SVM outperforms
other methods. Interestingly, both EKM and RMM
show slightly worse performance than SVM. This indicates the transformation in EKM and regularization
for scaling resistance in RMM seem to have adversary
effect. In turn, for mnist, RMM outperforms otherTable 3: Error rates for SVM, EKM, RMM and e-SVM
ng100
ng200
ng400
mnist100mnist200
mnist400

SVM
35.0
30.2
27.0
10.8
9.31
8.11

EKM
36.4
32.8
31.5
13.0
10.9
9.44

RMM
37.7
31.2
27.8
10.5
8.92
8.10

e-SVM
34.0
29.1
26.4
10.7
9.40
8.28

international conference on Machine learning, pages
209–216, New York, NY, USA, 2007. ACM.
[5] A.N. Dolia, T. De Bie, C.J. Harris, J. Shawe-Taylor,and D.M. Titterington. The minimum volume covering ellipsoid estimation in kernel-defined feature
spaces. In Proceedings of the 17th European Conference on Machine Learning (ECML 2006), Berlin,
September 2006. 2006.

invariance is desired.

[6] Ralf Herbrich, Thore Graepel, and Colin Campbell.
Bayes point machines. Journal of Machine Learning
Research, 1:245–279, 2001.

6[7] Steven C. H. Hoi, Rong Jin, and Michael R. Lyu.
Learning nonparametric kernel matrices from pairwise
constraints. In ICML, pages 361–368, 2007.

methods, which confirms RMM works well when scale

Conclusion

In this paper, the ellipsoidal support vector machine
was proposed. The formulation is based on that of thefamiliar SVM and the sequential minimal optimization
was successfully adapted to solve the e-SVM optimization problem. The framework is flexible for possible
modification of loss functions or application to otherproblems. Also, by the minimum volume ellipsoid interpretation, it can be used to learn the metric guided
through the maximum margin framework. None ofthese advantages is available in BPM and thus novel in
e-SVM. Furthermore, e-SVM showed comparable performance with BPM, indicating the approximations in
e-SVM do not affect the performance over wide variety
of datasets.
The SMO algorithm was shown to provide acceptable scalability and was much more efficient than BPM.
e-SVM thus can be applicable to real world applications up to several thousands of data points. Future
work includes developing a more efficient algorithm
that handles caching better and an algorithm for outof-memory computation.

References[1] C. L. Blake and C. J. Merz.
UCI
Repositoryofmachinelearning
databases,
1998.
http://www.ics.uci.edu/∼mlearn/
MLRepository.html.
[2] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, New York,NY, USA, 2004.
[3] Pai-Hsuen Chen, Chih-Jen Lin, and Bernhard
Schölkopf. A tutorial on ν-support vector machines:
Research articles. Appl. Stoch. Model. Bus. Ind.,21(2):111–136, 2005.
[4] Jason V. Davis, Brian Kulis, Prateek Jain, Suvrit Sra,and Inderjit S. Dhillon. Information-theoretic metric learning. In ICML ’07: Proceedings of the 24th[8] C. Hsieh, K. Chang, C. Lin, S. Keerthi, and S. Sundararajan. A dual coordinate descent method forlarge-scale linear SVM. pages 408–415, 2008.
[9] S. S. Keerthi, S. K. Shevade, C. Bhattacharyya, andK. R. K. Murthy. Improvements to Platt’s SMO algorithm for SVM classifier design. Neural Comput.,
13(3):637–649, 2001.
[10] GunnarRätsch.
Benchmarkrepository,
1998.
http://ida.first.fraunhofer.de/projects/bench/benchmarks.htm.
[11] Pál Ruján. Playing billiards in version space. NeuralComput., 9(1):99–122, 1997.
[12] B. Schölkopf and A. J. Smola. Learning with Kernels:
Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, 2001.
[13] Shai Shalev-Shwartz, Yoram Singer, and Nathan Srebro. Pegasos: Primal Estimated sub-GrAdient SOlverfor SVM. In ICML ’07: Proceedings of the 24th international conference on Machine learning, pages 807–
814, New York, NY, USA, 2007. ACM.
[14] P. Shivaswamy and T. Jebara. Ellipsoidal kernel machines. Artificial Intelligence and Statistics, 2007.
[15] P. Shivaswamy and T. Jebara. Relative margin machines. In Neural Information Processing Systems,
2008.
[16] Pannagadatta K. Shivaswamy, Chiranjib Bhattacharyya, and Alexander J. Smola. Second order cone
programming approaches for handling missing and uncertain data. J. Mach. Learn. Res., 7:1283–1314, 2006.
[17] K. C. Toh, M. J. Todd, and R. Tutuncu. SDPT3 —a Matlab software package for semidefinite programming. Optimization Methods and Software, 11:545–
581, 1999.
[18] Theodore B. Trafalis and Alexander M. Malyscheff.
An analytic center machine. Mach. Learn., 46(13):203–223, 2002.
[19] V. N. Vapnik. The Nature of Statistical Learning Theory. Springer, New York, 1996.