Lasso算法

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

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

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

历史来源

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

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

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

基本形式

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

假设一个样本包括N种事件，每个事件包括p个协变量和一个输出值。让${\ displaystyle y_ {i}}$为输出值，并且${\ displaystyle x_ {i}：=（x_ {1}，x_ {2}，\ ldots，x_ {p}）^ {T}}$为第i种情况的协变量向量，那么Lasso要计算的目标方程就是：

对所有 ${\ displaystyle \ sum _ {j = 1} ^ {p} | \ beta _ {j} | \ leq t}$，计算 ${\ displaystyle \ min _ {\ beta _ {0}，\ beta} \ left \ {{\ frac {1} {N}} \ sum _ {i = 1} ^ {N}（y_ {i}-\\ beta _ {0} -x_ {i} ^ {T} \ beta）^ {2} \ right \}}$^[1]

这里 ${\ displaystyle t}$ 是一个决定规则化程度的预定的自由参数。 设${\ displaystyle X}$为协方差矩阵，那么 ${\ displaystyle X_ {ij} =（x_ {i}）_ {j}}$，其中 ${\ displaystyle x_ {i} ^ {T}}$ 是 ${\ displaystyle X}$的第 i 行，那么上式可以写成更紧凑的形式：

对所有 ${\ displaystyle \ | \ beta \ | _ {1} \ leq t}$，计算 ${\ displaystyle \ min _ {\ beta _ {0}，\ beta} \ left \ {{\ frac {1} {N}} \ left \ | y- \ beta _ {0} -X \ beta \ right \ | _ {2} ^ {2} \ right \}}$

这里 ${\ displaystyle \ | \ beta \ | _ {p} = \ left（\ sum _ {i = 1} ^ {N} | \ beta _ {i} | ^ {p} \ right）^ {1 / p} }$ 是标准 ${\ displaystyle \ ell ^ {p}}$ 范数，${\ displaystyle 1_ {N}}$是${\ displaystyle N \ times 1}$维的1的向量。

因为 ${\ displaystyle {\ hat {\ beta}} _ {0} = {\ bar {y}}-{\ bar {x}} ^ {T} \ beta}$，所以有

${\ displaystyle y_ {i}-{\ hat {\ beta}} _ {0} -x_ {i} ^ {T} \ beta = y_ {i}-（{\ bar {y}}-{\ bar { x}} ^ {T} \ beta）-x_ {i} ^ {T} \ beta =（y_ {i}-{\ bar {y}}）-（x_ {i}-{\ bar {x}} ）^ {T} \ beta，}$

对变量进行中心化是常用的数据处理方法。并且协方差一般规范化为 ${\ displaystyle \ textstyle \ left（\ sum _ {i = 1} ^ {N} x_ {ij} ^ {2} = 1 \ right）}$ ，这样得到的解就不会依赖测量的规模。

它的目标方程还可以写为：

