Lasso算法

在统计学和机器学习中，Lasso算法（，又译最小绝对值收敛和选择算子、套索算法）是一种同时进行特征选择和正则化（数学）的回归分析方法，旨在增强统计模型的预测准确性和可解释性，最初由斯坦福大学统计学教授罗伯特·蒂布希拉尼于1996年基于Leo Breiman的非负参数推断（Nonnegative Garrote, NNG）提出。Lasso算法最初用于计算最小二乘法模型，这个简单的算法揭示了很多估计量的重要性质，如估计量与岭回归（Ridge regression，也叫吉洪诺夫正则化）和最佳子集选择的关系，Lasso系数估计值和软阈值（soft thresholding）之间的联系。它也揭示了当协变量共线时，Lasso系数估计值不一定唯一（类似标准线性回归）。

虽然最早是为应用最小二乘法而定义的算法，lasso正则化可以简单直接地拓展应用于许多统计学模型上，包括广义线性模型，广义估计方程，成比例灾难模型和M-估计。Lasso选择子集的能力依赖于限制条件的形式并且有多种表现形式，包括几何学，贝叶斯统计，和凸分析。

Lasso算法与基追踪降噪联系紧密。

历史来源
蒂布希拉尼最初使用Lasso来提高预测的准确性与回归模型的可解释性，他修改了模型拟合的过程，在协变量中只选择一个子集应用到最终模型中，而非用上全部协变量。这是基于有着相似目的，但方法有所不同的Breiman的非负参数推断。

在Lasso之前，选择模型中协变量最常用的方法是移步选择，这种方法在某些情况下是准确的，例如一些协变量与模型输出值有强相关性情况。然而在另一些情况下，这种方法会让预测结果更差。在当时，岭回归是提高模型预测准确性最常用的方法。岭回归可以通过缩小大的回归系数来减少过拟合从而改善模型预测偏差。但是它并不选择协变量，所以对模型的准确构建和解释没有帮助。

Lasso结合了上述的两种方法，它通过强制让回归系数绝对值之和小于某固定值，即强制一些回归系数变为0，有效地选择了不包括这些回归系数对应的协变量的更简单的模型。这种方法和岭回归类似，在岭回归中，回归系数平方和被强制小于某定值，不同点在于岭回归只改变系数的值，而不把任何值设为0。

基本形式
Lasso最初为了最小二乘法而被设计出来，Lasso的最小二乘法应用能够简单明了地展示Lasso的许多特性。

最小二乘
假设一个样本包括N种事件，每个事件包括p个协变量和一个输出值。让 y_i 为输出值，并且 x_i:=(x_1,x_2,\ldots,x_p)^T为第i种情况的协变量向量，那么Lasso要计算的目标方程就是：

对所有 \sum_{j=1}^p |\beta_j| \leq t ，计算 \min_{ \beta_0, \beta } \left\{ \frac{1}{N} \sum_{i=1}^N (y_i - \beta_0 - x_i^T \beta)^2 \right\} It is assumed that X is standardized with z-scores and that y is centered (zero mean). Let \beta_0 represent the hypothesized regression coefficients and let b_{OLS} 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

: \min_{ \beta \in \mathbb{R}^p }
\left\{
\frac{(y-X\beta)'(y-X\beta)}{(y-X\beta_0)'(y-X\beta_0)}+ 2\lambda \sum_{i=1}^p \frac{q_{i}}
\right\}

where q_i is specified below. The first fraction represents relative accuracy, the second fraction relative simplicity, and \lambda balances between the two.

Given a single regressor, relative simplicity can be defined by specifying q_i as |b_{OLS}-\beta_{0}|, which is the maximum amount of deviation from \beta_0 when \lambda=0 . Assuming that \beta_{0}=0, the solution path can be defined in terms of R^2:
:
b_{\ell_1} = \begin{cases}
(1-\lambda/R^{2})b_{OLS} & \mbox{if } \lambda \leq R^{2}, \\
0 & \mbox{if } \lambda>R^{2}.
\end{cases}

