Multiple Indefinite Kernel Learning for Feature Selection

1 Introduction

Feature selection is an important problem in machine learning and has been studied extensively, which aims to select only a subset of relevant features in order to speed up learning process, eliminate some noises and provide better model interpretability [Chandrashekar and Sahin, 2014]. In general, feature selection methods can be divided into three categories: "filter" which ranks the features according to some discrimination measures independent of learning algorithms, "wrapper" which evaluates the features by learning algorithms, and "embedded" which embeds feature selection into learning process.

∗Corresponding author.

In the past few years, multiple kernel learning for feature selection (MKL-FS) has attracted more attention in embedded methods. By means of MKL, MKL-FS can not only uncover complicated properties of the features effectively, but also convert the selection of the features into the learning on a sparse combination of multiple kernels [Xu et al., 2009; Varma and Babu, 2009]. Chen et al. treated the feature selection problem of gene expression data as an ordinary multiple parameter learning problem based on multiple kernel support vector machine [Chen et al., 2007]. Dileep and Sekhar further applied this method in image categorization tasks and showed its superiority over principal component analysis (PCA) [Dileep and Sekhar, 2009]. Varma and Babu proposed a more generalized MKL scheme for feature selection where the combination of base kernels can be generalized to be nonlinear [Varma and Babu, 2009]. Xu et al. presented a non-monotonic feature selection method to select a specific number of features and the corresponding combinatorial optimization problem was approximated by an MKL problem [Xu et al., 2009]. Tan et al. focused on sparse support vector machines (SVM) with l0-norm whose convex relaxation can be further formulated as an MKL problem, where each kernel corresponds to a sparse feature subset [Tan et al., 2010]. Yamada et al. proposed an alternative feature-wise kernelized Lasso to capture nonlinear input-output dependency and select informative features according to the kernel coefficients [Yamada et al., 2014].

However, MKL-FS methods usually require that base kernels should be positive definite (PD) and satisfy the Mercer's condition in order to obtain a bi-convex optimization problem. In fact, standard PD kernels are inapplicable in many practical situations. For example, kernels obtained from similarity measures often violate Mercer's conditions and are not positive definite [Saigo et al., 2004; Chen et al., 2009]. On the contrary, indefinite kernels have played an increasingly important role in machine learning and shown much better performance in some scenarios than PD kernels. Kowalski et al. focused on using mixed norm regularization to reach better sparsity [Kowalski et al., 2009]. Liwicki et al. applied an indefinite robust gradient-based kernel in an incremental kernel principal component analysis (KPCA) algorithm for visual tracking and achieved more efficient results [Liwicki et al., 2012]. Xue et al. integrated additional problem-specific prior knowledge in the construction of indefinite kernels and presented its superiority in supervised and semi-supervised classification [Xue and Chen, 2014]. Xu et al. further solved single indefinite kernel SVM with difference of convex functions (DC) programming. [Xu et al., 2017].

Recently, indefinite kernels have been widely studied in dimensionality reduction. Liu utilized an indefinite fractional power polynomial kernel in KPCA in face recognition, which can achieve higher recognition accuracies than the KPCA using PD polynomial kernels [Liu, 2004]. Haasdonk and Pekalska proposed indefinite kernel discriminant analysis (IKDA) to extend traditional KDA in indefinite kernel scenarios [Haasdonk and Pekalska, 2010]. Huang et al. addressed PCA with indefinite kernels (IKPCA) in the framework of least squares support vector machine and then gave IKPCA a feature space interpretation [Huang et al., 2016]. However, the problem of indefinite kernels applied in feature selection has got relatively little research. Furthermore, due to the nonconvexity of indefinite kernels, almost all existing MKL-FS methods can not be used.

