Home | About | Journals | Submit | Contact Us | Français |

**|**Cancer Inform**|**v.12; 2013**|**PMC3740816

Formats

Article sections

Authors

Related links

Cancer Inform. 2013; 12: 143–153.

Published online 2013 August 4. doi: 10.4137/CIN.S10212

PMCID: PMC3740816

Lingkang Huang,^{1,}^{3,}^{4}^{} Hao Helen Zhang,^{2,}^{5} Zhao-Bang Zeng,^{3} and Pierre R. Bushel^{4}

Corresponding author email: moc.liamg@gnauh.gnakgnil

Copyright © 2013 the author(s), publisher and licensee Libertas Academica Ltd.

This is an open access article published under the Creative Commons CC-BY-NC 3.0 license.

This article has been cited by other articles in PMC.

Microarray techniques provide promising tools for cancer diagnosis using gene expression profiles. However, molecular diagnosis based on high-throughput platforms presents great challenges due to the overwhelming number of variables versus the small sample size and the complex nature of multi-type tumors. Support vector machines (SVMs) have shown superior performance in cancer classification due to their ability to handle high dimensional low sample size data. The multi-class SVM algorithm of Crammer and Singer provides a natural framework for multi-class learning. Despite its effective performance, the procedure utilizes all variables without selection. In this paper, we propose to improve the procedure by imposing shrinkage penalties in learning to enforce solution sparsity.

The original multi-class SVM of Crammer and Singer is effective for multi-class classification but does not conduct variable selection. We improved the method by introducing soft-thresholding type penalties to incorporate variable selection into multi-class classification for high dimensional data. The new methods were applied to simulated data and two cancer gene expression data sets. The results demonstrate that the new methods can select a small number of genes for building accurate multi-class classification rules. Furthermore, the important genes selected by the methods overlap significantly, suggesting general agreement among different variable selection schemes.

High accuracy and sparsity make the new methods attractive for cancer diagnostics with gene expression data and defining targets of therapeutic intervention.

**Availability:** The source MATLAB code are available from http://math.arizona.edu/~hzhang/software.html.

With the boost of modern techniques such as microarrays and next-generation sequencing in biological sciences, more and more high-throughput data are generated and utilized for basic science and for translational medicine. A typical gene expression data set contains tens or hundreds of thousands (*p*) input variables, which greatly exceeds the sample size *n*, i.e., *p* >> *n*. Many classical multivariate analysis methods have difficulties in handling such data because of the curse of dimensionality. However, the support vector machine (SVM),^{1}^{,}^{2} originally designed for binary classification, has shown success in learning large *p* small *n* data and is useful for cancer classification.^{3}^{,}^{4}