If \lambda=0, the ordinary least squares solution (OLS) is used. The hypothesized value of \beta_0=0 is selected if \lambda is bigger than R^2. Furthermore, if R^2=1, then \lambda represents the proportional influence of \beta_0=0. In other words, \lambda\times100\% measures in percentage terms the minimal amount of influence of the hypothesized value relative to the data-optimized OLS solution.

If an \ell_2-norm is used to penalize deviations from zero given a single regressor, the solution path is given by

b_{\ell_2}=\bigg(1+\frac{\lambda}{R^{2}(1-\lambda)}\bigg)^{-1}b_{OLS}. Like b_{\ell_1}, b_{\ell_2} moves in the direction of the point (\lambda = R^2, b=0) when \lambda is close to zero; but unlike b_{\ell_1}, the influence of R^2 diminishes in b_{\ell_2} if \lambda increases (see figure).
Given multiple regressors, the moment that a parameter is activated (i.e. allowed to deviate from \beta_0) is also determined by a regressor's contribution to R^2 accuracy. First,
: R^2=1-\frac{(y-Xb)'(y-Xb)}{(y-X\beta_0)'(y-X\beta_0)}.
An R^2 of 75% means that in-sample accuracy improves by 75% if the unrestricted OLS solutions are used instead of the hypothesized \beta_0 values. The individual contribution of deviating from each hypothesis can be computed with the p x p matrix
: R^{\otimes}=(X'\tilde y_0)(X'\tilde y_0)' (X'X)^{-1}(\tilde y_0'\tilde y_0)^{-1},
where \tilde y_0=y-X\beta_0. If b=b_{OLS} when R^2 is computed, then the diagonal elements of R^{\otimes} sum to R^2. The diagonal R^{\otimes} values may be smaller than 0 or, less often, larger than 1. If regressors are uncorrelated, then the i^{th} diagonal element of R^{\otimes} simply corresponds to the r^2 value between x_i and y.

A rescaled version of the adaptive lasso of can be obtained by setting q_{\mbox{adaptive lasso},i}=|b_{OLS,i}-\beta_{0,i}|. If regressors are uncorrelated, the moment that the i^{th} parameter is activated is given by the i^{th} diagonal element of R^{\otimes}. Assuming for convenience that \beta_0 is a vector of zeros,
: b_{i} = \begin{cases}
(1-\lambda/R_{ii}^{\otimes})b_{OLS,i} & \mbox{if } \lambda \leq R_{ii}^{\otimes}, \\
0 & \mbox{if } \lambda>R_{ii}^{\otimes}.
\end{cases}

That is, if regressors are uncorrelated, \lambda again specifies the minimal influence of \beta_0. Even when regressors are correlated, the first time that a regression parameter is activated occurs when \lambda is equal to the highest diagonal element of R^{\otimes}.

These results can be compared to a rescaled version of the lasso by defining q_{\mbox{lasso},i}=\frac{1}{p} \sum_{l} |b_{OLS,l}-\beta_{0,l}|, which is the average absolute deviation of b_{OLS} from \beta_0. Assuming that regressors are uncorrelated, then the moment of activation of the i^{th} regressor is given by
: \tilde \lambda_{\text{lasso},i} = \frac{1}{p}\sqrt{R^{\otimes}_i} \sum_{l=1}^p\sqrt{R^{\otimes}_{l}}.

For p=1, the moment of activation is again given by \tilde \lambda_{\text{lasso},i}=R^2. If \beta_0 is a vector of zeros and a subset of p_B relevant parameters are equally responsible for a perfect fit of R^2=1, then this subset is activated at a \lambda value of \frac{1}{p}. The moment of activation of a relevant regressor then equals \frac{1}{p}\frac{1}{\sqrt{p_B}}p_B\frac{1}{\sqrt{p_B}}=\frac{1}{p}. 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.和高增长公司预测。

参见

• 降维
• 特征选择

参考文献