# Multinomial Regression with Elastic Net Penalty and Its Grouping Effect in Gene Selection

Authors: Liuyuan Chen; Jie Yang; Juntao Li; Xiaoyu Wang
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

For the multiclass classification problem of microarray data, a new optimization model named multinomial regression with the elastic net penalty was proposed in this paper. By combining the multinomial likeliyhood loss and the multiclass elastic net penalty, the optimization model was constructed, which was proved to encourage a grouping effect in gene selection for multiclass classification.


---

## Body

## 1. Introduction

Support vector machine [1], lasso [2], and their expansions, such as the hybrid huberized support vector machine [3], the doubly regularized support vector machine [4], the 1-norm support vector machine [5], the sparse logistic regression [6], the elastic net [7], and the improved elastic net [8], have been successfully applied to the binary classification problems of microarray data. However, the aforementioned binary classification methods cannot be applied to the multiclass classification easily. Hence, the multiclass classification problems are the difficult issues in microarray classification [9–11].Besides improving the accuracy, another challenge for the multiclass classification problem of microarray data is how to select the key genes [9–15]. By solving an optimization formula, a new multicategory support vector machine was proposed in [9]. It can be successfully used to microarray classification [9]. However, this optimization model needs to select genes using the additional methods. To automatically select genes during performing the multiclass classification, new optimization models [12–14], such as the L
1 norm multiclass support vector machine in [12], the multicategory support vector machine with sup norm regularization in [13], and the huberized multiclass support vector machine in [14], were developed.Note that the logistic loss function not only has good statistical significance but also is second order differentiable. Hence, the regularized logistic regression optimization models have been successfully applied to binary classification problem [15–19]. Multinomial regression can be obtained when applying the logistic regression to the multiclass classification problem. The emergence of the sparse multinomial regression provides a reasonable application to the multiclass classification of microarray data that featured with identifying important genes [20–22]. By using Bayesian L
1 regularization, the sparse multinomial regression model was proposed in [20]. By adopting a data augmentation strategy with Gaussian latent variables, the variational Bayesian multinomial probit model which can reduce the prediction error was presented in [21]. By using the elastic net penalty, the regularized multinomial regression model was developed in [22]. It can be applied to the multiple sequence alignment of protein related to mutation. Although the above sparse multinomial models achieved good prediction results on the real data, all of them failed to select genes (or variables) in groups.For the multiclass classification of the microarray data, this paper combined the multinomial likelihood loss function having explicit probability meanings [23] with multiclass elastic net penalty selecting genes in groups [14], proposed a multinomial regression with elastic net penalty, and proved that this model can encourage a grouping effect in gene selection at the same time of classification.


## 2. Problem Formulation and Preliminary

Given a training data set ofK-class classification problem (
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
n
,
y
n
), where x
i
=
(
x
i
1
,
x
i
2
,
…
,
x
i
p
) represents the input vector of the ith sample and y
i
∈
{
1,2
,
…
,
K
} represents the class label corresponding to x
i. For the microarray data, n and p represent the number of experiments and the number of genes, respectively. Restricted by the high experiment cost, only a few (less than one hundred) samples can be obtained with thousands of genes in one sample. Let Y
=
(
y
1
,
…
,
y
n
)
T and X
=
(
x
(
1
)
,
x
(
2
)
,
…
,
x
(
p
)
), where x
(
j
)
=
(
x
1
j
,
…
,
x
n
j
)
T, j
=
1
,
…
,
p. Without loss of generality, it is assumed that
(1)
∑
i
=
1
n
‍
y
i
=
0
,
1
n
∑
i
=
1
n
‍
x
i
j
=
0
,
∑
i
=
1
n
‍
x
i
j
2
=
1
.For the binary classification problem, the class labels are assumed to belong toL
=
{
1
,
-
1
}. The logistic regression model represents the following class-conditional probabilities; that is,
(2)
log
⁡
Pr
(
y
i
=
+
1
∣
x
)
Pr
(
y
i
=
-
1
∣
x
)
=
b
+
w
T
x
,
and then
(3)
Pr
(
y
i
=
+
1
∣
x
)
=
1
1
+
e
-
(
b
+
w
T
x
)
,
Pr
(
y
i
=
-
1
∣
x
)
=
1
1
+
e
+
(
b
+
w
T
x
)
=
1
-
Pr
(
y
i
=
+
1
∣
x
)
.
According to the common linear regression model, Y can be predicted as
(4)
Y
^
=
w
^
X
=
∑
j
=
1
p
‍
w
^
(
j
)
x
(
j
)
+
b
^
,
where b
^ represents bias and w
^
=
(
w
^
(
1
)
,
…
,
w
^
(
p
)
)
T represents the parameter vector.In this paper, we pay attention to the multiclass classification problems, which imply thatK
≥
3. Let f
=
(
f
1
,
f
2
,
…
,
f
K
) be the decision function, where f
k
(
x
)
=
b
k
+
w
k
T
x
,
(
k
=
1,2
,
…
,
K
). The multiclass classifier can be represented as
(5)
ϕ
(
x
)
=
arg
max
⁡
k
=
1,2
,
…
,
K
f
k
(
x
)
.
Let b
=
(
b
1
,
⋯
,
b
K
)
T and
(6)
w
=
{
w
11
w
12
⋯
w
1
p
w
21
w
22
⋯
w
2
p
⋮
⋮
⋮
⋮
w
K
1
w
K
2
⋯
w
K
p
}
.
For convenience, we further let w
k
=
(
w
k
1
,
…
,
w
k
p
)
T and w
(
j
)
=
(
w
1
j
,
…
,
w
K
j
)
T represent the kth row vector and jth column vector of the parameter matrix w. Then extending the class-conditional probabilities of the logistic regression model to (
K
-
1
)-logits, we have the following formula:
(7)
log
⁡
Pr
(
y
i
=
k
∣
x
)
Pr
(
y
i
=
K
∣
x
)
=
b
k
+
w
k
T
x
(
k
=
1,2
,
…
,
K
-
1
)
,
where (
b
k
,
w
k
) represent a pair of parameters which corresponds to the sample (
Y
=
k
∣
x
), and b
k
∈
R
1, w
k
∈
R
p. Similarly, we can construct the Kth as
(8)
log
⁡
Pr
(
y
i
=
K
∣
x
)
Pr
(
y
i
=
K
∣
x
)
=
log
⁡
1
=
0
log
⁡
Pr
(
y
i
=
K
∣
x
)
Pr
(
y
i
=
K
∣
x
)
=
b
K
+
w
K
T
x
holds if and only if (
b
K
,
w
K
)
=
(
0
,
0
→
). It can be easily obtained that
(9)
1
=
Pr
(
y
i
=
1
∣
x
)
+
Pr
(
y
i
=
2
∣
x
)
+
⋯
+
Pr
(
y
i
=
K
∣
x
)
ii
=
[
e
b
1
+
w
1
T
x
+
e
b
2
+
w
2
T
x
+
⋯
+
e
b
K
+
w
K
T
x
]
·
Pr
(
y
i
=
K
∣
x
)
.
that is,
(10)
Pr
(
y
i
=
K
∣
x
)
=
1
∑
k
=
1
K
e
(
b
k
+
w
k
T
x
)
.
It should be noted that (
b
K
,
w
K
)
=
(
0
,
0
→
) if k
=
K. Therefore, the class-conditional probabilities of multiclass classification problem can be represented as
(11)
Pr
(
y
i
=
k
∣
x
)
=
e
b
k
+
w
k
T
x
∑
k
=
1
K
e
(
b
k
+
w
k
T
x
)
.