Cancer classification using gene expression data often results in multi-class problems, classifying tumor cells to multiple subtypes. In previous studies, samples were defined as (x* _{i}*,

A better method for handling multi-class problems is to separate all the classes by estimating *K* discriminating functions (*f*_{1}(x), *f*_{2}(x), …, *f** _{K}*(x)) simultaneously. The decision rule is then defined as
$\mathrm{\Phi}(\text{X})=arg\underset{k=1}{\overset{K}{max}}\hspace{0.17em}{f}_{k}(\text{X})$, assigning the label

Besides classification, another question of primary interest to biologists is to identify important genes for tumor classification. Since including too many redundant variables in a model may negatively impact its prediction performance,^{3} variable selection is important and necessary for accurate cancer classification. The redundant variables include both noise variables and variables which are highly correlated with the predictor variables. Furthermore, building a sparse and more interpretable model can reduce the number of follow-up experiments to a manageable size. One common approach of variable selection is gene-ranking: first, rank genes using univariate measurements such as *p*-values from hypothesis tests or correlation coefficients between individual inputs and the response, then sequentially add/remove genes to/from the model, and finally select the model based on cross-validation or the validation error. Despite their popularity in practice, gene-ranking methods have some drawbacks. First, genes are pre-selected based on individual effects, so their combined effects cannot be taken into account. This can be an issue since many genes tend to be highly correlated. In addition, these procedures separate variable selection and classification in two stages, and hence selected variables are not guaranteed to contribute significantly to the final classifier. This may result in suboptimal performance of classification.

The standard SVMs are equipped with *L*_{2} penalty for regularization; see Guyon et al. (2002)^{11} for the binary SVM and Lee et al. (2004)^{7} for the MSVM. Since *L*_{2} penalty shrinks the fitted coefficients towards zero, it effectively controls the model variability and improves prediction performance especially when many variables are highly correlated.^{3} However, *L*_{2} penalty can not set small coefficients to exactly zeros, so all variables are utilized in the learned model. For the purpose of variable selection, Bradley and Mangasarian^{12} introduced *L*_{1} penalty to the binary SVM for achieving sparsity in the solution. By shrinking small coefficients to exact zeros, *L*_{1} SVM can build a parsimonious model with more accuracy than the standard *L*_{2} SVM when many redundant variables exist. A large *p* and small *n* data set can be directly fed into the *L*_{1} model without pre-screening.

In this paper, we consider variable selection for the multi-class SVM, which is more challenging than the binary case because of the increased complexity in multi-class learning. The work on the MSVM variable selection in literature is limited but includes ^{Wang et al. (2007)}^{,}^{13} Lee et al. (2006),^{14} and Zhang et al. (2008).^{15} In particular, Wang et al.^{13} studied the *L*_{1}-norm MSVM and developed the solution path algorithm, while Zhang et al.^{15} proposed a new penalty form, called the sup-norm penalty, which was shown to lead to more sparse models than *L*_{1} penalty. Lee et al.^{14} proposed to first make a functional ANOVA decomposition for the decision function and then conduct variable selection by imposing a soft-thresholding penalty on the functional components. All of these methods are based on the loss function of Lee et al.^{7}

In this work, we suggest several new variable selection procedures for MSVM based on the loss function of Crammer and Singer.^{8} Compared to other loss functions, this particular function provides a direct generalization of the hinge loss in binary SVMs and has a natural interpretation in terms of the functional margin. In practice, the resulting classifiers have shown competitive performance. We first considered linear classification problems. A group of regularization problems are proposed for sparse multi-class learning, and the computational algorithms are discussed as well. We then extended the methods to nonlinear cases. Our methods are particularly useful for analyzing large *p* and small *n* data, for example, high dimensional microarray or other “-omics” data. We applied the methods to two microarray data sets, acute leukemia study^{16} and small round blue cell tumors.^{17} The results suggest promising performance of the new methods in terms of accurately predicting the classes using a minimal number of genes.

Given a training set {(x* _{i}*,

When *K* = 2, the label *y* is coded as {+1, −1} by convention. Consider the linear classifier *f*(**x**) = *β*_{0} + x^{T}*β*. The binary SVM minimizes || *β*||^{2} + *λ* ∑_{i}_{=1}^{n}*ξ** _{i}* subject to the following constraint, depending on whether the data are separable:

Binary SVM

$$\{\begin{array}{ll}\text{separable\hspace{0.17em}case}:\hfill & {y}_{i}\hspace{0.17em}f({\text{x}}_{i})\ge 1,\forall i,\hfill \\ \text{non}-\text{separable}:\hfill & {y}_{i}\hspace{0.17em}f({\text{x}}_{i})\ge 1-{\xi}_{i},{\xi}_{i}\ge 0,\forall i\hfill \end{array}$$

(1) (2)

In the binary SVM objective function, the term || *β* ||^{2} = ∑_{j}_{=1}^{p}*β*_{j}^{2} controls the width of the margin, the quantity ∑_{i}_{=1}^{n}*ξ** _{i}* is an upper bound for the misclassification error on the training set when data are non-separable and λ > 0 is the tuning parameter. Equivalently, the binary SVM can be formulated as a regularization problem using the hinge loss function as: min

Crammer and Singer^{8} extended the hinge loss from the binary SVM to multi-class problems. In the separable case, the discriminating functions are required to satisfy constraint (3) for all observations: if *x* belongs to class *y*, then *f** _{y}*(x) is greater than any

MSVM

$$\{\begin{array}{ll}\text{separable\hspace{0.17em}case}:\hfill & {f}_{yi}({\text{x}}_{i})-\underset{\begin{array}{c}k\ne {y}_{i}\\ k=1,\dots ,K\end{array}}{\text{max}}\hspace{0.17em}{f}_{k}({\text{x}}_{i})\ge 1,\hfill \\ \text{no}-\text{separable}:\hfill & {f}_{yi}({\text{x}}_{i})-\underset{\begin{array}{c}k\ne {y}_{i}\\ k=1,\dots ,K\end{array}}{\text{max}}\hspace{0.17em}{f}_{k}({\text{x}}_{i})\ge 1-{\xi}_{i}\hfill \end{array}$$

(3) (4)

For linear classification, we assume *f** _{k}*(x) =

$$\begin{array}{ll}\underset{\beta ,{\beta}_{0},\xi}{\text{min}}\hfill & \sum _{i=1}^{n}{\xi}_{i}+\lambda \sum _{k=1}^{K}{\Vert {\beta}_{k}\Vert}^{2}\hfill \\ \text{subject\hspace{0.17em}to}:\hfill & {f}_{yi}({\text{x}}_{i})-\underset{k\ne {y}_{i}}{\text{max}}\hspace{0.17em}{f}_{k}({\text{x}}_{i})\ge 1-{\xi}_{i},\hfill \\ \hspace{0.17em}\hfill & \xi \ge 0,\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\forall i.\hfill \end{array}$$

(5)

To avoid estimation redundancy, the constraint ∑_{k}_{=1}^{K}*f** _{k}* =0 is often invoked. In (5), ∑

Crammer and Singer^{8} imposed *L*_{2} penalty on the coefficients *β* in (5). The resulting solution utilizes all variables, which may diminish the prediction accuracy when there are many redundant noise variables. In the following sections, we utilize the same loss function but suggest different penalty forms to control model complexity and achieve sparse solutions. In particular, we investigate four different penalties: *L*_{1} penalty, adaptive *L*_{1} penalty, sup-norm penalty and adaptive sup-norm penalty, and discuss computational algorithms for each type of regularization.

**L**_{1}**Penalty:** The *L*_{1} penalty is also known as LASSO penalty.^{18} The MSVM learning with *L*_{1} penalty solves:

$$\begin{array}{ll}\underset{\beta ,{\beta}_{0},\xi}{\text{min}}\hfill & \sum _{i=1}^{n}{\xi}_{i}+\lambda \sum _{k=1}^{K}\sum _{j=1}^{p}\mid {\beta}_{kj}\mid \hfill \\ \text{subject\hspace{0.17em}to}:\hfill & {f}_{yi}({\text{x}}_{i})-\underset{k\ne {y}_{i}}{max}\hspace{0.17em}{f}_{k}({\text{x}}_{i})\ge 1-{\xi}_{i},\hfill \\ \hspace{0.17em}\hfill & {\xi}_{i}\ge 0,\hspace{0.17em}\forall i.\hfill \end{array}$$

(6)

To eliminate the absolute operation in (6), define | *β** _{kj}* | =

$$\begin{array}{ll}\underset{\beta ,{\beta}_{0},\xi}{\text{min}}\hfill & \sum _{i=1}^{n}{\xi}_{i}+\lambda \sum _{k=1}^{K}\sum _{j=1}^{p}({\beta}_{kj}^{+}+{\beta}_{kj}^{-})\hfill \\ \text{s}.\text{t}.:\hfill & \sum _{j=1}^{p}({\beta}_{yj}^{+}-{\beta}_{yj}^{-}){x}_{ij}-\sum _{j=1}^{p}({\beta}_{kj}^{+}-{\beta}_{kj}^{-}){x}_{ij}\ge 1-{\xi}_{i},\hfill \\ \hspace{0.17em}\hfill & \text{for\hspace{0.17em}}i=1,\dots ,n;\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}k=1,\dots ,K,\hspace{0.17em}k\ne {y}_{i}\hfill \\ \hspace{0.17em}\hfill & \sum _{k=1}^{K}{\beta}_{k,0}=0;\sum _{k=1}^{K}({\beta}_{kj}^{+}-{\beta}_{kj}^{-})=0,\hspace{0.17em}j=1,\dots ,p\hfill \\ \hspace{0.17em}\hfill & {\beta}_{kj}^{+}\ge 0,\hspace{0.17em}{\beta}_{kj}^{-}\ge 0,\hspace{0.17em}{\xi}_{i}\ge 0,\hspace{0.17em}\forall k,j,i.\hfill \end{array}$$

(7)

**Adaptive L**_{1}**Penalty:** The adaptive *L*_{1} penalty, also known as the adaptive LASSO, was first studied in various regression models.^{19}^{–}^{21} Instead of applying the same penalty to coefficients, the adaptive *L*_{1} penalty assigns different penalties to coefficients adaptively: large coefficients receive small penalties, while small coefficients receive large penalties. In this way, large coefficients can be protectively preserved during the selection process and small coefficients are decreased to zero more, resulting more sparse models. We propose the adaptive *L*_{1} MSVM by solving the following optimization problem:

$$\begin{array}{ll}\underset{\beta ,{\beta}_{0},\xi}{\text{min}}\hfill & \sum _{i=1}^{n}{\xi}_{i}+\lambda \sum _{k=1}^{K}\sum _{j=1}^{p}{W}_{kj}\mid {\beta}_{kj}\mid \hfill \\ \text{subject\hspace{0.17em}to}:\hfill & {f}_{yi}({\text{x}}_{i})-\underset{k\ne yi}{\text{max}}\mathrm{^p\hspace{0.17em}^p}{f}_{k}({\text{x}}_{i})\ge 1-{\xi}_{i},\hfill \\ \hspace{0.17em}\hfill & {\xi}_{i}\ge 0,\hspace{0.17em}\forall i.\hfill \end{array}$$

(8)

Choices of weights in (8) are essential to adaptive procedures. We propose the construction of weights as *W** _{kj}* = |

$$\underset{\beta ,{\beta}_{0},\xi}{min}\mathrm{\hspace{0.17em}\u200a\u200a}\mathrm{\hspace{0.17em}\u200a\u200a}\mathrm{\hspace{0.17em}\u200a\u200a}\sum _{i=1}^{n}{\xi}_{i}+\lambda \sum _{k=1}^{K}\sum _{j=1}^{p}\frac{{\beta}_{kj}^{+}+{\beta}_{kj}^{-}}{\mid {\tilde{\beta}}_{kj}\mid}.$$

(9)

**Sup-norm Penalty:** In *K*-class learning problems, we need to fit *K* functions (*f*_{1}(x), …, *f** _{K}*(x)). These functions are associated with a

$$\begin{array}{ll}\underset{\beta ,{\beta}_{0},\xi}{\text{min}}\hfill & \sum _{i=1}^{n}{\xi}_{i}+\lambda \sum _{j=1}^{p}{\eta}_{j}\hfill \\ \text{s}.\text{t}.:\hfill & \sum _{j=1}^{p}({\beta}_{yj}^{+}-{\beta}_{yj}^{-}){x}_{ij}-\sum _{j=1}^{p}({\beta}_{kj}^{+}-{\beta}_{kj}^{-}){x}_{ij}\ge 1-{\xi}_{i},\hfill \\ \hspace{0.17em}\hfill & \text{for\hspace{0.17em}}i=1,\dots ,n;\mathrm{\hspace{0.17em}\u200a\u200a}k=1,\dots ,K,\hspace{0.17em}k\ne {y}_{i},\hfill \\ \hspace{0.17em}\hfill & {\eta}_{j}\ge {\beta}_{kj}^{+}+{\beta}_{kj}^{-},k=1,\dots ,K;\hspace{0.17em}j=1,\dots ,p,\hfill \\ \hspace{0.17em}\hfill & \sum _{k=1}^{K}{\beta}_{k,0}=0;\sum _{k=1}^{K}({\beta}_{kj}^{+}-{\beta}_{kj}^{-})=0,\hspace{0.17em}j=1,\dots ,p\hfill \\ \hspace{0.17em}\hfill & {\beta}_{kj}^{+}\ge 0,{\beta}_{kj}^{-}\ge 0,{\eta}_{j}\ge 0,{\xi}_{i}\ge 0,\forall k,j,i.\hfill \end{array}$$

(10)

**Adaptive Sup-norm Penalty:** The adaptive sup-norm penalty shares the same motivation as the adaptive *L*_{1} penalty: important variables are given small penalties and noise variables are given large penalties. In particular, we replace the second term in (10) by *λ*∑_{j}_{=1}^{p}*w*_{j}*η** _{j}*. To Construct the weights, we propose to use

$$\underset{\beta ,{\beta}_{0},\xi}{\text{min}}\mathrm{\hspace{0.17em}\u200a\u200a}\mathrm{\hspace{0.17em}\u200a\u200a}\mathrm{\hspace{0.17em}\u200a\u200a}\sum _{i=1}^{n}{\xi}_{i}+\lambda \sum _{j=1}^{p}\frac{{\eta}_{j}}{{\tilde{\eta}}_{j}}.$$

(11)

We have given four new regularization forms of MSVM for variable selection in linear classification. Next, we show that these methods can be easily extended to the non-linear case by using the basis expansion approach. Let **h**(**x**) = {*h*_{1}(x), *h*_{2}(x), …, *h** _{q}*(x)} be a dictionary of basis functions transformed from

The choice of tuning parameter λ is crucial in the above regularization problems, since it controls the trade-off between the training error and generalization performance of classifiers. It also has an impact on sparsity of the solution. To select the optimal λ, we use a validation set in simulated examples and use five-fold cross validation in real data analysis. A fine grid search is conducted over a wide range of values of λ, and the best λ is identified as the one which gives the least tuning error or cross validation error.

We illustrate the performance of new methods for prediction and variable selection in both linear and nonlinear settings using simulated data sets. The Bayes rule and *L*_{2} MSVM of Crammer and Singer^{8} (denoted as “L2 MSVM (C&S)”) are also included. The Bayes rule is the optimal classification rule if the underlying distribution of the data is known. It serves as the golden standard to evaluate the performance of the trained classifiers. We conducted 100 simulations for each classification method and report the average performance of the methods, including test error on test samples, model size, and the total selection frequency of individual inputs in 100 runs.

This is a linear classification problem with *p* = 20 and *k* = 4. The first two components of x from class k are from *N*(*μ** _{k}*,

Table 1 reports the selection frequency of each variable over 100 runs. Important variables x_{1} and x_{2} are never missed by any method. The rest of the variables, either noise variables or informative but redundant variables, are selected with different frequencies by different methods. The adaptive sup-norm MSVM selects noise or informative but redundant variables with fewer than 10 times in 100 runs, which is a much lower selection frequency than that of *L*_{1} MSVM. Furthermore, all methods except *L*_{2} MSVM can handle informative but redundant variables very well. The *x′*_{3} and *x′*_{4}, which are correlated to important variables *x*_{1} and *x*_{2} with ρ_{1} = 0.8 and ρ_{2} = 0.9, are selected fewer than 15 times in 100 runs using any of four proposed methods, which is fewer most noise variables.

Table 2 summarizes the average test error and model size of 100 runs. The numbers in the parentheses are standard errors (SE) of the mean of test errors from 100 simulations. The Bayes error (i.e., the optimum classification error) is 0.246 and *L*_{2} MSVM has test error 0.296. All new methods are statistically better than *L*_{2} MSVM, with adaptive sup-norm MSVM giving the smallest test error 0.255. Adaptive penalties tend to enhance model sparsity, and the adaptive sup-norm yields the most compact model of size 3.25 on average. Overall, adaptive sup-norm MSVM is the best for both variable selection and prediction accuracy.

Consider a nonlinear three-class example in a large *p* small *n* setting. Generate x *R*^{20} as following: (*x*_{1}, *x*_{2}) are uniformly distributed in the square [−3,3] × [−3,3], and the remaining 18 components *x*_{3}, …, *x*_{20} are i.i.d. from *N*(0, 2). Define the three functions:

$$\begin{array}{l}{f}_{1}(\text{x})=-2{x}_{1}+0.2{x}_{1}^{2}-0.4{x}_{2}^{2}+0.2,\\ {f}_{2}(\text{x})=-0.4{x}_{1}^{2}+0.8{x}_{2}^{2}-0.4,\\ {f}_{3}(\text{x})=2{x}_{1}+0.2{x}_{1}^{2}-0.4{x}_{2}^{2}+\mathrm{0.2.}\end{array}$$

For **x**, its class label is assigned using the multinomial sampling (*p*_{1}(x), *p*_{2}(x), *p*_{3}(x)) with *p** _{k}*(x)

Table 3 reports the average test error and model size over 100 runs for each method. Note that *L*_{1} MSVM and sup-norm MSVM are equivalent for three-class problems.^{15} The Bayes error is 0.120, *L*_{2} MSVM has the test error 0.441, and all the new methods show a significant improvement over *L*_{2} MSVM. Adaptive sup-norm MSVM gives the smallest error 0.147, very close to the Bayes error. *L*_{2} MSVM does not perform well here, mainly due to a large number of noise variables contained in data. With regard to variable selection, *L*_{2} MSVM includes almost all variables in the fitted model, and the average model size is 221.87. The new MSVMs produce much smaller models while identifying the three important variables correctly. Adaptive sup-norm MSVM yields the most parsimonious model of size 8.58 on average. Adaptive *L*_{1} MSVM works similarly, with test error 0.152 and on average, selecting nine variables. Again, adaptively-weighted penalties are shown to produce more sparsity than equally-weighted penalties.

Table 4 summarizes the selection frequency of each term in the adaptive sup-norm MSVM model: those of main effects given in the first row, those of quadratic terms given on the main diagonal line, and those of 190 two-way interaction terms given in intersections of the corresponding rows and columns. We observe that the three important effects (*x*_{1}, *x*_{1}^{2}, *x*_{2}^{2}) are always selected, and noise variables are selected with a low frequency (fewer than 10 times in 100 runs).

One important application of our new methods is classification and variable selection of microarray or other “-omics” data. We analyze two cancer gene expression data sets: leukemia data^{16} and small round blue cell tumor data.^{17} In addition to distinguishing multi-type tumors, another primary goal is to identify signature genes which are responsible for classification and helpful for understanding the underlying mechanism of cancer. Since microarray data typically represent a large number of genes (*p* >> *n*), one common practice is selecting relevant genes before building a classifier. A popular approach of gene selection is gene ranking based on univariate statistics such as F-statistic and *p*-value. The weaknesses of ranking methods include: (1) classification and variable selection are performed separately and (2) the correlation and interaction among genes cannot be fully taken into account. However, rank-based screening has been found useful at an initial step by filtering irrelevant features and therefore beneficial to the refined variable selection process that follows, as in Lee et al.,^{7} Wang and Shen,^{13} Zhang et al.,^{15} and so on. Pre-screening is commonly used in microarray data analysis to remove genes which do not contribute expression changes across the samples (i.e., those that are considered flat), as uninformative genes add noise to the downstream analysis. In practice, it is recommended to conduct two-stage modeling: feature screening (based on simple tests) followed by formal model building (based on more sophisticated variable selection procedures) to enhance the final variable selection results. We adopted the two-stage modeling in our real data analysis. Compared to univariate analysis done in most gene-ranking approaches, our new classification methods conduct joint selection and can account for gene-gene interactions naturally. The following results show that the methods effectively select important genes and achieve high accuracy at the same time. Therefore, they provide alternative promising tools for cancer classification using gene expression data.

The leukemia study^{16} analyzed human bone marrow samples using oligonucleotide microarrays produced by Affymetrix. The data consist of 7129 probe sets, which represent 6817 human genes and 72 samples in three classes: acute myeloid leukemia (AML), T-cell, and B-cell acute lymphoblastic leukemia (ALL_{–}T and ALL_{–}B). There are 38 training samples (19 ALL_{–}B, 8 ALL_{–}T, 11 AML) and 34 test samples (19 ALL_{–}B, 1 ALL_{–}T, 14 AML). We preprocessed the data following Dudiot et al.^{22} and selected the subset of 742 genes by F-ratio test for memory and computational efficiency. Then, *L*_{2} MSVM and four new approaches were applied for gene selection as well as model building. Variable selection and parameter choice during model building were done strictly on the training data set.

Table 5 shows that *L*_{2} MSVM only misclassifies 1 out of 34 test samples, but its solution depends on a large number of genes (429 genes). In contrast, our new methods select a very small set of genes (14, 9, 4 genes for *L*_{1} MSVM, adaptive *L*_{1} MSVM, and adaptive sup-norm MSVM respectively) while giving comparable accuracy. Table 6 shows a significant overlap in the selection: all four genes selected by adaptive sup-norm MSVM are also selected by others, and 8 of 9 genes selected by adaptive *L*_{1} MSVM are selected by *L*_{1} MSVM. Not all these genes are top-ranked by F-test, which does not take into account gene interactions.

To interpret the role of selected genes in classification, we now examine the three discriminant functions given by adaptive sup-norm MSVM:

$$\begin{array}{l}{\widehat{f}}_{\text{ALL}\_\text{B}}=-0.037*\text{TCRB}-0.330*\text{MAL}-0.640*\text{CST}3+0.091*\text{TCL}1,\\ {\widehat{f}}_{\text{ALL}\_\text{T}}=0.162*\text{TCRB}+0.450*\text{MAL},\\ {\widehat{f}}_{\text{AML}}=-0.124*\text{TCRB}-0.121*\text{MAL}+0.640*\text{CST}3-0.091*\text{TCL}1.\end{array}$$

Each test sample has three predicted decision values (_{ALL–B}, _{ALL–T}, _{AML}) and assigned to a class with the largest value. T-cell receptor, beta cluster (*TCRB*), and *MAL* genes have positive coefficients in _{ALL–T} and negative coefficients in _{ALL–B}, and _{AML,} and are useful to separate ALL_{–}T from the other two classes. This pattern is also confirmed by Figure 1, which illustrates the hierarchical clustering structure of the data corresponding to the four selected probe sets (i.e., four genes). *TCRB* (X00437_{–}s_{–}at) and *MAL* (X76223_{–}s_{–}at) have high expression values (in red) for most ALL_{–}T samples and low expression (in green) for most of the ALL_{–}B and AML samples. The relevance of the *MAL* gene with T-cell ALL was reported in the literature. For example, the *MAL* gene shows significant higher expression level in acute T-cell leukemia/lymphoma than in chronic T-cell leukemia.^{23} Gene Cystatin C (*CST3*) is helpful in distinguishing all three classes, since its coefficient is zero in _{ALL–T}, is negative in _{ALL–B}, and is positive in _{AML}. Correspondingly, gene *CST3* (M27891_{–}at) has low values in most ALL_{–}B samples but high values in most AML samples in Figure 1. *CST3* is one of the genes reported by Golub,^{16} which can differentiate the ALL vs. AML. Gene T-cell leukemia/lymphoma 1 (*TCL1*; X82240_{–}rna1_{–}at) reveals the opposite patterns, which has high values in most ALL_{–}B samples but low values in most AML and ALL_{–}T samples (Fig. 1). It is reported that *TCL1* shows significant higher expression during pre-B-cell acute lymphoblastic leukemia progression.^{24} All four genes have been individually or jointly identified as one of the predictor genes to differentiate between AML and ALL or among AML, ALL_{–}T and ALL_{–}B in the leukemia study using various analysis methods.^{25}^{–}^{29} In particular, a penalized likelihood method,^{29} called structured polychotomous machine, selected the exactly same four genes with the same prediction accuracy obtained in this study.

The SRBCT data are from cDNA microarrays using standard protocols of the National Human Genome Research Institute (NHGRI).^{17} There are 63 training and 20 test samples, categorized into 4 classes: neuroblastoma (NB), rhabdomyosarcoma (RMS), non-Hodgkin lymphoma (NHL), and the Ewing family of tumors (EWS). We began with 2308 genes available at http://research.nhgri.nih.gov/microarray/Supplement/, and conducted gene screening with F-ratio tests. We include the top 333 and bottom 300 genes for analysis and show results in Table 7. Variable selection and parameter choice during model building were done strictly on the training data set.

We observe that all the new methods have test error 0 except L1-norm SVM, which misclassifies 1 out of 20 test samples. With regard to gene selection, all the new methods successfully exclude the bottom 300 genes from the final model. The number of selected genes ranges between 28–36, with adaptive sup-norm MSVM selecting the smallest number of genes. Compared to other MSVM methods applied by Lee et al.^{14} and Zhang et al.^{15} on the same data set, our new methods give better or comparable prediction accuracy overall and they select a smaller number of genes. When examining the genes selected by the four new methods, we observe a large overlap across the final lists. In particular, 10 genes are commonly selected by all four methods, and 13 genes are selected by three methods, demonstrating general agreement among different variable selection schemes.

We proposed to improve the standard MSVM of Crammer and Singer^{8} by constructing a new class of regularization methods which incorporates variable selection in the model learning. Performance of the new methods is demonstrated via numerical studies. Compared to the standard *L*_{2} MSVM, the new methods are shown to achieve high prediction accuracy and are able to build sparse and more interpretable models. In both simulations and real data analyses, adaptive sup-norm MSVM shows the best performance among all the methods with regard to either variable selection or prediction accuracy. The combination of high accuracy and effective selection makes the new methods attractive for high-dimensional data analysis and powerful tools for cancer biomarker discovery based on gene expression data.

**Authors Contributions**

HZ and LH designed the penalized MSVMs. LH developed and implemented the method. HZ supervised the study. ZZ and PB provided valuable suggestions and evaluated the results. All authors contributed to writing this paper; proofread and approved the final manuscript.

**Competing Interests**

Author(s) disclose no potential conflicts of interest.

**Disclosures and Ethics**

As a requirement of publication the authors have provided signed confirmation of their compliance with ethical and legal obligations including but not limited to compliance with ICMJE authorship and competing interests guidelines, that the article is neither under consideration for publication nor published elsewhere, of their compliance with legal and ethical guidelines concerning human and animal research participants (if applicable), and that permission has been obtained for reproduction of any copyrighted material. This article was subject to blind, independent, expert peer review. The reviewers reported no competing interests.

**Funding**

This work was supported by National Science Foundation [DMS0645293 to HZ], National Institute of Health [R01CA085848 to HZ; R24GM078233, RC2GM092729 to ZZ], and National Institute of Environmental Health Sciences [ES102345-04 to PB].

1. Boser E, Guyon M, Vapnik V. A training algorithm for optimal margin classifiers. Proceedings of the Fifth Annual Conference on Computational Learning Theory; Pittsburgh, PA. 1992. pp. 144–52.

2. Cortes C, Vapnik V. Support-vector networks. Machine Learning. 1995;20:273–9.

3. Zhu J, Hastie T, Rosset S, Tibshirani R. 1-norm support vector machines. Neural Information Processing Systems. 2003;16:49–56.

4. Zhang HH, Ahn J, Lin X, Park C. Gene selection using support vector machines with non-convex penalty. Bioinformatics. 2006;22:88–95. [PubMed]

5. Dietterich TG, Bakiri G. Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research. 1995;2:263–86.

6. Allwein EL, Schapire RE, Singer Y. Reducing multi-class to binary: A unifying approach for margin classifiers. Machine Learning: Proceedings of the Seventeenth International Conference; 2000.

7. Lee Y, Lin Y, Wahba G. Multicategory support vector machines, theory, and application to the classification of microarray data and satellite radiance data. Journal of the American Statistical Association. 2004;99:465:67–81.

8. Crammer K, Singer Y. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of Machine Learning Research. 2001;2:265–92.

9. Weston J, Watkins C. Support vector machines for multi-class pattern recognition. 1999:219–24.

10. Liu Y, Shen X. Multicategory psi-learning. Journal of the American Statistical Association. 2006;101:474–509.

11. Guyon I, Weston J, Barnhill S, Vapnik V. Gene Selection for Cancer Classification using Support Vector Machines. Machine Learning. 2002;46:389–422.

12. Bradley PS, Mangasarian OL. Feature selection via concave minimization and support vector machines. Proceedings of the 13th International Conference on Machine Learning; CA. 1998. pp. 82–90.

13. Wang L, Shen X. On L1-norm multi-class support vector machines: methodology and theory. Journal of the American Statistical Association. 2007;102:583–94.

14. Lee Y, Kim Y, Lee S, Koo J. Structured multicategory support vector machines with analysis of variance decomposition. Biometrika. 2006;93:555–71.

15. Zhang HH, Liu Y, Wu Y, Zhu J. Variable selection for multicategory SVM via sup-norm regularization. Electronic Journal of Statistics. 2008;2:149–67.

16. Golub TR, Slonim DK, Tamayo P, et al. Molecular classification of cancer: class discovery and class prediction by gene expression monitoring. Science. 1999;286:531–7. [PubMed]

17. Khan J, Wei JS, Ringner M, et al. Classification and diagnostic prediction of cancers using gene expression profiling and artificial neural networks. Nature Medicine. 2001;7:673–9. [PMC free article] [PubMed]

18. Tibshirani R. Regression shrinkage and selection via the lasso. Journal of Royal Statistical Society, B. 1996;58:267–88.

19. Zou H. The adaptive lasso and its oracle properties. Journal of the American Statistical Association. 2006;101:1418–29.

20. Zhang HH, Lu W. Adaptive-LASSO for Cox’s proportional hazard model. Biometrika. 2007;94:691–703.

21. Wang H, Li G, Jiang G. Robust regression shrinkage and consistent variable selection via the LAD-LASSO. Journal of Business & Economics Statistics. 2007;25:347–55.

22. Dudoit S, Fridlyand J, Speed TP. Comparison of discrimination methods for the classification of tumors using gene expression data. Journal of the American Statistical Association. 2002;97:77–87.

23. Kohno T, Moriuchi R, Katamine S, Yamada Y, Tomonaga M, TM Identification of genes associated with the progression of adult T cell leukemia (ATL) Jpn J Cancer Res. 2000;91(11):1103–10. [PubMed]

24. Fears S, Chakrabarti SR, Nucifora G, Rowley JD. Difierential expression of TCL1 during pre-B-cell acute lymphoblastic leukemia progression. Cancer Genet Cytogenet. 2002;135(2):110–9. [PubMed]

25. Huang L. An integrated method for cancer classification and rule extraction from microarray data. J Biomed Sci. 2009;16:25. [PMC free article] [PubMed]

26. Krishnapuram B, Carin L, Hartemink A. Joint classifier and feature optimization for comprehensive cancer diagnosis using gene expression data. J Comput Biol. 2004;11(2–3):227–42. [PubMed]

27. Reverter F, Vegas E, Sanchez P. Mining gene expression profiles: an integrated implementation of kernel principal component analysis and singular value decomposition. Genomics Proteomics Bioinformatics. 2010;8(3):200–10. [PubMed]

28. Wang H, Huang D. A gene selection algorithm based on the gene regulation probability using maximal likelihood estimation. Biotechnol Lett. 2005;27(8):597–603. [PubMed]

29. Koo JY, Sohn I, Kim S, Lee JW. Structured polychotomous machine diagnosis of multiple cancer types using gene expression. Bioinformatics. 2006;22(8):950–8. [PubMed]

Articles from Cancer Informatics are provided here courtesy of **SAGE Publications**

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |