In this paper we propose a novel more flexible approach for the simultaneous feature selection and classification using Support Vector Machine and recent major advances of it, namely Multiple Kernel Learning. Using a quite simple kernel assembly scheme in the following paper we will indicate that feature selection and classification could be done in one step without applying computationally intensive and maybe inadequate filtering or wrapper approach. Later imply that to achieve dimensionality reduction, tractable and more compact as well as comprehensively accurate model it is necessary to accomplish all of above goals by ”training” SVM only once. Actually we apply some additional prerequirement that resulted in a ranking criteria that could be provided by any domain expert or created by our algorithm using Linear SVM by itself. Provided experimental results verify that our approach is comparable or even more accurate and robust than other feature extraction/selection schemes tested on public UCI datasets.
Recent advances in computer science and computational intelligence uncover
vital necessity for the feature selection and dimensionality reduction methods
applied to the variety of highly-dimensional data sources like biomedical CT
images, cardiogram, microarray and other data with high variance and insufficient
sample size. By this research we intend to resolve simultaneously several
problems of previous feature selection/extraction methods like SVM-RFE [
The upcoming sections of our paper are structured as follows: Section 2 briefly presents common SVM basics and MKL extension. Section 3 describes in details our feature selection method and presents generalized algorithm. Section 4 summarizes experimental setup and numerical results. And finally in Section 5 we analyze and compare our method with other feature extraction/selection approaches as well as conclude about further possible research area. 2
In this section we present some commonly recognized SVM basics [
Support Vector Machine is based on the concept of separating hyperplanes that
define decision boundaries using Statistical Learning Theory [
Further we present only dual representation of SVM primal objective that is expressed in terms of its Lagrangian multipliers λi and can be effectively optimized using any off-shell linear optimizer that supports constraint adaptation: l max{X λi − λ i=1 1 Xl l l
X λiλiyiyjK(xi, xj)}, λi ≥ 0, X λiyi = 0, 2 i=1 j=1 i=1 (1) where λi represents a Lagrangian multiplier, yi is {±1} - valued label of data sample xi, K(xi, xj) is a kernel function and l is a number of training samples.
Finally corresponding classification of a new sample x′ is derived by: d = sign(Pi λiK(xi, x′) + b), where K(xi, x′) and b correspond to a kernel function evaluated for a new sample and a linear offset of the optimal decision hyperplane. 2.2
Multiple Kernel Learning aims at simultaneously learning the kernel and the
associated predictor in general SVM context. Recent applications of MKL have
clearly proven that using multiple kernels instead of a single one can enhance the
interpretability of the decision function and improve performances [
m m K(x, y) = X wiKi(x, y), wi ≥ 0, X wi = 1, (2)
i=1 i=1
where m is the total number of kernels. Within this framework, the problem
of data representation through the different kernels is then transferred to the
choice of optimal weights wi that minimizes the MKL objective function [
In this section we describe in details aforementioned feature selection method and a general kernel assembly scheme for Multiple Kernel Learning. The overall approach is given in the form of abstract algorithm that depicts a clear view of all steps needed to implement proposed method. 3.1
Before handling actual feature selection procedure we apply some additional
ranking criteria that performs an ordering of all features according to their
relevant importance to an evaluated classifier. Similar approach was provided by
[
After evaluating the ranking criteria and obtaining ordered list of features we
perform following kernel assembly scheme that could be effectively summarized
by the generalized algorithm that incorporates several subroutines and inner
algorithms such that SimpleMKL [
Algorithm 1: Stepwise feature selection via kernel assembly scheme input : ordered list of features S of size m, training data X of size n × m, class labels Y of size n output: nonlinear SVM model: λ defines a dual SVM solution and b corresponds to a linear offset, selected feature subsets which correspond to not-null elements of weight vector w 1 begin 2 K ← InitKernelMatrices (); 3 IRBF ← InitRBFInterval (); 4 for i ← 1 to m do 5 S′ ← S(1, i); 6 X′ ← X(:, S′); 7 for j ← 1 to |IRBF | do 8 ind ← (i − 1) × |IRBF | + j; 9 K[ind] ← ComputeRBFKernel (X′, IRBF [j]); 10 end 11 12 end [w, λ, b] ← SimpleMKL (Y, K); 13 end
Finally classification using defined in Algorithm 1 SVM model could be handled using following equation: d = sign(X i
X λiwj Kj (xi, x′) + b), j (3) where Kj is the RBF kernel function and x′ is a test sample.
It is obvious that represented by Algorithm 1 kernel assembly scheme could be summarized as a stepwise feature subset selection from the ordered list of all attributes. Further algorithmic steps only broaden number of kernel matrices by additional parametrization of RBF kernel.
To implemented our approach we have selected to train and test our method
within SimpleMKL framework [
To fasten computation of incredibly many kernel matrices (in Algorithm 1 number of kernel matrices is bounded by m × |IRBF |) we have decided to estimate optimal iteration pace of the outer ”for” loop in our generalized algorithm. In order to lower a computational effort and memory load without significant performance degradation we conducted 10-fold cross-validation on the training set and averaged total error across all folds. The pace with the lowest averaged error was selected for performing Algorithm 1. 4
4.1
In our experiments we have tested proposed model under predefined C = 10
(error trade-off) value of the soft-margin SVM that showed most comprehensible
performance for imbalanced data sets and varying γ value of RBF kernel that
trade-offs kernel smoothness and could be effectively estimated via SimpleMKL
framework [
To verify and test our proposed approach we have selected several highly
dimensional public UCI datasets and evaluated them under following experimental
setup: for datasets that weren’t originally separated into validation and training
sets we performed 10-fold cross-validation and collected averaged total error and
balanced error rate (BER). For others we tested our approach on presented in
UCI repository validation set and collected single total error and BER.
Additionally we experiment with highly dimensional gene microarray dataset, namely
CNS-ET, that was very comprehensively inspected in [
In the following subsection we have summarized numerical results for all datasets
under fixed C parameter and enclosed subspace for γ parameter of RBF
kernel with some initial guess of its corresponding scaling factor1. In the Table 1
we present performance measures obtained by our approach under SimpleMKL
framework, linear/nonlinear SVM benchmark results as well as some additional
performance measures for SVM with differently applied filtering or wrapper
feature selection approach. In braces we give averaged number of selected features
for all presented in Table 1 approaches except linear/nonlinear SVM that was
”trained” using all features.
a SVM with the F-score feature selection scheme [
In this paper we propose novel stepwise feature selection method that basically
extends Multiple Kernel Learning approach and helps to provide classifier with
the most comprehensible and meaningful subset of features and perform actual
classification all in one step. As we can see from the above given experimental
results our feature selection method is comparable or even more accurate and
robust than other feature selection/extraction approaches. Remarkably that our
approach almost anywhere attains comparable or even smaller subset of
features. For UCI datasets it is clear that our stepwise feature selection algorithm
brings necessary discrimination capabilities and additional accuracy to the
nonlinear SVM classifier eliminating noisy and redundant features. Separately we
should examine CNS-ET dataset because we do not provide performance
measures for F-SVM and CSA methods. In original work of Pomeroy et al. [