Estimating Quality of Support Vector
Machines Learning Under Probabilistic andInterval Uncertainty: Algorithms andComputational Complexity
Canh Hao Nguyen1 , Tu Bao Ho1 , and Vladik Kreinovich2
1

School of Knowledge Science, Japan Advanced Institute of Science andTechnology, 1-1 Asahidai, Nomi, Ishikawa, 923-1292, Japan,{canhhao,bao}@jaist.ac.jp
2
Department of Computer Science, University of Texas, El Paso, TX 79968-0518,
USA, vladik@utep.edu
Summary. Support Vector Machines (SVM) is one of the most widely used technique in machines leaning. After the SVM algorithms process the data and produce
some classification, it is desirable to learn how well this classification fits the data.
There exist several measures of fit, among them the most widely used is kernel target alignment. These measures, however, assume that the data are known exactly.
In reality, whether the data points come from measurements or from expert estimates, they are only known with uncertainty. As a result, even if we know that theclassification perfectly fits the nominal data, this same classification can be a bad
fit for the actual values (which are somewhat different from the nominal ones). In
this paper, we show how to take this uncertainty into account when estimating thequality of the resulting classification.

1 Formulation of the Problem
Machine learning: main problem. In many practical situations, we have examples of several types of objects, and we would like to use these examples to teach the computers to distinguish between objects of different types.
Each object can be characterized by the corresponding values of several relevant quantities. If we denote the number of these quantities by d, then we
can say that each object i can be represented by a d-dimensional vector
(i)
(i)
(i)
(i)
x(i) = (x1 , . . . , xk , . . . , xd ), where xk denotes the value of the k-th quantity for i-th object. So, from the mathematical viewpoint, the problem is asfollows: in d-dimensional space X, we have several points x(1) , . . . , x(n) belonging to different classes, and we need to be able, given a new point x ∈ X,
to assign it to one of these classes.

2Canh Hao Nguyen, Tu Bao Ho, and Vladik Kreinovich

In the simplest case when we have two classes, we have several points
belonging to the first class, and several points which do not belong to the firstclass, and we must find a separating algorithm.
Linear classification: main idea. In the past, a typical approach to data classification was to find a hyperplane c1 · x1 + . . . + cd · xd = c0 which separates(i)(i)
the two classes – so that c1 · x1 + . . . + cd · xd > c0 for all positive examples(i)(i)(i.e., examples from the first class) and c1 · x1 + . . . + cd · xd < c0 for all
negative examples (i.e., examples which do not belong to the first class).
Linear classification: limitations. The main limitations of linear classification
approach is that in many important practical cases, there is no hyperplane
separating positive and negative examples.
For example, suppose that we want to teach the computer to distinguishbetween the center of the city and its suburbs. To do that, we mark several
places in the center as positive examples and places in the suburbs as negative
examples. Here, a natural idea is to take d = 2, so that x1 and x2 are twocoordinates of each point. To make it easier, we can take the central squareof the city as the origin of the coordinate system, i.e., as a point (0, 0).
p In this example, separation is straightforward: points whose distance
x21 + x22 to the center is below a certain threshold t are within the city
center, while points for which the distance is > t are in the suburbs. However,no straight line can separate close points from the distant ones – because oneach side of the straight line we have points which are far away from thecenter.
Support Vector Machines: main idea. What can we do when there is no linear
separation? In the 2-D case, as long as there is a separation, i.e., as long as
the same point x ∈ X does not appear as both a positive and a negative
example, we can draw a curve separating positive points from negative ones.
Similarly, in the d-dimensional case, we can always draw a (d − 1)-dimensionalsurface separating positive and negative examples. Moreover, we can always(i)(i)
find a continuous function f (x1 , . . . , xd ) such that f (x1 , . . . , xd ) > 0 for all(i)(i)
positive examples and f (x1 , . . . , xd ) < 0 for all negative examples.
A continuous function f (x1 , . . . , xd ) can be, with arbitrary accuracy, approximated by polynomials; thus, be selecting a good enough accuracy, we
can have a polynomial
fe(x1 , . . . , xd ) = c0 + c1 · x1 + . . . + cd · xd +

