# Coordinate Descent Based Hierarchical Interactive Lasso Penalized Logistic Regression and Its Application to Classification Problems

Authors: Jin-Jia Wang; Yang Lu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We present the hierarchical interactive lasso penalized logistic regression using the coordinate descent algorithm based on the hierarchy theory and variables interactions. We define the interaction model based on the geometric algebra and hierarchical constraint conditions and then use the coordinate descent algorithm to solve for the coefficients of the hierarchical interactive lasso model. We provide the results of some experiments based on UCI datasets, Madelon datasets from NIPS2003, and daily activities of the elder. The experimental results show that the variable interactions and hierarchy contribute significantly to the classification. The hierarchical interactive lasso has the advantages of the lasso and interactive lasso.


---

## Body

## 1. Introduction

Sparse linear models (such as the lasso) are a remarkable success of the regression analysis of high-dimensional data [1]. The lasso is a least squares regression with the L1 penalty function. It can also be extended to the generalized linear model [2], for example, the logistic regression with L1 penalty used for classification [3]. In the lasso model, the response variable is assumed to be a linear weighted sum of the predictor variables, and the optimization problem used to find the weighting coefficients can be solved by the coordinate descent algorithm [4]. If, in the analysis of high-dimensional data, the response variable cannot be explained by a linear weighted sum of predictor variables, a higher-order model and quadratic model need to be used. In most cases, this suggests the presence of variable interactions [5]. The presence of such interactions is considered important, as, for example, the interaction between single nucleotide polymorphisms (SNPs) plays an important role in the diagnosis of cancer and other diseases [6]. While the linear model has some advantages, such as good interpretability and simple calculations, the variable interaction models are considered to be a focus of the modern research [7].There are three types of methods used in the hierarchical interaction models. The first one is a multistep method. This method is based on removing or adding the best predictor variables or interaction variables in each iteration. Once the predictor variables corresponding to the interaction variables are in the model, the interaction variables must be in the model as well [8]. Alternatively, we can consider the variable selection before the interaction selection [9]. Usually, the modified LARS algorithm is used in such models to solve the interaction model [10]. The second type is the Bayes model method. This approach improves the random search variable selection method for the hierarchical interaction model [11]. The third type is based on optimization. The sparse interaction model is formulated as a nonconvex optimization problem [12] and further expressed as a convex optimization problem, such as all-pair lasso [13] or interaction group lasso [14].In the literature on the sparse structures [15], composite absolute penalties (CAP) can also obtain the sparseness of the group and interaction, but the interaction coefficient is penalized twice [16]. To solve for the hierarchical sparseness in the nonlinear interaction problem, the existing literature [17] has introduced the VANISH method. The logic regression method considers the binary variable high-level interaction [18]. The existing literature [19] uses a simple recursive approach to select the interaction variables from high-dimensional data. The literature [20] proposed a genetic algorithm using selection to choose interaction variables in high-dimensional data.The literature [13] presents a hierarchical interactive lasso method for regression and provides a method of model coefficients estimation using KKT conditions and the Lagrange multiplier method. Based on the literature [13] and our past work, the authors propose the concept of geometric algebra interaction and coordinate descent algorithm for the hierarchical interactive lasso penalized logistic regression. We used experimental data including 4 kinds of datasets from the UCI machine learning database, one Madelon datasets from NIPS2003, and one daily life activity recognition datasets. The experimental results reveal the outstanding advantages of the hierarchical interactive lasso method compared to the lasso and interactive lasso methods. The innovations include the following. (1) We use geometric algebra to explain variable interaction; (2) we derive an improved coordinate descent algorithm to solve the hierarchical interactive lasso penalized logistic regression; (3) we use the hierarchical interactive lasso for the classification problem.


## 2. The Variable Interaction Theory of Geometric Algebra

Definition 1.
If the functionf
(
x
,
y
) cannot be represented as a sum of independent functions, f
1
(
x
)
+
f
2
(
y
), then x, y in the f function are said to have interaction.A popular explanation of Definition1 is that if a response variable cannot be represented as a linear weighted sum of the prediction variables, it is probably because there are interactions between the variables.Interactions between variables can be easily explained by the geometric algebra theory. Figure1 is a diagram showing all subspace in geometric algebra. The 1-vectors, namely, order-1 main variables, can represent a p dimensional subspace of the original data. That is, p dimensional base of the original data is projected on the 1-vectors. The 2-vectors show the interaction between two variables. The simplest 2-vectors coefficient can be the product of two 1-vectors. In the literature [13] our proposed area feature is considered as one of the interactions. In the literature [20] our proposed orthocenter feature is considered as one of the interactions. Higher-order interactions are represented by k
-vectors. In this paper, we only study area interactions between 1-vectors. This method can also be extended to the nonlinear complex function interactions or higher order.Figure 1
The diagram of the subspaces in geometric algebra.


