Questions tagged [lasso]

LASSO is an acronym for least absolute shrinkage and selection operator. It is a form of regularization used in the estimation of regression coefficients that shrinks coefficient estimates by penalizing their absolute value (i.e. the $L_1$ norm of the estimates). Some coefficients may be shrunk to zero; thus the lasso performs feature selection. The lasso is equivalent to the Bayesian estimation problem where an i.i.d. standard Laplacian prior is used for the regression parameters.

In the context of linear regression, we can formulate the LASSO problem as:

Given a set of training data $(x_1,y_1),...,(x_n,y_n)$ where $x_i \in \mathbb{R}^{p}$ we attempt to find a vector of coefficients $\hat{\beta}_{LASSO} \in \mathbb{R}^{p}$ such that the following holds:

$$\hat{\beta}_{LASSO} = \underset{\beta} {\text{argmin}} \sum\limits_{i=1}^{N}(y_i - \sum\limits_{j=1}^{p}x_{i,j}\beta_{j})^2$$

$$ \text{subject to } \sum\limits_{j=1}^{p}|\beta_{j}| \leq t$$

Due to the nature of the $L_1$ penalty, there is no closed form solution for $\hat{\beta}_{LASSO}$, so computing the LASSO is a quadratic programming problem, unlike ridge where a closed form exists.

In a Bayesian context, we can derive an equivalent regularization penalty by finding the $\beta$ which maximizes the posterior, the MAP estimate:

Assume a Laplacian prior on $\beta$:

$$\pi(\beta|\tau) \propto e^{-\frac{1}{2\tau}\sum_{j=1}^{p} |\beta_j|}$$

If we assume that $y \sim N(X\beta,\sigma^2 I)$, then the posterior of $\beta$:

$$P(\beta|X,Y,\sigma^2,\tau) \propto \prod_{i=1}^{n}e^{-\frac{1}{2\sigma^2}(y_i - x_i^T\beta)^2}e^{-\frac{1}{2\tau}\sum_{j=1}^{p} |\beta_j|} $$

The MAP estimate above is equivalent to minimizing twice the negative log:

$$ \propto \frac{1}{\sigma^2} \sum_{i=1}^{n} (y_i - x_i^T \beta)^2 + \frac{1}{\tau}\sum_{j=1}^{p} |\beta_j| $$

Let $\lambda = \frac{\sigma^2}{\tau}$. The final expression is:

$$\hat{\beta} = \underset{\beta} {\text{argmin}} \sum_{i=1}^{n} (y_i - x_i\beta)^2 + \lambda\sum_{j=1}^{p} |\beta_j| = \hat{\beta}_{LASSO}$$