${\ displaystyle \ min _ {\ beta \ in \ mathbb {R} ^ {p}} \ left \ {{\ frac {1} {N}} \ left \ | yX \ beta \ right \ | _ {2} ^ {2} \ right \} {\ text {受}} \ | \ beta \ | _ {{1} \ leq t。}$

以所谓的拉格朗日形式

${\ displaystyle \ min _ {\ beta \ in \ mathbb {R} ^ {p}} \ left \ {{\ frac {1} {N}} \ left \ | yX \ beta \ right \ | _ {2} ^ {2} + \ lambda \ | \ beta \ | __ {1} \ right \}}$

之间的确切关系 ${\ displaystyle t}$ 和 ${\ displaystyle \ lambda}$ 与数据有关。

正交协变量

现在可以考虑套索估计器的一些基本属性。

首先假设协变量是正交的，这样${\ displaystyle（x_ {i} \ mid x_ {j}）= \ delta _ {ij}}$，在哪里 ${\ displaystyle（\ cdot \ mid \ cdot）}$是内在产物，${\ displaystyle \ delta _ {ij}}$是Kronecker三角洲，或者等效地，${\ displaystyle X ^ {T} X = I}$，那么使用次梯度方法可以证明

${\ displaystyle {\ begin {aligned} {\ hat {\ beta}} _ {j} = {}＆S_ {N \ lambda}（{\ hat {\ beta}} _ {j} ^ {\ text {OLS} }）= {\ hat {\ beta}} _ {j} ^ {\ text {OLS}} \ max \ left（0,1-{\ frac {N \ lambda} {| {\ hat {\ beta}} _ {j} ^ {\ text {OLS}} |}} \ right）\\＆{\ text {其中}} {\ hat {\ beta}} ^ {\ text {OLS}} ==（X ^ {T } X）^ {-1} X ^ {T} y \ end {aligned}}}$ ^[1]

${\ displaystyle S _ {\ alpha}}$ 之所以称为“软阈值运算符”，是因为它会将值转换为零（如果足够小，则使它们精确为零），而不是将较小的值设置为零，而将较大的值保持不变，通常称为“硬阈值运算符”。 ${\ displaystyle H _ {\ alpha}}$， 将。

可以将其与岭回归进行比较，后者的目标是最大程度地减少

${\ displaystyle \ min _ {\ beta \ in \ mathbb {R} ^ {p}} \ left \ {{\ frac {1} {N}} \ | yX \ beta \ | _ {2} ^ {2} + \ lambda \ | \ beta \ | __ {2} ^ {2} \ right \}}$

屈服

${\ displaystyle {\ hat {\ beta}} _ {j} =（1 + N \ lambda）^ {-1} {\ hat {\ beta}} _ {j} ^ {\ text {OLS}}。}$

因此，岭回归将所有系数收缩为一个均匀因子 ${\ displaystyle（1 + N \ lambda）^ {-1}}$ 并且不会将任何系数设置为零。

也可以将其与具有最佳子集选择的回归进行比较，其目的是最大程度地减少

${\ displaystyle \ min _ {\ beta \ in \ mathbb {R} ^ {p}} \ left \ {{\ frac {1} {N}} \ left \ | yX \ beta \ right \ | _ {2} ^ {2} + \ lambda \ | \ beta \ | _ {0} \ right \}}$

哪里 ${\ displaystyle \ | \ cdot \ | _ {0}}$ 是个 ”${\ displaystyle \ ell ^ {0}}$ 规范”，定义为 ${\ displaystyle \ | z \ | = m}$如果z的m个分量恰好为非零。在这种情况下，可以证明

${\ displaystyle {\ hat {\ beta}} _ {j} = H _ {\ sqrt {N \ lambda}} \ left（{\ hat {\ beta}} _ {j} ^ {\ text {OLS}} \\ right）= {\ hat {\ beta}} _ {j} ^ {\ text {OLS}} \ mathrm {I} \ left（\ left | {\ hat {\ beta}} _ {j} ^ {\ text {OLS}} \ right | \ geq {\ sqrt {N \ lambda}} \ right）}$

哪里 ${\ displaystyle H _ {\ alpha}}$ 是所谓的硬阈值函数， ${\ displaystyle \ mathrm {I}}$ 是一个指标函数（如果其参数为true，则为1，否则为0）。

因此，套索估计值共享来自岭和最佳子集选择回归的估计特征，因为它们既缩小了所有系数的大小（如岭回归），又像最佳子集选择情况一样将其中一些系数设置为零。此外，尽管ridge回归将所有系数按恒定因子缩放，但套索反而会将系数按恒定值向零转化，如果达到则将其设置为零。

相关协变量

回到一般情况，其中不同的协变量可能不是独立的，可以考虑一种特殊情况，其中对于每种情况，两个协变量（即j和k）相同，因此${\ displaystyle x _ {（j）} = x _ {（k）}}$，在哪里 ${\ displaystyle x _ {（j），i} = x_ {ij}}$。然后的值${\ displaystyle \ beta _ {j}}$ 和 ${\ displaystyle \ beta _ {k}}$最小化套索目标函数的值不是唯一确定的。其实如果有什么解决办法${\ displaystyle {\ hat {\ beta}}}$ 在其中 ${\ displaystyle {\ hat {\ beta}} _ {j} {\ hat {\ beta}} _ {k} \ geq 0}$，如果 ${\ displaystyle s \ in [0,1]}$ 更换 ${\ displaystyle {\ hat {\ beta}} _ {j}}$ 通过 ${\ displaystyle s（{\ hat {\ beta}} _ {j} + {\ hat {\ beta}} _ {k}）}$ 和 ${\ displaystyle {\ hat {\ beta}} _ {k}}$ 通过 ${\ displaystyle（1-s）（{\ hat {\ beta}} _ {j} + {\ hat {\ beta}} _ {k}）}$，同时保留所有其他 ${\ displaystyle {\ hat {\ beta}} _ {i}}$固定后，给出了新的解决方案，因此套索目标函数具有有效的最小化函数的连续体。^[5]套索的几种变体，包括弹性网，已被设计来解决这一缺点，下面将对此进行讨论。

一般形式

算法解释

参见

• 降维
• 特征选择

参考文献