## 3. The Binary Logistic Regression Based on Interaction and Hierarchy

The outcome variable in the binary logistic model is denoted byY; the income variables are predictors X. x
1
,
…
,
x
j
,
…
,
x
p are order-1 main variables, and the pairwise x
j
x
k are interactions variables between order-1 main variables. The binary logistic model has the form
(1)
log
⁡
⁡
i
t
P
Y
=
1
∣
X
=
∑
j
=
0
p
β
j
x
j
+
1
2
∑
j
≠
k
Θ
j
k
x
j
x
k
+
ε
,
where Θ
j
j
=
0, the main variables coefficients are β
∈
R
p
+
1, the interaction variables coefficients are Θ
∈
R
p
×
p, x
0 is 1, and ε satisfies N
(
0
,
σ
2
).Assume that the training samples are(
x
1
,
y
1
)
,
…
,
(
x
i
,
y
i
)
,
…
,
(
x
N
,
y
N
), x
i
∈
R
p,
(2)
y
i
=
1
Y
i
=
1
0
Y
i
≠
1
.Our goal is to select a feature subset from the order-1 main variables (dimensionp) and order-2 interaction variables (dimension p
(
p
-
1
)
/
2). We then estimate the coefficient values for nonzero model parameters. We can obtain the probability of two classes as follows:
(3)
Pr
⁡
Y
=
1
∣
x
i
=
1
1
+
exp
⁡
-
∑
j
β
j
x
i
j
-
1
/
2
∑
j
≠
k
Θ
j
k
x
i
j
x
i
k
=
p
x
i
,
P
Y
=
2
∣
x
i
=
1
1
+
exp
⁡
∑
j
β
j
x
i
j
+
1
/
2
∑
j
≠
k
Θ
j
k
x
i
j
x
i
k
=
1
-
p
x
i
.The maximum likelihood estimation is used to estimate the unknown model parameters, which make the likelihood function ofN independent observations the largest. We define
(4)
L
β
,
Θ
=
∏
i
=
1
N
p
x
i
y
i
1
-
p
x
i
1
-
y
i
.
Then, the logarithmic likelihood function of (4) is
(5)
1
N
ln
⁡
L
β
,
Θ
=
1
N
∑
i
=
1
N
y
i
x
i
T
β
+
1
2
x
i
T
Θ
x
i
+
ln
⁡
1
-
p
x
i
.We use the second-order Taylor expansion at the current estimated value(
β
~
,
Θ
~
) for (5) and obtain the subproblem as follows:
(6)
l
Q
β
,
Θ
=
1
2
ω
i
z
i
-
∑
j
β
~
j
x
i
j
-
1
2
∑
j
≠
k
Θ
~
j
k
x
i
j
x
i
k
2
+
y
i
-
p
~
x
i
2
2
*
p
~
2
x
i
1
-
p
~
x
i
2
+
y
i
∑
j
β
~
j
x
i
j
+
∑
j
≠
k
Θ
~
j
k
x
i
j
x
i
k
h
h
h
h
+
∑
j
β
~
j
x
i
j
+
∑
j
≠
k
Θ
~
j
k
x
i
j
x
i
k
ln
⁡
1
-
p
~
x
i
,
where ω
i
=
p
~
(
x
i
)
[
1
-
p
~
(
x
i
)
], z
i
=
∑
j
β
j
x
i
j
+
1
/
2
∑
j
≠
k
Θ
j
k
x
i
j
x
i
k
+
(
y
i
-
p
~
x
i
)
/
p
~
(
x
i
)
[
1
-
p
~
(
x
i
)
].The proof that (5) implies (6) is presented in the Appendix A.In order to obtain the sparse solution for the main variable coefficients and interaction coefficients, the penalty function is used to enhance the stability of the interactive model:(7)
β
,
Θ
=
arg
Min
⁡
β
∈
R
p
+
1
,
Θ
∈
R
p
×
p
-
l
Q
β
,
Θ
+
λ
1
β
1
+
λ
2
Θ
1
.We focus on those interactions that have large main variable coefficients. Such restrictions are known as “hierarchy.” The mathematical expression for them isΘ
^
j
k
≠
0
⇒
β
^
j
≠
0 or β
^
k
≠
0. So, we add the constraints enforcing the hierarchy into (7) as follows:
(8)
β
,
Θ
=
Min
⁡
β
∈
R
p
+
1
,
Θ
∈
R
p
×
p
-
l
Q
β
,
Θ
+
λ
1
β
1
+
λ
2
Θ
1
s
.
t
.
Θ
j
1
≤
β
j
for
j
=
1
,
…
,
p
,
where Θ
j is the jth column of Θ. If Θ
^
j
k
≠
0, then Θ
^
j
1
>
0, Θ
^
k
1
>
0, so β
^
j
≠
0, and β
^
k
≠
0. The new constraint guarantees the hierarchy, but we cannot obtain a convex solution because (8) is not convex. So, instead of β we use β
+, β
-. And the corresponding convex relaxation of (8) is as follows:
(9)
β
±
,
Θ
=
Min
⁡
β
0
∈
R
,
β
±
∈
R
p
,
Θ
∈
R
p
×
p
-
l
Q
β
+
-
β
-
,
Θ
+
λ
1
1
T
β
+
+
β
-
+
λ
2
∑
j
Θ
j
s
.
t
.
Θ
j
1
≤
β
j
+
+
β
j
-
β
j
+
≥
0
,
β
j
-
≥
0
for
j
=
1
,
…
,
p
,
where β
=
β
+
-
β
-, β
±
=
max
⁡
{
±
β
,
0
},  β
+
,
β
-
∈
R
p
+
1, and β
1
=
β
+
+
β
-.