d X
d
X

ckl · xk · xl + . . .

k=1 l=1

which has the same separating property, i.e.,
(i)

(i)

c0 + c1 · x1 + . . . + cd · xd +d X
dX
k=1 l=1(i)(i)

ckl · xk · xl + . . . > 0

Support Vector Machines Under Interval Uncertainty

3

for all positive examples and
(i)

(i)

c0 + c1 · x1 + . . . + cd · xd +

d X
d
X

(i)

(i)

ckl · xk · xl + . . . < 0

k=1 l=1

for all negative examples. These formulas clearly show that this non-linear
separation means that we linearly separate points (x1 , . . . , xn , x21 , x1 · x2 , . . .).
Instead of polynomials, we could use trigonometric polynomials or sumsof Gaussian functions, or any other class of approximating functions. In
all these cases, what we are doing is mapping each point x into a point
φ(x) = (φ1 (x), . . . , φp (x), . . . , φN (x)) in a higher-dimensional space (of dimension N ≥ d), and then use linear separation to separate the resulting
points φ(x(1) ), . . . , φ(x(n) ) in the N -dimensional space. This, in a nutshell, isthe main idea behind the Support Vector Machines (SVM) techniques; see,e.g., [10].
Need to estimate classification quality. The fact that we have a surface separating positive examples from negative examples does not necessarily meanthat this classification is good. Intuitively, if we have a new example x which
is similar to one of the previously given examples x(i) , then this new example
should be classified to the same class as x(i) . So, we want to make sure not
only that all the positive examples are on the right side of the separating
surface, but also that the points which are close to these examples are also on
the same side of the separating surface. In other words, we want to make surethat all the examples are sufficiently far away from the separating surface.
Thus, some reasonable measure of the distance from this surface can serve as
the measure of the quality of the resulting classification.
Several such criteria have been proposed. These criteria are usually defineddef
in terms of the kernel matrix kij = hφ(x(i) ), φ(x(j) )i, where0

defhφ, φ i =NX

φp · φ0p .

p=1

KTA. The most widely used criterion is the kernel target alignment (KTA)
A [1], which is defined as follows (in our notations):n X
nXkij · yi · yj
i=1 j=1
A=
,
n X
n
X
2
n·
kij
i=1 j=1
where yi = 1 for positive examples and yi = −1 for negative examples. This
criterion has a very intuitive meaning. In the ideal situation, the separation
should be as sharp as possible: we should have all the vectors φ(x(i) ) corresponding to the positive examples to be equal to some unit vector e and all4Canh Hao Nguyen, Tu Bao Ho, and Vladik Kreinovich

the vectors corresponding to the negative examples to be equal to −e. In thisideal situation, the kernel matrix is equal to yi · yj . To estimate the qualityof a classification, it is reasonable to check how close the actual kernel matrix
is to this ideal one. One way to check is to consider both matrices as vectors
in a N × N dimensional space, and estimate the cosine of the angle between
these vectors; if the vectors coincide, the angle is 0, and the cosine is 1; if thevectors are close, the angle is close to 0, and the cosine is close to 1, etc. This
cosine is equal tohK, ·y T iF
p,hK, KiF hy · y T , y · y T iF
where
n X
n
X
def
0
0
hK, K iF =kij · kij,
i=1 j=1

