Kernel Matrix Evaluation
Canh Hao Nguyen and Tu Bao Ho
School of Knowledge Science
Japan Advanced Institute of Science and Technology
1-1 Asahidai, Nomi, Ishikawa, 923-1292, Japan{canhhao,bao}@jaist.ac.jp
Abstract

The goodness of kernel function can only be seen from thegoodness of the kernel matrix K; therefore, measuring thegoodness of K is of primary interest in various contexts.

We study the problem of evaluating the goodness ofa kernel matrix for a classiﬁcation task. As kernel
matrix evaluation is usually used in other expensive
procedures like feature and model selections, thegoodness measure must be calculated efﬁciently.
Most previous approaches are not efﬁcient, except
for Kernel Target Alignment (KTA) that can be calculated in O(n2 ) time complexity. Although KTA
is widely used, we show that it has some serious
drawbacks. We propose an efﬁcient surrogate measure to evaluate the goodness of a kernel matrix
based on the data distributions of classes in the feature space. The measure not only overcomes thelimitations of KTA, but also possesses other properties like invariance, efﬁciency and error boundguarantee. Comparative experiments show that themeasure is a good indication of the goodness of akernel matrix.

There are many ways to measure the goodness of a kernel matrix (kernel function) for a classiﬁcation task, differently reﬂecting the expected quality of the kernel function.
Commonly used measures are regularized risk [Schölkopf
and Smola, 2002], negative log-posterior [Fine and Scheinberg, 2002] and hyperkernels [Ong et al., 2005]. These measures do not give a speciﬁc value, but only assert certain criteria in form of regularities in certain spaces, for example,
RKHS or hyper-RKHS. All of these kernel measures require
an optimization procedure for evaluation. Therefore, they
are prohibitively expensive to be incorporated into other expensive procedures like model and feature selections. Other
techniques like cross validation, leave-one-out estimators or
radius-margin bound can also be considered as expected quality functionals. Like the previously mentioned works, theyrequire the whole learning process.

1 Introduction
Kernel methods, such as Support Vector Machines, GaussianProcesses, etc., have delivered extremely high performancein a wide variety of supervised and non-supervised learning
tasks [Schölkopf and Smola, 2002]. The key to success is that
kernel methods can be modularized into two modules: theﬁrst is to map data into a (usually higher dimensional) feature
space, which is a powerful framework for many different datatypes; and the second is to use a linear algorithm in the feature space, which is efﬁcient and has theoretical guarantees[Shawe-Taylor and Cristianini, 2004]. While many linear algorithms can be kernelized, the major effort in kernel methods is put into designing good mappings deﬁned by kernel
functions φ:
φ : X → H.
(1)
X is the original data space and H is the feature space, which
is a Reproducing Kernel Hilbert Space (RKHS). While H
may be a many-dimensional space, the algorithm takes advantage of the kernel trick to operate solely on the kernel matrix induced from data:
K = {φ(xi ), φ(xj )}i=1..n,j=1..n .

(2)

To be used in feature and model selection processes, goodness measures of kernel matrices must be efﬁciently calculated. To the best of our knowledge, the only efﬁcient kernel
goodness measure is Kernel Target Alignment [Cristianini etal., 2002]. Due to its simplicity and efﬁciency, KTA has beenused in many methods for feature and model selections. Somenotable methods are learning conic combinations of kernels[Lanckriet et al., 2004], learning idealized kernels [Kwok andTsang, 2003], feature selection [Neumann et al., 2005] andkernel design using boosting [Crammer et al., 2002].
In this work, we ﬁrst analyze KTA to show that having
a high KTA is only a sufﬁcient condition to be a good kernel matrix, but not a necessary condition. It is possible for akernel matrix to have a very good performance even though
its KTA is still low. We then propose an efﬁcient surrogate
measure based on the data distributions in the feature space
to relax the strict conditions imposed by KTA. The measure
is invariant to linear operators in the feature space and retains several properties of KTA, such as efﬁciency and an error bound guarantee. The measure is closely related to someother works on worst-case error bounds and distance metriclearning. We show experimentally that the new measure ismore closely correlated to the goodness of a kernel matrix,
and conclude ﬁnally with some future works.