In this paper, we propose a novel multiple indefinite kernel feature selection method (MIK-FS) based on the primal framework of indefinite kernel support vector machine (IKSVM) in embedded method scenarios. MIK-FS uses an indefinite base kernel to represent each feature respectively and an l1-norm constraint is then enforced on kernel combination coefficients in order to select features naturally. A two-stage algorithm is further presented to optimize the coefficients of IKSVM and kernel combination alternately. Concretely, when the kernel combination coefficients are fixed, the non-convex primal problem of IKSVM is reformulated as a difference of convex functions (DC) programming and then converted into a convex one by the affine minorization approximation. Once the coefficients of IKSVM have been solved, kernel combination coefficients can be optimized by projected gradient descent. We further prove that the value of the objective function in MIK-FS is strictly monotonic decreasing with each iteration in the algorithm. Experimental results on real-world datasets have shown that MIK-FS outperforms some related methods in terms of feature selection and classification.

2 RelatedWork

Given a training set {(xi, yi)}ni=1 , where xi ∈ RM is a training sample and yi ∈ {-1, +1} is the corresponding class label. MKL-FS firstly applies a base kernel km on each feature of the samples and then combines these kernels into a kernel combination including two ways: additive and multiplicative combinations.

Most MKL-FS methods integrated the kernels into an additive combination [Dileep and Sekhar, 2009]:

where xi,m denotes the mth feature of xi and dm represents the coefficient of the kernel km.

Varma and Babu further extended the linear combination Eq. (1) into a nonlinear product form [Varma and Babu, 2009]:

MKL-FS aims to learn a sparse combination of the kernels so that the feature can be selected naturally. Consequently, SVM-based MKL-FS methods further embeds the kernel combination into the dual problem of SVM, which can learn the coefficients of SVM and the combination simultaneously:

where d is the kernel combination coefficients. An l1-norm regularizer is used on d to obtain a spares solution.

When the kernels are PD, MKL-FS can select the informative features while training a good classifier SVM. However, when the kernels become indefinite, it more likely leads to bad classification performance if we directly embed the combination into the dual problem of indefinite kernel SVM (IKSVM). In the case of indefinite kernels, the primal and dual problems of IKSVM are both non-convex. Consequently, there is a dual gap between the two problems and their solutions are not equivalent [Xu et al., 2017]. As a result, the selected features and the classifier's coefficients learned from the dual IKSVM are more likely not beneficial for the subsequent classification. In other words, it is more reasonable that the indefinite kernel combination should be embedded into the primal IKSVM. However, existing SVM-based MKL-FS methods mostly focus on the dual problem and will fail in solving the non-convex indefinite kernel problems.

3 MIK-FS

In this section, we will present our multiple indefinite kernel feature selection method (MIK-FS). In MIK-FS method, each feature of the samples is characterized by an indefinite kernel and the global optimization problem would come to be non-convex. In order to avoid suffering from the dual gap, we attempt to focus on the primal problem of IKSVM and its objective function can be formulated as an unconstrained optimization problem:

where K represents a Reproducing Kernel Kreˇın Space (RKKS) and L is a loss function. According to [Ong et al., 2004], the Representer Theorem still holds in RKKS and the solution to Eq. (4) can be expressed as

where βi ∈ R, k(·, ·) is a kernel function in RKKS and the corresponding kernel matrix can be indefinite. Combining Eqs. (4) and (5), the kernelized primal form of IKSVM can be formulated as:

We further embed the indefinite kernel combination of Eq. (1) into Eq. (6) to obtain our MIK-FS. An l1-norm regularizer is added to get sparse kernel combination coefficients. The corresponding model of MIK-FS is:

where K = ∑Mm=1 dmKm is an indefinite kernel matrix derived from associated kernel function Kij = k(xi, xj) described in Eq. (1) and Km is derived from kernel function km. Ki represents the ith row of K.

Furthermore, in order to ensure the MIK-FS model is continuously differentiable, we select the smooth quadratic hinge loss function as L(·) and the optimization problem becomes

In Eq. (8), the first term is the regularizer related to hypothesis f. Specially, it is worth noting that β is unconstrained which is different to the Lagrange multiplier α in Eq. (3). The second term is the l1-norm regularizer related to d. If the coefficient dm equals to zero, it means that the corresponding feature has no effect on the classification and can be discarded.