so we get the above expression for the KTA.
Class Separability Measure (CSM). An alternative measure to KTA has been
proposed in [13]. This measure is actually defined for a general case of classifying the data into several (C ≥ 2) classes. The main idea is that in a goodclassification, data points within each class should be close to each other,while data points from different classes should be far away from each other. In
other words, “within-class” scatter should be much smaller than the “betweenclasses” scatter.
Each class is naturally characterized by its average. Thus, for each data
point, its contribution to the “within-class” scatter can be described as a(squared) distance from this data point to the average, and its contribution
to the “between-classes” scatter can be described as a (squared) distance
between the average of this class and the overall average.
In the SVM approach, each data point x(i) is represented by the vector
φ(x(i) ). Thus, the above idea can be reformulated as follows. For each class
Sc , c = 1, 2, . . . , C, let nc denote the number of data points classified into thisclass. Let φc denote the average of all the vectors φ(x(i) ) from the c-th class,and let φ denote the average of all n vectors φ(x(i) ). Then, we can define thewithin-class scatter sw as
def

sw =

C X
X

kφ(x(i) ) − φc k2 ,c=1 i∈Sc

and the between-classes scatter as
def

sb =

C
X

nc · kφc − φk2 .

c=1
def

We can also define total scatter as the sum st = sw + sb . A classification is ofdef sbisgood quality if sw ¿ sb , i.e., equivalently, if sb ≈ st and the ratio C =stclose to 1. This ratio C is used as an alternative quality characteristic.

Support Vector Machines Under Interval Uncertainty

5

For the case of two classes, we will denote the number of the corresponding
examples as n+ and n− , and the averages of the corresponding vectors φ(x(i) )by φ+ and φ− . The value of the CSM ratio C can be computed in terms of
the kernel matrix kij = hφ(x(i) ), φ(x(j) )i as follows:• First, for every i, we compute
a+
i =

1 X
1 X
−
k
;
a
=
kij .
ij
i
n+ j:y =1
n− j:y =−1j•jSecond, we compute
a++ =

1 X +
1 X +
+−
a
,
a
a ,
=
i
n+ j:y =1
n− j:y =−1 i
j

a−+ =

j

1 X −
1 X −
ai , a−− = +a ,+n j:y =1
n j:y =−1 i
j

++

+−

and sb = a−a• Then, we compute

−a

sw =

−+

n
X

j

−−

+a

.

kii − n+ · a++ − n− · a−− ,

i=1

sb
.
sb + sw
A new alternative quality measure: FSM. In many practical examples, KTA
and CSM provides a reasonable estimate for the quality of fit, in the sensethat cases when we have a better fit have a larger value of KTA or CSM.
However, there are examples when the values of KTA and CSM are larger forthe cases when intuitively, the classification quality is worse.
One reason for the sometimes counterintuitive character of CSM is that
CSM estimates a within-class scatter based on deviations in all directions. For
example, if for some coordinate φp (x), we have φp (x(i) ) = 1 for all positive
examples and φp (x(i) ) = −1 for all negative examples, then intuitively, we
have a perfect classification. However, since the values φq (x(i) ) for q 6= p may
be widely scattered, we can have a huge value of the within-class scatter, andthus, a very low value of the CSM measure of fit.
To avoid this problem, it is reasonable to take into account only the scatterin the direction between the centers φ− and φ+ . The corresponding FeatureSpaced Measure (FSM) was proposed in [7].
To estimate this measure, we do the following:
and C =•First, we compute the average φ+ of the values φ(x(i) ) for all the positive
examples and the average φ− of the values φ(x(i) ) for all the negative
examples. In the ideal case, as we have mentioned, we should have φ+ = e
and φ− = −e for some unit vector e.

6Canh Hao Nguyen, Tu Bao Ho, and Vladik Kreinovich•Then, we estimate the vector e as the unit vector in the direction of theφ+ − φ−.
difference φ+ − φ− , i.e., as e = +kφ − φ− k• Next, for each example i, we compute the projection pi = hφ(x(i) ), ei ofthe vector φ(i) to the direction e.
• Finally, we compute the population meansXX
1
1
p+ = + ·pi ; p− = − ·pi ,nni:y =1i:y =−1iiwhere n+ and n− (= n − n+ ) denote the numbers of positive and negative
examples, compute population variancesX
X
1
1
V+ = +·(pi − p+ )2 ; V − = −·(pi − p− )2 ,n − 1 i:y =1
n − 1 i:y =−1ii