## 4. Coordinate Descent Algorithm and KKT Conditions

The basic idea of the coordinate descent algorithm is to convert multivariate problems into multiple single variable subproblems. It allows optimizing only one-dimensional variables at a time. The solution can be updated in a cycle. We solve (9) using the coordinate descent algorithm.The Lagrange function corresponding to (9) is as follows:
(10)
L
β
+
,
β
-
,
Θ
=
-
l
Q
β
+
-
β
-
,
Θ
+
λ
1
1
-
α
^
-
γ
+
1
T
β
+
+
λ
1
1
-
α
^
-
γ
-
1
T
β
-
+
diag
⁡
λ
2
1
+
α
^
U
,
Θ
,
where
(11)
U
^
j
k
=
∈
-
1,1
Θ
^
k
j
=
0
sign
⁡
Θ
^
j
k
Θ
^
j
k
≠
0
,
and α
^ and γ
± are the dual variables corresponding to the hierarchical constraint and the nonnegative constraints. Formula (10) can be decomposed into p subproblems:
(12)
L
β
j
+
,
β
j
-
,
Θ
j
=
-
l
Q
β
j
+
-
β
j
-
,
Θ
j
+
λ
1
-
α
^
j
-
γ
+
T
β
j
+
+
λ
1
-
α
^
j
-
γ
-
T
β
j
-
+
λ
2
+
α
U
j
,
Θ
j
.The solution of (12) as a convex problem can be obtained by a set of optimality conditions, known as the KKT (Karush-Kuhn-Tucker) conditions. This is the key advantage of our approach.The stationary conditions of (12) according to KKT are ∂
L
/
∂
β
^
j
±
=
0, ∂
L
/
∂
Θ
^
j
k
=
0. The complementary conditions are Θ
^
j
1
≤
β
^
j
+
+
β
^
j
-, γ
j
±
β
^
j
±
=
0, β
^
±
≥
0, γ
^
±
≥
0, α
^
≥
0, α
^
j
(
Θ
^
j
1
-
β
^
j
+
-
β
^
j
-
)
=
0. We assume that (
1
/
N
)
∑
i
=
1
N
x
i
j
2
=
1. For our problem, the KKT conditions can be written as follows:
(13)
β
^
j
+
-
β
^
j
-
=
S
x
i
j
z
i
-
A
i
+
β
^
j
+
-
β
^
j
-
,
λ
1
+
α
^
j
ω
i
,
Θ
^
j
k
=
S
x
i
j
x
i
k
T
z
i
-
A
i
+
Θ
^
j
k
x
i
j
x
i
k
,
2
λ
2
+
α
^
j
/
ω
i
x
i
j
x
i
k
2
,
where A
i
=
∑
j
β
~
j
x
i
j
+
(
1
/
2
)
∑
j
≠
k
Θ
~
j
k
x
i
j
x
i
k, z
i, ω
i are from (6), and S denotes the soft-threshold operator defined by S
(
c
,
λ
)
=
sign
⁡
(
c
)
(
c
-
λ
)
+.The proof of both expressions (13) can be found in Appendix B.Now, we definef
(
α
^
j
)
=
Θ
^
j
1
-
β
^
j
+
-
β
^
j
-. Then
(14)
f
α
^
j
=
∑
k
=
1
P
S
x
i
j
x
i
k
T
z
i
-
A
i
+
Θ
^
j
k
x
i
j
x
i
k
,
2
λ
2
+
α
^
j
ω
i
h
h
h
h
h
h
h
h
h
2
λ
2
+
α
^
j
ω
i
h
h
h
h
h
2
λ
2
+
α
^
j
ω
i
·
x
i
j
x
i
k
2
2
-
1
1
-
S
x
i
j
z
i
-
A
i
+
β
^
j
+
-
β
^
j
-
,
λ
1
+
α
^
j
ω
i
1
.
The remaining KKT conditions only involve α
^
:
α
^
f
(
α
^
)
=
0, f
(
α
^
)
≤
0, α
^
≥
0. Observing that f is nonincreasing with respect to α
^ and is piecewise linear, it is easy to get the solution for α
^.In conclusion, the overall idea of the coordinate descent algorithm is that the minimization of (9) is equivalent to the minimization of (10). Formula (10) can be decomposed into p independent formula (12). Formula (12) can be solved as (13). The final coefficient optimization iteration formula is as follows:
(15)
β
^
j
+
m
+
1
-
β
^
j
-
m
+
1
=
S
x
i
j
z
i
m
-
A
i
m
+
β
^
j
+
m
-
β
^
j
-
m
,
λ
1
+
α
^
j
m
ω
i
k
,
Θ
^
j
k
m
+
1
=
S
x
i
j
x
i
k
z
i
m
-
A
i
m
+
Θ
^
j
k
m
x
i
j
x
i
k
,
2
λ
2
+
α
^
j
m
/
ω
i
m
x
i
j
x
i
k
2
,
where β
^
j
+
(
m
)
-
β
^
j
-
(
m
) is the estimated value of the jth main variable coefficient after m iterations and Θ
^
j
k
m is the estimation of the interaction coefficient between the jth variable and the kth variable after m iterations.