Compared to traditional MKL-FS methods, the proposed MIK-FS has two advantages. Firstly, the kernels used in MIK-FS can actually involve both PD and indefinite kernels. Consequently, MIK-FS is a broader method to exploit more generalized kernels. Secondly, we construct MIK-FS on the the primal form of IKSVM and avoid the dual gap in the non-convex optimization problem effectively.

4 Optimization Algorithm

We adopt a two-stage algorithm to optimize the coefficients (β, b) of IKSVM and d of kernel combination alternately. The complete algorithm is described in Algorithm 1. We will introduce the two stages in detail in the following subsections.

4.1 Solving (β, b)

Firstly, we denote the objective function of MIK-FS as

When the coefficients d are fixed, Eq. (9) degenerates into a non-convex problem of IKSVM with a single indefinite kernel. That is

where L = ∑ni=1 max (0, 1- yi(Kiβ + b))2 and Constantd = λ2‖d‖1 is a constant.

According to [Xu et al., 2017], the non-convex problem of Eq (10) can be reformulated as a DC programming [Tao

Algorithm 1 MIK-FS

Inputs:

• T: the maximum number of iterations
• λ1, λ2: the regularization parameters
• ϵ: the tolerance value for convergence

Process:

• 1: set t = 0, initialize dt, objt ;
• 2: while (t < T) do
• 3: set t = t +1;
• 4: fix dt-1 and solve Eq. (8) to obtain (βt, bt) ;
• 5: fix (βt, bt) and solve Eq. (8) to obtain a solution dt;
• 6: calculate the value of objective function objt ;
• 7: if |objt - objt-1 | ≤ ϵ then
• 8: MIK-FS converges and break;
• 9: end if
• 10: end while
• 11: return βt, bt, dt;

and An, 1997; Dinh and Le Thi, 2014] equivalently due to the favorable property of the spectra for indefinite kernel matrices. Concretely, the objective function can be decomposed as

where the positive number ρ satisfies the condition: ρ ≥ η and the number η is the maximum eigenvalue of the kernel matrix K. As a result, the functions g(β, b) and h(β, b) can both be guaranteed to be convex.

Then, the conjugate dual problem of Eq. (11) can be formulated as f ∗ (β, b) = h∗ (β, b)-g∗ (β, b), where g∗ (β, b) = sup{〈(β, b), (β, b)〉 - g(β, b), (β, b) ∈ Rn ×R} is the conjugate function of g and h∗ is the conjugate function of h . And the relationship between variables {(β, b)} and {(β, b)} is

Using Eq. (12), we can approximate the functions h and g∗ with their affine minorization at points (βk , bk ) and (βk , bk ) respectively

where (βk , bk ) ∈ ∂h(βk , bk ) and (βk+1 , bk+1 ) ∈ ∂g∗ (βk , bk ). Embedding Eq. (13) into the primal and conjugate dual problems of IKSVM, we have

So these two problems of IKSVM become convex after the transformation in Eq. (14). We can construct two sequences {(β, b)} and {(β, b)} by solving Eq. (14).

Furthermore, in order to simplify the solving process [Dinh and Le Thi, 2014], we directly compute {(β, b)} in the way that {(βk , bk )} ∈ ∂h(βk , bk ). Aa a result, the two sequences {(β, b)} and {(β, b)} can be constructed as follows:

Since g(β, b) is a convex function and the related convex optimization problem in Eq. (15) can be easily solved. The detailed steps for solving (β, b) in Eq. (10) are described in Algorithm 2.

Algorithm 2 Primal IKSVM

Inputs:

T1: the maximum number of iterations

ϵ: the tolerance value for convergence

d: the kernel coefficients

K1 . . .KM: matrix obtained from features

δ: the offset for dc decomposition

Process:

• 1: calculate K = ∑Mm=1 dmKm;
• 2: calculate η, the maximum eigenvalue of K;
• 3: set ρ = |η| + δ;
• 4: set k = 0, initialize βk ;
• 5: while (k < T1) do
• 6: calculate βk = λ1(ρI -K)βk ;
• 7: calculate (βk+1 , bk+1 ) = argmin{g(β, b) - 〈β, βk 〉};
• 8: set αk+1 = (βk+1 , bk+1 ) and αk = (βk , bk );
• 9: if ‖αk+1 -αk ‖22 ≤ ϵ then
• 10: the algorithm converges and break the loop;
• 11: end if
• 12: set k = k +1;
• 13: end while
• 14: return βk , bk ;