and the desired value√
V++ V−.
kφ+ − φ− k√This algorithm describes how to compute these values based on the vectors
φ(x(i) ); alternatively, as shown in [7], we can compute it from the kernel matrix
kij as follows:−• First, we compute the values a+i and ai as in the CSM case.
++• Second, we compute the values a , a+− , a−+ , and a−− as in the CSM
case, and compute kφ+ − φ− k2 = a++ − a+− − a−+ + a−− .
• Then, we compute
X
−+
++ 2
((a−
) − (a+
))
i −a
i −a

V+ =

i:yi =1(n+ − 1) · kφ+ − φ− k2
X

V− =and the desired value

,

+−
−− 2
((a+
) − (a−
))
i −a
i −a

i:yi =−1(n− − 1) · kφ+ − φ− k2,√√
V++ V−.
kφ+ − φ− k

2 How to Take into Account Probabilistic and Interval
Uncertainty: Formulation of the Problem and Linearized
Algorithms for Solving this Problem
Need to take into account probabilistic and interval uncertainty. In presenting
algorithms for computing the SVM quality measures, we (implicitly) assumed

Support Vector Machines Under Interval Uncertainty
(i)

7
(i)

that we know the exact values of the data points x(i) = (x1 , . . . , xd ). In(i)
reality, the values xk come from measurements or from expert estimates,and both measurements and expert estimates are never 100% accurate. As a(i)result, the measured (estimated) values x
ek of the corresponding quantities(i)are, in general, different from the (unknown) actual values xk .
It is desirable to take into account this measurement (estimation) uncertainty when estimating the quality measures.
Need to describe measurement and/or estimation uncertainty. In order togauge the effect of the measurement (estimation) uncertainty on the valuesof the quality measures, we must have the information about the measurement (estimation) uncertainty, i.e., the information about the measurement(i) def(i)(i)(estimation) errors ∆xk = x
ek − xk .
For simplicity, in the following text, we will mainly talk about measurement errors; for estimation errors the situation is very similar.
Upper bound on the measurement error. How can the measurement error be
described? First, the manufacturer of a measuring instrument must provide us
with an upper bound ∆ on the absolute value |∆x| of the measurement error∆x. If no such bound was guaranteed, this would mean that the difference ∆x
can be arbitrarily large; in this situation, after getting a measurement result
say x
e = 1, we cannot be sure whether the actual value x of the measured
quantity is 1, 0, 10, 100, or 1,000,000. In this situation, xe = 1 is a wild guess,not a measurement result.
When we know this upper bound ∆, this means that the actual value ∆xof the measurement error must be inside the interval [−∆, ∆].
Probabilistic information. In addition to the upper bound ∆, we often also
know the probabilities of different values ∆x from the interval [−∆, ∆].
This situation of probabilistic uncertainty is traditionally used in engineering and scientific practice. Most frequently, scientists and engineers consider
the situation when the measurement error is normally distributed, with 0mans and known standard deviation σ; see, e.g,., [9].
Case of interval uncertainty. In many important practical situations, we do
not have the information about the probabilities of different values of ∆x, weonly know the upper bound ∆.
The reason is that the probabilistic information usually comes from comparing the results of measuring the same quantity with two different measuring
instruments: the one used for actual measurements and the standard (muchmore accurate) one – whose results are so much closer to the actual values
that we can ignore the corresponding measurement errors and consider theseresults actual values.
There are two situations when this comparison is not done. The first suchsituation is the situation of cutting-edge measurements, when we are actuallyusing the best possible measuring instrument. For example, if we perform

8

Canh Hao Nguyen, Tu Bao Ho, and Vladik Kreinovich