## 5. The Experimental Results and Analysis

### 5.1. The Experimental Results and Analysis of Four UCI Datasets

There are four UCI study database datasets, which include the breast-cancer-Wisconsin datasets, Ionosphere datasets, Liver_disorders datasets, and Sonar datasets, as shown in Table1.Table 1
Datasets information.
Datasets
Samples
Variable dimension
Interactive dimension
Class
1
Breast-cancer-Wisconsin
683
9
36
2
2
Ionosphere
351
33
528
2
3
Liver_disorders
345
6
15
2
4
Sonar
208
60
1770
2We do the 10-fold cross-validation (10-CV) experiments in the paper for 20 times usingR, where λ
1
=
2
λ
2
=
λ. Besides we complete an experiment employing the interactive hierarchical lasso logistic regression method. The results include the number of nonzero variable coefficients, average error rate of the 10-CV, standard deviation (SD), CPU time, and the value of lambda (λ) estimated. The results are shown in Table 2.Table 2
The experimental results of our method.
Datasets
Coefficients
Error rate (%)
SD
Time (/s)
λ
Breast-cancer-Wisconsin
22
3.0
0.01
9.49
3.14
Ionosphere
101
28.0
0.02
124.63
2.82
Liver_disorders
25
26.0
0.02
12.11
2.37
Sonar
117
14.0
0.02
150.69
0.73The results of the 10-CV based on the four datasets are presented in Figures2 to 5 using the proposed method. In the figures, the horizontal axis represents the logarithmic value of λ and the vertical axis is the error rate of the 10-CV. Besides, the horizontal axis at the top of each figure represents the number of nonzero variable coefficients corresponding to the λ value.Figure 2
The results of breast-cancer-Wisconsin.The results for the breast-cancer-Wisconsin datasets are shown in Figure2. The minimum error rate is 0.03 and the number of selected variables is more than 11. The results for the Ionosphere experimental datasets are shown in Figure 3. When the number of selected variables is 101, the lowest error rate is 0.28 with the smaller standard deviation. The number of the selected variables is larger than the original dimension, so the interactions provide the classified information. The results for the Liver_disorders datasets are presented in Figure 4. If the number of selected variables is 25, the lowest error rate can reach 0.26, while the standard deviation is 0.02. Finally, the results for the Sonar datasets are presented in Figure 5. When more than 80 variables are selected, the minimum error rate is 0.14.Figure 3
The results of Ionosphere.Figure 4
The results of Liver_disorders.Figure 5
The results of Sonar.In what follows, we compare our method to the existing literature [13]. The classification results and training time of our method are better than those shown in the literature [13]. The experimental results of the lasso, all-pair lasso, and conventional pattern recognition methods with 10-fold cross-validation of 20 times in the four UCI datasets are listed, respectively, in Tables 3, 4, and 5. Conventional pattern recognition methods include support vector machine (SVM), linear discriminant analysis (LDA), quadratic discriminant analysis (QDA), K-nearest neighborhood (K-NN), and decision tree (DT) methods. The lasso is a method that considers the main variables without the interaction variables. All-pair lasso is a method that considers the main variables and interaction variables but without the hierarchy. The experimental results show that our model is better in classification results and more stable. This highlights the advantage of the variable interactions and hierarchy.Table 3
The experimental results of the lasso penalized logistic regression model.
Datasets
Error rate (%)
SD
Time (/s)
Breast-cancer-Wisconsin
3.22
0.0001
0.3744
Ionosphere
31.15
0.0075
0.4863
Liver_disorders
30.77
0.0077
0.0908
Sonar
22.13
0.0121
15.6806Table 4
The experimental results of the all-pair lasso penalized logistic regression model.
Datasets
Error rate (%)
SD
Time (/s)
Breast-cancer-Wisconsin
2.93
0.0001
12.1213
Ionosphere
27.00
0.0089
3.1734
Liver_disorders
26.36
0.0058
4.9190
Sonar
20.63
0.0115
4.1041Table 5
The experimental results of the traditional pattern recognition methods.
Datasets
Classifier
Error rate (%)
SD
Time (/s)
Breast-cancer-Wisconsin
SVM
3.42
0.0019
1.3092
LDA
3.96
0.0007
0.2429
QDA
4.92
0.0014
0.2309
K-NN
4.61
0.0030
0.6636
DT
4.99
0.0041
1.6201
Ionosphere
SVM
35.83
0.0063
2.9149
LDA
33.10
0.0090
0.6168
QDA
32.01
0.0076
0.4516
K-NN
28.30
0.0090
0.6363
DT
38.23
0.0408
3.0865
Liver_disorders
SVM
30.80
0.0100
1.1401
LDA
31.31
0.0089
0.2474
QDA
40.19
0.0119
0.1958
K-NN
36.89
0.0124
0.6089
DT
36.94
0.0187
1.9921
Sonar
SVM
25.70
0.0197
1.2181
LDA
25.13
0.0145
0.5897
QDA
23.80
0.0205
0.4594
K-NN
13.09
0.0101
0.5345
DT
35.91
0.0303
0.7153