Algorithm 2 firstly integrates the kernel matrixes Km into an additive combination with coefficients d and performs eigenvalue decomposition on K to find the maximum eigenvalue for DC decomposition (Step 1-3). Within the loop, algorithm 2 calculates the solution of conjugate dual problem (Step 6) and then solves primal problem by approximating h(β, b) with its affine minorization (Step 7). Difference between two points obtained in adjacent iterations is calculated for measuring convergence (Step 8-11).

4.2 Solving d

When (β, b) is fixed, Eq. (8) can be reformulated as:

where γ = [λ1βT K1β + λ2, . . . , λ1βT KMβ + λ2]T , θ = [K1β, · · · ,KMβ] and θi represents the ith row of θ. Eq. (16) can be solved by projected gradient descent (PGD). The gradient of d at dm is:

where SV = {xi ∈ X|yi (Kiβ + b) ≤ 1} is the set of support vectors in current iteration. PGD method for solving d is summarized in Algorithm 3.

Algorithm 3 PGD

Inputs:

T2: the maximum number of iterations ϵ: the tolerance value for convergence

Process:

• 1: set k = 0, initialize dk ;
• 2: while (k < T2 and ‖∇dk‖22 ≥ ϵ) do
• 3: calculate ∇dk according to Eq. (17);
• 4: calculate step size α by Armijo rule ;
• 5: set dk+1 = dk -α ∗∇dk;
• 6: set dk+1 =max(dk+1 , 0);
• 7: set k = k +1;
• 8: end while
• 9: return dk ;

Algorithm 3 calculates the gradient of Eq. (16) and the step size α based on the Armijo rule (Step 3-4). After that, d is updated and projected to feasible sets (Step 5-6).

4.3 Convergence Analysis

We further present a theoretical analysis for the convergence of MIK-FS. As mentioned above, MIK-FS is a two-stage algorithm and thus we will analyze the convergence of these two stages respectively. First of all, when the kernel combination coefficients d are fixed, MIK-FS can be formulated as a primal IKSVM problem. We solve it by DC programming which can guarantee that the objective function of IKSVM is monotonically decreasing [Xu et al., 2017].

Proposition 1. For the sequence {αk = (βk , bk )}, we have

the equality holds if and only if τ‖d(α)‖2 = 0, where τ is a positive parameter to make functions g and h strongly convex.

Furthermore, the local minimum would be obtained when ‖d(α)‖2 = 0 is satisfied.

Then, when the coefficients (β, b) of IKSVM are fixed, MIK-FS is transformed into a convex problem to solve the kernel combination coefficients. Thus, we can obtain the following proposition for the whole algorithm MIK-FS.

Proposition 2. For the sequence {(βk , bk , dk )} , we have

that is, the objective function F(βk , bk , dk ) is strictly monotonic decreasing along the solution sequence.

When F(βk , bk , dk ) = F(βk+1 , bk+1 , dk+1 ) comes true, the algorithm MIK-FS can converge to a stationary point.

5 Experiments

We conduct a series of experiments on several real-world datasets to compare our MIK-FS to some related state-of-theart algorithms.

5.1 Experimental Setup

We select ten datasets from three different repositories for experiments: (a) seven datasets from a feature selection repository 1 , namely ALLAML, Colon, Gli 85, Prostate GE, Isolet, Glioma, Carcinom; (b) two binary datasets from an online repository 2 of high-dimensional biomedical datasets, namely Central Nervous System, Lung Cancer; (c) one dataset Dbworld from UCI Machine Learning Repository. Table 1 lists a brief description of these ten datasets, including the number of samples and the number of features in each sample. As we can see from the table, the number of features in the ten datasets are all very large. So there are more likely high redundancies among these features.

We randomly divide the samples into two non-overlapping training and testing sets which contain almost half of the samples in each class. The processes are repeated ten times to generate ten independent runs for each dataset and then the average results are reported. Since the three datasets Isolet, Glioma and Carcinom are designed for multi-class classification , we choose the first two classes.

