Lasso算法

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

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

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

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

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

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

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

假设一个样本包括N种事件，每个事件包括个协变量和一个输出值。让${\displaystyle y_i}$ 行，那么上式可以写成更紧凑的形式：

这里 ${\displaystyle \Vert <!--\; \Vert \; -->\mathrm{\beta <!--\; \beta \; -->}{\Vert <!--\; \Vert \; -->}_p={\left(\underset{i=1}{\overset{N}{\sum <!--\; \sum \; -->}}|{\mathrm{\beta <!--\; \beta \; -->}}_i{|}^p\right)}^{1/p}}$ and , are identical for each case, so that ${\displaystyle x_{(j)}=x_{(k)}}$, where ${\displaystyle x_{(j),i}=x_{ij}}$. Then the values of ${\displaystyle {\mathrm{\beta <!--\; \beta \; -->}}_j}$ and ${\displaystyle {\mathrm{\beta <!--\; \beta \; -->}}_k}$ that minimize the lasso objective function are not uniquely determined. In fact, if there is some solution ${\displaystyle \stackrel{^<!--\; ^\; -->}{\mathrm{\beta <!--\; \beta \; -->}}}$ in which ${\displaystyle {\stackrel{^<!--\; ^\; -->}{\mathrm{\beta <!--\; \beta \; -->}}}_j{\stackrel{^<!--\; ^\; -->}{\mathrm{\beta <!--\; \beta \; -->}}}_k\ge <!--\; \ge \; -->0}$, then if ${\displaystyle s\in <!--\; \in \; -->}$ replacing ${\displaystyle {\stackrel{^<!--\; ^\; -->}{\mathrm{\beta <!--\; \beta \; -->}}}_j}$ by ${\displaystyle s({\stackrel{^<!--\; ^\; -->}{\mathrm{\beta <!--\; \beta \; -->}}}_j+{\stackrel{^<!--\; ^\; -->}{\mathrm{\beta <!--\; \beta \; -->}}}_k)}$ and ${\displaystyle {\stackrel{^<!--\; ^\; -->}{\mathrm{\beta <!--\; \beta \; -->}}}_k}$ by ${\displaystyle (1-<!--\; -\; -->s)({\stackrel{^<!--\; ^\; -->}{\mathrm{\beta <!--\; \beta \; -->}}}_j+{\stackrel{^<!--\; ^\; -->}{\mathrm{\beta <!--\; \beta \; -->}}}_k)}$, while keeping all the other ${\displaystyle {\stackrel{^<!--\; ^\; -->}{\mathrm{\beta <!--\; \beta \; -->}}}_i}$ 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, have been designed to address this shortcoming, which are discussed below.