LASSO回归与L1正则化西瓜书

r囧r小猫 2023-06-04 02:42 17阅读 0赞

# LASSO回归与L1正则化 西瓜书 #

2018年04月23日 19:29:57 [BIT\_666][BIT_666] 阅读数 2968更多

分类专栏： [机器学习][Link 1] [机器学习数学原理][Link 2] [西瓜书][Link 3]

本文链接： [https://blog.csdn.net/BIT\_666/article/details/80051737][https_blog.csdn.net_BIT_666_article_details_80051737]

1.结构风险与经验风险

在支持向量机部分，我们接触到松弛变量，正则化因子以及最优化函数，在朴素贝叶斯分类，决策树我们也遇到类似的函数优化问题。其实这就是结构风险和经验风险两种模型选择策略，经验风险负责最小化误差，使得模型尽可能的拟合数据，而结构风险则负责规则化参数，使得参数的形式尽量简洁，从而达到防止过拟合的作用.所以针对常见模型，我们都有下式：

![20180423161114360][]

第一项经验风险L(yi,f(xi,w))衡量真实值与预测值之间的误差，第二项结构风险Ω(w)规则化项使得模型尽可能简单.而第二项Ω(w)一般是模型复杂度的单调函数，模型越复杂，则规则化项的值越大，这里常引入范数作为规则化项，这也就引入了我们常见的L0范数，L1范数以及L2范数.

2.L0范数，L1范数，L2范数与LASSO回归，岭回归

1）广义定义

L0范数 ![20180423161818358][] : 向量中非零元素的个数.

L1范数 ![20180423161858109][]：向量中各个元素绝对值之和

L2范数 ![20180423161924631][]：向量各元素平方和然后求平方根

L0，L1范数可以实现稀疏化，而L1系数因为有比L0更好的特性而被广泛应用，L2范数在回归里就是岭回归，也叫均值衰减，常用于解决过拟合，通过对向量各元素平方和再求平方根，使得L2范数最小，从而使得参数W的各个元素都接近于0，与L1范数不同，L2范数规划后w的值会接近于0但不到0，而L1范数规范后则可能令w的一些值为0，所以L1范数规范在特征选择中经常用到，而L2范数在参数规则化时经常用到.在回归模型中，通过添加L1,L2范数引入正则化项，便得到了LASSO回归和岭回归：

2）回归模型

常见线性模型回归：

![20180423162957700][]

LASSOO回归：

![2018042316300553][]

岭回归：

![20180423163017764][]

3.嵌入式选择与LASSO回归

这里主要针对西瓜书第11节的内容，对近端梯度下降PGD法解决L1正则化问题进行讨论.

1）优化目标

令▽表示微分算子，对优化目标：

![20180423164021935][]

若f(x)可导，且▽f 满足L-Lipschitz（利普希茨连续条件），即存在常数L＞0使得：

![20180423164636417][]

2）泰勒展开

则在Xk处我们可以泰勒展开：

![20180423164916885][]

上式是严格相等，由L-Lipschitz条件我们可以看到：

![20180423165432703][]

这里给出了一个L的下界，且下界的形式与二阶导函数形式类似，从而泰勒展开式的二阶导便通过L替代，从而严格不等也变成了近似：

![20180423165826953][]

3）简化泰勒展开式

接下来我们化简上式：

![20180423170749723][]

![20180423170756881][]![20180423170802996][]

![2018042317082553][]

其中φ(xk)是与x无关的const常数.

![20180423170836433][]

4）简化优化问题

这里若通过梯度下降法对f(x)进行最小化，则每一步下降迭代实际上等价于最小化二次函数f(x)，从而推广到我们最上面的优化目标，类似的可以得到每一步的迭代公式:

![20180423171328325][]

令

![20180423171428263][]

则我们可以先计算z，再求解优化问题：

![20180423171809713][]

5）求解

令xi为x的第i个分量，将上式展开可以看到没有xixj（x≠j）的项，即x的各分量互不影响，所以优化目标有闭式解.这里对于上述优化问题求解需要用到Soft Thresholding软阈值函数，其解为：

![20180423193617769][]

对于本例，带入求解即得：

![20180423172511243][]

因此，PGD能使LASSO和其他基于L1范数最小化的方法得以快速求解.

4.Soft Thresholding软阈值函数证明

1）软阈值函数

上式求解用到了软阈值函数，下面对软阈值函数的解进行求证，从而更好理解上述求解过程.

先看一下软阈值函数：

![20180423173134995][]

2）证明

Proof：

对于优化问题：

![20180423173415313][]

此处X,Z均为n维向量.

展开目标函数：

![2018042317371267][]

![20180423173717870][]![20180423173730922][]

从而优化问题变为求解N个独立的函数：

![201804231738545][]

这是我们常见的二次函数，对其求导：

![20180423174001898][]

令导数为0：

![20180423174107656][]

看到两边都有x，所以我们要对上述情况进行讨论：

A.z>λ/2时

假设 x<0 ,   所以  sign(x)=-1 ，但 z-λ/2sign(x)＞0 ，所以矛盾.

假设 x>0 ，所以  sign(x) = 1，z-λ/2sign(x)>0,所以极小值在x>0 取得1.

此时极小值小于f(0)：

![20180423184149532][]

再看x<0,

![20180423174001898][]

![20180423175003436][]

所以f(x)在负无穷到0单调递减，所以最小值在z-λ/2处取得.

B.z<-λ/2时

假设 x<0 ,   所以  sign(x)=-1 ，z-λ/2sign(x)<0 ，所以极值点在 x<0 处取得.

假设 x>0 ，所以  sign(x) = 1，z-λ/2sign(x)<0,所以矛盾.

此时极值小于f(0）：

![20180423184457617][]

再看 x>0 ,

![20180423174001898][]

![20180423180150340][]

所以f(x)在0到正无穷单调递增，所以最小值在z+λ/2处取得.

C.λ/2<z<λ/2时

假设 x<0 ,   所以  sign(x)=-1 ，z-λ/2sign(x)>0 ，所以矛盾.

假设 x>0 ，所以  sign(x) = 1，z-λ/2sign(x)<0,所以矛盾.

所以x>0,x<0均不满足条件.

所以有：

![20180423184839796][]

![20180423185038799][]

![20180423185046114][]

![20180423185052456][]

当△x>0时,由条件z<λ/2:

![20180423185724303][]

![20180423185731852][]

![20180423185740458][]

当△x<0时,由条件z<λ/2:

![20180423185724303][]

![20180423185731852][]

![20180423185957359][]

所以在0处取极小值，同时也是最小值.

综合以上三种情况：

![20180423191308770][]

3）对应西瓜书的L1正则化与LASSO回归

这里的解对应的优化问题是：

![20180423173415313][]

而我们PGD优化的问题是：

![20180423171809713][]

对上式同乘2/L不影响极值点位置的选取，所以我们的PGD优化问题变成：

![20180423190926181][]

带入综合三种情况的到的最终解：

![20180423172511243][]

西瓜书上11.14也就得证了~

总结：

终于看完了西瓜书11章特征选择与稀疏学习，发现从头至尾都在提到用LASSO解决问题，所以就结合第六章的正则化和之前的模型评价，对正则化范数以及LASSO重新认识了一下，书中解决LASSO的大致方法就是通过利普希茨连续条件得到L，带入到优化函数中对函数简化变形，简易优化函数，然后通过软阈值函数得到最后的解.LASSO大致就是这些了，有问题欢迎大家交流~

转载于:https://www.cnblogs.com/think90/p/11555691.html

[BIT_666]: https://me.csdn.net/BIT_666
[Link 1]: https://blog.csdn.net/bit_666/article/category/7546440
[Link 2]: https://blog.csdn.net/bit_666/article/category/7585074
[Link 3]: https://blog.csdn.net/bit_666/article/category/7614867
[CC 4.0 BY-SA]: http://creativecommons.org/licenses/by-sa/4.0/
[https_blog.csdn.net_BIT_666_article_details_80051737]: https://blog.csdn.net/BIT_666/article/details/80051737
[20180423161114360]: /images/20230601/59c4ddc24f7144aaa9e7f928a1e4856d.png
[20180423161818358]: /images/20230601/7b857ee4dce3463987c838727b753261.png
[20180423161858109]: /images/20230601/247d8206ae244fc0a35cdb6cae088a12.png
[20180423161924631]: /images/20230601/e52ca1e670ae44e7a3f2aa7dfa6d2db2.png
[20180423162957700]: /images/20230601/e17f2592194541328cb738f93a34341d.png
[2018042316300553]: /images/20230601/8792167c440144f596a811b9415e304e.png
[20180423163017764]: /images/20230601/1988dd3ea3a24373b1329c4fdbcd3a19.png
[20180423164021935]: /images/20230601/f076d333acde49d0989bdb9c348a591d.png
[20180423164636417]: /images/20230601/bcae3141410f41e6af00f200d7d73c6f.png
[20180423164916885]: /images/20230601/8e510aa7bd514a2194e8fc3a6be23531.png
[20180423165432703]: /images/20230601/07631877ae744ff4b0c4d9e5c575afec.png
[20180423165826953]: /images/20230601/e2871018fc3f4ada8b097bfec8bc2c53.png
[20180423170749723]: /images/20230601/1dcdda5a5fc241e2a54c712fc68a6063.png
[20180423170756881]: https://img-blog.csdn.net/20180423170756881
[20180423170802996]: /images/20230601/081f1d2c790a46c498a749dd5de90371.png
[2018042317082553]: /images/20230601/7ff8e429abb4419087531234f8e70378.png
[20180423170836433]: /images/20230601/5d1fda8f971240319ca3ba9675823982.png
[20180423171328325]: /images/20230601/e4126272176445db98f0222d1c86ea8d.png
[20180423171428263]: /images/20230601/d50dc7ea7960470d851f9d0930c67245.png
[20180423171809713]: /images/20230601/d95c0a245de2481788f77f08e59fd59e.png
[20180423193617769]: /images/20230601/8470f0b6e3aa4c5da1787788b602dec3.png
[20180423172511243]: /images/20230601/cccac563fce443e2bf53404fe53f2441.png
[20180423173134995]: /images/20230601/f64f0c9fd1214a00a26558c034fc0c0a.png
[20180423173415313]: /images/20230601/e3ed42133d184a57b1f11d4ca52446e4.png
[2018042317371267]: /images/20230601/cff1136904d647cfa11d50cd3a6d440f.png
[20180423173717870]: https://img-blog.csdn.net/20180423173717870
[20180423173730922]: /images/20230601/c7a2665e685040f888e26881ed7ff81c.png
[201804231738545]: /images/20230601/6f82b6a7f2534b4aa8ffad11e25b89e2.png
[20180423174001898]: /images/20230601/b94d8430cf3d4dc385fe5b728e4038ec.png
[20180423174107656]: /images/20230601/e298af89f8aa489bb996a5aa095f69f3.png
[20180423184149532]: /images/20230601/67f9f0f7d3f44ef99327e9d4008ff4e1.png
[20180423175003436]: /images/20230601/2b0f2735640a45a78ffa38b7fac697b4.png
[20180423184457617]: /images/20230601/c125da80fb684b2480240b79403cdd20.png
[20180423180150340]: /images/20230601/7c241dea8eea4056a22564a563c27e25.png
[20180423184839796]: /images/20230601/6e5d01a563e148c0923b31c0622a1766.png
[20180423185038799]: /images/20230601/4887ea4452044b6dac51cc98aea4648e.png
[20180423185046114]: /images/20230601/cc199d3132b44c61ba15d05462036e82.png
[20180423185052456]: /images/20230601/cf82b433d2bd4054b825a64d214b5631.png
[20180423185724303]: /images/20230601/ff0ea0716f7b491888034a3dd99c34e7.png
[20180423185731852]: /images/20230601/681852783a00418fa38a2ab75d6a8def.png
[20180423185740458]: /images/20230601/691199cdda164e34a1780f70a1ae12a4.png
[20180423185957359]: /images/20230601/35431d2d3f3244839db911c52bb626d0.png
[20180423191308770]: /images/20230601/12968277846546fc92a73a750acfe367.png
[20180423190926181]: /images/20230601/40732189f1294f53adf8ccb4c4719451.png