IJCAI-07987

2 Kernel Target Alignment
Kernel target alignment is used to measure how well a kernel
matrix aligns to a target (or another kernel) [Cristianini et al.,2002]. Alignment to the target is deﬁned as the (normalized)
Frobenius inner product between the kernel matrix and thecovariance matrix of the target vector. It is interpreted as cosine distance between these two bi-dimensional vectors. We
ﬁrst introduce some notations.
Training example set {xi }i=1..n ⊂ X with the corresponding target vector y = {yi }Ti=1..n ⊂ {−1, 1}n. Suppose thaty1 = .. = yn+ = 1 and yn+ +1 = .. = yn+ +n− = −1; n+examples belong to class 1, n− examples belong to class −1,
n+ + n− = n. Under a feature map φ, the kernel matrix is
deﬁned as:
K = {kij = φ(xi ), φ(xj )}i=1..n,j=1..n .

(3)

Frobenius inner product is deﬁned as:
K, K ∗ F =

n
n 


∗
kij kij.

(4)

i=1 j=1

The target matrix is deﬁned to be y.y T . Kernel target alignment of K is deﬁned as the normalized Frobenius inner product:
K, y.y T F.
(5)
A(K, y) = 
K, KF y.y T , y.y T F
The advantage, which makes KTA popular in many featureand model selection methods, is that it satisﬁes several properties. It is efﬁcient as its computational time is O(n2 ). It ishighly concentrated around its expected value, giving a highprobability that a value is close to the true alignment value.
It also gives some error bounds, meaning that when KTA ishigh, one can expect that the error rate using the kernel mustbe limited to a certain amount.
We claim that having a very high value A(K,y) is only a
sufﬁcient condition, but not a necessary condition, for K to bea good kernel matrix for a given task speciﬁed by the targety. As 0  A(K, y)  11 , when A(K, y) = 1, the two bidimensional vectors K and y.y T are linear. Up to a constant,the optimal alignment happens when kij = yi .yj . This isequivalent to two conditions:
1. All examples of the same class are mapped into the same
vector in the feature space (kij = 1 for xi , xj in the sameclass).
2. The mapped vectors of different classes in the feature
space are additive inverse (kij = −1 for xi , xj in different classes).
It is a sufﬁcient condition that having a high K, one can
expect good performance, as classes are collapsed into a pointin the feature space. Violating any of the conditions would
mean that KTA is penalized. However, it is not a necessary
condition as we analyze below.
The ﬁrst condition implies that the within-class variancepenalizes KTA. However, there is a gap between the condition and the concept of margin in Support Vector Machines
1
In [Cristianini et al., 2002], it is −1  A(K, y). The inequality
here comes from the fact that K is positive semideﬁnite.

