Lasso (statistics)
In statistics and machine learning, lasso (least absolute shrinkage and selection operator; also Lasso or LASSO) is a regression analysis method that performs both variable selection and regularization in order to enhance the prediction accuracy and interpretability of the resulting statistical model. It was originally introduced in geophysics, and later by Robert Tibshirani, who coined the term. Lasso was originally formulated for linear regression models. This simple case reveals a substantial amount about the estimator. These include its relationship to ridge regression and best subset selection and the connections between lasso coefficient estimates and so-called soft thresholding . It also reveals that (like standard linear regression) the coefficient estimates do not need to be unique if covariates are collinear. Though originally defined for linear regression, lasso regularization is easily extended to other statistical models including generalized linear models, generalized estimating equations, proportional hazards models, and M-estimators. Lasso's ability to perform subset selection relies on the form of the constraint and has a variety of interpretations including in terms of geometry, Bayesian statistics and convex analysis. The LASSO is closely related to basis pursuit denoising. Motivation. Lasso was introduced in order to improve the prediction accuracy and  interpretability of regression models. It selects a reduced set of the known covariates for use in a model. History. Lasso was developed independently in geophysics literature in 1986, based on prior work that used the formula_1 penalty for both fitting and penalization of the coefficients. Statistician Robert Tibshirani independently rediscovered and popularized it in 1996, based on Breiman's nonnegative garrote. Prior to lasso, the most widely used method for choosing covariates was stepwise selection. That approach only improves prediction accuracy in certain cases, such as when only a few covariates have a strong relationship with the outcome. However, in  other cases, it can increase prediction error. At the time, ridge regression was the most popular technique for improving prediction accuracy. Ridge regression improves prediction error by shrinking the sum of the squares of the regression coefficients to be less than a fixed value in order to reduce overfitting, but it does not perform covariate selection and therefore does not help to make the model more interpretable. Lasso achieves both of these goals by forcing the sum of the absolute value of the regression coefficients to be less than a fixed value, which forces certain coefficients to zero, excluding them  from impacting prediction. This idea is similar to ridge regression, which also shrinks the size of the coefficients, however Ridge Regression tends to set far fewer coefficients to zero. Basic form. Least squares. Consider a sample consisting of "N" cases, each of which consists of "p" covariates and a single outcome. Let formula_2 be the outcome and formula_3 be the covariate vector for the "i" case. Then the objective of lasso is to solve Here formula_5 is the constant coefficient, formula_6 is the coefficient vector, and formula_7 is a prespecified free parameter that determines the degree of regularization. Letting formula_8  be the covariate matrix, so that formula_9 and formula_10 is the "i" row of formula_11, the expression can be written more compactly as where formula_13 is the standard formula_14 norm. Denoting the scalar mean of the data points formula_15 by formula_16 and the mean of the response variables formula_17 by formula_18, the resulting estimate for formula_19 is formula_20, so that and therefore it is standard to work with variables that have been made zero-mean. Additionally, the covariates are typically standardized formula_22 so that the solution does not depend on the measurement scale. It can be helpful to rewrite in  the so-called Lagrangian form where the exact relationship between formula_25 and formula_26 is data dependent. Orthonormal covariates. Some basic properties of the lasso estimator can now be considered. Assuming first that the covariates are orthonormal so that formula_27, where formula_28 is the inner product and formula_29 is the Kronecker delta, or, equivalently, formula_30, then using subgradient methods it can be shown that formula_32 is referred to as the soft thresholding operator, since it translates values towards zero (making them exactly zero if they are small enough) instead of setting smaller values to zero and leaving larger ones untouched as  the hard thresholding operator, often denoted formula_33, would. In ridge regression the objective is to minimize yielding Ridge regression shrinks all coefficients by a uniform factor of formula_36 and does not set any coefficients to zero. It can also be compared to regression with best subset selection, in which the goal is to minimize where formula_38 is the "formula_39 norm", which is defined as formula_40 if exactly m components of z are nonzero. In this case, it can be shown that where formula_33 is the so-called hard thresholding function and formula_43 is an indicator function (it is 1 if  its argument is true and 0 otherwise). Therefore, the lasso estimates share features of both ridge and best subset selection regression since they both shrink the magnitude of all the coefficients, like ridge regression and set some of them to zero, as in the best subset selection case. Additionally, while ridge regression scales all of the coefficients by a constant factor, lasso instead translates the coefficients towards zero by a constant value and sets them to zero if they reach it. Correlated covariates. In one special case two covariates, say "j" and "k", are identical for each observation, so that  formula_44, where formula_45. Then the values of formula_46 and formula_47 that minimize the lasso objective function are not uniquely determined. In fact, if some formula_48 in which formula_49, then if formula_50 replacing formula_51 by formula_52 and formula_53 by formula_54, while keeping all the other formula_55 fixed, gives a new solution, so the lasso objective function then has a continuum of valid minimizers. Several variants of the lasso, including the Elastic net regularization, have been designed to address this shortcoming. General form. Lasso regularization can be extended to other objective functions such as those for generalized linear models, generalized estimating equations , proportional hazards models, and M-estimators. Given the objective function the lasso regularized version of the estimator "s" the solution to where only formula_58 is penalized while formula_59 is free to take any allowed value, just as formula_5 was not penalized in the basic case. Interpretations. Geometric interpretation. Lasso can set coefficients to zero, while the superficially similar ridge regression cannot. This is due to the difference in the shape of their constraint boundaries. Both lasso and ridge regression can be interpreted as minimizing the same objective function but with respect to different constraints: formula_62 for lasso and formula_63  for ridge. The figure shows that the constraint region defined by the formula_64 norm is a square rotated so that its corners lie on the axes (in general a cross-polytope), while the region defined by the formula_65 norm is a circle (in general an "n"-sphere), which is rotationally invariant and, therefore, has no corners. As seen in the figure, a convex object that lies tangent to the boundary, such as the line shown, is likely to encounter a corner (or a higher-dimensional equivalent) of a hypercube, for which some components of formula_58 are identically zero, while in the  case of an "n"-sphere, the points on the boundary for which some of the components of formula_58 are zero are not distinguished from the others and the convex object is no more likely to contact a point at which some components of formula_58 are zero than one for which none of them are. Making λ easier to interpret with an accuracy-simplicity tradeoff. The lasso can be rescaled so that it becomes easy to anticipate and influence the degree of shrinkage associated with a given value of formula_26. It is assumed that formula_11 is standardized with z-scores and that  formula_71 is centered (zero mean). Let formula_19 represent the hypothesized regression coefficients and let formula_73 refer to the data-optimized ordinary least squares solutions. We can then define the Lagrangian as a tradeoff between the in-sample accuracy of the data-optimized solutions and the simplicity of sticking to the hypothesized values. This results in where formula_75 is specified below. The first fraction represents relative accuracy, the second fraction relative simplicity, and formula_76 balances between the two. Given a single regressor, relative simplicity can be defined by specifying formula_77 as formula_78, which is the maximum amount of deviation from formula_19  when formula_80. Assuming that formula_81, the solution path can be defined in terms of formula_82: If formula_84, the ordinary least squares solution (OLS) is used. The hypothesized value of formula_85 is selected if formula_76 is bigger than formula_82. Furthermore, if formula_88, then formula_76 represents the proportional influence of formula_85. In other words, formula_91 measures in percentage terms the minimal amount of influence of the hypothesized value relative to the data-optimized OLS solution. If an formula_92-norm is used to penalize deviations from zero given a single regressor, the solution path is given by formula_93. Like formula_94, formula_95 moves in  the direction of the point formula_96 when formula_76 is close to zero; but unlike formula_94, the influence of formula_82 diminishes in formula_95 if formula_76 increases (see figure). Given multiple regressors, the moment that a parameter is activated (i.e. allowed to deviate from formula_19) is also determined by a regressor's contribution to formula_82 accuracy. First, An formula_82 of 75% means that in-sample accuracy improves by 75% if the unrestricted OLS solutions are used instead of the hypothesized formula_19 values. The individual contribution of deviating from each hypothesis can be computed with the formula_107 x formula_107 matrix where formula_110. If  formula_111 when formula_82 is computed, then the diagonal elements of formula_113 sum to formula_82. The diagonal formula_113 values may be smaller than 0 or, less often, larger than 1. If regressors are uncorrelated, then the formula_116 diagonal element of formula_113 simply corresponds to the formula_118 value between formula_15 and formula_71. A rescaled version of the adaptive lasso of can be obtained by setting formula_121. If regressors are uncorrelated, the moment that the formula_116 parameter is activated is given by the formula_116 diagonal element of formula_113. Assuming for convenience that formula_19 is a vector of zeros, That is, if regressors are  uncorrelated, formula_76 again specifies the minimal influence of formula_19. Even when regressors are correlated, the first time that a regression parameter is activated occurs when formula_76 is equal to the highest diagonal element of formula_113. These results can be compared to a rescaled version of the lasso by defining formula_131, which is the average absolute deviation of formula_73 from formula_19. Assuming that regressors are uncorrelated, then the moment of activation of the formula_116 regressor is given by For formula_136, the moment of activation is again given by formula_137. If formula_19 is a vector of zeros and a subset of formula_139  relevant parameters are equally responsible for a perfect fit of formula_88, then this subset is activated at a formula_76 value of formula_142. The moment of activation of a relevant regressor then equals formula_143. In other words, the inclusion of irrelevant regressors delays the moment that relevant regressors are activated by this rescaled lasso. The adaptive lasso and the lasso are special cases of a '1ASTc' estimator. The latter only groups parameters together if the absolute correlation among regressors is larger than a user-specified value. Bayesian interpretation. Just as ridge regression can be interpreted as linear regression for which the  coefficients have been assigned normal prior distributions, lasso can be interpreted as linear regression for which the coefficients have Laplace prior distributions. The Laplace distribution is sharply peaked at zero (its first derivative is discontinuous at zero) and it concentrates its probability mass closer to zero than does the normal distribution. This provides an alternative explanation of why lasso tends to set some coefficients to zero, while ridge regression does not. Convex relaxation interpretation. Lasso can also be viewed as a convex relaxation of the best subset selection regression problem, which is to find the subset of formula_144 covariates that  results in the smallest value of the objective function for some fixed formula_145, where n is the total number of covariates. The "formula_39 norm", formula_147, (the number of nonzero entries of a vector), is the limiting case of "formula_148 norms", of the form formula_149 (where the quotation marks signify that these are not really norms for formula_150 since formula_151 is not convex for formula_150, so the triangle inequality does not hold). Therefore, since p = 1 is the smallest value for which the "formula_14 norm" is convex (and therefore actually a norm), lasso is, in some sense, the best convex  approximation to the best subset selection problem, since the region defined by formula_154 is the convex hull of the region defined by formula_155 for formula_150. Generalizations. Lasso variants have been created in order to remedy limitations of the original technique and to make the method more useful for particular problems. Almost all of these focus on respecting or exploiting dependencies among the covariates. Elastic net regularization adds an additional ridge regression-like penalty that improves performance when the number of predictors is larger than the sample size, allows the method to select strongly correlated variables together, and improves overall prediction  accuracy. Group lasso allows groups of related covariates to be selected as a single unit, which can be useful in settings where it does not make sense to include some covariates without others. Further extensions of group lasso perform variable selection within individual groups (sparse group lasso) and allow overlap between groups (overlap group lasso). Fused lasso can account for the spatial or temporal characteristics of a problem, resulting in estimates that better match system structure. Lasso-regularized models can be fit using techniques including subgradient methods, least-angle regression (LARS), and proximal gradient methods. Determining the optimal value for  the regularization parameter is an important part of ensuring that the model performs well; it is typically chosen using cross-validation. Elastic net. In 2005, Zou and Hastie introduced the elastic net. When "p" > "n" (the number of covariates is greater than the sample size) lasso can select only "n" covariates (even when more are associated with the outcome) and it tends to select one covariate from any set of highly correlated covariates. Additionally, even when "n" > "p", ridge regression tends to perform better given strongly correlated covariates. The elastic net extends lasso by adding an additional formula_65  penalty term giving which is equivalent to solving This problem can be written in a simple lasso form letting Then formula_164, which, when the covariates are orthogonal to each other, gives So the result of the elastic net penalty is a combination of the effects of the lasso and ridge penalties. Returning to the general case, the fact that the penalty function is now strictly convex means that if formula_44, formula_167, which is a change from lasso. In general, if formula_168 is the sample correlation matrix because the formula_170 's are normalized. Therefore, highly correlated covariates tend to have similar  regression coefficients, with the degree of similarity depending on both formula_171 and formula_172, which is different from lasso. This phenomenon, in which strongly correlated covariates have similar regression coefficients, is referred to as the grouping effect. Grouping is desirable since, in applications such as tying genes to a disease, finding all the associated covariates is preferable, rather than selecting one from each set of correlated covariates, as lasso often does. In addition, selecting only one from each group typically results in increased prediction error, since the model is less robust (which is why ridge regression often outperforms lasso). Group lasso . In 2006, Yuan and Lin introduced the group lasso to allow predefined groups of covariates to jointly be selected into or out of a model. This is useful in many settings, perhaps most obviously when a categorical variable is coded as a collection of binary covariates. In this case, group lasso can ensure that all the variables encoding the categorical covariate are included or excluded together. Another setting in which grouping is natural is in biological studies. Since genes and proteins often lie in known pathways, which pathways are related to an outcome may be more significant than whether individual  genes are. The objective function for the group lasso is a natural generalization of the standard lasso objective where the design matrix formula_8 and covariate vector formula_58 have been replaced by a collection of design matrices formula_176 and covariate vectors formula_46, one for each of the J groups. Additionally, the penalty term is now a sum over formula_65 norms defined by the positive definite matrices formula_179. If each covariate is in its own group and formula_180, then this reduces to the standard lasso, while if there is only a single group and formula_181, it reduces to ridge regression. Since the  penalty reduces to an formula_65 norm on the subspaces defined by each group, it cannot select out only some of the covariates from a group, just as ridge regression cannot. However, because the penalty is the sum over the different subspace norms, as in the standard lasso, the constraint has some non-differential points, which correspond to some subspaces being identically zero. Therefore, it can set the coefficient vectors corresponding to some subspaces to zero, while only shrinking others. However, it is possible to extend the group lasso to the so-called sparse group lasso, which can select  individual covariates within a group, by adding an additional formula_64 penalty to each group subspace. Another extension, group lasso with overlap allows covariates to be shared across groups, e.g., if a gene were to occur in two pathways. Fused lasso. In some cases, the phenomenon under study may have important spatial or temporal structure that must be considered during analysis, such as time series or image-based data. In 2005, Tibshirani and colleagues introduced the fused lasso to extend the use of lasso to this type of data. The fused lasso objective function is The first constraint is the lasso  constraint, while the second directly penalizes large changes with respect to the temporal or spatial structure, which forces the coefficients to vary smoothly to reflect the system's underlying logic. Clustered lasso is a generalization of fused lasso that identifies and groups relevant covariates based on their effects (coefficients). The basic idea is to penalize the differences between the coefficients so that nonzero ones cluster. This can be modeled using the following regularization: In contrast, variables can be clustered into highly correlated groups, and then a single representative covariate can be extracted from each cluster. Algorithms exist that solve the  fused lasso problem, and some generalizations of it. Algorithms can solve it exactly in a finite number of operations. Quasi-norms and bridge regression. Lasso, elastic net, group and fused lasso construct the penalty functions from the formula_64 and formula_65 norms (with weights, if necessary). The bridge regression utilises general formula_14 norms (formula_189) and quasinorms (formula_190). For example, for "p"=1/2 the analogue of lasso objective in the Lagrangian form is to solve where It is claimed that the fractional quasi-norms formula_14 (formula_190) provide more meaningful results in data analysis both theoretically and empirically. The non-convexity of these quasi -norms complicates the optimization problem. To solve this problem, an expectation-minimization procedure is developed and implemented for minimization of function where formula_196 is an arbitrary concave monotonically increasing function (for example, formula_197 gives the lasso penalty and formula_198 gives the formula_199 penalty). The efficient algorithm for minimization is based on piece-wise quadratic approximation of subquadratic growth (PQSQ). Adaptive lasso. The adaptive lasso was introduced by Zou in 2006 for linear regression and by Zhang and Lu in 2007 for proportional hazards regression. Prior lasso. The prior lasso was introduced for generalized linear models by Jiang et al. in  2016 to incorporate prior information, such as the importance of certain covariates. In prior lasso, such information is summarized into pseudo responses (called prior responses) formula_200 and then an additional criterion function is added to the usual objective function with a lasso penalty. Without loss of generality, in linear regression, the new objective function can be written as which is equivalent to the usual lasso objective function with the responses formula_203 being replaced by a weighted average of the observed responses and the prior responses formula_204 (called the adjusted response values by the prior information). In prior lasso, the parameter  formula_205 is called a balancing parameter, in that it balances the relative importance of the data and the prior information. In the extreme case of formula_206, prior lasso is reduced to lasso. If formula_207, prior lasso will solely rely on the prior information to fit the model. Furthermore, the balancing parameter formula_205 has another appealing interpretation: it controls the variance of formula_58 in its prior distribution from a Bayesian viewpoint. Prior lasso is more efficient in parameter estimation and prediction (with a smaller estimation error and prediction error) when the prior information is of high quality, and is robust to  the low quality prior information with a good choice of the balancing parameter formula_205. Computing lasso solutions. The loss function of the lasso is not differentiable, but a wide variety of techniques from convex analysis and optimization theory have been developed to compute the solutions path of the lasso. These include coordinate descent, subgradient methods, least-angle regression (LARS), and proximal gradient methods. Subgradient methods are the natural generalization of traditional methods such as gradient descent and stochastic gradient descent to the case in which the objective function is not differentiable at all points. LARS is a method that is  closely tied to lasso models, and in many cases allows them to be fit efficiently, though it may not perform well in all circumstances. LARS generates complete solution paths. Proximal methods have become popular because of their flexibility and performance and are an area of active research. The choice of method will depend on the particular lasso variant, the data and the available resources. However, proximal methods generally perform well. Choice of regularization parameter. Choosing the regularization parameter (formula_76) is a fundamental part of lasso. A good value is essential to the performance of lasso since it controls the strength  of shrinkage and variable selection, which, in moderation can improve both prediction accuracy and interpretability. However, if the regularization becomes too strong, important variables may be omitted and coefficients may be shrunk excessively, which can harm both predictive capacity and inferencing. Cross-validation is often used to find the regularization parameter. Information criteria such as the Bayesian information criterion (BIC) and the Akaike information criterion (AIC) might be preferable to cross-validation, because they are faster to compute and their performance is less volatile in small samples. An information criterion selects the estimator's regularization parameter by maximizing a model 's in-sample accuracy while penalizing its effective number of parameters/degrees of freedom. Zou et al. proposed to measure the effective degrees of freedom by counting the number of parameters that deviate from zero. The degrees of freedom approach was considered flawed by Kaufman and Rosset and Janson et al., because a model's degrees of freedom might increase even when it is penalized harder by the regularization parameter. As an alternative, the relative simplicity measure defined above can be used to count the effective number of parameters. For the lasso, this measure is given by which monotonically increases  from zero to formula_213 as the regularization parameter decreases from formula_214 to zero. Selected applications. LASSO has been applied in economics and finance, and was found to improve prediction and to select sometimes neglected variables, for example in corporate bankruptcy prediction literature, or high growth firms prediction.