## 3. Main Results

### 3.1. Multinomial Regression with the Multiclass Elastic Net Penalty

Following the idea of sparse multinomial regression [20–22], we fit the above class-conditional probability model by the regularized multinomial likelihood. Let p
k
(
x
i
)
=
Pr
(
y
i
=
k
∣
x
i
). It is easily obtained that
(12)
p
y
i
(
x
i
)
=
e
(
b
y
i
+
w
y
i
T
x
i
)
∑
k
=
1
K
e
(
b
k
+
w
k
T
x
i
)
.
Hence,
(13)
1
n
∑
i
=
1
n
‍
log
⁡
p
y
i
(
x
i
)
=
1
n
[
log
⁡
p
y
1
(
x
1
)
+
log
⁡
p
y
2
(
x
2
)
+
⋯
+
log
⁡
p
y
n
(
x
n
)
]
=
1
n
[
log
⁡
e
(
b
y
1
+
w
y
1
T
x
1
)
∑
k
=
1
K
e
(
b
k
+
w
k
T
x
1
)
+
log
⁡
e
(
b
y
2
+
w
y
2
T
x
2
)
∑
k
=
1
K
e
(
b
k
+
w
k
T
x
2
)
hhhhhhh
+
⋯
+
log
⁡
e
(
b
y
n
+
w
y
n
T
x
n
)
∑
k
=
1
K
e
(
b
k
+
w
k
T
x
n
)
]
=
1
n
[
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
n
)
(
b
y
1
+
w
y
1
T
x
1
)
+
⋯
+
(
b
y
n
+
w
y
n
T
x
n
)
hhhiiiiiiii
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
1
)
-
⋯
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
n
)
]
=
1
n
[
(
b
y
1
+
w
y
1
T
x
1
)
+
⋯
+
(
b
y
n
+
w
y
n
T
x
n
)
]
iiiiiii
-
1
n
∑
i
=
1
n
‍
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
.
Let
(14)
y
i
k
=
I
(
y
i
=
k
)
=
{
1
,
y
i
=
k
,
0
,
y
i
≠
k
.
Then (13) can be rewritten as
(15)
1
n
∑
i
=
1
n
‍
∑
k
=
1
K
‍
y
i
k
(
b
k
+
w
k
T
x
i
)
-
1
n
∑
i
=
1
n
‍
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
=
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
‍
y
i
k
(
b
k
+
w
k
T
x
i
)
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
]
.
Note that
(16)
log
⁡
p
y
i
(
x
i
)
=
log
⁡
e
(
b
y
i
+
w
y
i
T
x
i
)
∑
k
=
1
K
e
(
b
k
+
w
k
T
x
i
)
<
log
⁡
1
=
0
,
-
1
n
∑
i
=
1
n
‍
log
⁡
p
y
i
(
x
i
)
>
0
.
Hence, the multinomial likelihood loss function can be defined as
(17)
l
(
{
b
k
,
w
k
}
1
K
)
=
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
‍
y
i
k
(
b
k
+
w
k
T
x
i
)
hhhhhhhhhhhhhhhhhh
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
]
.In order to improve the performance of gene selection, the following elastic net penalty for the multiclass classification problem was proposed in [14]
(18)
J
(
b
,
w
)
=
λ
2
∑
k
=
1
K
‍
∑
j
=
1
p
‍
w
k
j
2
+
λ
1
∑
k
=
1
K
‍
∑
j
=
1
p
‍
|
w
k
j
|
.
By combing the multiclass elastic net penalty (18) with the multinomial likelihood loss function (17), we propose the following multinomial regression model with the elastic net penalty:
(19)
arg
min
⁡
(
b
,
w
)
{
∑
j
=
1
p
‍
|
w
k
j
|
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
‍
y
i
k
(
b
k
+
w
k
T
x
i
)
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
]
h
h
h
h
h
h
h
h
h
+
λ
2
∑
k
=
1
K
‍
∑
j
=
1
p
‍
w
k
j
2
+
λ
1
∑
k
=
1
K
‍
∑
j
=
1
p
‍
|
w
k
j
|
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
‍
y
i
k
(
b
k
+
w
k
T
x
i
)
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
]
}
,
where λ
1
,
λ
2 represent the regularization parameter. Note that (
b
K
,
w
K
)
=
(
0
,
0
→
). Hence, the optimization problem (19) can be simplified as
(20)
arg
min
⁡
(
b
,
w
)
{
(
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
|
w
k
j
|
)
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
-
1
‍
y
k
i
(
b
k
+
w
k
T
x
i
)
hhhhhhhhhhhhhhh
-
log
⁡
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
k
+
w
k
T
x
i
)
)
]
hhhhh
+
λ
2
(
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
w
k
j
2
)
+
λ
1
(
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
|
w
k
j
|
)
}
.