### 5.2. The Experimental Results for High-Dimensional Small Sample Data

The Madelon datasets from NIPS2003 was used to evaluate our method. The sample numbers of the training, validation, and testing of the data were, respectively, 2000, 600, and 1800. The class number is 2. The variable dimension is 500. So the interactive dimension is 124750. You can find more information about the datasets following the linkhttp://www.nipsfsc.ecs.soton.ac.uk/; you can also download the datasets and see the results of challenges, balance error rates, and the area under the curve. The model is trained by using a training set. The model parameters are selected by using a validation set. Also, the prediction results of the final model using the test set are uploaded online. The classification score of the final model is obtained. Our results are shown in Table 6. The results show that our method is slightly better than the lasso and all-pair lasso. This implies that the interactions may also be important in the Madelon datasets.Table 6
The experimental results for the Madelon datasets.
Methods
Balance error rate (%)
Area under the curve (%)
Training
Validation
Testing
Training
Validation
Testing
Lasso
38.08
37.21
36.61
64.78
62.79
63.40
All-pair lasso
34.98
37.01
36.57
65.02
62.99
63.43
Our method
30.00
36.35
35.12
70.00
68.08
67.76


### 5.3. Activity Recognition (AR) Using Inertial Sensors of Smartphones

Anguita et al. collected sensor data of smartphones [10]. They used the support vector machine (SVM) method to solve the classification problem of the daily life activity recognition. These results play an extremely significant role in disability and elderly care. Datasets can be downloaded following the literature [10]. 30 volunteers aged 19–48 years participated in the study. Each person performed six activities wearing the smartphone on the waist. To obtain the data class label, experiments were conducted using video recording. The smartphone used in the experiments had built-in accelerometer and gyroscope for measuring 3D linear acceleration and angular acceleration. The sampling frequency was 50 Hz, which is more than enough for capturing human movements.We use the datasets to evaluate our method. We use the upstairs and downstairs movements as two active classes. The training sets have 986 samples and 1,073 samples, respectively. The test sets have 420 samples and 471 samples, respectively. The variable dimension is 561, which includes the time and frequency from sensor signals.Experimental results of the three lasso methods and some pattern recognition methods are shown in Table7. The results show that our method is better than the pattern recognition methods, since it takes the variable selection and interaction into account. Our method achieves the best classification results with less training and testing time.Table 7
The experimental results of the three lasso methods and five traditional pattern recognition methods.
Methods
Error rate in training (%)
Training time (/s)
Error rate in testing (%)
Testing time (/s)
Lasso
0.00
0.2649
1.46
0.0312
All-pair lasso
0.00
0.8807
1.35
0.0953
Our method
0.00
0.6012
1.12
0.0556
SVM
0.00
0.9516
1.23
0.0936
1-NN
0.00
0.0000
9.20
0.7956
3-NN
0.00
0.0000
8.98
0.7488
QDA
6.61
1.4196
4.04
0.2184
DT
0.00
0.7332
14.93
0.1092


