The Kernel Support Vector Machine (KSVM) has achieved promising classi cation performance. However, since it is based only on local information (Support Vectors), it is sensitive to directions with large data spread. On the other hand, Kernel Nonparametric Discriminant Analysis (KNDA) is an improvement over the more general Kernel Fisher Discriminant Analysis (KFD), where the normality assumption from KFD is relaxed. Furthermore, KNDA incorporates the partially global information in the Kernel space, to detect the dominant normal directions to the decision surface, which represent the true data spread. However, KNDA relies on the choice of the -nearest neighbors ( N N 's) on the decision boundary. This paper introduces a novel Combined KSVM and KNDA (CKSVMNDA) model which controls the spread of the data, while maximizing a relative margin separating the data classes. This model is considered as an improvement to KSVM by incorporating the data spread information represented by the dominant normal directions to the decision boundary. This can also be viewed as an extension to the KNDA where the support vectors improve the choice of -nearest neighbors ( N N 's) on the decision boundary by incorporating local information. Since our model is an extension to both SVM and NDA, it can deal with heteroscedastic and non-normal data. It also avoids the small sample size problem. Interestingly, the proposed improvements only require a rigorous and simple combination of KNDA and KSVM objective functions, and preserve the computational efficiency of KSVM. Through the optimization of the CKSVMNDA objective function, surprising performance gains were achieved on real-world problems.
Keywords: Kernel Nonparametric Discriminant Analysis, Kernel Support Vector Machines, Partially Global Information, Local Information, Small Sample Size Problem. 1
Supervised learning is the task of nding a function which relates inputs and targets. A training set X of input vectors fxigiN=1 is given, where xi 2 Rk(k 1) 8i = 1; 2; :::; N . The corresponding set T of tags are ftigiN=1, where ti 2 0; 1 8i = 1; 2; :::; N . The objective is to learn a model of dependency of the targets on the inputs. The ultimate goal is to be able to make accurate predictions of t for unseen values of x. Typically, we base our predictions upon some function y(x) de ned over the input/training space X , and learning is the process of inferring the parameters of this function. A new representation of data is necessary to learn non-linear relations with a linear classi er. This is equivalent to applying a xed non-linear mapping F of the data to a feature space, in which the linear classi er can be used. Hence, the objective function will be of the form: y(x; w) =
N ∑ fixwi + w0 = i=1
T (xi)w + w0; (1) where (x) = (f1x; f2x; : : : ; fNx ) : X ! F describes a non-linear mapping from the input space to a feature space for the input variable x. Hence, non-linear classi ers have two stages: (i) a xed non-linear mapping transforms the data into a feature space F and then (ii) a linear classi er is used to classify them in F . Analysis of functions of the type (1) is facilitated since the adjustable weight vector w and the offset w0 appear linearly, and the objective is to estimate optimum values of the weight coefficients. There are a large number of functions of type (1). Our concentration here is on some relevant state-of-theart kernel-based models, such as, the Kernel Support Vector Machine (KSVM) and the Nonparametric Discriminant Analysis in kernel space, which we will call KNDA. KNDA extends the linear NDA based on the same principles that the Kernel Fisher Discriminant Analysis (KFD) is built upon. The advantage of KNDA over KFD is the relaxation of normality assumption. KNDA measures the between-class scatter matrix on a local basis in the neighborhood of the decision boundary in the higher dimensional feature space. This is based on the observation that the normal vectors on the decision boundary are the most informative for discrimination. In case of a two-class classi cation problem, these normal vectors are approximated by the N N 's from the other class for one point. We can consider KND as a classi er based on the \near-global" characteristics of data. Although KNDA gets rid of the underlying assumptions of KFD and results in better classi cation performance, no additional importance is given to the boundary samples. In other words, the margin criterion (as calculated in KSVM) is not considered here. Moreover, it is not always an easy task to nd a common and appropriate choice of N N 's on the decision boundary for all data points to obtain the best linear discrimination.
Another category of kernel-based classi ers is the Kernel Support Vector Machine (KSVM). KSVM is based on the idea of maximizing the margin or degree of separation in the training data. There are many hyperplanes which can divide the data between two classes for classi cation. One reasonable choice for the optimal hyperplane is the one which represents the largest separation or margin between the two classes. KSVM tries to nd the optimal hyperplane using support vectors. The support vectors are the training samples that approximate the optimal separating hyperplane and are the most difficult patterns to classify. In other words, they are consisted of those data points which are closest to the optimal hyperplane. As KSVM deals with a subset of data points (support vectors) which are close to the decision boundary, it can be said that the KSVM solution is based on the \local" variations of the training data.
It has been shown in the literature that maximum margin based classi ers like
the KSVM typically perform better than discriminant (or average margin) based
methods like the KNDA due to their robustness and local margin consideration.
However, KSVM can perform poorly when the data varies in such a way that
data points exist far from the classi cation boundary [
Several methods exist in literature which have addressed these issues inherent
in discriminant based and maximum margin based methods. The ellipsoidal
kernel machine was proposed in [
Although the method proposed in [
Another approach to improve the classi cation performance of KSVM is
to include additional training examples. This approach has been used in [
We propose a novel CKSVMNDA model which combines the KNDA and
KSVM methods. In that way, a decision boundary is obtained which re ects
both near-global characteristics (realized by KNDA) of the training data in
feature space and its local properties (realized by the local margin concept of the
KSVM). Being a kernel-based model, CKSVMNDA can deal with nonlinearly
separable data efficiently. Rather than introducing new constraints like [
The proposed method improves upon our recently proposed models [
We also show that our method is a variation of the KSVM optimization problem, so that even existing KSVM implementations can be used. The experimental results on real and arti cial datasets show the superiority of our method both in terms of accuracy.
The rest of the paper is organized as follows: Section 2 provides formulations of the KSVM and KNDA. Section 3 contains derivation of the novel CKSVMNDA model. Section 4 provides a comparative evaluation of the CKSVMNDA model to the KSVM and KNDA methods. This evaluation is carried out on a number of benchmark real datasets. Finally, Section 5 provides some conclusions.
Let X1 = fxigiN=11 and X2 = fxigiN=1N+1N+21 be two different classes constituting an input space of N = N1 + N2 samples or vectors in RM where, class X1 contains N1 samples and class X2 contains N2 samples. Let the associated tags with these vectors be represented by T = ftigiN=1, where ti 2 f0; 1g 8i = 1; 2; : : : ; N . Since real-life data has inherent non-linearity, KSVM tries to map the data samples to a higher dimensional feature space F , where linear classi cation might be achieved. Let the function map the classes X1 and X2 to two higher dimensional feature classes F1 = f (xi)giN=11 and F2 = f (xi)giN=N1+1, respectively.
However, in case when the dimension of F is very high, it is not possible
to do mapping directly. In such a case, the kernel trick [
K(xi; xj ) =<
(xi): (xj ) >; 8i; j 2 f1; 2; : : : ; N g: Our target is to learn the weight vector w which minimizes (or maximizes) some objective function of the form of Equation (1). 2.1
As stated before, KSVM tries to map the samples to a higher dimensional feature space in the hope that the classi cation problem will be linear in that space. In the feature space, KSVM tries to nd the optimal decision hyperplane. The optimal hyperplane is the one with the largest margin, or, in other words, the plane which has largest minimal distance from any of the samples. Maximizing the distance of samples to the optimal decision hyperplane is equivalent to minimizing the norm of w. As a result, this becomes part of the objective function. However, it might be the case that the problem is non-linear even in the higher dimensional space. To solve this, the margin constraint is relaxed or slacked. Also, a penalty factor is introduced in the objective function to control the amount of slack. This penalty factor is of the form of a loss function, usually a hinge loss function. Incorporating all these, the KSVM optimization problem can be written as:
min w̸=0;w0 { 1 2
N wT w + C ∑ max(0; 1 i=1
} ti( T (xi)w + w0)) ;
Here, max(0; 1 ti( T (xi)w + w0)) is the hinge loss function. For correctly classi ed training samples, this function does not incur any loss. For misclassi cation, the loss factor is controlled by C. Note that although KSVM is generally described as an optimization problem with constraints on the weights, we are presenting it slightly differently with the hinge-loss function so that it will be easier to derive the probabilistic interpretation of our proposed method later. This representation can easily be converted to the more familiar constrained optimization problem.
Since the weight vector w resides in the feature space, it cannot be calculated
directly. Instead, the Lagrangian dual problem is solved [
N ∑ ti i K(x; xi) + w0 ; i=1 where w0 is computed using the primal-dual relationship, and where only samples with non-zero Lagrange multipliers i contribute to the solution. The corresponding data samples are called Support Vectors (SVs). These points are the crucial samples for classi cation. Therefore, KSVM considers only those data points which are close to the decision hyperplane and are critical to nd the decision boundary. In other words, KSVM only considers the local variations in data samples. The overall distributions of the training samples are not taken into consideration. Incorporating some kind of global distribution (e.g. results from classi ers like KNDA) can provide better classi cation. 2.2
The NDA can be extended to the feature space F . We call this the Kernel Nonparametric Discriminant Analysis (KNDA). Instead of calculating the simple mean vectors, the nearest neighbor mean vectors are calculated to formulate the between-class scatter matrix of the NDA. In our feature space, this vector can be de ned as:
Mm( (xi)) =
(x)NN (j); 1 ∑ j=1 where, (xi)NN (j) de nes the jth nearest neighbor from data point xi of class m. is the free parameter which de nes how many neighbors to consider. This parameter needs to be optimized for each dataset. Now, let us de ne two matrices L1( (xi)) and L2( (xi)). We will use the kernel trick to formulate these matrices. In that case, the matrices are calculated on a component by component basis, where, a component of L1( (xi)) is de ned as: (L1( (xi)))j = K(xj ; xi)
(M2 ( (xi)))j ; 8i 2 f1; 2; : : : ; N1g; 8j 2 f1; 2; : : : ; N g; and a component of L2( (xi)) is de ned as (L2( (xi)))j = K(xj ; xi)
(M1 ( (xi)))j ; 8i 2 fN1 + 1; N1 + 2; : : : ; N1 + N2g; 8j 2 f1; 2; : : : ; N g: (2) (3) (4) (5) With these formulations, the between-class scatter matrix in the feature space can be de ned as: ∇ = + 1
N1+N2
∑ (N1 + N2) i=N1+1
1 ∑N1 iL1( (xi))L1( (xi))T (N1 + N2) i=1
iL2( (xi))L2( (xi))T :
Here, i are the weighting functions to nullify the effects of samples that are far
from the boundary. It is de ned as follows [
The motivation behind KNDA is the observation that essentially the nearest neighbors represent the classi cation structure in the best way. For small values of , the matrices in Equation (4) and (5) represent the direction of the gradients of the respective class density functions in the feature space. If the weighting functions are not used, samples with large gradients that are far from the boundary may pollute the necessary information. Hence, these gradients with combination of the weighting functions form the between-class scatter matrix ∇, which preserves the classi cation structure.
The KNDA does not make any modi cations to the within-class scatter matrix. As a result, the formula for within-class scatter matrix ∆ is similar to the KFD, and can be written as follows: ∆ = K1(I 1N1 )K1T + K2(I 1N2 )K2T ; (8) where K1 is a N N1 Kernel matrix for the class X1 and K2 is a N N2 Kernel matrix for the class X2. I is the identity matrix and 1N1 and 1N2 are the matrices with all entries N11 and N12 , respectively. With these de nitions of ∇ and ∆, the KNDA method proceeds by computing the eigenvectors and eigenvalues of ∆ 1∇. Since the higher dimensional feature space F is of dimension N , the matrix ∆ is needed to be regularized before calculating the inverse. This is achieved by adding a small multiple of the identity matrix I. Hence, the eigenvectors and eigenvalues of (∆ + I) 1∇ are computed, and the eigenvector corresponding to the largest eigenvalue forms the optimal decision hyperplane. We can exploit the fact that the matrix ∇ is only of rank one (i.e., T ∇ = (N1 +1N2) ∑iN=11 i( T L1( (xi))L1( (xi))T ) + (N1 +1N2) ∑iN=1N+1N+21 i( T L2( (xi)) L2( (xi))T )). Thus, we can x T ∇ to any non-zero value, for example 1 and minimize T ∆ . This amounts to the following quadratic optimization problem: s:t: ∇
T ∆ ; = 1: 3
In this section, we present our proposed model CKSVMNDA which combines the data spread information represented by the normal vectors to the decision surface for the KNDA (partially global information), and the support vectors for the KSVM (local information). Thus, the CKSVMNDA overcomes the drawbacks of KSVM by controlling the spread of the data, which is represented by the KNDA dominant normal directions to the decision boundary, while maximizing a relative margin separating the data classes. Moreover, the choice of KNDA nearest neighbors ( N N 's) on the decision boundary is improved by the KSVM support vectors. Therefore, the CKSVMNDA objective function is a simple and rigorous summation of the KSVM and KNDA objective functions: (9) (10) (11) (12) min ̸=0; 0
N +C ∑ max(0; 1 { 1 T [2 (∆ +
2 i=1
∇) + I] ti( T (xi) +
} 0)) : In theory, CKSVMNDA should outperform both KSVM and KNDA if the control parameter can be optimally chosen. In practice, the values of and will be tuned via the cross validation technique, where data is divided into a number of subsets. Then, one subset is used for testing while the others are used for training. All the subsets are used for testing in turns and the average is taken into consideration to reduce variability. This whole process is repeated with different values of and . The latter are assigned the values with the best performance. 3.1
Since our optimization problem is similar to the KSVM optimization problem, we can solve it in a similar way, i.e., by using Lagrange multipliers. However, obtaining the CKSVMNDA solution this way requires an entirely new implementation to test this method. The following lemma gives us an easier alternative to implement this method: Lemma 1. The CKSVMNDA method formulation is equivalent to: min w^ ̸=0;w0 where and Proof. Substituting Equations (14-16) into equation (13) we get the original CKSVMNDA problem (Equation (11)).
This lemma gives us a signi cant advantage from the implementation viewpoint.
This essentially means that we can use the existing SVM implementations [
In this section we evaluate the proposed CKSVMNDA method against three other contemporary classi ers, namely, the KSVM, KNDA and the Kernel Fisher Discriminant (KFD). To strengthen the signi cance of our method, we provide results for both real-world datasets and a face recognition application.
For kernelization of the data, we use the Gaussian RBF Kernel K(xi; xj ) = e ∥xi xj∥2= . This kernel is proven to be robust and exible. Here, represents the positive \width" parameter. For KNDA and KFD, after nding the optimal eigenvector, Bayes classi er was used for conducting the nal classi cation.
The involved parameters were optimized using exhaustive search to try all possible combinations. Although the parameter optimization is a lengthy process, this needs to be done only once for a new dataset, and, hence, does not contribute to the actual classi cation performance. If the optimization needs to be faster, efficient methods like coordinate descent technique can be used at the cost of a small degradation in accuracy values.
The number of parameters to tune for the CKSVMNDA method is 4, while it is 2 for KSVM and KNDA. It might seem that an accurate t of the parameter values is necessary for CKSVMNDA to perform well, specially if we have a small training dataset. But as we will see from the results, CKSVMNDA performs better compared to other methods by tuning over a limited range of parameter values we have used (e.g. we use a set of only 20 values and 20 values for parameter tuning to obtain the results of Table 1). Since this is a combination of KSVM and KNDA, the parameters compensate each other, and the t doesn't necessarily have to be perfect. Also, for small training set, we tackle the problem of poor performance due to inaccuracies in matrix inversion by adding a regularization term before inverting. 4.1
We have applied the classi cation algorithms on 11 real-world and arti cial
datasets.The datasets are obtained from the Benchmark Repository used in [
Table 1 contains the average accuracy values and the standard deviations obtained over all the runs. We see that the CKSVMNDA method outperforms the KSVM, KNDA and the KFD in almost all cases. Since the CKSVMNDA combines the global and near-global variations provided by the KSVM and the KNDA, respectively, it can classify the relatively difficult test samples. Also, being a variation of the KSVM and KNDA, this method is free from any underlying distribution assumption, and, hence, can provide better results. Concerning the parameters and , in order to reduce the time of optimization, we had to restrict ourselves to only a few values. Still, as we can see, these limited values are good enough for almost all the datasets. This establishes the fact that our method can be used in practical applications. To measure the statistical signi cance of the results, we paired up the CKSVMNDA method with the other methods and performed paired t-tests on the accuracy values. The paired t-test determines whether or not two paired sets of measured values are signi cantly different. The last row of Table 1 provides the con dence intervals (in %) obtained from the performed t-tests. This con dence interval quanti es the probability of the paired distributions being the same. The higher the condence interval, the lower is the probability that the underlying distributions are statistically indifferent. As we can see, all the con dence intervals are almost 100%, which proves that the CKSVMNDA method indeed provides statistically signi cant accuracy improvements.
If we compare the results between the KNDA and KFD, we see that in some cases, the KFD provides better classi cation results than the KNDA. This is due to the fact that the optimal nearest neighbor parameter for the KNDA (the
N N 's) is not always easy to nd. But since our method combines the KNDA with KSVM, the optimality of this parameter is not as crucial as it is in the KNDA.
The computational complexity of the KSVM scales with O(N 2) for one iteration. The KNDA and KFD scale with a computational complexity of O(N 3) (dominated by the inversion of the within-class scatter matrix). Each of the KNDA and KFD methods requires only one run as there is no iterative process involved.
In the CKSVMNDA, the complexity for the inversion of scales with O(N 3). However, this inversion process can be considered to be part of pre-processing, as it is needed to be done only once before start of the training. Therefore, the computational complexity of our proposed CKSVMNDA can be considered similar to that of the KSVM, i.e., O(N 2) per iteration. This can also be seen from the obtained results (second last row of Table 1), where we see that the average computational time of our method is on par with that of KSVM. In this paper, we have proposed a novel classi cation method named CKSVMNDA. The CKSVMNDA method incorporates the global variational information from the KSVM and the near-global information from the KNDA. Being a combination of these two methods, CKSVMNDA is a robust classi er, free from any underlying assumption regarding class distribution. Our method is also capable of tackling the small sample size problem. Being a convex optimization problem, our method provides a global optimum solution and can be solved efficiently by using numerical methods. Besides, we have shown that our method can be reduced to the classical KSVM model so that existing KSVM implementations can be used. The experimental results on some contemporary datasets veri es the superiority of our method, where we compare CKSVMNDA with the KSVM, KND and KFD. In future, we plan to build a multi-class classi er based on the principles of the CKSVMNDA method.