### 3.2. Grouping Effect

For the microarray classification, it is very important to identify the related gene in groups. In the section, we will prove that the multinomial regression with elastic net penalty can encourage a grouping effect in gene selection. To this end, we must first prove the inequality shown in Theorem1.Theorem 1.
Let(
b
^
,
w
^
) be the solution of the optimization problem (19) or (20). For any new parameter pairs which are selected as (
b
*
,
w
*
)
=
(
[
b
-
*
;
0
→
]
,
[
w
k
;
0
→
]
), the following inequality
(21)
|
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
k
*
+
w
k
*
T
x
i
)
)
-
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
^
k
+
w
^
k
T
x
i
)
)
|
≤
∑
k
=
1
K
-
1
‍
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
holds, where b
-
* and b
^
- represent the first K
-
1 rows of vectors b
* and b
^ and w
-
* and w
^
- represent the first K
-
1 rows of matrices w
* and w
^.Proof.
Note that the inequalityn
+
|
m
-
n
|
≥
m holds for the arbitrary real numbers m and n. Hence, the following inequality
(22)
(
b
^
t
+
w
^
t
T
x
i
)
+
|
(
b
t
*
+
w
t
*
T
x
i
)
-
(
b
^
t
+
w
^
t
T
x
i
)
|
≥
(
b
t
*
+
w
t
*
T
x
i
)
holds for any pairs (
b
t
*
,
w
t
*
), (
b
^
t
,
w
^
t
). From (22), it can be easily obtained that
(23)
(
b
^
t
+
w
^
t
T
x
i
)
+
∑
k
=
1
K
-
1
‍
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
≥
(
b
t
*
+
w
t
*
T
x
i
)
.
that is,
(24)
e
(
b
^
t
+
w
^
t
T
x
i
)
+
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
≥
e
(
b
t
*
+
w
t
*
T
x
i
)
.
Note that
(25)
e
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
≥
e
0
=
1
.
Hence, from (24) and (25), we can get
(26)
Δ
1
Δ
2
≤
1
,
where
(27)
Δ
1
=
1
+
e
(
b
1
*
+
w
1
*
T
x
i
)
+
⋯
+
e
(
b
t
*
+
w
t
*
T
x
i
)
+
⋯
+
e
(
b
K
-
1
*
+
w
K
-
1
*
T
x
i
)
,
Δ
2
=
e
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
+
e
(
b
^
1
+
w
^
1
T
x
i
)
+
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
+
⋯
+
e
(
b
^
t
+
w
^
t
T
x
i
)
+
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
+
⋯
+
e
(
b
^
K
-
1
+
w
^
K
-
1
*
T
x
i
)
+
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
.
Equation (26) is equivalent to the following inequality:
(28)
(
1
+
e
(
b
1
*
+
w
1
*
T
x
i
)
+
⋯
+
e
(
b
K
-
1
*
+
w
K
-
1
*
T
x
i
)
)
×
(
·
e
∑
k
=
1
K
-
1
‍
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
[
1
+
e
(
b
^
1
+
w
^
1
T
x
i
)
+
⋯
+
e
(
b
^
K
-
1
+
w
^
K
-
1
T
x
i
)
]
h
h
h
h
·
e
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
)
-
1
≤
1
⟺
log
⁡
1
+
e
(
b
1
*
+
w
1
*
T
x
i
)
+
⋯
+
e
(
b
K
-
1
*
+
w
K
-
1
*
T
x
i
)
1
+
e
(
b
^
1
+
w
^
1
T
x
i
)
+
⋯
+
e
(
b
^
K
-
1
+
w
^
K
-
1
T
x
i
)
i
≤
∑
k
=
1
K
-
1
‍
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
⟺
|
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
k
*
+
w
k
*
T
x
i
)
)
-
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
^
k
+
w
^
k
T
x
i
)
)
|
i
≤
∑
k
=
1
K
-
1
‍
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
.
Hence, inequality (21) holds. This completes the proof.Using the results in Theorem1, we prove that the multinomial regression with elastic net penalty (19) can encourage a grouping effect.Theorem 2.
Give the training data set(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
n
,
y
n
) and assume that the matrix X and vector Y satisfy (1). If the pairs (b
^
,
w
^) are the optimal solution of the multinomial regression with elastic net penalty (19), then the following inequality
(29)
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
≤
2
K
n
λ
2
2
(
1
-
ρ
)
.
holds, where ρ
=
x
(
m
)
T
x
(
l
)
=
∑
i
=
1
n
‍
x
i
m
x
i
l, w
^
(
m
) is the mth column of parameter matrix w
^, and w
^
(
m
) is the lth column of parameter matrix w
^.Proof.
First of all, we construct the new parameter pairs(
b
*
,
w
*
)
=
(
[
b
-
*
;
0
→
]
,
[
w
k
*
;
0
→
]
), where
(30)
b
-
*
=
b
^
-
,
w
k
j
′
*
=
{
1
2
(
w
^
k
m
+
w
^
k
l
)
,
j
′
=
m
,
l
,
w
^
k
j
′
,
j
′
≠
m
,
l
.
Let
(31)
L
¯
=
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
-
1
‍
y
k
i
(
b
k
+
w
k
T
x
i
)
hhhhhhhhhhhhhh
-
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
k
+
w
k
T
x
i
)
)
]
iii
+
λ
2
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
w
k
j
2
+
λ
1
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
|
w
k
j
|
.
Since the pairs (b
^
,
w
^) are the optimal solution of the multinomial regression with elastic net penalty (19), it can be easily obtained that
(32)
0
≤
L
¯
(
λ
1
,
λ
2
,
b
-
*
,
w
-
*
)
-
L
¯
(
λ
1
,
λ
2
,
b
^
-
,
w
^
-
)
.
Note that the function L
k
i
(
b
^
k
,
w
^
k
,
x
i
)
=
b
k
+
w
k
T
x
i is Lipschitz continuous. Hence, we have
(33)
|
L
k
i
(
b
k
*
,
w
k
*
,
x
i
)
-
L
k
i
(
b
^
k
,
w
^
k
,
x
i
)
|
≤
|
(
w
k
*
-
w
^
k
)
T
x
i
|
.
From (33) and (21) and the definition of the parameter pairs (
b
*
,
w
*
), we have
(34)
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
-
1
‍
L
k
i
(
b
k
*
,
w
k
*
,
x
i
)
-
L
k
i
(
b
^
k
,
w
^
k
,
x
i
)
h
h
h
h
h
h
h
h
-
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
k
*
+
w
k
*
T
x
i
)
)
h
h
h
h
h
h
h
h
+
log
⁡
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
^
k
+
w
^
k
T
x
i
)
)
]
≤
|
-
1
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
L
k
i
(
b
k
*
,
w
k
*
,
x
i
)
-
L
k
i
(
b
^
k
,
w
^
k
,
x
i
)
|
+
1
n
∑
i
=
1
n
‍
|
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
k
*
+
w
k
*
T
x
i
)
)
iiiiiiiiiiiiiiiiiiiiiiiiiiiii
-
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
^
k
+
w
^
k
T
x
i
)
)
|
≤
1
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
L
k
i
(
b
k
*
,
w
k
*
,
x
i
)
-
L
k
i
(
b
^
k
,
w
^
k
,
x
i
)
|
+
1
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
≤
1
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
k
*
-
w
^
k
)
T
x
i
|
+
1
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
k
*
-
w
^
k
)
T
x
i
|
=
1
2
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
^
k
m
-
w
^
k
l
)
(
x
i
m
-
x
i
l
)
|
+
1
2
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
^
k
m
-
w
^
k
l
)
(
x
i
m
-
x
i
l
)
|
=
1
2
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
^
k
m
-
w
^
k
l
)
(
x
i
m
-
x
i
l
)
|
+
1
2
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
^
k
m
-
w
^
k
l
)
(
x
i
m
-
x
i
l
)
|
=
1
2
n
∑
i
=
1
n
‍
|
(
x
i
m
-
x
i
l
)
|
·
∑
k
=
1
K
-
1
‍
|
(
w
^
k
m
-
w
^
k
l
)
|
+
1
2
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
^
k
m
-
w
^
k
l
)
(
x
i
m
-
x
i
l
)
|
=
1
n
∥
x
(
m
)
-
x
(
l
)
∥
1
·
∥
w
^
(
m
)
-
w
^
(
l
)
∥
1
.
Analogically, we have
(35)
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
(
|
w
k
j
*
|
-
|
w
^
k
j
|
)
=
∑
k
=
1
K
-
1
‍
(
2
|
w
^
k
m
+
w
^
k
l
2
|
-
|
w
^
k
m
|
-
|
w
^
k
l
|
)
≤
0
,
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
(
w
k
j
*
)
2
-
(
w
^
k
j
2
)
=
-
1
2
∑
k
=
1
K
-
1
‍
(
w
^
k
m
-
w
^
k
l
)
2
=
-
1
2
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
2
.
Substituting (34) and (35) into (32) gives
(36)
0
≤
1
n
∥
x
(
m
)
-
x
(
l
)
∥
1
·
∥
w
^
(
m
)
-
w
^
(
l
)
∥
1
-
λ
2
2
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
2
.
that is,
(37)
0
≤
2
n
λ
2
∥
x
(
m
)
-
x
(
l
)
∥
1
·
∥
w
^
(
m
)
-
w
^
(
l
)
∥
1
-
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
2
ii
≤
2
K
n
λ
2
∥
x
(
m
)
-
x
(
l
)
∥
1
·
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
-
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
2
.
From (37), it can be easily obtained that
(38)
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
2
≤
2
K
n
λ
2
∥
x
(
m
)
-
x
(
l
)
∥
1
≤
2
K
n
λ
2
·
n
∥
x
(
m
)
-
x
(
l
)
∥
2
=
2
K
n
λ
2
2
-
2
x
(
m
)
T
x
(
l
)
=
2
K
n
λ
2
2
(
1
-
ρ
)
,
where ρ
=
x
(
m
)
T
x
(
l
)
=
∑
i
=
1
n
‍
x
i
m
x
i
l. This completes the proof.According to the inequality shown in Theorem2, the multinomial regression with elastic net penalty can assign the same parameter vectors (i.e., w
^
(
m
)
=
w
^
(
l
)) to the high correlated predictors x
(
m
)
,
x
(
l
) (i.e., ρ
=
1). This means that the multinomial regression with elastic net penalty can select genes in groups according to their correlation. According to the technical term in [14], this performance is called grouping effect in gene selection for multiclass classification. Particularly, for the binary classification, that is, K
=
2, inequality (29) becomes
(39)
|
w
^
1
m
-
w
^
1
l
|
≤
2
n
λ
2
2
(
1
-
ρ
)
.
This corresponds with the results in [7].


