A Subspace Kernel for Nonlinear Feature Extraction

1 Introduction

Feature extraction or dimensionality reduction is a widely used pre-processing step for classification and data mining tasks, since extracting proper features can reduce the effect of noise and remove redundant information in the data that is irrelevant to the classification or data analysis tasks.

Suppose that we are given a set of n data points, {xi}ni=1 , where xi ∈ X ⊂ Rd is the input data, X is the input space. Traditional feature extraction approaches, such as the Principle Component Analysis (PCA) and Linear Discriminant Analysis (LDA) are linear methods and they project the input data xi into a low dimensional subspace of the input space X .

Recently, constructing nonlinear algorithms based on the kernel methods [Sch¨olkopf and Smola, 2002] have proved successful. For a given positive definite kernel function K : X × X → R, the input data xi, 1 ≤ i ≤ n are implicitly mapped to a feature space F with usually very high dimensionality. Let φ(·) denote the map from X to F, then

A kernel based algorithm essentially applies linear methods in F for the mapped data {(φ(xi)}ni=1 . For example, in the Kernel Principal Component Analysis (KPCA) algorithm [Sch¨olkopf and Smola, 2002], PCA is used to extract a representative subspace of F. Compared with the traditional linear approaches, kernel methods are more powerful since they can explore nonlinear structures of the data, and more flexible as we can recover the linear algorithms by simply using the linear kernel in the kernel based methods.

Usually the dimensionality of F is very high or even infinite, which is helpful for separating different classes of data. However, such a high dimensional space F may contain some redundancy that is irrelevant or even noisy for the given classification or data mining tasks. Hence, as is the case for feature extraction in the input space, it may be also helpful for classification or data mining tasks to find a lower dimensional subspace S of F.

Many Kernel based Feature Extraction (KFE) approaches have been proposed to find a lower dimensional subspace S of the feature space F. For example, KPCA [Sch¨olkopf and Smola, 2002] is widely used for this task. As mentioned above, it essentially performs linear PCA in the feature space F. The goal is to find directions along which the data variance is the largest.

In this paper, we discuss feature extraction methods with the focus on improving the classification accuracy. In the c-class classification problem, each data point xi is associated with a label yi ∈ Rc , where yi = [yi1, . . . , yic]⊤, and yik = 1 (1 ≤ k ≤ c) if xi belongs to class k, and 0 otherwise. 1 It can be seen that KPCA may be not effective for classification problems since it is an unsupervised feature extraction method, which ignores the labels of the given data.

Hence several supervised KFE algorithms have been proposed, which make use of both the input data and the corresponding labels. Like KPCA, they also perform linear feature extraction or linear dimensionality reduction in the feature space F.

The Kernel Fisher Discriminant Analysis (KFDA) [Mika et al., 2001] aims to find a data projection by minimizing the within-class variance and maximizing the between-class variance simultaneously, thus achieving good discrimination between different classes. An efficient variant of KFDA based on QR decomposition, called AKDA/QR, is proposed in [Xiong et al., 2005]. A distinct property of AKDA/QR is that it scales as O(ndc). And in AKDA/QR, the number of features extracted is fixed to the number of classes.

1 Other strategies for constructing the label yi (1 ≤ i ≤ n) are also possible.

The Partial Least Squares (PLS) algorithm [Wold, 1975] has been widely applied in the domain of chemometrics. Unlike the PCA algorithm, which extracts features only based on the variance of the input data, the PLS algorithm uses the covariance between the inputs and the labels to guide the extraction of features. The Kernel PLS (KPLS) algorithm is proposed in [Rosipal and Trejo, 2001].

The Orthogonal Centroid (OC) [Park and Park, 2004] algorithm is a linear dimensionality reduction method that preserves the cluster structure in the data. In this algorithm, the given data are firstly clustered, and then projected into a space spanned by the centroids of these clusters. An orthogonal basis of this subspace is computed by applying QR decomposition to the matrix whose columns consist of the cluster centroids. In [Kim et al., 2005], this method is applied for dimensionality reduction in text classification tasks and exhibits good results. Its kernel based nonlinear extension, i.e. the Kernel Orthogonal Centroid (KOC) algorithm is also presented in [Park and Park, 2004]. To incorporate the label information, the KOC (and OC) algorithm treats input data in the same class as one single cluster, therefore the number of extracted features equals the number of classes. However this method can be easily extended by allowing more clusters in each class.

In this paper, we propose a subspace kernel, based on which the nonlinear feature extraction problem can be transformed into a kernel parameter learning problem.

The rest of this paper is organized as follows. In section 2, we propose the basic idea of our approach and formulate the subspace kernel. Some connections to the related methods are described in section 3. In section 4, we present one possible way to optimize the proposed subspace kernel. Experimental results are provided in section 5 and we conclude the paper in the last section.

2 Nonlinear Feature Extraction via Kernel Parameter Learning

2.1 Basic Idea

As mentioned before, a given positive definite kernel K implicitly introduces a mapping of the given data φ(xi), 1 ≤ i ≤ n, to a usually high dimensional feature space F. When projecting φ(xi) (1 ≤ i ≤ n) into a subspace S of F, the kernel function has to be modified correspondingly since the feature space has changed from F to S. For convenience, we call this modified kernel function the subspace kernel. As will be shown later, the parameters that are used for describing S are also the parameters of the corresponding subspace kernel. Therefore current kernel parameter learning methods can be adapted to optimize this kernel function. This way we can find a discriminating subspace S where different classes of data are well separated. In the following, we will explain the above idea in detail by formulating the aforementioned subspace kernel.

2.2 The Subspace Kernel

Suppose S is an nf dimensional subspace of F and O = [o1, . . . , onf ] is a matrix whose columns constitute an orthogonal basis of S. Let T denote the subspace spanned by the mapped data φ(xi) (1 ≤ i ≤ n) in F, then each oi can be uniquely decomposed into two parts, one is contained in T and the other one is in the orthogonal complement of T ,

where o‖k ∈ T and 〈o⊥k , φ(xi)〉 = 0 for 1 ≤ i ≤ n. Therefore for any φ(xi), its projection into S can be computed as

where O‖ = [o‖1 , . . . , o‖nf ]. 2

Equation (1) indicates that to compute the projection of φ(xi) in S, it is enough to only consider the case where S is a subspace of T , which implies that any vector in S can be expressed as a linear combination of φ(xi), 1 ≤ i ≤ n. Therefore, for any nf vectors z1, . . . , znf ∈ S, let Z denote [z1, . . . , znf ], and X denote [φ(x1), . . . , φ(xn)], then Z can be written as

whereW= [wik] ∈ Rn×nf is a matrix of combination coefficients.

Moreover, if z1, . . . , znf are linearly independent, then the nf dimensional subspace S can be spanned by these nf vectors. Thus the elements of W introduce a subspace S of F, for which we have the following lemma.

Lemma 1. When projecting the data φ(xi) into S, the kernel matrix of the projected data in S can be computed as, 3

where K = [kij] ∈ Rn×n is the kernel matrix of the input data, i.e. kij =K(xi, xj).

Proof. For any φ(xi), 1 ≤ i ≤ n, in order to calculate its projection into the subspace S, spanned by the columns of Z = XW, we need an orthogonal basis U of S. We build U as follows:

In the above equation, T is computed as follows: Assume Kz = Z⊤Z then

where Λ ∈ Rnf×nf is a diagonal matrix of eigenvalues of matrix Kz, and V ∈ Rnf×nf is a matrix whose columns are eigenvectors of Kz. Equation (6) leads to

2 More precisely, the result of equation (1) is the coordinate of the projection of φ(xi) in S. As is widely done in the literature of feature extraction and dimensionality reduction, this coordinate will be used as the extracted features for classification.

3 Here the "kernel matrix of the projected data" refers to the matrix whose elements equal the inner product of the projected data in S.

and

where I is the unit matrix. The following equation follows from (5) and (8),

So the columns of U form an orthogonal basis of the subspace S.

Thus, for φ(xi) ∈ F, 1 ≤ i ≤ n, their projections into the subspace S can be computed as

where Xw is the matrix whose columns are the projections of φ(xi) in S, 1 ≤ i ≤ n.

Having obtained the projected data Xw, we can now compute the inner product between points in the subspace as the following:

where we used equation (5) in the second line, equation (7) in the third line and equation (2) in the fifth line. The equations (11) and (12) are identical to (3) and (4) respectively, therefore the lemma is proven.

The proof also tells that for a givenW, the projection of the data into the subspace S introduced by W can be computed as equation (9).

Let Kw(·, ·) denote corresponding subspace kernel function. Then according to (3) and (4), for any x, x′ ∈ X, the subspace kernel Kw(·, ·) between them can be computed as

where

is the empirical kernel map [Sch¨olkopf and Smola, 2002].

Equation (14) illustrates that the elements ofW, by which the subspace S is described, also serve as the kernel parameters of Kw(·, ·). So in order to find a discriminating subspace S where different classes of data are well separated, we can turn to optimize the corresponding subspace kernel Kw.

3 Connections to RelatedWork

3.1 Feature Selection via Kernel Parameter Learning

In [Weston et al., 2000; Chapelle et al., 2002], kernel parameter learning approaches are adopted for feature selection problem. The kernel of the following form is considered

where .∗ denotes the component-wise product between two vectors. Namely, for θ = [θ1, . . . , θd]⊤ and u = [u1, . . . , ud]⊤, θ. ∗ u = [θ1u1, . . . , θdud]⊤. By optimizing the kernel parameter θ with margin maximization or RadiusMargin bound [Chapelle et al., 2002] minimization, and with a 1-norm or 0-norm penalizer on θ, feature selection can be done by by choosing the features corresponding to the large elements of the optimized θ.

Feature selection locates a discriminating subspace of the input space X. Similarly as the above approaches, we also use kernel parameter learning algorithms to find a discriminating subspace. However, in this paper, we address the problem of feature extraction but not feature selection, and the subspace we want to find is contained in the feature space F but not the input space X.

3.2 Sparse Kernel Learning Algorithms

The subspace kernel function given by (14) is in a general form. As described before, each column in the matrix Z = [z1, . . . , znf ] (c.f (2)) is a vector in the feature space F. Now we show that this kernel relates to the work of [Wu et al., 2005] in the special case where each column of Z has a preimage [Sch¨olkopf and Smola, 2002] in the input space X. That is, for each zi ∈ F, there exists a vector ˆzi ∈ X, such that zi = φ(ˆzi). So now the subspace S can be spanned by φ(ˆz1), . . . , φ(ˆznf ).

For convenience, let ˆZ = [φ(ˆz1), . . . , φ(ˆznf )] (note that ˆZ = Z). Then in this case, according to (13), the subspace kernel function now becomes:

where ψˆ z(x) = φ(x)⊤ˆZ = [K(x, ˆz1), . . . ,K(x, ˆznf )]⊤, and Kˆ z = ˆZ⊤ ˆZ.

In [Wu et al., 2005], an algorithm for building Sparse Large Margin Classifiers (SLMC) is proposed, which builds a sparse Support Vector Machine (SVM) [Vapnik, 1995] with nf expansion vectors, where nf is an given integer. In [Wu et al., 2005], it is pointed out that building an SLMC is equivalent to building a standard SVM with the kernel function computed as (16). And the SLMC algorithm essentially finds an nf dimensional subspace of F, which is spanned by φ(ˆz1), . . . , φ(ˆznf ), and where the different classes of data are linearly well separated.

In [Wu et al., 2005], the kernel function (16) is obtained with the Lagrange method, which is different from the one adopted in the above. And the kernel function (16) is a special case of the subspace kernel (14). Therefore it can be seen that based on the general subspace kernel (14), useful special cases can be derived for some applications.

4 Optimizing Kw

We optimize Kw based on the Kernel-Target Alignment (KTA) [Cristianini et al., 2002], which is a quantity to measure the degree of fitness of a kernel for a given learning task. In particular, we compute W by solving the following KTA

maximization problem:

where 〈·, ·〉F denotes the Frobenius product between two matrices that are of the same size, i.e. for any two equally sized matrices M and N, 〈M,N〉F = ∑ij MijNij. In (17), Ky ∈ Rn×n is the gram matrix between the labels, defined by

where Y = [y1, . . . , yn] ∈ Rc×n , and yi is the label of xi, 1 ≤ i ≤ n.

The elements in Ky reflect the similarities between labels, as Kyij equals 1 if xi and xj belong to the same class, and 0 otherwise. Therefore 'aligning' Kw with Ky will make the similarities between the data points in the same class higher than the similarities between the points in different classes. Thus by maximizing A(W), we can find a subspace of F, where points in the same class are closer to each other than those in different classes. Hence a good classification performance can be expected for the data projected into this subspace.

Note that the subspace kernel allows us to apply many kernel parameter learning algorithms to the feature extraction problem. Therefore apart from KTA, we can also choose other approaches to compute W, such as the one based on the Radius-Margin Bound [Chapelle et al., 2002]. For simplicity, we use KTA in this paper.

Gradient based algorithms can be used to maximize A(W). In our implementation, we use the conjugate gradient algorithm to solve problem (17). To compute A(W), we utilize the fact that Kw = X⊤w Xw (see (10)) and Ky = Y⊤Y (see (18)). Thus, we can decompose Kw and Ky as follows

where ˆxi ∈ Rn (1 ≤ i ≤ nf ) denotes the i-th column of X⊤w and ˆyj ∈ Rn (1 ≤ j ≤ c) denotes the j-th column of Y⊤.

Based on the above two equations, we have

Equation (21) and (22) can be computed with time complexity O(ncnf) and O(nn2f ) respectively. When both nf and c are small, they are more efficient than computing the Frobenius product directly, which requires time complexity of O(n2 ).

Similarly, to compute ∇A(W), we can use the following equations:

where wuv (1 ≤ u ≤ n, 1 ≤ v ≤ nf ) is the element of W. Inspired by (23) and (24), we investigate how to compute α⊤( ∂Kw ∂wuv )α, where α ∈ Rn is an arbitrary vector. Actually, by performing linear algebra straightforwardly, we have

where βv is the v-th element of a vector β, computed as

and in (25), tu is the u-th element of a vector t, defined as:

Note that for any given α, the vectors β and t need to be computed only once, according to (26) and (27) respectively, then α⊤ ∂Kw ∂wuv α can be calculated as (25) for 1 ≤ u ≤ n and 1 ≤ v ≤ nf . Now we can apply (25) to (23) and (24), and ∇A(W) can be calculated.

5 Experimental Results

5.1 Experimental Settings

We empirically investigate the performance of the following KFE algorithms on classification tasks: KPLS, KOC, AKDA/QR and the proposed Subspace Kernel based Feature Extraction (SKFE) method. Following the same scheme in [Xiong et al., 2005], the features extracted by each KFE algorithm are input to a 1-Nearest Neighbor (1-NN) classifier, and the classification performance on the test data is used to evaluate the extracted features. As a reference, we also report the classification results of the 1-NN algorithm using the input data directly without KFE.

As mentioned before, in a c-class classification problem, the number of features nf extracted by both AKDA/QR and KOC is fixed at c. To compare with these two algorithms, the value of nf for SKFE is also set to c in the experiments, although the number of features extracted by SKFE can be varied. For KPLS, three different values of nf are tried: c/4, c/2 and c. The best results are reported for KPLS. 4

For our proposed SKFE algorithm, the function A(W) in (17) is not convex, so the optimization result depends on the initial choice of W. To get a good initial guess, we can use the subspaces found by other KFE algorithms for initialization. In the experiments, for efficiency we use the KOC algorithm to compute the initial W.

4 When c = 2, only two values of nf are tried for KPLS: 1 and 2.

5.2 Experiments onMicroarray Gene Expression Data

In this subsection, we take seven microarray gene datasets to test various KFE methods: Brain Tumor1, Brain Tumor2, Leukemia1, Leukemia2, Prostate Tumor, DLBCL and 11 Tumors. 5 Descriptions of these datasets are presented in Table 1. As shown in Table 1, a typical characteristic of these datasets is that the number of data n is much smaller than the data dimensionality d.

A Gaussian kernel is used in the experiments:

Five fold cross validation is conducted for parameter selection, and the best cross validation error rate is used to measure the performance of different algorithms. The experiment is repeated 20 times independently. And the results in Table 2 show the mean cross validation error and the standard deviation over these 20 runs.

From Table 2, we can observe that SKFE and KPLS compare favorably to the other KFE algorithms. In particular, SKFE improves the results of KOC algorithm in all cases, although KOC is used to initialize SKFE. It can also be seen that SKFE and KPLS are competitive with each other. They are are not significantly different (judged by t-test) on Leukemia1, Leukemia2, DLBCL and 11 Tumors, and KPLS is better than SKFE on Brain Tumor2, while SKFE outperforms KPLS on Brain Tumor1 and Prostate Tumor.

5.3 Experiments on Text Classification

In this subsection, we investigate different KFE methods on the text classification task. It has been observed that there usually exist cluster structures in the text data. The OC algorithm (or equivalently the KOC algorithm with the linear kernel), which can keep these structures, is used for dimensionality reduction in text classification tasks in [Kim et al., 2005] and exhibits good results.

5 They are available at http://www.gems-system.org.

Seven text datasets from the TREC collections are adopted: tr11, tr23, tr41, tr45, la1, la2 and hitech. More information about these seven datasets are available at Table 1.

Similar to the microarray gene data, the data used in text classification tasks are also of very high dimensionality. Another characteristic of these seven datasets is that they are highly unbalanced, which means that the number of data contained in different classes are quite different. For example, in the tr11 dataset, there are 132 data points contained in the seventh class, while just 6 data points in the ninth class, only 4.6% of the former.

On each dataset, we randomly select half of the data from each class to form the training set and use the remaining data for test. As is done in the OC algorithm, the linear kernel is used in this set of experiments. Similarly as before, for each dataset, the experiment is repeated independently 20 times. The average test error and the standard deviation over these 20 runs are reported in Table 3.

Table 3 illustrates that SKFE outperforms other KFE methods on most datasets. Also it can be seen from both Table 2 and 3 that in most cases, all the KFE algorithms obtain better performances than the 1-NN algorithm with the raw data, whilst reducing the data dimensionality dramatically from d to nf , where nf << d. (c.f. section 5.1 for the choice of nf .)

Although SKFE compares favorably to the other KFE methods in terms of the classification accuracy, its computational cost is higher than the others. For the problems reported in Table 1, on a 2.2 GHz Pentium-4 PC, KPLS requires from 0.15 to 39 seconds, AKDA/QR takes between 0.35 and 3 seconds, KOC requires between 0.11 and 5 seconds, while SKFE takes between 0.38 to 69 seconds. The optimization step of SKFE is implemented in C++, and the others are implemented in Matlab.

6 Conclusion

We have presented a subspace kernel based on which nonlinear feature extraction can be conducted by kernel parameter learning. Connections to related work have been explained. In particular, the comparison with the Spare Large Margin Classifier (SLMC) [Wu et al., 2005] illustrates that useful special cases can be derived from the proposed subspace kernel for some applications. We have also described a method to optimize the subspace kernel by Kernel-Target Alignment (KTA) [Cristianini et al., 2002] maximization. But other kernel parameter learning approaches can also be applied. Finally, experimental results have been provided to validate the effectiveness of our approach.