(SVMs). Varying data (in the feature space) along the separating hyperplane will not affect the margin. If data varies along
the perpendicular direction of the separating hyperplane, themargin can be changed. However, KTA does not take into
account variances in different directions.
The second condition is too strict, and not applicable inmany cases, because it requires the mapped vectors of different classes to be additive inverses of each other. Ideally, if
the kernel function maps all examples of a class to one vector
in the feature space, the kernel matrix should be evaluated as
optimal. This is the reason why having high KTA is only a
sufﬁcient condition, but not a necessary condition. We usesome examples to show this limitation quantitatively.
Example 1 (best case): The kernel function φ maps all
examples of class 1 into vector φ+ ∈ H and all examples
of class −1 into vector φ− ∈ H. Assume that φ+ .φ+ =φ− .φ− = 1 and φ+ .φ− = α, −1  α < 1. For any α, thekernel matrix K should be evaluated as optimal, as it is induced from an optimal feature map. However, its KTA valueis:n2 + n2− − 2n+ n− α.
(6)A(K, y) =  +n2+ + n2− + 2n+ n− α2 ∗ n
KTA values of these kernel matrices change as α varies
from 1 to −1, and any value in that range can be the KTA
value of a kernel matrix of an optimal feature function. As
2
2
−)
−)
, KTA ranges from (n+ −nlimα→1 A(K, y) = (n+ −nn2n2
to 1 in this case.
Example 2 (worst case): The kernel function φ maps halfof the examples of each class into vector φ1 ∈ H and theother half into vector φ2 ∈ H. Assume that φ1 .φ1 = φ2 .φ2 =1 and φ1 .φ2 = α, −1  α  1. For any α, the kernel matrix K should be evaluated very low, as it is induced from theworst kernel function, which fuses the two classes together
and has no generalization ability. However, its KTA value is:A(K, y) =(n+ − n− )2 1+α2.
2n2 ∗ ( 1+α
2 )

(7)
2

−)
As shown above, limα→1 A(K, y) = (n+ −n, which is then2same limit as the best case. We
can
see
that
KTA of this2−)case ranges from 0 to (n+ −n
.
There
is
a
similarcautionn2
in [Meila, 2003]. As the best and the worst cases cover thewhole range of KTA values, any other case would coincidewith one of them. Therefore, KTA may mistake any case tobe either the best or the worst.
Example 3 (popular case): Consider the case when a kernel function maps all examples into an orthant in the feature
space, inducing a kernel matrix with non-negative entries, i.e.
kij  0. In this case:n2+ + n2−A(K, y) .
(8)nProof can be derived by using the fact that kij  0 and the
Cauchy-Schwarz inequality [Gradshteyn and Ryzhik, 2000].
Take a special case when n+ = n− , A(K, y)  √12 . Recall that KTA of a kernel matrix ranges from 0 to 1, and the

IJCAI-07988

calculate the within-class variance (of both classes) in the di−φ+as therection between class centers. Denote e = φφ−
− −φ+ unit vector in this direction. The total within-class varianceof two classes in the direction is:var = [
nFigure 1: Data variance in the direction between class centers.
higher the better. This example means that these types of kernel functions will have bounded KTA values, no matter how
good the kernel functions are. This is a drawback of KTA.
Unfortunately, this type of kernel function is extensively usedin practice. Gaussian kernels [Shawe-Taylor and Cristianini,2004], and many other kernels deﬁned over discrete structures[Gartner et al., 2004] or distributions [Jebara et al., 2004], etc.
fall into this category.
The above examples show that KTA can mistake any kernel matrix to be the best or the worst. KTA is always boundto some numbers for many popular kernel matrices with positive entries (e.g., Gaussian, and many kernels for discrete
structures or distributions). KTA will disadvantage the use ofsuch kernels.

3 Feature Space-based Kernel Matrix
Evaluation Measurei=n+1 φ(xi )+. Our evaluation measure FSM is deφ− =n−ﬁned to be the ratio of the total within-class variance in the
direction between the class centers to the distance between
the class centers:

F SM (K, y) :=

3.1

var
.
 φ− − φ+ 

2i=1 φ(xi ) − φ+ , e(9)

FSM Calculation

We show that the evaluation measure can be calculated using
the kernel matrix efﬁciently with simple formulas. We ﬁrst

1

]2

n+ − 1(10)2
φ(xi ) − φ− , e 1
i=n+ +1+[]2 .
n− − 1
We calculate the ﬁrst term in equation (10), the total
within-class variance of the class +1 in the direction between
φ+ and φ− , denoted as var+ .
2=(n+ − 1)var+n+

φ(xi ) − φ+ , e2

i=1

n+

φ(xi ) − φ+ , φ− − φ+ 2= i=1(φ− − φ+ )2n+(φ(xi )φ− + φ2+ − φ(xi )φ+ − φ+ φ− )2= i=1.
(φ− − φ+ )2Pn

Pn+

j=1 φ(xj )(11)+1 φ(xj )j=n+
We substitute φ+ =and φ− =n+n−into equation (11), and then we deﬁne some auxiliary variables as follows. For i = 1..n+ :• ai = φ(xi )φ+ =• bi = φ(xi )φ− =In this section, we introduce a new goodness measure ofa kernel matrix for a given (binary classiﬁcation) task,
named Feature Space-based Kernel Matrix Evaluation Measure (FSM). This measure should be computed on the kernel matrix efﬁciently, and overcome the limitations of KTA.
Our idea is to use the data distributions in the feature space.
Speciﬁcally, two factors are taken into account: (1) thewithin-class variance in the direction between class centers; and (2) relative positions of the class centers. These
factors are depicted in Figure 1. The ﬁrst factor improves
the ﬁrst condition of KTA, by allowing data to vary in certain directions. The second factor solves the problem imposed by the second condition of KTA. Let var be the total
within-class variance (for both classes) in the direction between class centers. Denote center of a class
as+ the meanPnφ(x )of the class data in the feature space: φ+ = i=1n+ i andPnn+

For i = n+ + 1..n:• ci = φ(xi )φ+ =• di = φ(xi )φ− =Denote A =
Pn
n

+1 di

Pn +

Pn+

j=1 φ(xi )φ(xj )Pn

j=1 kij

j=n+ +1 φ(xi )φ(xj )

=

n−
Pn+

j=1 φ(xi )φ(xj )Pn

i=1 ai

n+

n+

Pn+

=

n+

=

,B =

i=1 bin+,j=n+ +1 kij

.

n−

Pn+

j=n+ +1 φ(xi )φ(xj )

n−
Pn +

n+
Pn

j=1 kij

,
n+
Pn

=

,C =

j=n+ +1 kij

Pn

n−

i=n+

+1 ci

n−

.

and

+
. Hence, A = φ+ φ+ , B = C = φ+ φ− andD =n−
D = φ− φ− . Therefore, (φ− − φ+ )2 = A + D − B − C.
Plugging them into equation (11), then:n+(bi − ai + A − B)22(n+ − 1)var+ = i=1.
(12)
A+D−B−C
We can use a similar calculation for the second term in equation (10):n2i=n+ +1 (ci − di + D − C)2
. (13)(n− − 1)var− =A+D−B−C
The proposed kernel matrix evaluation measure FSM, asdeﬁned in formula (9), is calculated as:
var+ + var−.
(14)
F SM (K, y) = √A+D−B−C
F SM (K, y)  0, and the smaller F SM (K, y) is, the better
K is.
One can easily see that ai , bi , ci , di , A, B, C and D canbe all calculated together in O(n2 ) time complexity (one passthrough the kernel matrix). Therefore, the evaluation measureis also efﬁciently calculated in O(n2 ) time complexity.

IJCAI-07989

3.2

Invariance

1

There are some properties of F SM (K, y) regarding linear
operations that make it closer to SVMs than KTA is.
Theorem 1: F SM (K, y) is invariant under translation,
rotation and scale in the feature space.
Sketch of proof: F SM (K, y) is scale invariant owing to
its normalization factor A + D − B − C. F SM (K, y) is
rotation and translation invariant, as it is built on the building
blocks of ai − bi and di − ci .
The performance of SVMs and other kernel methods areunchanged under rotation, translation and scale in the feature
space. Therefore, it is reasonable to ask for measures to havethese properties. However, KTA is neither rotation invariant
nor translation invariant.

3.3

Error BoundWe show that for any kernel matrix, it is possible to obtain a
training error rate, which is bounded by some amount proportionate to F SM (K, y). This means that a low F SM (K, y)value can guarantee a low training error rate. In this case, we
can expect a low generalization error rate.
Theorem 2: There exists a separating hyperplane suchthat its training error is bounded by:
F SM err :=F SM (K, y)2.
1 + F SM (K, y)2(15)

Proof: We use a one-tailed version of Chebyshev’s inequality [Feller, 1971]. Consider the data distribution in the
direction between class centers. For each class, the data distribution has a mean of either φ+ or φ− , and the corresponding variance var+ or var− . The following inequalities canbe derived:1
P r(φ − φ− , −e  k.var− |φ ∈ class(−)) 
1 + k2
1
P r(φ − φ+ , e  k.var+ |φ ∈ class(+)) .
1 + k2(16)
The separating hyperplane, which takes e as its norm vector and intersects the line segment between φ+ and φ− at the|h−φ+ |var+
= var
, has the formula:point h such that |h−φ−|−f (x) = e.x − e.

var− φ+ + var+ φ−= 0.
var+ + var−

(17)

The error rate of this hyperplane for each class is bounded us|φ− −φ+|=ing the inequalities in equation (16) with k = var+ +var−1
F SM(K,y) . Therefore, the total training error rate on bothclasses is also bounded by:
F SM (K, y)2
1=.
1 + k2
1 + F SM (K, y)2

3.4

0.9

1−KTA
FSMerr
error

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
30

60

90

120

150

180

Figure 2: Results on synthetic data with different β values.
scale, and relaxes the strict conditions of KTA by considering
relative positions of classes in the feature space. For the examples in Section 2, FSM values of the best cases are always
0, those of the worst cases are always ∞, and for the popular case, there are no bounds. This measure also has somesimilarities with other works.
The minimax probability machine (MPM) [Lanckriet et al.,2002] controls misclassiﬁcation probability in the worst-casesetting. The worst-case misclassiﬁcation probability is minimized using Semideﬁnite Programming. The worst case isdetermined by making no assumption rather than the mean
and the covariance matrix of each class. MPM is similar to
our approach that our measure also shows the worst-case misclassiﬁcation error. The difference is that MPM considers thedata variance in all directions (by using the covariance matrix), while our measure takes only the variance in the direction between the class centers. That is the reason why our
measure is a lightweight version of MPM and can be calculated efﬁciently. A special case of MPM is when the direction
between class centers contains eigenvectors of both covariance matrices; the objective function that MPM optimizes is
equivalent to our measure.
In the context of nearest neighbor classiﬁcation, one of thecriteria of learning a good distance function is to transform
data such that examples from the same class are collapsed into
one point [Globerson and Roweis, 2006]. Our measure also
shows quantitatively how much a class collapses. However,
the key difference is that in their method, the objective is thewhole class collapses to one point, while our measure shows
how the whole class collapses to a hyperplane. This difference explains why their method is applied to nearest neighborclassiﬁcation, while our measure is for kernel methods.

(18)

4 Experiments

Discussion

The measure can be interpreted as the ratio of within-classvariance to between-class variance. It indicates how well thetwo classes are separated. It is advantageous over KTA because it takes into account the within-class variances at a ﬁner

As the purpose of these measures is to predict efﬁciently how
good a kernel matrix is for a given task using kernel methods,
we compare the measures to the de facto standard of crossvalidation error rates of SVMs. We mimicked the model selection process by choosing different kernels. We monitored

IJCAI-07990

australianbreast−cancer

1diabetes

fourclass

0.7

1

0.6

0.9

0.5

0.8

0.6

0.4

0.7

0.6

0.4

0.3

0.6

0.4

0.2

0.5

0.1

0.4

0.8

0.2
0
Lin.

Poly

RBF

Tanh

0
Lin.

Poly

german

RBF

Tanh

0.3
Lin.

heart

1

1
0.8

0.2

Poly

RBF

Tanh

0
Lin.

ionosphere

RBF

Tanh

vehicle

1

1

1

0.8

0.8

0.8

0.7

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.2

0.2

0.2

0.9

Poly

0.8

1−KTA
FSMerr
error

0.5
0.4
0.3
Lin.

Poly

RBF

Tanh

0
Lin.

Poly

RBF

Tanh

0
Lin.

Poly

RBF

Tanh

0
Lin.

Poly

RBF

Tanh

Figure 3: Results on different UCI data sets.

the error rates (as baselines), KTA and FSM, to see if how
they reﬂect the baselines. We used 10-times 5-fold stratiﬁed
cross validations to estimate the error rates.
To facilitate visual inspection of the results, we instead
showed the following quantities: (a) 1−KT A, (b) F SM err,deﬁned as error bound based on FSM measure in formula(15), and (c) error, cross validation error rates. The reason
is that all of these quantities range from 0 to 1 and relate to
the expected error rates of the kernel function in some sense.
The smaller their values, the better the kernel. The ﬁrst two
quantities are expected to be correlated to the third one.

4.1

Synthetic Data

We generated synthetic data in R2 , and used linear kernels tosimulate different data distributions by different kernels in afeature space. For each data set parameterized by an angle
β, we used two Gaussian distributions (ﬁxed variance in all
directions) for two classes centered at φ+ = (1, 0) ∈ R2
for class +1 and at φ− = (cos(β), sin(β)) ∈ R2 forclass −1. Each class contains 500 training examples. The
variances of the Gaussian distributions are determined to bevar+ = var− = 21  φ− − φ+ . This ensures that for any β,
any data set can be images of another after a linear operation.
Therefore, these data sets with linear kernels are equivalent to
one data set with different kernel functions. For any β < 1,
the problems should have the same level of error rates (orother measures) when using linear kernels, i.e. linear kernels
should be evaluated at the same level of goodness. We run
experiments with different β values of 30, 60, 90, 120, 150
and 180 (degrees) in turn. The results of 1-KTA, F SM err
and error are shown in Figure 2.
From Figure 2, we can observe that error is stable acrossdifferent β, as we expected. F SM err is also rather stable,
varying similarly to error. 1-KTA changes dramatically from
0.936 down to 0.395. It can be concluded that KTA is too
sensitive to absolute positions of data in the feature space.
This conﬁrms our claim about the limitations of KTA, andshows that our measure is more robust.

4.2

Real Data

We showed the advantage of our proposed measure over KTA
in real situations by selecting several popular data sets fromthe UCI collection for experiments. Data names and experimental results are displayed in Figure 3. Data was normalized
to [−1, 1]. Classes were grouped to make binary classiﬁcation
problems. We chose four types of kernel for model selection:
linear kernels, polynomial kernels (degree 3 with scale 1),
RBF (Gaussian) kernels (default), and tan-hyperbolic kernels(default)2. As described above, we ran cross validations anddisplayed the results of different kernels.
The following conclusions can be observed from thegraphs:• RBF kernels give the (approximately) lowest cross validation error rates in 7 out of 8 data sets. This shows that
RBF kernels are usually a good choice. However, KTA
makes RBF kernels the worst one as values of 1-KTA
are the highest ones in 7 out of 8 cases. Our measureagrees with the error rates in most cases, making it morereliable than KTA is.
• Similarly, Tanh kernels perform worst in most cases,
while KTA values are among the best ones.
2
Default parameter values are set by LIBSVM environment at
http://www.csie.ntu.edu.tw/˜ cjlin/libsvm/

IJCAI-07991

• In case of very low error rates as in breast-cancer dataset, FSMerr is highly correlated to error rates, but KTA
is not.
We ranked the kernels according to error, KTA and FSM
separately from 1 to 4. We collected the rank of the best kernel (according to error) for each dataset. On average, KTA
ranks the best kernel at 2.63 (±1.061) while FSM ranks it
at 1.63 (±0.518). A student t-test (with 95% level of conﬁdence) shows that FSM ranks the best kernel closer to 1 than
KTA. This also conﬁrms the advantage of FSM.
In summary, we used synthetic and real data sets and compared measures against the de facto standard of cross validation error rates. We showed that our measure correlates moreclosely to the error rates than KTA does. When ranking thebest kernel according to the error rates, FSM shows a signiﬁcantly lower rank, on average. This suggests that our measure
is more reliable. This conﬁrms our analysis of the limitationsof KTA and that our measure can overcome themse limitations. It was also observed that there is still a gap between
kernel matrix evaluation measures and error rates, as error
rates are collected from many training rounds while measures
are calculated with one pass through the kernel matrices. Thisis the trade off necessary for efﬁciency.

5 Conclusion
The paper shows that KTA, an efﬁcient kernel matrix measure, which is popular in many contexts, has fundamental
limitations, as it is only a sufﬁcient, not a necessary condition to evaluate the goodness of a kernel matrix. A new
measure is proposed to overcome those limitations by using
data distributions in the feature space. This new measure follows the conventional wisdom of measuring within-class andbetween-class variances in an appropriate way. The measureprovides the same efﬁciency as KTA, as evaluated in O(n2 )time complexity, and other properties. It also has links withother methods. This measure is more correlated to the error
rates of SVMs than KTA is.
The implication of this work is vast. One can take into account ﬁner data distribution models in the feature space, toimprove the current work. Also, there are a large number ofapplications of this measure for other methods. We can directly apply this measure (similarly to KTA) to many featureand model selection problems, such as boosting kernel matrices, multiple kernel learning, feature selection and so on. In
general, with efﬁcient kernel evaluation, we can leverage thework of kernel matrix and kernel function learning, which isof central interest in kernel methods.

Acknowledgements
We would like to thank Japan MEXT for the ﬁrst author’s
ﬁnancial support, and anonymous reviewers for helpful comments.

References[Crammer et al., 2002] Koby Crammer, Joseph Keshet, andYoram Singer. Kernel design using boosting. In NIPS,
pages 537–544, 2002.

[Cristianini et al., 2002] Nello Cristianini, John ShaweTaylor, Andre Elisseeff, and Jaz Kandola. On kernel-targetalignment. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing
Systems 14, Cambridge, MA, 2002. MIT Press.
[Feller, 1971] William Feller. An Introduction to Probability Theory and Its Applications, volume 2. John Wiley &Sons, 1971.
[Fine and Scheinberg, 2002] Shai Fine and Katya Scheinberg. Efﬁcient svm training using low-rank kernel representations. Journal of Machine Learning Research, 2:243–
264, 2002.
[Gartner et al., 2004] Thomas Gartner, John W. Lloyd, andPeter A. Flach. Kernels and distances for structured data.
Machine Learning Journal, 57(3):205–232, 2004.
[Globerson and Roweis, 2006] Amir Globerson and Sam
Roweis. Metric learning by collapsing classes. In Y. Weiss,
B. Schölkopf, and J. Platt, editors, Advances in Neural Information Processing Systems 18, pages 451–458, 2006.
[Gradshteyn and Ryzhik, 2000] I. S. Gradshteyn and I. M.
Ryzhik. Table of Integrals, Series, and Products. Academic Press, San Diego, CA, 2000.
[Jebara et al., 2004] Tony Jebara, Risi Kondor, and Andrew
Howard. Probability product kernels. Journal of Machine
Learning Research, 5:819–844, 2004.
[Kwok and Tsang, 2003] James T. Kwok and Ivor W. Tsang.
Learning with idealized kernels. In ICML, pages 400–407,
2003.
[Lanckriet et al., 2002] Gert R. G. Lanckriet, Laurent El
Ghaoui, Chiranjib Bhattacharyya, and Michael I. Jordan.
A robust minimax approach to classiﬁcation. Journal of
Machine Learning Research, 3:555–582, 2002.
[Lanckriet et al., 2004] Gert R. G. Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui, and Michael I. Jordan. Learning the kernel matrix with semideﬁnite programming. J. Mach. Learn. Res., 5:27–72, 2004.
[Meila, 2003] Marina Meila. Data centering in feature space.
In Christopher M. Bishop and Brendan J. Frey, editors,
Ninth International Workshop on Artiﬁcial Intelligenceand Statistics, 2003.
[Neumann et al., 2005] Julia Neumann, Christoph Schnorr,and Gabriele Steidl. Combined svm-based feature selection and classiﬁcation. Machine Learning, 61(1-3):129–
150, 2005.
[Ong et al., 2005] Cheng Soon Ong, Alexander J. Smola,and Robert C. Williamson. Learning the kernel with hyperkernels. Journal of Machine Learning Research, 6:1043–
1071, 2005.
[Schölkopf and Smola, 2002] Bernhard Schölkopf andAlexander J. Smola. Learning with Kernels. MIT Press,
Cambridge, MA, 2002.
[Shawe-Taylor and Cristianini, 2004] John
Shawe-Taylor
and Nello Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, New York, NY, USA,
2004.

IJCAI-07992