### 3.3. Solving Algorithm

Microarray is the typical smalln, large p problem. Because the number of the genes in microarray data is very large, it will result in the curse of dimensionality to solve the proposed multinomial regression. To improve the solving speed, Friedman et al. proposed the pairwise coordinate decent algorithm which takes advantage of the sparse property of characteristic. Therefore, we choose the pairwise coordinate decent algorithm to solve the multinomial regression with elastic net penalty. To this end, we convert (19) into the following form:
(40)
arg
min
⁡
(
b
,
w
)
{
[
α
∑
k
=
1
K
‍
∑
j
=
1
p
‍
]
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
‍
y
i
k
(
b
k
+
w
k
T
x
i
)
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
]
h
h
h
h
+
λ
[
α
∑
k
=
1
K
‍
∑
j
=
1
p
‍
w
k
j
2
+
(
1
-
α
)
∑
k
=
1
K
‍
∑
j
=
1
p
‍
|
w
k
j
|
]
}
.
Equation (40) can be easily solved by using the R package “glmnet” which is publicly available.


## 3.1. Multinomial Regression with the Multiclass Elastic Net Penalty

Following the idea of sparse multinomial regression [20–22], we fit the above class-conditional probability model by the regularized multinomial likelihood. Let p
k
(
x
i
)
=
Pr
(
y
i
=
k
∣
x
i
). It is easily obtained that
(12)
p
y
i
(
x
i
)
=
e
(
b
y
i
+
w
y
i
T
x
i
)
∑
k
=
1
K
e
(
b
k
+
w
k
T
x
i
)
.
Hence,
(13)
1
n
∑
i
=
1
n
‍
log
⁡
p
y
i
(
x
i
)
=
1
n
[
log
⁡
p
y
1
(
x
1
)
+
log
⁡
p
y
2
(
x
2
)
+
⋯
+
log
⁡
p
y
n
(
x
n
)
]
=
1
n
[
log
⁡
e
(
b
y
1
+
w
y
1
T
x
1
)
∑
k
=
1
K
e
(
b
k
+
w
k
T
x
1
)
+
log
⁡
e
(
b
y
2
+
w
y
2
T
x
2
)
∑
k
=
1
K
e
(
b
k
+
w
k
T
x
2
)
hhhhhhh
+
⋯
+
log
⁡
e
(
b
y
n
+
w
y
n
T
x
n
)
∑
k
=
1
K
e
(
b
k
+
w
k
T
x
n
)
]
=
1
n
[
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
n
)
(
b
y
1
+
w
y
1
T
x
1
)
+
⋯
+
(
b
y
n
+
w
y
n
T
x
n
)
hhhiiiiiiii
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
1
)
-
⋯
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
n
)
]
=
1
n
[
(
b
y
1
+
w
y
1
T
x
1
)
+
⋯
+
(
b
y
n
+
w
y
n
T
x
n
)
]
iiiiiii
-
1
n
∑
i
=
1
n
‍
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
.
Let
(14)
y
i
k
=
I
(
y
i
=
k
)
=
{
1
,
y
i
=
k
,
0
,
y
i
≠
k
.
Then (13) can be rewritten as
(15)
1
n
∑
i
=
1
n
‍
∑
k
=
1
K
‍
y
i
k
(
b
k
+
w
k
T
x
i
)
-
1
n
∑
i
=
1
n
‍
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
=
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
‍
y
i
k
(
b
k
+
w
k
T
x
i
)
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
]
.
Note that
(16)
log
⁡
p
y
i
(
x
i
)
=
log
⁡
e
(
b
y
i
+
w
y
i
T
x
i
)
∑
k
=
1
K
e
(
b
k
+
w
k
T
x
i
)
<
log
⁡
1
=
0
,
-
1
n
∑
i
=
1
n
‍
log
⁡
p
y
i
(
x
i
)
>
0
.
Hence, the multinomial likelihood loss function can be defined as
(17)
l
(
{
b
k
,
w
k
}
1
K
)
=
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
‍
y
i
k
(
b
k
+
w
k
T
x
i
)
hhhhhhhhhhhhhhhhhh
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
]
.In order to improve the performance of gene selection, the following elastic net penalty for the multiclass classification problem was proposed in [14]
(18)
J
(
b
,
w
)
=
λ
2
∑
k
=
1
K
‍
∑
j
=
1
p
‍
w
k
j
2
+
λ
1
∑
k
=
1
K
‍
∑
j
=
1
p
‍
|
w
k
j
|
.
By combing the multiclass elastic net penalty (18) with the multinomial likelihood loss function (17), we propose the following multinomial regression model with the elastic net penalty:
(19)
arg
min
⁡
(
b
,
w
)
{
∑
j
=
1
p
‍
|
w
k
j
|
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
‍
y
i
k
(
b
k
+
w
k
T
x
i
)
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
]
h
h
h
h
h
h
h
h
h
+
λ
2
∑
k
=
1
K
‍
∑
j
=
1
p
‍
w
k
j
2
+
λ
1
∑
k
=
1
K
‍
∑
j
=
1
p
‍
|
w
k
j
|
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
‍
y
i
k
(
b
k
+
w
k
T
x
i
)
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
]
}
,
where λ
1
,
λ
2 represent the regularization parameter. Note that (
b
K
,
w
K
)
=
(
0
,
0
→
). Hence, the optimization problem (19) can be simplified as
(20)
arg
min
⁡
(
b
,
w
)
{
(
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
|
w
k
j
|
)
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
-
1
‍
y
k
i
(
b
k
+
w
k
T
x
i
)
hhhhhhhhhhhhhhh
-
log
⁡
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
k
+
w
k
T
x
i
)
)
]
hhhhh
+
λ
2
(
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
w
k
j
2
)
+
λ
1
(
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
|
w
k
j
|
)
}
.