### 5.4. The Numerical Simulation Results and Discussion

Now, suppose that the number and dimension of the samples aren
=
200, p
=
20. We take interactions into consideration and provide the following three kinds of simulation based on formula (1).(1)
The real model is hierarchical:Θ
j
k
≠
0
⇒
β
j
≠
0 or β
k
≠
0,  j
,
k
=
1
,
…
,
p. There are 10 nonzero elements in β and 20 nonzero elements in Θ.
(2)
The real model only includes interactive variables:β
j
=
0,  j
=
1
,
…
,
p. There are 20 nonzero elements in Θ.
(3)
The real model only includes main variables:Θ
j
k
=
0,  j
,
k
=
1
,
…
,
p. There are 10 nonzero elements in β.The SNR of the main variables is 1.5, and SNR of the interaction variables is 1. The experiment results of 100 times are shown in Figure6.The error rate of the three lasso methods in the simulation experiment (the Bayes error is shown by the purple dotted line in the graph).
(a)
Hierarchical interaction
(b)
Interaction variances only
(c)
Main variances onlyWhen the real model is hierarchical, our method is the best, and the lasso is the worst. This is shown in Figure6(a). When the real model only includes interaction variances, the interactive lasso is the best, and our method takes the second place, while the lasso is still the worst, as shown in Figure 6(b). The reason for this result is that when our method fits the model, the interaction variables are considered to be main variables. When the real model only includes main variables, the lasso is the best, and our method still takes the second place, and the all-pair lasso is the worst, as shown in Figure 6(c).We believe that many actual classification problems could be hierarchical and interactive. They contain both main variables and interaction variables. Our method fits in this kind of situation.


## 5.1. The Experimental Results and Analysis of Four UCI Datasets

