Linear least squares, Lasso,ridge regression有何本质区别?

理由
举报 取消

Linear least squares, Lasso,ridge regression有何本质区别?还有ridge regression uses L2 regularization; and Lasso uses L1 regularization. L1和L2一般如何选取?

2018年1月2日 10 条回复 1731 次浏览

发起人:stark-summer 中层经理

搞大数据的coder

回复 ( 10 )

  1. peter
    理由
    举报 取消

    Linear regression一般只对low dimension适用,比如n=50, p=5,而且这五个变量还不存在multicolinearity.

    Ridge Regression的提出就是为了解决multicolinearity的,加一个L2 penalty term也是因为算起来方便。然而它并不能shrink parameters to 0.所以没法做variable selection。

    LASSO是针对Ridge Regression的没法做variable selection的问题提出来的,L1 penalty虽然算起来麻烦,没有解析解,但是可以把某些系数shrink到0啊。

    然而LASSO虽然可以做variable selection,但是不consistent啊,而且当n很小时至多只能选出n个变量;而且不能做group selection。

    于是有了在L1和L2 penalty之间做个权重就是elastic net, 针对不consistent有了adaptive lasso,针对不能做group selection有了group lasso, 在graphical models里有了graphical lasso。然后有人说unbiasedness, sparsity and continuity这三条都满足多好,于是有了MCP和SCAD同时满足这三条性质。penalized regression太多了,上面提到的都是比较popular的方法了。

  2. 党元初
    理由
    举报 取消

    很多回答都很全面了,大意就是lasso在优化过程的目标函数中使用如下的L1 penalty:

    从而把一些线性回归项的系数“逼成”零;ridge是用L2 penalty,旨在把系数变得小一些,但非完全成零。两者原理上的区别可由下图表示:

    不难看出由于L1 penalty规定的范围“四四方方、有棱有角”,所以最优解的系数会被刚好缩成零,因此lasso可以实现对变量的选择(系数为零的变量就被筛掉了)。

    有趣的是,我们还可以将所有变量分组,然后在目标函数中惩罚每一组的L2范数,这样达到的效果就是可以将一整组的系数同时消成零,即抹掉一整组的变量,这种手法叫做group lasso,其目标函数如下:

    其中我们把所有变量分为 m 组,第一项是通常的OLS,第二项是每一组系数的L2范数之和。这里, \lambda控制整体惩罚的力度,\sqrt{\rho_l}是每一组的加权,可以按需调节。

    比如一个regression若有10个系数 \beta_1, \beta_2, ..., \beta_{10},我们如果选择将其分成2组:其中 \beta_1, ..., \beta_5 一组, \beta_6, ..., \beta_{10} 一组。那么group lasso的惩罚项目将会是:

    \rho(\sqrt{p_1}\sqrt{\sum_{i = 1}^5\beta_i^2} + \sqrt{p_2}\sqrt{\sum_{j = 6}^{10}\beta_j^2})

    通过施加group-wise的L2 penalty,我们有可能促使 \beta_1 = \beta_2 = ... = \beta_5 = 0 或者 \beta_6 = \beta_7 = ... = \beta_{10} = 0

    最后,还有一种lasso和group lasso的奇葩结合,叫做sparse group lasso,由 Simon et al 在2013年提出,sparse group lasso的目标函数(如下)的惩罚项中,既有所有系数的L1范数,又有每一组系数的L2范数

    其中 \lambda 依然控制总体的惩罚力度,有新引入 \alpha 控制两个惩罚项之间的相互强弱。所以sparse group lasso既可以把系数和变量一组一组地筛掉,又可以在剩下的组中筛掉一些单个的系数,原理图如下:

    当然了,这只是在简单OLS背景下的lasso、ridge、和group lasso和sparse group lasso,更常用的目标函数的第一项一般是log likelihood(用于maximum likelihood手法)。相似的概念也可以迁移到其他场景,比如因子分析模型(factor analysis model),其中group lasso可以帮助进行对可被观测的变量选取,而sparse group lasso可以选取隐藏因子,我统计的thesis做的就是这个啦。

  3. 杨军
    理由
    举报 取消

    线性回归问题是很经典的机器学习问题了。

    适用的方法也蛮多,有标准的Ordinary Least Squares,还有带了L2正则的Ridge Regression以及L1正则的Lasso Regression。

    这些不同的回归模型的差异和设计动机是什么?

    在本帖的一个高票回答[1]里,把这个问题讨论得其实已经相当清楚了。

    我在这里的回答更多是一个知识性的总结,在Scott Young的《如何高效学习》[6]里提到高效学习的几个环节: 获取、理解、拓展、纠错、应用、测试。

    在我来看,用自己的语言对来整理对一个问题的认识,就是理解和扩展的一种形式,而发在这里也算是一种应用、测试兼顾纠错的形式了。

    首先来看什么是回归问题,直白来说,就是给定

    \vec X \in \mathcal R_D (1.1)

    Y \in \mathcal R (1.2)

    Y=\boldsymbol f(\vec X) (1.3)

    其中映射函数
    \boldsymbol f未知,但是我们手上有一堆数据样本\mathcal T,形式如下:

    (\vec X_1, Y_1), (\vec X_2, Y_2), ... (\vec X_n, Y_n)      (2.1)

    我们期望从数据样本里推断出映射函数
    \boldsymbol f,满足

    argmin_fE(f(\vec X_i) - Y_i)^2   (3.1)

    即期望推断出的映射函数在数据样本上与真实目标的期望差异尽可能最小化。

    通常来说,数据样本中每个样本的出现频率都可以认为是1,而我们要推断的映射函数可以认为是

    一个线性函数

    f(\vec X)=w_1X_1 + w_2X_2 + ... + w_nX_n + \beta(4.1)

    其中
    w_1, w_2, ... w_n, \beta (4.2)就是我们要推断的关键参数了。

    这样的问题就是线性回归(Linear Regression)问题。

    Ordinary Linear Square的求解方法很直白,结合上面的描述,我们可以将 argmin_fE(f(\vec X) - Y)^2 (5.1)

    具像化为求解函数

    \sum_{i=1}^{N}(f(\vec X_i) - Y_i)^2 (5.2)

    的最小值以及对应的关键参数。

    对于这个目标函数,我们可以通过求导计算[2],直接得出解析解如下 :
    \vec w = (X_TX)^{-1}X^T\vec Y(5.3)

    当然,这是一个典型的Convex优化问题,也可以通过迭代求优的算法来进行求解,比如Gradient Descent或者Newton法[2]。

    看起来不错,那么为什么我们还要在OLS的基础上提供了Ridge Regression(L2正则)和Lasso Regression(L1正则)呢?

    如果说得笼统一些的话,是为了避免over-fit,如果再深入一些,则可以这样来理解:

    不引入正则项的OLS的解很可能会不stable,具体来说,两次不同的采样所采集到的训练数据,用于训练同一个线性回归模型,训练数据的些微差异,最终学出的模型差异可能是巨大的。在[3]里有一个例子:

    还是在[3]里,提供了一个定量的证明:

    结果的证明细节,有兴趣的同学可以自己去查阅,这里直接把关键点引用如下:

    一个有名的病态矩阵是Hilbert矩阵[4],其形如下:

    再回到我们关于OLS的讨论,我们不难看出,随着训练样本采样次数的增加,采样到病态阵的概率会增多,这样一来学出的模型的稳定性就比较

    差。想象一下,今天训练出来的模型跟明天训练出的模型,存在明显的模型权值差异,这看起来并不是一件非常好的事情。

    那么病态阵的根本原因是什么呢?条件数的描述还是相对有些抽象,所以这里又引入了奇异阵的概念。

    什么是奇异阵呢?

    形式化来说,不存在逆矩阵的方阵(因为OLS的闭式解里,需要求逆的矩阵是
    X^TX(6.1)

    一定是一个方阵,所以这里仅讨论方阵这一特殊形态)就是奇异阵,即
    A^{-1}A=\mathcal I, \not \exists A^{-1}(6.2)

    那么再具体一些,什么样的方阵会不存在逆呢?

    非满秩、矩阵的特征值之和为0、矩阵的行列式为0。

    满足这三个条件中的任意一个条件,即可推出方阵为奇异阵,不可求逆,实际上这三个条件是可以互相推导出来的。

    而我们又知道,一个方阵的逆矩阵可以通过其伴随矩阵和行列式求出来[7]

    A^{-1}=\frac {1} {|A|} adj(A); adj(A) \in R^{n*n}, (adj(A))_{ij}=(-1)^{i+j}|A_{\setminus j,\setminus i}|(6.3)

    从这里,其实可以看的出来,对于近似奇异阵,其行列式非常接近于0,所以

    \frac 1 {|A|} (6.4)

    会是一个非常大的数,这其实反映出来就是在计算A的逆矩阵时,伴随矩阵上的些微变化,会被很大程度上放大,就会导致多次采样出来的训练数据,学出的模型差异很大,这是除了上面提到的条件数以外的另一种比较形象的解释了。

    如果类比普通代数的话,奇异阵就好比是0,0不存在倒数,越接近0的数,其倒数越大,同样,奇异阵不存在逆矩阵,而接近奇异阵的逆矩阵的波动也会比较大。

    所以跟奇异阵有多像(数学语言里称为near singularity),决定了我们的线性回归模型有多么不稳定。

    既然知道了奇异阵的性质并且了解到是奇异阵使得从训练数据中学出来的线性回归模型不那么稳定,那么我们是不是可以人为地通过引入一些transformation让
    X^TX(7.1)长得跟奇异阵不那么像呢?

    我们知道

    |A|=\Pi_i^n \lambda_i(7.2)

    trA=\sum_{i=1}{n}\lambda_i(7.3)

    trA=\sum_{i=1}^nA_{ii}(7.4)

    于是一个直观的思路是在方阵X^TX的对角线元素上施加如下的线性变换

    X^TX+\lambda\mathcal  I (7.5)

    其中
    \mathcal I是单位阵。

    有了上面的变换以后,对角线的元素为全零的概率就可以有效降低,也就达到了减少
    X^TX

    near singularity的程度,进而减少线性回归模型不稳定性的目的了。

    那么这个变换跟Ridge或是Lasso有什么关系呢?

    实际上,
    \vec w=(X^TX+\lambda \mathcal I)^{-1}X\vec Y(7.6)(7.6)
    正是对下面的
    \sum_{i=1}^{N}(\vec w\vec X_i - Y_i)^2 + \lambda ||\vec w||_2^2(7.7)

    这个优化问题为
    \vec w计算闭式解得到的结果(在[2]里OLS的闭式解的推导过程里加入二范数正则项,蛮自然地就会得到7.6里的结果,[8]里也有类似的推论)。

    而(7.7)正是Ridge Regression的标准写法。

    进一步,Lasso Regression的写法是
    \sum_{i=1}^{N}(\vec w\vec X_i - Y_i)^2 + \lambda ||\vec w||_1

    这实际上也是在原始矩阵上施加了一些变换,期望离奇异阵远一些,另外1范数的引入,使得模型训练的过程本身包含了model selection的功能,在上面的回复里都举出了很多的例子,在一本像样些的ML/DM的教材里也大抵都有着比形象的示例图,在这里我就不再重复了。

    一个略微想提一下的是,对于2范数,本质上其实是对误差的高斯先验,而1范数则对应于误差的Laplace先验,这算是另一个理解正则化的视角了。

    只不过1范数的引入导致优化目标不再处处连续不能直接求取闭式解,而不得不resort到迭代求优的方法上了,而因为其非处处连续的特点,
    即便是在迭代求优的过程中,也变得有些特殊了,这个我们可以在以后讨论OWLQN和LBFGS算法的时后再详细引出来。

    [1]. Linear least squares, Lasso,ridge regression有何本质区别? – 数据挖掘

    [2].

    [3]. 《数值分析导论》(数值分析导论 (豆瓣) )的 例6.5.3

    [4]. 《数值分析导论》(数值分析导论 (豆瓣) )的例6.5.5

    [5]. 关于奇异阵的资料。

    [6]. 如何高效学习 (豆瓣)如何高效学习 (豆瓣)

    [7].

    [8]. PRML 3.28

  4. 高明哲
    理由
    举报 取消

    题主这个问题算是比较基础的,那我回答也详细点好了。个人理解,不当之初欢迎各位大牛指正。

    知乎公式编辑器导致意外换行问题不知如何解决……各位看官帮帮忙。

    1. Least-squares(最小二乘法)是最经典的机器学习算法,后续的大部分机器学习算法(包括题主提到的Lasso,ridge regression)都是在其基础上发展而来的。Linear model即f _{\theta}(x)=\sum_{j=1}^{b}{\theta _{j}\phi _{j}(x)} ,只要求得其参数\left\{ \theta  \right\} _{j=1}^{b} ,便可以得到自变量x与因变量y的映射关系。因此有监督回归的任务就是通过n个成对的训练样本\left\{ (x_{i}, y_{i} )\right\} _{i=1}^{n} 来求得学习模型的参数\left\{ \theta  \right\} _{j=1}^{b}

    2. 最小二乘法是对模型的输出f _{\theta}(x_{i} )和训练样本的输出\left\{y_{i} \right\} _{i=1}^{n} 的平方误差\sum_{i=1}^{n}{\left( f _{\theta}(x_{i} )-y_{i}  \right) } ^{2} 为最小时的参数\theta _{LS}进行学习\sum_{i=1}^{n}{\left( f _{\theta}(x_{i} )-y_{i}  \right) } ^{2} 称之为损失函数。随着学习模型f _{\theta}(x)复杂度的提高,这种经典最小二乘法存在的诸多缺陷也表露出来,其中一个重要的问题就是对训练数据的过拟合(overfitting)。过拟合的原因被认为是学习模型相比真实模型过于复杂。因此为解决过拟合问题,可在损失函数的后面加上一个约束条件从而限制模型的复杂度,这个约束条件即为正则化项(regularizer)。典型的正则化方法就是引入l_{2} 约束,l_{2} 约束的约束条件是参数的\left\{ \theta  \right\} _{j=1}^{b} l_{2} 范数小于某个阈值,此时最小二乘学习法的学习目标变为使学习结果的平方误差与正则化项的和最小。虽然这种方法对于预防过拟合非常有效,但当学习模型中的参数特别多时,求解各参数需要花费大量的时间。因此,一种能够把大部分参数都设置为0的学习方法便被提出,就是稀疏学习,Lasso回归就是典型的稀疏学习。

    3. Lasso回归的本质是l_{1} 约束的最小二乘法,即学习模型参数\left\{ \theta  \right\} _{j=1}^{b} l_{1} 范数小于某个阈值。想象一下,l_{2} 约束下的参数分布趋向于以圆点为中心的圆周内部,而l_{1} 约束下的参数则集中分布在各坐标轴附近,因此l_{1} 约束能够有效的将若干参数的解收敛到0。约束的求解相对于l_{2} 约束更为复杂,通常解法是需要数个l_{2} 约束求解的迭代过程。因此,题主所问的l_{1} l_{2} 约束如何选取的问题,个人认为如果不考虑l_{1} +l_{2} 约束的弹性网回归,l_{1} 约束更适合参数较多或需要特征提取的情况下,l_{2} 约束更适合模型简单或是不想求解那么复杂的情况下(MATLAB算这两种约束都很简单)。

    4. 岭回归也是最小二乘法正则化方法的一种延伸,特点是以损失无偏性为代价换取数值稳定性。

    希望能帮到你。

  5. 伊首衡
    理由
    举报 取消

    J(theta)是模型的cost function

    y是实际数据

    y_hat是你的模型推算出来的数据

    theta是模型的参量

    最原始的regression:

    J(theta) = sum((y – y_hat)^2)

    加上L1(也就是LASSO):

    J_lasso(theta) = sum((y – y_hat)^2) + sum(abs(theta))

    加上L2(也就是Ridge):

    J_ridge(theta) = sum((y – y_hat)^2) + sum(theta^2)

    对于两个参量的cost function来说,把模型视觉化出来就是这样的:

    那个长得像年轮蛋糕的圈圈就是J(theta),左边的圆圈是L2,右边的方块是L1。也就是说你在做最优化的时候,你在原有的空间里叠加了一个圆圈/方块,这样就会有一种“力”把你的theta向0拉,这也是为什么叫LASSO的原因。

    L1和L2什么时候用呢?

    如果你有很多features,不知道哪个最重要,那么你可以用L1,因为L1会更鼓励theta为0。这样你可以直接用非0的theta,那么模型的复杂程度会降低很多

  6. Yeung Evan
    理由
    举报 取消

    不太赞同高票答案关于Lasso产生的motivation,高票答案说:“你可能又要问了,多加的那一项凭什么是模长呢?不能把2-norm改成1-norm吗?”实际上,Tibshirani (1996) 原文中对此也有颇多阐述,Lasso产生的初因并非只是简单地把2修改到1(虽然表现出来确实如此,后面对此详叙)。我尝试在楼上各个答案的基础上,添加一些历史线索。

    先回答题主问题:

    最小二乘法的一些讨论可参见 Logistic 回归模型的参数估计为什么不能采用最小二乘法? – Yeung Evan 的回答 ;Linear least squares是对线性回归模型进行参数估计的一种选择,同时我们当然可以从非最小二乘的方法对线性回归模型的参数进行估计。在使用最小二乘法进行求解时,我们会对线性回归模型进行假设,当这些假设在实际中并不满足时,最小二乘法是有问题的。其中很重要的一个假设是要求各个变量要相互独立,而实际样本可能会有较大的共线性(multicollinearity)。从数学上来说,这种情况会造成\textbf{X}^\top \textbf{X}(至少一个)特征值很小,从而估计量的MSE会很大(*)。所以ridge regression就很粗暴,因为\textbf{X}^\top \textbf{X}(至少一个)特征值很小,所以就强行加上一个\lambda \textbf{I}把特征值“掰”大。ridge regression 大约是在1970年Hoerl提出。

    后来(或同时)人们考虑回归方程的选择问题,比如说,不一定所有的自变量的数据都需要放入模型,因为有些自变量本身对模型的影响不大,但引入之后却会增加对其他参数的估计所需的计算量以及减少其精度(那个年代计算机还远未普及)。但到底哪些变量需要选,哪些变量需要弃,就是一个颇为棘手的问题。后来比较经典的处理方法就是逐步回归法,又细分为向前逐步回归和向后逐步回归。这一方法的成熟大约也是在70年代左右。再然后,此问题的发展是1993年Frank和Friedman提出的bridge regression,他们提出的对优化目标函数的限制已经是形如\sum_j|\beta_j| ^ {\gamma}的样子了,但可惜他们没有能力进一步对\gamma取特殊值(**)时的情况进行讨论。

    最终在1996年Tibshirani把上述两个问题同时解决了:

    (*)MSE偏大时估计的精确度会降低,因为方差偏大;

    (**)\gamma=1时模型具有“挑选”自变量的能力,并将这个情况下的优化问题讲清楚了;

    这里回到本文开头,看上去只是把 \gamma = 2 改成了 \gamma = 1 ,但实际上背后的工作原理相当复杂,这也是CS的一些研究在严密性上,相对容易忽视的地方:即对变量的选择性从何而来?换句话说,怎么证明把 \gamma 数值改了,就把变量压缩了呢?

    要回答这个问题是相当难的,仅以ridge回归为例,在考虑 \gamma = 2 时,可以通过相当的篇幅证明,在此约束下的回归结果 \hat{\beta}_\text{ridge} < \hat{\beta}_\text{OLS} 。这意味着,估计向量的长度缩短了——当然其中的某些分量一定变小了——这就是最初的变量被压缩的雏形。而更一般的变量选择性,需要更艰深的证明,而不是简单一句“把 \gamma 值改了,模型就能避免over fitting”——中间的因果逻辑需要相当多的数学推导。

    Lasso后续的发展请关注千面人的答案,当然包括真正把Lasso变得“好算”的Lars算法也是该问题的里程碑之一。

    上述即是Lasso和ridge regression的一些历史线索,是最自然、最符合一个研究发展脉络的逻辑。在机器学习中还有一些和此问题相关的概念,比如正则化,它们本质上都是相似的,在机器学习中引入正则化这一概念的渊源非我能置喙,但至少说引入正则因子或者惩罚项是为了避免overfitting,是不太自然的。

  7. 司徒功源
    理由
    举报 取消

    这个问题可以从以下几个方面回答:

    1:optimization的角度,即1楼;

    2:regularization的角度,L1,L2 regularization都是为了预防或者减少过拟合,机器学习的过程本质上是从一个假设空间(函数空间)中根据一定的算法选择某个最优的假设(函数)的过程,加上一些regularization就是限制了我们所选择的假设(函数)只能在一定的范围内选取,对线性回归而言,过拟合的一个明显标志就是某些权重的值会很大,加上一些限制可以减少这样的情况的发生,L1的解通常稀疏,L2从计算角度而言更方便;

    3:从贝叶斯角度而言,不同的regularization代表了对权重使用不同的先验分布,这一点建议看PRML的前面的章节,由更具体的描述;

  8. 曾博
    理由
    举报 取消

    这个问题我才疏学浅,只能从下面几个方面回答:

    1,linear regression是个很大的题目,还有general linear regression。题主说的least square, 姑且认为是ordinary least square,那么其实很简单,就是证明了(在特定情况下)这个quadratic loss function估计出来的参数是blue (best linear unbiased estimator),指的是在所有linear,无偏 estimator当中,这个估计的结果是variance最小的。

    2,加上regularizer的一个数学原因是1中参数估计的表达式存在inverse,如果存在multi-colinearity或者非唯一解,那么estimator 的数值解可能不存在/极不稳定。加入一个regularizer 可以保证inverse的非奇异性。

    3,l1, l2都是可行的regularizer,唯一的区别可能就是l1得到的估计更加sparse。

  9. 用户头像
    理由
    举报 取消

    三者都是找一个weights使total cost最小

    不同的是怎么定义total cost

    Linear regression的cost 的定义是

    即残差平方和,把预测值与实际值的差异(残差)平方后相加。

    Linear regression方法便是用一些最优化的方法(直接求解析解,梯度下降等)求这个total cost的最小值对应的weights.

    实际用这个方法若没有足够的训练样本或features数很多时会出现overfitting的情况。

    overfitting的时候weights的数值经常会很大。

    为了克服这个问题在totally cost加入对weights数值的惩罚项。

    惩罚项是weights数值的大小。用2范数来量化,即每个weights分量的平方和。

    在weights的惩罚项前加入调节参数lambda。

    这就是Ridge regression

    Ridge regression方法也是用最优化求使Total cost最小的weights。

    Ridge regression比Linear regression好的另一点是,它总是可以对方程直接求解析解,就算在方程的未知数(weights)比方程数(样本数)多的情况。

    实际用Ridge regression时weights会慢慢变小但不会为零。

    (图为Ridge regression中随lambda大小的变化每个weights分量大小的变化情况,可以看到随着lambda变大(即惩罚项越重要),weights分量越趋近0)

    当features很多的时候那些weights非常小的对应的feature对学习结果没什么影响。

    于是改变total cost使在优化total cost 过程中不仅使weight变小,还能使其变为0。

    将weights惩罚项变为1范数就能实现。

    这就是Lasso regression

    惩罚项变成1范数即weights分量的绝对值后Total cost在收敛的过程中会使一些分量变为0

    变为0的分量对结果影响较小,即对应的feature相对不重要。因此lasso regression也有对features进行筛选的作用。

    (图为lasso regression中随lambda大小的变化每个weights分量大小的变化情况,可以看到随着lambda变大(即惩罚项越重要),一些weights分量会变成0)

    综上:Linear regression, Ridge regression 和 Lasso regression的区别在对cost的定义上。不同的total cost定义对应着不同的模型。

我来回答

Captcha 点击图片更换验证码