some protein measurements by using a state-of-the-art electronic microscope,
it would be nice to be able to compare the results with a much more accurate
microscope – but ours is already the best.
Another case when the probabilities are not determined is when we have
limited resources. For example, in geophysics, in every seismic experiment,
we use a large number of sensors to measure the corresponding time delays.
It would be nice to be able to compare all these sensors with more accurate
ones. However, the detailed comparison of each sensor requires the use of
costly standard sensors and, as a result, costs several orders of magnitude
more than the cost of buying a new sensor – so we often cannot do thisdetailed probabilistic “calibration” within our limited resources.
In both cases, the only information we have about the measurement error∆x = xe − x is the upper bound ∆: |∆x| ≤ ∆. In such situations, once we havethe measurement result xe, the only conclusion that we can make about the(unknown) actual value x is that x belongs to the interval x = [x, x], where
def

def

x = x
e − ∆ and x = x
e + ∆. This situation is called the situation of interval
uncertainty.
Estimating the measures of fit under measurement uncertainty: formulationof the problem. In general, we have an algorithm
(1)

(2)

(2)

(n)

(n)

(2)

(2)

(n)

(n)

(1)

Q(x1 , . . . , xd , x1 , . . . , xd , . . . , x1 , . . . , xd )which transforms the values
(1)

(1)

x1 , . . . , xd , x1 , . . . , xd , . . . , x1 , . . . , xdof the corresponding quantities into the value
(1)

(1)

(2)

(2)

(n)

(n)

y = Q(x1 , . . . , xd , x1 , . . . , xd , . . . , x1 , . . . , xd )of the corresponding quality characteristic. Due to measurement errors, we do
(i)
(i)
(i)
not know the actual values xk . Instead, we only know the intervals [xk , xk ](i)of possible values of xk – and possible also the probabilities of different values
from these intervals.
(i)
(i)
(i)
Different values xk ∈ [xk , xk ] lead, in general, to different values of the(1)(n)
measure of fit y = Q(x1 , . . . , xd ). It is therefore desirable to find the range
y of possible values of y:
(1)

(n)

(1)

(1)

(1)

(n)

y = {Q(x1 , . . . , xd ) | x1 ∈ [x1 , x1 ], . . . , xd

(n)

(n)

∈ [xd , xd ]},and, if possible, the probability of different values of y within this interval.
Case of relatively small measurement error: possibility of linearization. Whenthe measurement errors ∆xi are relatively small, we can use linearization.
(i)
(i)
(i)
(i)
By definition of the measurement error ∆xk = x
ek − xk , hence xk =
(i)
(i)
(i)
x
ek − ∆xk . When the measurement errors ∆xk of direct measurements are
relatively small, we can expand the expression

Support Vector Machines Under Interval Uncertainty
(1)

(n)

(1)

9

(n)

∆y = ye − y = Q(ex1 , . . . , xed ) − Q(x1 , . . . , xd ) =
(1)

(n)

(1)

(1)

(n)

(n)

Q(e
x1 , . . . , xed ) − Q(ex1 − ∆x1 , . . . , x
ed − ∆xd )in Taylor series and only keep linear terms in the resulting expansion. Since
(1)

(1)

(n)

(n)

(1)

(n)