There are four UCI study database datasets, which include the breast-cancer-Wisconsin datasets, Ionosphere datasets, Liver_disorders datasets, and Sonar datasets, as shown in Table1.Table 1
Datasets information.
Datasets
Samples
Variable dimension
Interactive dimension
Class
1
Breast-cancer-Wisconsin
683
9
36
2
2
Ionosphere
351
33
528
2
3
Liver_disorders
345
6
15
2
4
Sonar
208
60
1770
2We do the 10-fold cross-validation (10-CV) experiments in the paper for 20 times usingR, where λ
1
=
2
λ
2
=
λ. Besides we complete an experiment employing the interactive hierarchical lasso logistic regression method. The results include the number of nonzero variable coefficients, average error rate of the 10-CV, standard deviation (SD), CPU time, and the value of lambda (λ) estimated. The results are shown in Table 2.Table 2
The experimental results of our method.
Datasets
Coefficients
Error rate (%)
SD
Time (/s)
λ
Breast-cancer-Wisconsin
22
3.0
0.01
9.49
3.14
Ionosphere
101
28.0
0.02
124.63
2.82
Liver_disorders
25
26.0
0.02
12.11
2.37
Sonar
117
14.0
0.02
150.69
0.73The results of the 10-CV based on the four datasets are presented in Figures2 to 5 using the proposed method. In the figures, the horizontal axis represents the logarithmic value of λ and the vertical axis is the error rate of the 10-CV. Besides, the horizontal axis at the top of each figure represents the number of nonzero variable coefficients corresponding to the λ value.Figure 2
The results of breast-cancer-Wisconsin.The results for the breast-cancer-Wisconsin datasets are shown in Figure2. The minimum error rate is 0.03 and the number of selected variables is more than 11. The results for the Ionosphere experimental datasets are shown in Figure 3. When the number of selected variables is 101, the lowest error rate is 0.28 with the smaller standard deviation. The number of the selected variables is larger than the original dimension, so the interactions provide the classified information. The results for the Liver_disorders datasets are presented in Figure 4. If the number of selected variables is 25, the lowest error rate can reach 0.26, while the standard deviation is 0.02. Finally, the results for the Sonar datasets are presented in Figure 5. When more than 80 variables are selected, the minimum error rate is 0.14.Figure 3
The results of Ionosphere.Figure 4
The results of Liver_disorders.Figure 5
The results of Sonar.In what follows, we compare our method to the existing literature [13]. The classification results and training time of our method are better than those shown in the literature [13]. The experimental results of the lasso, all-pair lasso, and conventional pattern recognition methods with 10-fold cross-validation of 20 times in the four UCI datasets are listed, respectively, in Tables 3, 4, and 5. Conventional pattern recognition methods include support vector machine (SVM), linear discriminant analysis (LDA), quadratic discriminant analysis (QDA), K-nearest neighborhood (K-NN), and decision tree (DT) methods. The lasso is a method that considers the main variables without the interaction variables. All-pair lasso is a method that considers the main variables and interaction variables but without the hierarchy. The experimental results show that our model is better in classification results and more stable. This highlights the advantage of the variable interactions and hierarchy.Table 3
The experimental results of the lasso penalized logistic regression model.
Datasets
Error rate (%)
SD
Time (/s)
Breast-cancer-Wisconsin
3.22
0.0001
0.3744
Ionosphere
31.15
0.0075
0.4863
Liver_disorders
30.77
0.0077
0.0908
Sonar
22.13
0.0121
15.6806Table 4
The experimental results of the all-pair lasso penalized logistic regression model.
Datasets
Error rate (%)
SD
Time (/s)
Breast-cancer-Wisconsin
2.93
0.0001
12.1213
Ionosphere
27.00
0.0089
3.1734
Liver_disorders
26.36
0.0058
4.9190
Sonar
20.63
0.0115
4.1041Table 5
The experimental results of the traditional pattern recognition methods.
Datasets
Classifier
Error rate (%)
SD
Time (/s)
Breast-cancer-Wisconsin
SVM
3.42
0.0019
1.3092
LDA
3.96
0.0007
0.2429
QDA
4.92
0.0014
0.2309
K-NN
4.61
0.0030
0.6636
DT
4.99
0.0041
1.6201
Ionosphere
SVM
35.83
0.0063
2.9149
LDA
33.10
0.0090
0.6168
QDA
32.01
0.0076
0.4516
K-NN
28.30
0.0090
0.6363
DT
38.23
0.0408
3.0865
Liver_disorders
SVM
30.80
0.0100
1.1401
LDA
31.31
0.0089
0.2474
QDA
40.19
0.0119
0.1958
K-NN
36.89
0.0124
0.6089
DT
36.94
0.0187
1.9921
Sonar
SVM
25.70
0.0197
1.2181
LDA
25.13
0.0145
0.5897
QDA
23.80
0.0205
0.4594
K-NN
13.09
0.0101
0.5345
DT
35.91
0.0303
0.7153


## 5.2. The Experimental Results for High-Dimensional Small Sample Data

The Madelon datasets from NIPS2003 was used to evaluate our method. The sample numbers of the training, validation, and testing of the data were, respectively, 2000, 600, and 1800. The class number is 2. The variable dimension is 500. So the interactive dimension is 124750. You can find more information about the datasets following the linkhttp://www.nipsfsc.ecs.soton.ac.uk/; you can also download the datasets and see the results of challenges, balance error rates, and the area under the curve. The model is trained by using a training set. The model parameters are selected by using a validation set. Also, the prediction results of the final model using the test set are uploaded online. The classification score of the final model is obtained. Our results are shown in Table 6. The results show that our method is slightly better than the lasso and all-pair lasso. This implies that the interactions may also be important in the Madelon datasets.Table 6
The experimental results for the Madelon datasets.
Methods
Balance error rate (%)
Area under the curve (%)
Training
Validation
Testing
Training
Validation
Testing
Lasso
38.08
37.21
36.61
64.78
62.79
63.40
All-pair lasso
34.98
37.01
36.57
65.02
62.99
63.43
Our method
30.00
36.35
35.12
70.00
68.08
67.76