## 3.2. Grouping Effect

For the microarray classification, it is very important to identify the related gene in groups. In the section, we will prove that the multinomial regression with elastic net penalty can encourage a grouping effect in gene selection. To this end, we must first prove the inequality shown in Theorem1.Theorem 1.
Let(
b
^
,
w
^
) be the solution of the optimization problem (19) or (20). For any new parameter pairs which are selected as (
b
*
,
w
*
)
=
(
[
b
-
*
;
0
→
]
,
[
w
k
;
0
→
]
), the following inequality
(21)
|
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
k
*
+
w
k
*
T
x
i
)
)
-
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
^
k
+
w
^
k
T
x
i
)
)
|
≤
∑
k
=
1
K
-
1
‍
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
holds, where b
-
* and b
^
- represent the first K
-
1 rows of vectors b
* and b
^ and w
-
* and w
^
- represent the first K
-
1 rows of matrices w
* and w
^.Proof.
Note that the inequalityn
+
|
m
-
n
|
≥
m holds for the arbitrary real numbers m and n. Hence, the following inequality
(22)
(
b
^
t
+
w
^
t
T
x
i
)
+
|
(
b
t
*
+
w
t
*
T
x
i
)
-
(
b
^
t
+
w
^
t
T
x
i
)
|
≥
(
b
t
*
+
w
t
*
T
x
i
)
holds for any pairs (
b
t
*
,
w
t
*
), (
b
^
t
,
w
^
t
). From (22), it can be easily obtained that
(23)
(
b
^
t
+
w
^
t
T
x
i
)
+
∑
k
=
1
K
-
1
‍
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
≥
(
b
t
*
+
w
t
*
T
x
i
)
.
that is,
(24)
e
(
b
^
t
+
w
^
t
T
x
i
)
+
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
≥
e
(
b
t
*
+
w
t
*
T
x
i
)
.
Note that
(25)
e
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
≥
e
0
=
1
.
Hence, from (24) and (25), we can get
(26)
Δ
1
Δ
2
≤
1
,
where
(27)
Δ
1
=
1
+
e
(
b
1
*
+
w
1
*
T
x
i
)
+
⋯
+
e
(
b
t
*
+
w
t
*
T
x
i
)
+
⋯
+
e
(
b
K
-
1
*
+
w
K
-
1
*
T
x
i
)
,
Δ
2
=
e
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
+
e
(
b
^
1
+
w
^
1
T
x
i
)
+
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
+
⋯
+
e
(
b
^
t
+
w
^
t
T
x
i
)
+
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
+
⋯
+
e
(
b
^
K
-
1
+
w
^
K
-
1
*
T
x
i
)
+
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
.
Equation (26) is equivalent to the following inequality:
(28)
(
1
+
e
(
b
1
*
+
w
1
*
T
x
i
)
+
⋯
+
e
(
b
K
-
1
*
+
w
K
-
1
*
T
x
i
)
)
×
(
·
e
∑
k
=
1
K
-
1
‍
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
[
1
+
e
(
b
^
1
+
w
^
1
T
x
i
)
+
⋯
+
e
(
b
^
K
-
1
+
w
^
K
-
1
T
x
i
)
]
h
h
h
h
·
e
∑
k
=
1
K
-
1
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
)
-
1
≤
1
⟺
log
⁡
1
+
e
(
b
1
*
+
w
1
*
T
x
i
)
+
⋯
+
e
(
b
K
-
1
*
+
w
K
-
1
*
T
x
i
)
1
+
e
(
b
^
1
+
w
^
1
T
x
i
)
+
⋯
+
e
(
b
^
K
-
1
+
w
^
K
-
1
T
x
i
)
i
≤
∑
k
=
1
K
-
1
‍
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
⟺
|
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
k
*
+
w
k
*
T
x
i
)
)
-
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
^
k
+
w
^
k
T
x
i
)
)
|
i
≤
∑
k
=
1
K
-
1
‍
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
.
Hence, inequality (21) holds. This completes the proof.Using the results in Theorem1, we prove that the multinomial regression with elastic net penalty (19) can encourage a grouping effect.Theorem 2.
Give the training data set(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
n
,
y
n
) and assume that the matrix X and vector Y satisfy (1). If the pairs (b
^
,
w
^) are the optimal solution of the multinomial regression with elastic net penalty (19), then the following inequality
(29)
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
≤
2
K
n
λ
2
2
(
1
-
ρ
)
.
holds, where ρ
=
x
(
m
)
T
x
(
l
)
=
∑
i
=
1
n
‍
x
i
m
x
i
l, w
^
(
m
) is the mth column of parameter matrix w
^, and w
^
(
m
) is the lth column of parameter matrix w
^.Proof.
First of all, we construct the new parameter pairs(
b
*
,
w
*
)
=
(
[
b
-
*
;
0
→
]
,
[
w
k
*
;
0
→
]
), where
(30)
b
-
*
=
b
^
-
,
w
k
j
′
*
=
{
1
2
(
w
^
k
m
+
w
^
k
l
)
,
j
′
=
m
,
l
,
w
^
k
j
′
,
j
′
≠
m
,
l
.
Let
(31)
L
¯
=
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
-
1
‍
y
k
i
(
b
k
+
w
k
T
x
i
)
hhhhhhhhhhhhhh
-
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
k
+
w
k
T
x
i
)
)
]
iii
+
λ
2
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
w
k
j
2
+
λ
1
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
|
w
k
j
|
.
Since the pairs (b
^
,
w
^) are the optimal solution of the multinomial regression with elastic net penalty (19), it can be easily obtained that
(32)
0
≤
L
¯
(
λ
1
,
λ
2
,
b
-
*
,
w
-
*
)
-
L
¯
(
λ
1
,
λ
2
,
b
^
-
,
w
^
-
)
.
Note that the function L
k
i
(
b
^
k
,
w
^
k
,
x
i
)
=
b
k
+
w
k
T
x
i is Lipschitz continuous. Hence, we have
(33)
|
L
k
i
(
b
k
*
,
w
k
*
,
x
i
)
-
L
k
i
(
b
^
k
,
w
^
k
,
x
i
)
|
≤
|
(
w
k
*
-
w
^
k
)
T
x
i
|
.
From (33) and (21) and the definition of the parameter pairs (
b
*
,
w
*
), we have
(34)
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
-
1
‍
L
k
i
(
b
k
*
,
w
k
*
,
x
i
)
-
L
k
i
(
b
^
k
,
w
^
k
,
x
i
)
h
h
h
h
h
h
h
h
-
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
k
*
+
w
k
*
T
x
i
)
)
h
h
h
h
h
h
h
h
+
log
⁡
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
^
k
+
w
^
k
T
x
i
)
)
]
≤
|
-
1
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
L
k
i
(
b
k
*
,
w
k
*
,
x
i
)
-
L
k
i
(
b
^
k
,
w
^
k
,
x
i
)
|
+
1
n
∑
i
=
1
n
‍
|
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
k
*
+
w
k
*
T
x
i
)
)
iiiiiiiiiiiiiiiiiiiiiiiiiiiii
-
log
⁡
(
1
+
∑
k
=
1
K
-
1
‍
e
(
b
^
k
+
w
^
k
T
x
i
)
)
|
≤
1
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
L
k
i
(
b
k
*
,
w
k
*
,
x
i
)
-
L
k
i
(
b
^
k
,
w
^
k
,
x
i
)
|
+
1
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
b
k
*
+
w
k
*
T
x
i
)
-
(
b
^
k
+
w
^
k
T
x
i
)
|
≤
1
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
k
*
-
w
^
k
)
T
x
i
|
+
1
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
k
*
-
w
^
k
)
T
x
i
|
=
1
2
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
^
k
m
-
w
^
k
l
)
(
x
i
m
-
x
i
l
)
|
+
1
2
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
^
k
m
-
w
^
k
l
)
(
x
i
m
-
x
i
l
)
|
=
1
2
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
^
k
m
-
w
^
k
l
)
(
x
i
m
-
x
i
l
)
|
+
1
2
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
^
k
m
-
w
^
k
l
)
(
x
i
m
-
x
i
l
)
|
=
1
2
n
∑
i
=
1
n
‍
|
(
x
i
m
-
x
i
l
)
|
·
∑
k
=
1
K
-
1
‍
|
(
w
^
k
m
-
w
^
k
l
)
|
+
1
2
n
∑
i
=
1
n
‍
∑
k
=
1
K
-
1
‍
|
(
w
^
k
m
-
w
^
k
l
)
(
x
i
m
-
x
i
l
)
|
=
1
n
∥
x
(
m
)
-
x
(
l
)
∥
1
·
∥
w
^
(
m
)
-
w
^
(
l
)
∥
1
.
Analogically, we have
(35)
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
(
|
w
k
j
*
|
-
|
w
^
k
j
|
)
=
∑
k
=
1
K
-
1
‍
(
2
|
w
^
k
m
+
w
^
k
l
2
|
-
|
w
^
k
m
|
-
|
w
^
k
l
|
)
≤
0
,
∑
k
=
1
K
-
1
‍
∑
j
=
1
p
‍
(
w
k
j
*
)
2
-
(
w
^
k
j
2
)
=
-
1
2
∑
k
=
1
K
-
1
‍
(
w
^
k
m
-
w
^
k
l
)
2
=
-
1
2
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
2
.
Substituting (34) and (35) into (32) gives
(36)
0
≤
1
n
∥
x
(
m
)
-
x
(
l
)
∥
1
·
∥
w
^
(
m
)
-
w
^
(
l
)
∥
1
-
λ
2
2
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
2
.
that is,
(37)
0
≤
2
n
λ
2
∥
x
(
m
)
-
x
(
l
)
∥
1
·
∥
w
^
(
m
)
-
w
^
(
l
)
∥
1
-
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
2
ii
≤
2
K
n
λ
2
∥
x
(
m
)
-
x
(
l
)
∥
1
·
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
-
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
2
.
From (37), it can be easily obtained that
(38)
∥
w
^
(
m
)
-
w
^
(
l
)
∥
2
2
≤
2
K
n
λ
2
∥
x
(
m
)
-
x
(
l
)
∥
1
≤
2
K
n
λ
2
·
n
∥
x
(
m
)
-
x
(
l
)
∥
2
=
2
K
n
λ
2
2
-
2
x
(
m
)
T
x
(
l
)
=
2
K
n
λ
2
2
(
1
-
ρ
)
,
where ρ
=
x
(
m
)
T
x
(
l
)
=
∑
i
=
1
n
‍
x
i
m
x
i
l. This completes the proof.According to the inequality shown in Theorem2, the multinomial regression with elastic net penalty can assign the same parameter vectors (i.e., w
^
(
m
)
=
w
^
(
l
)) to the high correlated predictors x
(
m
)
,
x
(
l
) (i.e., ρ
=
1). This means that the multinomial regression with elastic net penalty can select genes in groups according to their correlation. According to the technical term in [14], this performance is called grouping effect in gene selection for multiclass classification. Particularly, for the binary classification, that is, K
=
2, inequality (29) becomes
(39)
|
w
^
1
m
-
w
^
1
l
|
≤
2
n
λ
2
2
(
1
-
ρ
)
.
This corresponds with the results in [7].