ed −∆xd ) ≈ Q(eed )−y = Q(ex1 −∆x1 , . . . , x
x1 , . . . , x

we conclude that ∆y = ye − y =n PdP
i=1 k=1

(i)

n X
d
X
∂Q
(i)
i=1 k=1 ∂xk(i) def(i)ck · ∆xk , where ck =

∂Q
(i)

∂xk

(i)

·∆xk ,.

(i)

Linearization: probabilistic case. When ∆xk are independent normally dis(i)tributed random variables with 0 means and known standard deviations σk ,
n P
d
P
(i)
(i)
the linear combination ∆y =ck · ∆xk is also normally distributed,
i=1 k=1

with 0 mean and standard deviationv
u n d
uX X (i) (i)(ck · σk )2 .
σ=ti=1 k=1

So, in this case, to find the uncertainty in the value of the measure of fit,
it is sufficient to be able to compute the values of the corresponding partial(i)derivatives ck .
(i)Linearization: interval case. The dependence of ∆y on ∆xk is linear: it is
(i)
(i)
(i)
increasing relative to xk if ck ≥ 0 and decreasing if ck < 0. So, to find thelargest possible value ∆ of ∆y, we must take:
(i)

(i)

(i)

• the largest possible value ∆xk = ∆k when ck ≥ 0, and
(i)
(i)
(i)
• the smallest possible value ∆xk = −∆k when ck < 0.
(i)

(i)

In both cases, the corresponding term in the sum has the form |ck | · ∆k , so
we can conclude that
n X
d
X
(i)
(i)
∆=
|ck | · ∆k .
i=1 k=1

Similarly, the smallest possible value of ∆y is equal to −∆. Thus, the rangeof possible values of y is equal to [y, y] = [ey − ∆, ye + ∆]. So, to compute ∆, it(i)is also sufficient to know the partial derivatives ck .
How to compute the derivatives. For all the above characteristics y, we havean explicit expression in terms of the values kij . Thus, we can find the explicit
analytic formulas in terms of the corresponding derivatives as10Canh Hao Nguyen, Tu Bao Ho, and Vladik Kreinovich
(i)

ck =

n X
n
X
∂y
∂kab
·
.
(i)
∂k
ab ∂x
a=1
b=1

k

Here, the first partial derivative can be explicitly computed: e.g., for KTA
Q = A, we have
n P
n
P

∂y
=
∂kab

n·

ya · ybn P
nP− 2kab ·i=1 j=1

For kab =

N
P
p=1

2
kij

i=1 j=1

Ãn·if a = i or b = i:
N
X
∂φp

∂xk

∂xk
p=1

∂kai

N
X

∂xk

p=1

=
(i)

=
(i)
∂kii
(i)

∂xk

N
X
∂φp
p=1

∂kab
(i)

∂xk

!2 .
2
kij

is only different from 0(x(i) ) · φp (x(b) ) for a = i and b 6= i;

φp (x(a) ) ·

=2

n P
n
P
i=1 j=1

φp (x(a) ) · φp (x(b) ), the derivative∂kib

kij · yi · yj∂xk∂φp (i)(x ) for a 6= i and b = i;∂xk(x(i) ) · φp (x(i) )for a = b = i.

3 In General, Estimating Quality of SVM Learning
Under Interval Uncertainty Is NP-Hard
Motivations. In the previous section, we considered the case when measurement errors are small, e.g., no more than 10%, so that we can ignore terms
which are quadratic in terms of these errors. For example, for 10% = 0.1, thequadratic terms are proportional to 0.12 = 1% ¿ 10% and thus, indeed, muchsmaller than the original errors. In this case, we can linearize the formulas forthe quality of SVM learning and get efficient algorithms for computing therange of the corresponding quality characteristics.
In practice, however, the measurement errors are often not very small. For
example, for a realistic measurement error of 30%, the square is ≈ 10% andis no longer negligible in comparison with the original measurement errors. In
such situations, we can no longer use linearized techniques, we must consider
the original problem of computing the range [y, y] of a given characteristic
(1)

(n)

Q(x1 , . . . , xd ) under interval uncertainty:
(1)

(n)

(1)

(1)

(1)

(n)

[y, y] = {Q(x1 , . . . , xd ) | x1 ∈ [x1 , x1 ], . . . , xd

(n)

(n)

∈ [xd , xd ]}.

Support Vector Machines Under Interval Uncertainty

11

It turns out that in general, this problem is NP-hard – at least it is NP-hardfor the most widely used measures of fit KTA and CSM.
Crudely speaking, NP-hard means that there is practically no hope of designing an efficient algorithm which would always correct compute this range;
for precise definitions, see, e.g., [3, 4, 8].
Theorem 1. Computing the range of KTA under interval uncertainty is NPhard.
Proof. To prove NP-hardness of our problem, we will reduce a known NPhard problem to our problem of computing the range A of KTA A underinterval uncertainty. Specifically, we will reduce, to our problem, the following
partition problem [3] that is known to be NP-hard:••

Given k positive integers s1 , . . . , sk ,check whether it is possible to find the values εi ∈ {−1, 1} for whichkP
εi · si = 0.
i=1

To each instance s1 , . . . , sk of this problem, we assign the following instanceof the problem of computing A: we take d = 1, n = k + 1, y1 = . . . = yk = 1,
def
yk+1 = −1, x(i) = [−si , si ] for i ≤ k, and x(n) = {2S}, where S = max si .
i=1,...,kAs φ, we take a 2-dimensional mapping φ = (φ1 , φ2 ) consisting of the following
two piece-wise linear functions:
if x ≤ S
if x ≤ S
0x
φ1 (x) = 2S − x if S ≤ x ≤ 2S ; φ2 (x) = x/S − 1 if S ≤ x ≤ 2S .




1
if x ≥ 2S0
if x ≥ 2S
In this case,

(i)
(i)

x · x(i)(j)
kij = hφ(x ), φ(x )i = 10

if i, j < n,if i = j = n,otherwise.

Therefore,n X
nXkij · yi · yj =i=1 j=1n X
nX
i=1 j=1

2
kij
=

k X
k
X

x

(i)

(i)

·x

+1=

Ã k
X

i=1 j=1
k X
k ³
X
i=1 j=1´2 ³´2x· x(j) + 1 =
(i)

!2
(i)

x

+ 1;

i=1

Ã k
X³
i=1

(i)

x

´2

!2
+ 1; and12Canh Hao Nguyen, Tu Bao Ho, and Vladik Kreinovich

µ k
P

A=

¶2
(i)

x
+1
sµi=1
.
¶
k ¡
¢2 2
P
n·
x(i)
+1
i=1

(i)
The numerator is always greater than or equal to 1. Since≤ si , we havesµ |x | ¶2k
¡ (i) ¢2Px
≤ s2i and hence, the denominator is always ≤ n·s2i
+ 1. Thus,defsµ

we always have A ≥ A0 =

n·

i=1

1
k
P

i=1

. The only possibility for A =

¶2
s2i

+1

A0 is when thesnumerator of the fraction A is equal to 1, and its denominator
µ k
¶2
P 2
is equal to n ·si+ 1. This is only possible when |x(i) | = si for all i,
i=1

(i)

i.e., when x= εi · si for some εi ∈ {−1, 1}, andkPx(i) = 0 – i.e., exactly

i=1

when the original instance of the partition problem has a solution. So, A = A0
if and only if the original instance has a solution. This reduction proves thatour problem is indeed NP-hard.
Theorem 2. Computing the range of CSM under interval uncertainty is NPhard.
Proof. Under the same reduction as in Theorem 1, we get n+ = k, n− = 1,k
1 X (i)++an = 0 and for i < n, we have ai =·x · x(j) = x(i) · E, where
k j=1
def

E =

k
1 X (i)−++·x . Similarly, a−=n = 1 and ai = 0 for all i < n. Thus, a
k i=1

k
k
1 X +
1 X (i)·ai = E · ·x = E 2 , a+− = a−+ = 0, and a−− = 1. Hence, sb =
k i=1
k i=1
k ¡
¢2
P
E2 + 1.
E 2 + 1, sw =x(i) − k · E 2 − 1 and thus, C = k
P ¡ (i) ¢2
i=1
2x− (k − 1) · E

The numerator is ≥ 1, the denominator is ≤

k
P
i=1

i=1
def
s2i , hence C ≥ C0 =

1
.
k
P
2
si

i=1

The only possibility to have C = C0 is when E = 0 and |x(i) | = si for all i,i.e., when the original instance of the partition problem has a solution. The
theorem is proven.

Support Vector Machines Under Interval Uncertainty

13

4 Conclusion
For classification produced by machine learning techniques, it is desirable tolearn how well this classification fits the data. There exist several measures offit, among them the most widely used is kernel target alignment.
The existing formulas for these measures assume that the data are known
exactly. In reality, whether the data points come from measurements or fromexpert estimates, they are only known with uncertainty. As a result, even if
we know that the classification perfectly fits the nominal data, this same classification can be a bad fit for the actual values (which are somewhat different
from the nominal ones). In this paper, we show how, when the measurement
errors are relatively small, we can take this uncertainty into account whenestimating the quality of the resulting classification. We also show that in thegeneral case of large uncertainty, the problem of estimating the range of thesemeasures of fit is NP-hard.
Acknowledgments. Vladik Kreinovich supported in part by NSF grants
HRD-0734825, EAR-0225670, and EIA-0080940, by Texas Department ofTransportation grant No. 0-5453, and by the Japan Advanced Institute of
Science and Technology (JAIST) International Joint Research Grant 2006-08.
The authors are thankful to the anonymous referees for valuable comments.

References
1. Cristianini N, Shawe-Taylor J, Elisseeff A, Kandola J (2002) On kernel-targetalignment. In: Dietterich TG, Becker S, Ghahramani Z (eds) Advances in Neural
Information Processing Systems 14, MIT Press, Cambridge, Massachusetts
2. Ferson S, Ginzburg L, Kreinovich V, Longpré L, Aviles M (2002) Computing
variance for interval data is NP-hard. SIGACT News 33(2):108–118
3. Garey MR, Johnson DS (1979) Computers and Intractability, a Guide to the
Theory of NP-Completeness. WH Freeman and Company, San Francisco, California
4. Kreinovich V, Lakeyev A, Rohn J, Kahl P (1997) Computational Complexity
and Feasibility of Data Processing and Interval Computations Kluwer, Dordrecht
5. Kreinovich V, Longpré L, Starks SA, Xiang G, Beck J, Kandathi R, Nayak
A, Ferson S, Hajagos J (2007) Interval versions of statistical techniques, withapplications to environmental analysis, bioinformatics, and privacy in statistical
databases. Journal of Computational and Applied Mathematics 199:418–423
6. Jaulin L, Kieffer M, Didrit O, Walter E (2001) Applied Interval Analysis: With
Examples in Parameter and State Estimation, Robust Control and Robotics.
Springer Verlag, London
7. Nguyen CH, Ho TB (2007) Kernel matrix evaluation. In: Manuela M. Veloso
MM (ed) Proceedings of the 20th International Joint Conference on Artificial
Intelligence IJCAI’07, Hyderabad, India, January 6-12, 2007, 987–992
8. Papadimitriou CH, Steiglitz K (1998) Combinatorial Optimization: Algorithms
and Complexity, Dover Publications, Inc., Mineola, New York

14

Canh Hao Nguyen, Tu Bao Ho, and Vladik Kreinovich

9. Rabinovich SG (2005) Measurement Errors and Uncertainty. Theory and Practice, Springer Verlag, Berlin
10. Schölkopf B, Smola AJ (2002) Learning with Kernels, MIT Press, Cambridge,
Massachusetts
11. Shawe-Taylor J, Cristianini N (2004) Kernel Methods for Pattern Analysis,
Cambridge University Press, New York, New York12. Vapnik VN (1995) The Nature of Statistical Learning Theory, Springer-Verlag,
New York, New York13. Wang L, and Chan KL (2002) Learning kernel parameters by using class separability measure. In: NIPS’s Sixth Kernel Machines Workshop, Whistler, Canada,
2002.