## 5.3. Activity Recognition (AR) Using Inertial Sensors of Smartphones

Anguita et al. collected sensor data of smartphones [10]. They used the support vector machine (SVM) method to solve the classification problem of the daily life activity recognition. These results play an extremely significant role in disability and elderly care. Datasets can be downloaded following the literature [10]. 30 volunteers aged 19–48 years participated in the study. Each person performed six activities wearing the smartphone on the waist. To obtain the data class label, experiments were conducted using video recording. The smartphone used in the experiments had built-in accelerometer and gyroscope for measuring 3D linear acceleration and angular acceleration. The sampling frequency was 50 Hz, which is more than enough for capturing human movements.We use the datasets to evaluate our method. We use the upstairs and downstairs movements as two active classes. The training sets have 986 samples and 1,073 samples, respectively. The test sets have 420 samples and 471 samples, respectively. The variable dimension is 561, which includes the time and frequency from sensor signals.Experimental results of the three lasso methods and some pattern recognition methods are shown in Table7. The results show that our method is better than the pattern recognition methods, since it takes the variable selection and interaction into account. Our method achieves the best classification results with less training and testing time.Table 7
The experimental results of the three lasso methods and five traditional pattern recognition methods.
Methods
Error rate in training (%)
Training time (/s)
Error rate in testing (%)
Testing time (/s)
Lasso
0.00
0.2649
1.46
0.0312
All-pair lasso
0.00
0.8807
1.35
0.0953
Our method
0.00
0.6012
1.12
0.0556
SVM
0.00
0.9516
1.23
0.0936
1-NN
0.00
0.0000
9.20
0.7956
3-NN
0.00
0.0000
8.98
0.7488
QDA
6.61
1.4196
4.04
0.2184
DT
0.00
0.7332
14.93
0.1092


## 5.4. The Numerical Simulation Results and Discussion

Now, suppose that the number and dimension of the samples aren
=
200, p
=
20. We take interactions into consideration and provide the following three kinds of simulation based on formula (1).(1)
The real model is hierarchical:Θ
j
k
≠
0
⇒
β
j
≠
0 or β
k
≠
0,  j
,
k
=
1
,
…
,
p. There are 10 nonzero elements in β and 20 nonzero elements in Θ.
(2)
The real model only includes interactive variables:β
j
=
0,  j
=
1
,
…
,
p. There are 20 nonzero elements in Θ.
(3)
The real model only includes main variables:Θ
j
k
=
0,  j
,
k
=
1
,
…
,
p. There are 10 nonzero elements in β.The SNR of the main variables is 1.5, and SNR of the interaction variables is 1. The experiment results of 100 times are shown in Figure6.The error rate of the three lasso methods in the simulation experiment (the Bayes error is shown by the purple dotted line in the graph).
(a)
Hierarchical interaction
(b)
Interaction variances only
(c)
Main variances onlyWhen the real model is hierarchical, our method is the best, and the lasso is the worst. This is shown in Figure6(a). When the real model only includes interaction variances, the interactive lasso is the best, and our method takes the second place, while the lasso is still the worst, as shown in Figure 6(b). The reason for this result is that when our method fits the model, the interaction variables are considered to be main variables. When the real model only includes main variables, the lasso is the best, and our method still takes the second place, and the all-pair lasso is the worst, as shown in Figure 6(c).We believe that many actual classification problems could be hierarchical and interactive. They contain both main variables and interaction variables. Our method fits in this kind of situation.


## 6. Conclusion

Taking into consideration the interaction between variables, the hierarchical interactive lasso penalized logistic regression using the coordinate descent algorithm is derived. We provide the model definition, constraint condition, and the convex relaxation condition for the model. We obtain a solution for the coefficients of the proposed model based on the convex optimization and coordinate descent algorithm. We further provide experimental results based on four UCI datasets, NIPS2003 feature selection challenge datasets, and true daily life activities identification datasets. The results show that the interaction widely exists in the classification models. They also demonstrate that the variable interaction contributes to the response. The classification performance of our method is superior to the lasso, all-pair lasso, and some pattern recognition methods. It turns out that the variable interaction and hierarchy are two important factors. Our further research is planned as follows: other convex optimization methods including the generalized gradient descent method or alternating direction multiplier method, the hierarchical interactive lasso penalized multiclass logistic regression method, the elastic net method, or the hierarchical group lasso method. The application of the multisensor interaction in the daily life activities of the elderly is a new way of using of our method.



---

*Source: 430201-2014-12-16.xml*