## 3.3. Solving Algorithm

Microarray is the typical smalln, large p problem. Because the number of the genes in microarray data is very large, it will result in the curse of dimensionality to solve the proposed multinomial regression. To improve the solving speed, Friedman et al. proposed the pairwise coordinate decent algorithm which takes advantage of the sparse property of characteristic. Therefore, we choose the pairwise coordinate decent algorithm to solve the multinomial regression with elastic net penalty. To this end, we convert (19) into the following form:
(40)
arg
min
⁡
(
b
,
w
)
{
[
α
∑
k
=
1
K
‍
∑
j
=
1
p
‍
]
-
1
n
∑
i
=
1
n
‍
[
∑
k
=
1
K
‍
y
i
k
(
b
k
+
w
k
T
x
i
)
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
-
log
⁡
∑
k
=
1
K
‍
e
(
b
k
+
w
k
T
x
i
)
]
h
h
h
h
+
λ
[
α
∑
k
=
1
K
‍
∑
j
=
1
p
‍
w
k
j
2
+
(
1
-
α
)
∑
k
=
1
K
‍
∑
j
=
1
p
‍
|
w
k
j
|
]
}
.
Equation (40) can be easily solved by using the R package “glmnet” which is publicly available.


## 4. Conclusion

By combining the multinomial likelihood loss function having explicit probability meanings with the multiclass elastic net penalty selecting genes in groups, the multinomial regression with elastic net penalty for the multiclass classification problem of microarray data was proposed in this paper. The proposed multinomial regression is proved to encourage a grouping effect in gene selection. In the next work, we will apply this optimization model to the real microarray data and verify the specific biological significance.



---

*Source: 569501-2014-03-31.xml*