We consider variable selection problems in high dimensional sparse regression models with strongly correlated variables. To handle correlated variables, the concept of clustering or grouping variables and then pursuing model fitting is widely accepted. When the dimension is very high, finding an appropriate group structure is as difficult as the original problem. We propose to use Elastic-net as a pre-selection step for Cluster Lasso methods (i.e. Cluster Group Lasso and Cluster Representative Lasso). The Elastic-net selects correlated relevant variables, but it fails to reveal the correlation structure among the active variables. We use cluster Lasso methods to address shortcoming of the Elastic-net, and the Elasticnet is used to provide reduced feature set for the cluster Lasso methods. We theoretically explore, the group selection consistency of the proposed combination of algorithms under various conditions, i.e. Irrepresentable Condition (IC), Elastic-net Irrepresentable Condition (EIC) and Group Irrepresentable Condition (GIC). We support the theory using simulated and real dataset examples.
Y = X0 + , ( ) with response vector Y×1, design matrix X×, true underlying coefficient vector 0×1 and error vector ×1. When the number of predictors (p) is much larger than the number of observations (n), ≫ , the Lasso [ ] and its variants are mostly used for sparse estimation and variable selection. However, variable selection in situations involving high empirical correlation remains one of the most important issues. This problem is encountered in many applications such as microarray data analysis and genome analysis, see [ ].
It has been proven that the design matrix must satisfy the following conditions for the Lasso to perform exact variable selection: irrepresentable condition (IC) [ ] and beta-min condition [ ]. Having highly correlated variables implies that the design matrix violates the IC. To deal with correlated variables, mainly two approaches have been proposed in literature: simultaneous clustering and model fitting (see [ ]), and clustering followed by the sparse estimation (see [ ]) and [ ]). The former approach imposes restrictive conditions on the design matrix. However, the time complexity for clustering of variables severely limits the dimension of data sets that can be processed by the later approach. Moreover, group selection in models with a larger number of groups is more difficult (see [ ]). To overcome the limitations of the later approach, we propose to use Elastic-net [ ] as a pre-selection procedure for the Cluster Lasso [ ] methods. Basically, we try to reduce the noise (dimension) first using the Elastic-net which is known to select correlated variables, before applying the Cluster Lasso (CL) methods. This scheme allows for a significant decrease in the cost of clustering, especially in the high dimensional problems.
Basically, we propose to combine Elastic-net and Cluster Lasso methods to improve both speed of computation and accuracy of the results in the case of sparsity. This goal is achieved by using Elastic-net to first reduce the number of variables under consideration and then using CL methods on the reduced data to select correlated variables. We theoretically explore, how the proposed combination of algorithms will perform under various conditions, i.e. Irrepresentable Condition (IC), Elastic-net Irrepresentable Condition (EIC) and Group Irrepresentable Condition (GIC). This theoretical analysis is validated by experiments on simulated datasets by comparison with different methods: Lasso, Elastic-net and Cluster Group Lasso. Moreover, we shows that the algorithm is able to improve the results compared to the mentioned methods on a real-world dataset.
The rest of this paper is organized as follows. In section , we provide notations, assumptions and background to be used later. In section , we review mathematical theory of the Lasso, the Elastic-net and the group Lasso. In section , we describe the proposed algorithm which mostly selects more adequate models in terms of model interpretation and prediction performance. In section , we provide numerical results based on simulated and real dataset. Section contains the computational details and we shall provide conclusion in section .
.
We consider the usual linear regression set up as given in Equation ( ). We assume that the components of the noise vector ∈ are i.i.d. (0, 2). The columns of the design matrix X are denoted by . We assume that the design matrix X is fixed, the data is centred and the predictors are standardized, so that ∑︀=1 = 0, ∑︀ =1 = 0 and 1 ′ = 1 for all = 1, ..., . The ℓ1-norm is denoted by ‖.‖1, the ℓ2-norm is denoted by ‖.‖2 and the ℓ∞ norm is denoted by ‖.‖∞. The minimum eigenvalue of a matrix A is denoted as (). The true active set 0 denotes the support of the subset selection solution (0 = (0)) and defined as 0 = {; 0 ̸= 0}. For any given ⊂ {1, 2, ..., }, the is a × 1 vector which has zeroes outside the set S, as given by where I is the indicator function. Then we have The (scaled) Gram matrix (covariance matrix) is defined as = { ( ∈ )}, = + .
^ =
X′X We use correlation based, bottom-up agglomerative hierarchical clustering methods to cluster predictors, which forms groups of variables based on correlations between them. To determine number of clusters we use the bootstrap approach, see stability feature in [ ]. variable selection simultaneously due to the nature of the ℓ1-penalty. We denote ^ , as a Lasso estimated parameter vector, which is defined as: where is the regularization parameter. The Lasso estimated active set is denoted as ^ and defined as ^ = {; (^) ̸= 0}.
The major disadvantages of the Lasso are: the Lasso tends to select single variable from any group and, it can select at most n variables for ≫ case. To overcome the above limitations of the Lasso, the Elastic-net was proposed by [ ]. The estimated parameter vector by naive Elastic-net is denote by , and defined as
1 ^ = { ‖y − X‖22 + ‖‖1 + ‖‖2},
∈R where ∈ [0, 1] and ≥ 0 are the regularization parameters. Since the Elastic-net estimate is (1 + 2)^ , it selects the same variable as the ^ , we consider the ^ as the Elastic-net estimate. The Elastic-net estimated active set is denoted as ^ and defined as ^ = {; (^ ) ̸= 0}.
When the distinct groups or clusters among the variables are known a priory and it is desirable to select or drop the whole group instead of single variables, then the Group Lasso (see [ ]) or its variants (i. e., Group Square-Root Lasso [ ] and Adaptive group Lasso [ ] are used, that imposes an 2-penalty on the coefficients within each group to achieve group sparsity.
Here we define some more notations and state assumptions for the group Lasso. We may interchangeably use 0 and for the true regression coefficient vector, the later one is without the superscript. Let us assume that the parameter vector is structured into groups, = {1, ..., }, where < , denotes the number of groups. The partition basically builds a partition of the index set {1, ..., } with ∪=1 = {1, ..., } and ∩ = ∅, for ̸= . The parameter vector , then has the structure = {1 , ..., } where = { : ∈ }. The columns of each group are represented by X , then the response vector Y can also be written as
Y = ∑︁ X() + ,
=1 The loss function of the group Lasso is the same as the loss function of the Lasso 1 ‖Y − X‖22. The group Lasso penalty is defined as
‖‖2,1 = ∑︀=1 ‖X ‖2√︁ , where = | | is the group size. Since the penalty is invariant under parametrizations within-group. Therefore, without loss of generality, we can assume = . Hence the group Lasso penalty can be written as
‖‖2,1 = ∑︁ √ ‖ ‖2 =1 ( ) ( ) The Group Lasso estimator (with known q groups) is defined as ^ 1 ∈ { ‖Y − X‖22 + ‖‖2,1}
Let W denote the active group set, ⊂ {1, ..., }, with cardinality = | |, then we assume: (i) the size of the each group is less than the number of observations < , and (ii) the number of active groups, w, is less than the number of observations (sparsity assumption). We denote the clusters selected by the group Lasso as ^, which is defined as ^ = { : cluster is selected, = 1, ..., } The union of the selected clusters gives the selected set of variables. ^ = ∪∈^ ( ) ( ) ( ) .4
When group structure is not known, the cluster Lasso methods are preferred, they perform clustering followed by the sparse estimation. The clusters 1, ..., are generated from the design matrix X ( i.e. using correlation based method etc.). When the group Lasso is applied to the resulting clusters, it is called Cluster Group Lasso, and when the Lasso is applied for the cluster representatives, it is called Cluster Representative Lasso, see [ ].
In this section, we briefly review the results required for proving consistent variable selection (and group variable selection) in high dimensional linear models. For more details on mathematical theory for the Lasso and the group Lasso, we refer to: [ ], [ ], [ ], [ ] and [ ], and for the Elastic-net we refer to [ ]. Let us assume a fixed set ⊂ {1, ..., } with cardinality = || and partitions of the covariance matrix and parameter vector as given by the Equations ( ) and ( ) respectively, for the following definitions.
condition is said to be met for the set S with a constant > 0, if the following holds: ‖121−11()(1)‖∞ ≤ 1 − . ( )
Sufficient conditions (eigenvalue and mutual incoherence) on the design matrix to hold IC are discussed in [ ] and [ ].
Definition (Beta-min Condition). The Beta Min Condition is met for the regression coefficient , if min | | ≥ 42() , where () is the compatibility condition, see [ ].
Lemma . Under the following assumptions the Lasso selects the set with a high probability: – Irrepresentable condition holds for .
– Beta-min condition holds for the parameter vector .
EIC is met for the set , with a constant > 0, if the following holds.
)−1((10) + 2 10)‖∞ ≤ 1 − Proposition . For a given set , if IC holds then it implies that for any > 0, there exists , such that EIC holds, but EIC does not imply IC.
When IC holds it is easy to show that the EIC also holds, since = 0 makes the EIC same as IC. The EIC may hold even when 11 is not invertible, it proves that the EIC does not imply the IC .
Now we discuss necessary conditions for the group variable selection. Our error analysis for the group Lasso is based on the pure active group and pure noise group assumptions, that is all variables are active variables within an active group and no variables are active in a noise group and we also assume that the clustering process identifies the group structure correctly.
It is convenient to assume the following. Let ⊂ {1, ..., } be a group index set, say, = {1, ..., } Consider the full index set corresponding to W as = {(1, 1), ..., (1, 1), ..., (, 1), ..., (, )} = {1, ..., } where = ∑︀=1 . We partition the 11() covariance matrix group wise, and denote its inverse as . (here we assume that each , is non-singular, or one may use the pseudo inverse) . . .
We note that diagonal elements are × identity matrix due to within group parameterization invariance property.
Definition 4 (Group Irrepresentability Condition (GIC)). The GIC is met for the set W with a constant > 0, if the following holds ‖(21 ()) ‖ ≤ 1 − ∀ ̸∈ , ( ) where the inequality holds group wise.
⎡
⎢ 2−21/2211−11/2 = ⎢⎣⎢⎢ ...
−1/211−11/2 −1/222−21/2 ...
1−11/2122−21/2 ... 1−11/21−1/2 ⎤ ... 2−21/22−1/2 ⎥⎥ . . . ... ⎦⎥⎥ We note that the GIC definition reduces to the IC for singleton groups.
is met for , if ‖ ‖∞ ≥ √ ∀ ∈ , where > 0 is a constant which depends on , and other constants used in cone constraints and GIC. For its exact form, we refer to [ ]. We note that, only one component of the , ∀ ∈ has to be sufficiently large, because we aim to select groups as a whole, and not individual variables.
Theorem . Under the following assumptions the group Lasso selects the set of active groups with a high probability.
– The GIC holds for . – Group beta-min condition holds for , ∀ ∈ .
Now we show that the IC implies the GIC, and the converse is not true. Lemma . If the IC holds for the set S, then the GIC holds for the set W, but the converse is not true.
Here we give sketch of the proof. If the IC holds for the set S, then the GIC holds for the singleton groups, therefore the GIC holds for any group structure within S. It is easy to show that the 11 is not invertible when active variables are correlated, but the 11 may be invertible after within group transformation and GIC may hold. Therefore IC is more restrictive than GIC, hence converse of the theorem is not true.
We consider high dimensional settings, where group of variables are highly correlated. It is known that the Lasso tends to select one or few variables from the group of highly correlated variables, even though many or all of them belong to the active set. The CL methods have proven to be effective in selecting group variables and reducing false negatives. The two major drawbacks of the CL methods are: selection of groups does not work well when there is a large number of groups, and the time complexity for clustering when p is large is unacceptable. We try to address these problems using Elastic-net as a pre-selection for the CL methods, as described in the Algorithm . The variable selection consistency for the Elastic-net and the CL methods have been already proven under the EIC and the GIC respectively, see [ ] and [ ]. In the following, we discuss various situations where Elastic-net+CL consistently selects the active set with a high probability, and situations where our scheme may fail to select the true variables.
: The Elastic-net+CL Algorithm Input: dataset (Y,X) Output: ^:= set of selected variables Steps: . Perform Elastic-net on data (Y,X), and denote ^ as variable set selected.
Let X = X^ be the reduced design matrix. . Perform Clustering of variables on data X, and denote the clusters as 1, ..., . . Perform group Lasso on (Y, X) with group information 1, ..., , and denote the selected set of groups as ^ = {; cluster is selected, = 1, ..., }.
The union of the selected groups is then the selected set of variables ^ = ∪ ∈ ^ return ^
Suppose that for a given set , the design matrix X satisfies the IC, which implies that the EIC and the GIC will also be satisfied for the set , see Proposition and Lemma . It follows that with a high probability (w.h.p.) the Elastic-net will select the true variables and similarly, for any group structure within S will yield the group selection consistency for the group Lasso, w.h.p. Therefore in this situation, the Elastic-net+CL shows variable selection consistency.
Case The EIC and the GIC both hold:
Apart from the previous case, this situation may also arise when two or more variables within set are highly correlated, then IC does not hold for the set S (since 11 is not invertible), but the EIC and the GIC will be satisfied. Using the same argument as for the preceding case, it is easy to show that the combination has variable selection consistency.
Case The EIC holds but the GIC does not hold:
This situation may arise for the overlapping groups, when the active groups are highly correlated, then the design matrix does not satisfy the GIC, but the EIC may hold for the set . In such cases, though the Elastic-net may select true active set w.h.p., but the subsequent group Lasso may fail to select the active set.
Case The GIC holds but the EIC does not hold:
This situation can come when there are near linear dependences among set of active variables, the EIC may not hold and Elastic-net tends to select single or a few variables from the group of linearly dependent variables. If we correctly put the linearly dependent variables in appropriate clusters (one may use the canonical correlation based clustering, see [ ]) then GIC may hold. Since, the pre-selection step itself fails to select the true active set, hence our scheme of pre-selection for CL methods may not work in this case.
We illustrate the above four cases with simulation studies in the next section. We do not consider the case when the EIC and the GIC both do not hold, because neither the pre-selection nor the CL methods are guaranteed to select the true variables. 5
In this section, we consider four simulation settings and a real data example in order to empirically compare performance of the proposed scheme with the other existing methods; the Lasso [ ], the Elastic-net [ ] and the CGLCor [ ]. 5.
Four examples are considered in this simulation that correspond to the cases discussed in the preceding section. In each example, data is simulated from the linear model in Equation ( ) with fixed design X. For each example, our simulated dataset consisted of a training and an independent validation set and such datasets were simulated for each example. The models were fitted on the training data for each datasets and the model with the lowest test set Mean Squared Error (MSE) was selected as the final model. For model interpretation, we consider the pair (TN, FN), where TN denotes true negative, that is the number of zero coefficients that are correctly estimated by zero and FN denotes false negative, that is the number of non zero coefficients that are incorrectly estimated by zero. As our aim is to avoid false negatives, we mainly focus on FN while analysing the different estimators. The MSE and the (TN, FN) are defined as follows.
= 1 ∑︁( − ^)2
=1 = |^ ⋂︁ | = |^ ⋂︁ | ( ) ( ) ( )
We generate covariates from (0, ) with p= and n= , where for four different cases are defined later. ∼ (0, 2), we set the = 3. For the regression coefficient we set 0 = {3, ..., 3, 0, ..., 0} , where the first twenty variables are set as active variables, = {1, ..., 20}, and the remaining variables are noise features.
The Orthogonal Model: In this case, the variables are uncorrelated that implies 1 is a 40 × 40 identity matrix, hence the IC, EIC and GIC hold for the set .
The simulation results (the minimum MSE with standard deviation for runs, and the minimum TN and FN) are presented in the Table , from which it is easy to interpret that all the estimators report no false negatives.
The Table shows the simulation results for the block diagonal model. As expected, the Lasso fails to select the correlated active components. However, the Elastic-net, CGLCor and Elastic-net+CGLCor report no false negatives. Linear Dependency Model: This situation arises, when a covariate is near linear dependent on two or more covariates. Here we simulate X ∼ (0, ), then we set the linear dependency as follows. Here we use the canonical correlation based clustering technique for CL methods, see CGL method in [ ]. The Table shows the simulation results for the linear dependency model, from which it is clear that the Lasso, the Elastic-net and the Elastic-net+CGL could not avoid false negatives. Correlation within active groups: We consider similar set up as block diagonal model except we make the first two groups (active groups) correlated. In this case, the smallest eigenvalue of the 11 is very small and the GIC does not hold. But the EIC will be satisfied since the correlation is high within active groups only. Though, the Elastic-net is consistent but the Elastic-net+CGLCor may perform poorly.
The simulation results are presented in the Table , from which it is clear that only Elastic-net method correctly identifies the true active set.
In this section, we consider the gene selection problem in leukaemia data (see [ ]) to compare the Elastic-net+CL scheme with other methods. The leukaemia data consists of genes and samples, among which are type leukaemia and are type leukaemia. We consider part of the leukaemia dataset, we first select the most significant genes and then the least significant genes, according to their t-statistic scores (see [ ]), so that the true active set is = {1, ..., 50}. We used tenfold Cross-Validation method for choosing the regularization parameters.
The simulation results (TN and FN along with cross-validation error) are presented in the Table , from which it is clear that the Elastic-net+CGLCor outperforms in terms of model interpretation and variable selection. Statistical analysis was performed in R . . . We used the package glmnet for penalized regression methods (the Lasso and the Elastic-net), the package gglasso to perform group Lasso and the package ClustOfVar for clustering of variables. 7
In this article, we proposed pre-selection using Elastic-net for CL methods for variable selection in high-dimensional linear model with strongly correlated variables. We proved that the variable set selected by the Elastic-net+CL method contains the true active set consistently under IC or EIC+GIC and beta-min conditions. We discussed that reducing dimensionality improves the speed and accuracy of the clustering process, and we explored theoretically how the proposed combination of algorithms performed under various conditions. Our simulation studies showed that combining Elastic-net and Cluster Lasso methods improved variable selection and predictive performance.
The authors would like to thank the anonymous reviewers of this paper for their suggestions and constructive comments.