In our experiments, we choose the indefinite sigmoid kernel k = tanh(a · xTi xj -r) as the base feature kernel in MIK-FS. Gaussian kernel is used for two MKL-FS methods. For all the algorithms, the regularization parameters and the kernel parameters are chosen from the set {10-2 , 10-1 , 1, 101 , 102 }. A feature is discarded if the corresponding kernel combination coefficient di is less than a small threshold, e.g., 10-5 .

We compare the proposed MIK-FS with the following algorithms:

• l1-SVM [Bradley and Mangasarian, 1998]: SVM with l1-norm regularizer .
• ElasticNet-SVM [Wang et al., 2006]: SVMwith mixed l1-norm and l2-norm regularizer.
• RFMKL [Dileep and Sekhar, 2009]: An SVM-based MKL-FS algorithm with additive kernel combination.

1 http://featureselection.asu.edu/datasets.php

2 http://datam.i2r.a-star.edu.sg/datasets/krbd/

• GMKL [Varma and Babu, 2009]: An SVM-based MKLFS algorithmwith multiplicative kernel combination. .
• IKPCA [Huang et al., 2016]: Kernel principal component analysis with indefinite kernels.

5.2 Experimental Results

Table 2 lists the average classification accuracies and the corresponding number of selected features in each compared algorithm on the ten datasets. The best results are highlighted in bold.

As shown in Table 2, l1-SVM is simple and fast, but it performs poorly compared to other algorithms. Elasticnet-SVM outperforms l1-SVM in terms of classification accuracies but tends to select too many features. GMKL achieves similar results with RFMKL on most datasets except that it performs worse than RFMKL on Gli 85, Central Nervous System and Lung Cancer. MIK-FS excels GMKL and RFMKL on all datasets. The reduced dimensions in IKPCA are limited by the number of samples and it performs even worse than l1-SVM on most datasets. Overall, our proposed MIK-FS achieves higher accuracies than other algorithms on almost all the datasets while selecting a smaller number of features.

Figure 1 shows the classification accuracies corresponding to the specified number of features of five embedded feature selection algorithms on six datasets including ALLAML, Colon, Central Nervous System, Isolet, Glioma and Carcinom. The maximum number of selected feature is set to 60 which is enough for most algorithms to reach the highest accuracies on the datasets.

As shown in Figure 1, our algorithm obviously outperforms the other algorithms in terms of the highest classification accuracies, whose accuracies can even exceed the others' beyond 7% on the datasets Carcinom and Glioma. With the increasing of the number of selected features, the classification accuracies of MIK-FS rise more quickly than the other algorithms on most datasets. MIK-FS can achieve the highest accuracies on all the six datasets when the number of selected feature is larger than 30.

The experiments about the convergence of MIK-FS are conducted on six datasets the same as previous experiments. We plot the value of {F(βk , bk , dk )-F(βk+1 , bk+1 , dk+1 )} during the iterations in MIK-FS. Figure 2 shows difference value of objective function in MIK-FS changing with iterations on six datasets. Obviously, MIK-FS method converges rapidly within 10 iterations on all the six datasets.

6 Conclusion

In this paper, we propose an embedded feature selection method MIK-FS based on the primal framework of IKSVM, which applies an indefinite base kernel for each feature and generates sparse kernel combination coefficients by l1-norm to select features automatically. A two-stage algorithm is accordingly designed to optimize the coefficients of IKSVM and kernel combination alternately. Experiments on real-world datasets validate the effectiveness of MIK-FS in feature selection and classification.

60

Figure 1: Classification accuracies versus the number of selected features of five embedded feature selection algorithms.

Acknowledgments

This work was supported by National Natural Science Foundation of China (Grant Nos. 61375057, 61300165 and 61403193), Natural Science Foundation of Jiangsu Province of China (Grant No. BK20131298) and the National Key Research and Development Program of China (Grant No. 2016YFC1306704). Furthermore, the work was also supported by Collaborative Innovation Center of Wireless Communications Technology.