机器学习(8)之范数正则与Lasso详解

关键字全网搜索最新排名

【机器学习算法】：排名第一

【机器学习】：排名第二

【Python】：排名第三

【算法】：排名第四

线性回归及L2正则

大家对于线性回归以及带有二范数正则的线性回归已经比较熟悉了，其权值可以采用正规方程求解，亦可采用基于梯度下降的迭代求解。本文首先带大家回顾一下线性回归，然后主要介绍Lasso回归以及其求解方式。

回顾线性回归

回顾Ridge回归

由于直接套用线性回归可能产生过拟合，需要加入正则化项，如果加入的是L2正则化项，就是Ridge回归，有时也翻译为脊回归。它和一般线性回归的区别是在损失函数上增加了一个L2正则化的项，和一个调节线性回归项和正则化项权重的系数α。损失函数表达式如下：

Ridge回归的解法和一般线性回归大同小异。如果采用梯度下降法，则每一轮θ迭代的表达式是：

如果用最小二乘法，则θ的结果是：

Ridge回归在不抛弃任何一个变量的情况下，缩小了回归系数，使得模型相对而言比较的稳定，但这会使得模型的变量特别多，模型解释性差。有没有折中一点的办法呢？即又可以防止过拟合，同时克服Ridge回归模型变量多的缺点呢？这就是下面说的Lasso回归。

Lasso回归

Lasso回归有时也叫做线性回归的L1正则化，和Ridge回归的主要区别就是在正则化项，Ridge回归用的是L2正则化，而Lasso回归用的是L1正则化。Lasso回归的损失函数表达式如下：

Lasso回归使得一些系数变小，甚至还是一些绝对值较小的系数直接变为0，因此特别适用于参数数目缩减与参数的选择，因而用来估计稀疏参数的线性模型。

但是Lasso回归有一个很大的问题，导致需要把它单独拎出来讲，就是它的损失函数不是连续可导的，由于L1范数用的是绝对值之和，导致损失函数有不可导的点。也就是说，我们的最小二乘法，梯度下降法，牛顿法与拟牛顿法对它统统失效了。那我们怎么才能求有这个L1范数的损失函数极小值呢？

OK，本文总结了两种全新的求极值解法坐标轴下降法（coordinate descent）和最小角回归法（ Least Angle Regression， LARS）。PS:主要是为了告诉大家这类问题该如何求解，所以不会详细的叙述求解算法的原理，想详细了解可以查看相关文档，后期会统一给大家一份推荐阅读的博客清单。　　　

坐标下降法

坐标轴下降法顾名思义，是沿着坐标轴的方向去下降，这和梯度下降不同。梯度下降是沿着梯度的负方向下降。不过梯度下降和坐标轴下降的共性就都是迭代法，通过启发式的方式一步步迭代求解函数的最小值。

坐标轴下降法的数学依据主要是这个结论（此处不做证明）：一个可微的凸函数J(θ), 其中θ是nx1的向量，即有n个维度。如果在某一点θ¯，使得J(θ)在每一个坐标轴θ¯i(i = 1,2,...n)上都是最小值，那么J(θ¯i)就是一个全局的最小值。

于是我们的优化目标就是在θ的n个坐标轴上(或者说向量的方向上)对损失函数做迭代的下降，当所有的坐标轴上的θi(i = 1,2,...n)都达到收敛时，我们的损失函数最小，此时的θ即为我们要求的结果。

下面我们看看具体的算法过程：

以上就是坐标轴下降法的求极值过程，可以和梯度下降做一个比较：

　　a) 坐标轴下降法在每次迭代中在当前点处沿一个坐标方向进行一维搜索 ，固定其他的坐标方向，找到一个函数的局部极小值。而梯度下降总是沿着梯度的负方向求函数的局部最小值。

　　b) 坐标轴下降优化方法是一种非梯度优化算法。在整个过程中依次循环使用不同的坐标方向进行迭代，一个周期的一维搜索迭代过程相当于一个梯度下降的迭代。

　　c) 梯度下降是利用目标函数的导数来确定搜索方向的，该梯度方向可能不与任何坐标轴平行。而坐标轴下降法法是利用当前坐标方向进行搜索，不需要求目标函数的导数，只按照某一坐标方向进行搜索最小值。

　　d) 两者都是迭代方法，且每一轮迭代，都需要O(mn)的计算量(m为样本数，n为系数向量的维度)

最小角回归

最小角回归法对前向梯度算法和前向选择算法做了折中，保留了前向梯度算法一定程度的精确性，同时简化了前向梯度算法一步步迭代的过程。具体算法是这样的：首先，还是找到与因变量Y最接近或者相关度最高的自变量Xk，使用类似于前向梯度算法中的残差计算方法，得到新的目标Yyes，此时不用和前向梯度算法一样小步小步的走。而是直接向前走直到出现一个Xt，使得Xt和Yyes的相关度和Xk与Yyes的相关度是一样的，此时残差Yyes就在Xt和Xk的角平分线方向上，此时我们开始沿着这个残差角平分线走，直到出现第三个特征Xp和Yyes的相关度足够大的时候，即Xp到当前残差Yyes的相关度和θt，θk与Yyes的一样。将其也叫入到Y的逼近特征集合中，并用Y的逼近特征集合的共同角分线，作为新的逼近方向。以此循环，直到Yyes足够的小，或者说所有的变量都已经取完了，算法停止。此时对应的系数θ即为最终结果。（http://www.cnblogs.com/pinard/p/6018889.html）

最小角回归法是一个适用于高维数据的回归算法，其主要的优点有：

1）特别适合于特征维度n 远高于样本数m的情况。

2）算法的最坏计算复杂度和最小二乘法类似，但是其计算速度几乎和前向选择算法一样

3）可以产生分段线性结果的完整路径，这在模型的交叉验证中极为有用

主要的缺点是：

由于LARS的迭代方向是根据目标的残差而定，所以该算法对样本的噪声极为敏感。

作者：刘建平

原文链接：

http://www.cnblogs.com/pinard/p/6018889.html

参考：

1. 周志华《机器学习》

2. http://www.cnblogs.com/pinard/p/6018889.html