Boosting Kernel Discriminant Analysis and Its Application on Tissue Classification of Gene Expression Data

1 Introduction

Principal component analysis (PCA) and linear discriminant analysis (LDA) are two classical feature extraction and dimensionality reduction techniques broadly used in many tasks involving high-dimensional data. It is generally believed that for pattern classification problems such as face recognition and tissue classification of gene expression data, LDA-based algorithms usually outperform PCA-based ones. The reason is that the former optimizes the low-dimensional representation of the objects for classification by maximizing the ratio of the between-class scatter to the within-class scatter, while the latter simply optimizes object reconstruction without taking class information into consideration. Many LDA-based algorithms have been proposed. Among them, as an attractive approach, some new LDA algorithms [Lu et al., 2003a;

Masip and Vitri`a, 2006] which effectively integrate the boosting and LDA techniques have been developed recently to further enhance the classification performance.

On the other hand, a major problem of linear subspace methods such as PCA and LDA is that they fail to extract nonlinear features representing higher-order statistics. In order to overcome this limitation, kernel dimensionality reduction techniques such as kernel principal component analysis (KPCA) [Sch¨olkopf et al., 1999] and kernel discriminant analysis (KDA) [Baudat and Anouar, 2000; Lu et al., 2003b; Dai and Qian, 2004; Xiong et al., 2005; Dai and Yeung, 2005; Zheng et al., 2005] have been proposed recently to extend linear dimensionality reduction techniques to nonlinear versions by using the kernel trick, demonstrating better performance in many applications than that obtained using their linear counterparts. The basic idea is to first map each input data point x ∈ Rn into the feature space F via a nonlinear mapping φ and then apply the corresponding linear dimensionality reduction algorithm in F. Moreover, similar to their linear counterparts, KDA-based methods are generally better than KPCAbased methods for classification tasks. However, KDA-based algorithms usually suffer from the small sample size problem, because the number of training examples available is usually smaller than the dimensionality of the feature space F especially for high-dimensional data. In order to overcome this problem, many approaches have been developed based on different criteria. Recently, more effective solutions [Dai and Qian, 2004; Zheng et al., 2005] have been proposed to calculate the optimal discriminant vectors in the null space of the within-class scatter operator where the significant discriminant information exists. On the other hand, similar to conventional LDA-based techniques [Lotlikar and Kothari, 2000; Tang et al., 2005; Dai and Yeung, 2005], the performance of KDA degrades further due to the following deficiencies which are referred to as non-balanced problems in this paper:

1. For multi-class pattern classification problems, the optimal criterion based on the conventional between-class scatter is not directly related to classification accuracy. In particular, the corresponding dimensionality reduction procedure tends to overemphasize the inter-class distances of well-separated outlier classes in the input space at the expense of classes that are close to each other, leading to significant overlap between them.
2. The expression of the average within-class scatter has an implicit assumption that all classes have the same weight

for the covariances. In fact, if the class with dominant covariance is simultaneously an outlier class in the input space, the within-class scatter will fail to estimate the correct value for improved classification, due to minimizing the spread of the outlier classes while neglecting the minimization of other covariances.

In this paper, we further improve the overall performance of KDA by proposing a novel KDA algorithm called boosting KDA (BKDA). The proposed approach effectively integrates the boosting technique with the most recently developed KDA algorithms based on the pairwise class discriminant information. The BKDA approach employs the boosting technique to robustly calculate the pairwise class discriminant information that is integrated into the scatter operators in order to solve the non-balanced problems of KDA. Although boosting has been applied to LDA, so far it has not been studied much for KDA. It is worthwhile to mention here several appealing properties of the proposed BKDA method:

1. It handles nonlinearity in a disciplinedmanner that is also computationally attractive like all kernel methods.
2. By introducing the pairwise class discriminant information into the discriminant criterion and simultaneously employing boosting to robustly adjust the information, it effectively overcomes the non-balanced problems in KDA and further increases the classification accuracy.
3. It effectively boosts the significant discriminant information contained in the null space of the within-class scatter operator and simultaneously deals with the small sample size problem. However, the algorithm and analysis presented here can also be applied easily to boost other discriminant information such as that included in the orthogonal complement of the null space of the within-class scatter operator.
4. It constitutes a strong ensemble-based kernel KDA framework, taking advantage of both the boosting and KDA techniques.

To demonstrate the effectiveness of the BKDA method, we apply the proposed method to effectively extract discriminant features for the tissue classification of gene expression data. Experimental results confirm that our BKDA method is superior to several existing dimensionality reduction methods in terms of classification accuracy.

2 Nonlinear Feature Extraction via Kernel Discriminant Analysis

As a nonlinear extension of LDA, KDA essentially performs LDA in the feature space F. Note that F may be infinitedimensional and it should be regarded as a Hilbert space. As such, the scatter matrices in the input space for LDA correspond to operators in F for KDA. For any operator A in F, we let A(0) denote the null space of A, i.e., A(0) = {x |Ax = 0}, and A(0) the orthogonal complement of A(0). Thus, A(0) ⊕ A(0) = F .

Suppose X denotes a training set of N examples belonging to C classes, with each example being a vector in Rn. Let Xi ⊂ X be the ith class containing Ni examples, with xio i denoting the ioth example in it. In addition, each example xio i ∈ X has the corresponding label i ∈ {1, . . . ,C}. By the implicit nonlinear mapping φ : Rn → F, the N images in F can be represented by the set {φ(xio i )}. The conventional between-class scatter operator Sφb , within-class scatter operator Sφw , and population scatter operator Sφt can be expressed as: Sφb = 1N ∑Ci=1 Ni(mφi -mφ )(mφi -mφ )T , Sφw = 1N ∑Ci=1 ∑Ni io=1 (φ(xio i ) - mφi )(φ(xio i ) - mφi )T , Sφt = Sφb + Sφw = 1N ∑Ci=1 ∑Ni io=1 (φ(xio i ) -mφ )(φ(xio i ) -mφ)T , where mφi = 1 Ni ∑Ni io=1 φ(xio i ) and mφ = 1N ∑Ci=1 ∑Ni io=1 φ(xio i ). We maximize the Fisher criterion below to obtain the optimal projection directions w in F:

However, in many practical applications, one of the major problems with KDA is the so-called small sample size problem with respect to (1), because of the degeneracy of the withinclass scatter operator in F. In general, this problem is solved by applying techniques such as pseudoinverse, kernel PCA, and QP decomposition. Recently, some more effective methods [Dai and Qian, 2004; Zheng et al., 2005] have been developed to explore the significant discriminant information in the null space of the within-class scatter operator. In general, a simple and efficient approach of finding this significant discriminant information is to calculate the optimal discriminant vectors in the intersection subspace Sφt (0) ⋂ Sφw(0) with respect to the following modified criterion:

Furthermore, in many situations, nonlinear feature extraction based on the above criterion (2) indeed further enhances the overall performance in terms of classification accuracy and numerical stability. In addition, it should be pointed out that, according to [Chen et al., 2000], for conventional LDA, when the dimensionality n of the training examples is less than the total number of examples N, some useful discriminant information in the null space of the within-class scatter operator will be lost. This is especially the case when n is less than N - C because all this discriminant information will be fully discarded. In KDA described above, this situation can be avoided by choosing the kernel function appropriately, with which the dimensionality of F nonlinearly mapped from the input space can become larger than the number of training examples.

3 Boosting Kernel Discriminant Analysis Learner

3.1 Boosting Kernel Discriminant Analysis

Similar to LDA, KDA also suffers from the non-balanced problems described in Section 1. Here, we will present the BKDA algorithm that combines the strengths of the boosting and KDA techniques and effectively solves the non-balanced problems of KDA at the same time.

Boosting is a general machine learning meta-algorithm for improving the accuracy of any given learning algorithm. One of the most effective boosting algorithms, referred to as AdaBoost, can be used in conjunction with many learning algorithms to improve their performance. Boosting algorithms are adaptive in the sense that the classifiers built are tweaked in favor of those instances misclassified by previous classifiers [Freund and Schapire, 1997]. More specifically, the underlying idea of AdaBoost is based on the sample distribution, which, in essence, is a measure of how hard to classify an example. Moreover, it should be notable that for multiclass problems, a version of AdaBoost called AdaBoost.M2 outperforms AdaBoost.M1 for many real-world applications. Thus we prefer using AdaBoost.M2 in this paper. In order to effectively overcome the non-balanced problems of KDA and simultaneously form a strong connection between KDA and AdaBoost.M2, following [Freund and Schapire, 1997; Lu et al., 2003a], the pairwise class discriminant distribution is introduced on the basis of the mislabel distribution from AdaBoost.M2. Further, at the tth iteration in AdaBoost.M2, any pairwise class discriminant distribution dti,j between classes Xi and Xj can be calculated as follows:

Here, the mislabel distribution Γt (⋆, ∗) measures the extent of the difficulty of discriminating the example ⋆ from the improper label ∗ on the basis of the previous boosting results. Obviously, a larger value of dti,j intuitively indicates worse separability between two classes Xi and Xj, further embodying also that both are closer together in F.

To address the first non-balanced problem in KDA, we replace the ordinary between-class scatter operator Sφb by a weighted between-class scatter operator SφB :

where the weighting function w(⋆) is generally chosen to be a monotonically increasing function of ⋆. For simplicity, we let w(⋆) = ⋆ in this paper. Obviously, based on the definitions of the pairwise class discriminant distribution and the weighting function w(⋆), it can be seen that classes that are not well separated in F and thus can potentially impair the classification performance should be more heavily weighted in F.

In addition, a weighting scheme should also be employed to alleviate the second non-balanced problem, i.e., the negative effect of outlier classes when estimating the within-class scatter operator. Further, at the tth iteration, we replace the ordinary within-class scatter operator Sφw by the weighted withinclass scatter operator SφW as follows:

where rt i = ∑j̸=i w(dti,j ) is the relevance-based weight for class Xi and qt iio = w(∑j̸=i Γt (xio i , j)) is that for xio i . Let us highlight some characteristics of SφW here:

- By incorporating rt i in (5), it ensures that the estimated SφW is only influenced slightly if class Xi is an outlier class. This is reasonable since if one class is well separated from the other classes in F, then whether the within-class covariance operator of this class in the new space is compact or not will not have much effect on classification [Tang et al., 2005].

- Generally, a larger value of qt iio indicates a greater difficulty of classifying example xio i w.r.t. the previous boosting results. As such, qt iio emphasizes the difficult examples in the within-class covariance of class Xi.

Based on the AdaBoost.M2 algorithm and the definitions of SφB and SφW , we propose the BKDA algorithm as detailed in Fig.1. 1 It should be pointed out that the KDA involved in the BKDA algorithm is to calculate the optimal discriminant vectors in the null space of the new SφW in order to take advantage of the significant discriminant information in SφW (0), and the detailed calculation procedure can be found in subsection 3.2 below. In addition, discriminant analysis is quite a strong feature extraction technique for classification. As a result, the boosting process cannot go forward due to the very small pseudo-loss ϵt. In general, some sampling procedures are employed to artificially weaken the corresponding discriminant technique, and, in BKDA, we choose some examples in each class based on qt iio to focus on the hardest examples in each class. For the features extracted by discriminant analysis, a simple nearest neighbor classifier is generally employed for classification. In order to be consistent with the AdaBoost algorithm, in BKDA, the hypothesis ht(⋆, ∗) between example ⋆ and class ∗ can be built easily based on the normalized nearest neighbor classifier, while it gives results identical to the classical nearest neighbor classifier.

3.2 How to Calculate the Optimal Discriminant Vectors in the Feature Space F

In what follows, we will describe how to efficiently calculate the significant discriminant information in the null space of the variant SφW in (5). Furthermore, on the basis of the variants SφB and SφW , we also represent the corresponding population scatter operator as SφT = SφB + SφW . As described in Section 2, the optimal discriminant vectors can be obtained in SφT (0) ⋂ SφW (0) with respect to the following criterion:

Furthermore, based on the above criterion, we have to calculate SφT (0) ⋂ SφW (0), which requires calculating SφT (0) or SφW (0) first. However, the computation of SφT (0) or SφW (0) is quite intractable to some extent, due to the following reasons: 1) unlike Sφt , it is intractable to directly compute SφT (0) by the eigenanalysis of SφT , since SφT cannot be explicitly expressed as SφT = AAT , where A is an operator with the explicit formulation; 2) the direct computation of SφW (0) is very infeasible, since SφW (0) is in general very large in F; 3) according to [Cevikalp et al., 2005], SφW (0) can be indirectly calculated by F - SφW (0) on the basis of first calculating SφW (0), while, in F, high computational complexity is involved at the same time. In order to efficiently solve this problem, we provide the following theorem.

1 For simplicity, KDA in subsection 3.2 is described on X but it is essentially very similar to that based on St.

Input: A set of training examples X = {xio i | xio i ∈ Rn, i = 1, . . . ,C, io = 1, . . . ,Ni}; a set of all mislabels M = {[(i, io), j] | i, j ∈ {1, . . . ,C}, io ∈ {1, . . . , Ni}, i ̸= j}; the initial mislabel distribution onM: Γt (xio i , j) = 1 |M| = 1 N(C-1) ; a small constant ε. for t = 1, . . . , Tmax do

- Calculate the terms dti,j by (3), and rt i and qt iio in (5). - Select s hardest examples per class based on qt

iio to form a training subset St ⊂ X.

- Apply KDA in subsection 3.2 on St, and constitute the KDA-based feature extraction technique, denoted by KDA-t; apply KDA-t on X to obtain {yio,t i ∈ Rr }; build the hypothesis ht(⋆, ∗) ∈ [0, 1] on the subset Y t of {yio,t ∈ Rr }, corresponding to St.

i

- Calculate the pseudo-loss based on ht: ϵt = ∑[(i,io),j]∈M Γt (xio i ,j)(1+ht(yio,t i ,j)-ht(yio,t i ,i)) 2 .

- Set βt = ϵt/(1 - ϵt). If βt ≤ ε, then Tmax = t - 1 and break.

- Update the mislabel distribution Γt : Γt+1 (xio i , j) = Γt (xio i , j)β(1+ht(yio,t i ,i)-ht(yio,t i ,j))/2 t .

end for

Output: The final hypothesis: hf (x) =

supi∈{1,...,C}{- ∑Tmax t=1 log(βt)ht(yt , i)}, where, for any example x, yt ∈ Rr is the corresponding nonlinear feature vector extracted by KDA (KDA-t) in subsection 3.2 over St .

Figure 1: Summary of BKDA algorithm.

Theorem 1. The subspace SφT (0) = {x | 〈SφT , x〉 ̸= 0, x ∈ F} is equivalent to the subspace Sφt (0) = {x | 〈Sφt , x〉 ̸= 0, x ∈ F}, where SφT = SφB + SφW and Sφt is the conventional population scatter operator.

Based on Theorem 1, we thus propose to use the following steps to calculate the optimal discriminant vectors for (6): 1) Calculate the orthonormal basis of Sφt (0); 2) Calculate the orthonormal basis of SφW (0) in Sφt (0) to construct SφT (0) ⋂ SφW (0); 3) Calculate the optimal discriminant vectors with respect to the discriminant criterion (6) in SφT (0) ⋂ SφW (0).

In what follows, we will present the detailed computation procedure. From the discussions above, we first need to calculate the orthonormal basis of Sφt (0) by applying KPCA on Sφt . Moreover, Sφt can be rewritten as:

where Φi = [φ(x1i ) - mφ , . . . , φ(xNi i ) - mφ ] and Ξ =

1 √N [Φ1, . . . , ΦC]. Since the dimensionality of Sφt in F is usually very high or even infinite-dimensional, KPCA can be carried out by the eigenanalysis of ΞT Ξ instead, with size N×N . From the training set {φ(xio i )}, an N ×N matrix K can be defined as K = (Kij)i,j=1,...,C where Kij = (kiojo )jo=1,...,Nj io=1,...,Ni and kiojo = 〈φ(xio i ), φ(xjo j )〉. By the kernel trick, ΞT Ξ can be expressed as

where 1 is an N ×N matrix with all terms being one. Let λl and el (l = 1, . . . ,m) be the ith positive eigenvalue and the corresponding eigenvector of ΞT Ξ, respectively. Then θl = Ξelλ-1/2 l (l = 1, . . . ,m) constitute the orthonormal basis of Sφt (0) (or SφT (0)) [Dai and Qian, 2004; Zheng et al., 2005]. Hence, any input x ∈ Rn can be transformed into r in the low-dimensional space Rm via KPCA as follows:

where P = [θ1, . . . , θm], E = [e1λ-1/2 1 , . . . , emλ-1/2 m ], I is the identity matrix, and Υ = (k1 1 , . . . , kN1 1 , k1 2 , . . . , kN2 2 , . . . , k1C , . . . , kNC C ) with kio i = 〈φ(xio i ), φ(x)〉. Then, by (9), the training examples {xio i } in Rn (or {φ(xio i )} in F) can be mapped to the corresponding points {rio i } in the low-dimensional space Rm. The scatter matrices SB and SW in the low-dimensional space Rm corresponding to SφB and SφW can be computed by either of the following two approaches (for simplicity, this paper adopts the first approach):

- By the corresponding definitions of SφB and SφW , SB and SW can be reconstructed based on the training examples {rio } in Rm;

i

- By the kernel trick, the scatter matrices can be directly computed using SB = PT SφB P and SW = PT SφW P, similar to KPCA.

Furthermore, we can directly calculate the null space of SφW in SφT (0) by the eigenanalysis of SW, since SW is only an m × m matrix. More specifically, let V = [γ 1 , . . . , γ u] be the eigenvectors corresponding to the zero eigenvalues of SW, and then SφT (0) ⋂ SφW (0) can be spanned by PV. As a result, the discriminant criterion (6) can be further transformed into the projection space of SφT (0) ⋂ SφW (0) by JF (z) = zT VT PT SφB PVz = zT VT SBVz (‖z‖ = 1). Let zl (l = 1, . . . , r) be the eigenvectors of VT SBV, sorted in descending order of the corresponding eigenvalues. According to [Dai and Qian, 2004; Zheng et al., 2005], it is clear that wl = PVzl (l = 1, . . . , r) constitute the optimal discriminant vectors with respect to the corresponding criterion

(6) in SφT (0) ⋂ SφW (0). For an input pattern x, its corresponding nonlinear feature vector extracted by the KDA procedure described above can be computed as y = 〈W, φ(x)〉 ∈ Rr , where W = (w1, . . . ,wr). This expression can be rewritten via the kernel trick as follows:

Here, 1 is an N ×N matrix with all terms being one, I is the identity matrix, and kx = (k(x, x11 ), . . . , k(x, xNC ))T .

C

4 Experimental Results

Gene expression data are usually high-dimensional involving a large number of genes but a small sample size. Thus, how to effectively extract discriminant features plays a very important role in gene expression data classification [Ye et al., 2004]. To evaluate the performance of the proposed BKDA algorithm, we conduct some gene expression classification experiments to compare BKDA with some other dimensionality reduction methods.

Since the non-balanced problems mentioned above only exist in multi-class classification problems, our experiments are performed on three different data sets involving more than two classes each in order to demonstrate the behavior of BKDA: 2

1. 11 Tumors: 174 human tumor examples corresponding to 11 different cancer types;
2. A subset A of 14 Tumors: contains all 218 human tumor examples corresponding to 14 different cancer types;
3. A subset B of 14 Tumors: contains all examples corresponding to various human tumor and normal tissue types, each of which contains at least eight examples.

Each data set is randomly partitioned into disjoint training and test sets. For the training set X, each class Xi contains L examples. Since the first data set is less challenging than the second and third data sets, we set L = 5 for the first data set and L = 7 for the other two. Moreover, in our experiments, no preprocessing such as gene selection is applied on the data sets. For each feature extraction method, we use a simple and efficient minimum mean distance rule with Euclidean distance measure to assess the classification accuracy, and simultaneously build the corresponding normalized version for the hypothesis in BKDA based on [Lu et al., 2003a]. Each experiment is repeated 10 times and the average classification rate is reported. For the kernel methods, we use the RBF kernel k(z1, z2) = exp(‖z1 -z2‖2/σ) and polynomial kernel k(z1, z2) = (zT1 z2/σ + 1)2 where σ = 1012 . In addition, it should be noted that BKDA can effectively boost the discrimination ability of the different features extracted by KDA in BKDA. To reduce the computational cost and simultaneously consider the space limitation in this paper, we simply fix the number of features r in BKDA to C - 3 for each data set, where C is the number of classes.

For comparison, the first set of experiments implements BKDA and KDA [Zheng et al., 2005] using both the polynomial and RBF kernels above, since KDA [Zheng et al., 2005] can effectively calculate the significant discriminant information in the null space of the within-class scatter operator and the proposed method [Ye et al., 2004] for gene expression data classification is in essence a special case of KDA in highdimensional spaces. Furthermore, to explicitly show the effectiveness of BKDA, in each comparison, KDA offers two baselines: KDA* denotes the maximum classification rate over the variant features; KDA-r denotes the classification rate based on r fixed features. In addition, in BKDA, the number of chosen examples per class is set to s = L1, where L is the number of examples for each class in the training set. The experimental results shown in Fig. 2 reveal that: as expected, BKDA

2 All data sets are available at http://discover1.mc.vanderbilt.edu /discover/public/mc-svm/.

is capable of improving the overall performance for both kernel functions on all three data sets due to its advantages as discussed above; specially, BKDA can effectively improve the performance of the corresponding KDA-r on the same number of features. In addition, we find that when s is fixed at very small values, BKDA fails to show its effectiveness when compared with KDA* since the ensemble-based learner is too weak.

The second experiment compares BKDA with several effective linear dimensionality reduction methods, including BDLDA [Lu et al., 2003a], LPP [He and Niyogi, 2004], and NPE [He et al., 2005], and several other effective kernelbased nonlinear dimensionality reduction methods, including KPCA [Sch¨olkopf et al., 1999], GDA [Baudat and Anouar, 2000], KDDA [Lu et al., 2003b], WKDA [Dai and Yeung, 2005], and KDA/QR [Xiong et al., 2005]. Table 1 reports the maximum classification rates of different methods on the three data sets. We can see that BKDA is generally more effective than all other methods compared here.

Notice that there has been extensive research based on classifiers for tissue classification of gene expression data [Statnikov et al., 2005], including k-nearest neighbor classifier

(kNN), decision tree, naive Bayes classifier, bagging, boosting, support vector machine (SVM), etc. However, our comparative experiments have not included these methods since we focus on the dimensionality reduction and feature extraction aspect in our study. In addition, over the past decade or so, dimensionality reduction techniques have been playing a very important role in face recognition. We have also applied BKDA to face recognition based on the extended YaleB and PIE databases, showing again that BKDA outperforms all other dimensionality reduction methods compared. The results are not included in this paper due to space limitation.

5 Conclusion

In this paper, a novel KDA algorithm has been presented by incorporating the boosting technique into KDA to give the BKDA algorithm. This new algorithm effectively integrates the strengths of the boosting and KDA techniques to give an ensemble-based KDA framework with strong nonlinear feature extraction capability, and simultaneously overcomes the non-balanced and small sample size problems commonly encountered by KDA-based methods. Extensive empirical comparison of BKDA with many other linear and nonlinear dimensionality reduction methods on gene expression data classification shows that BKDA is a very promising method.

6 Acknowledgments

This research has been supported by Competitive Earmarked Research Grant 621305 from the Research Grants Council of the Hong Kong Special Administrative Region, China.