广义线性模型（3）线性回归模型—Lasso回归、Ridge回归

1 Ridge回归和Lasso回归概述

在机器学习中，如果特征很多，但是训练数据 $X$ 量不够大的情况下，学习器很容易把 $X$ 特有的一些特点也当做是整个样本空间的一般性质进行学习，这就会出现过拟合的现象，线性回归模型也不例外。对于过拟合，在模型层面上我们一般会在模型中加入正则化项来优化模型，正则化项一般分为两种：L1正则和L2正则。

线性回归的L1正则称为Lasso（least absolute shrinkage and selection operator）回归，Lasso回归和普通线性回归模型的区别是在损失函数上增加了一个L1正则项， $\lambda$ 为调节经验风险和结构风险之间关系的系数，其损失函数为：

$L(\theta )=\frac{1}{2}\sum_{i=1}^m(\sum_{i=1}^m\theta_ix_i-y_i)^2+\sum_{i=1}^m|\theta_i|=\frac{1}{2}(Xθ-Y)^T(Xθ-Y)+\lambda||\theta||_1$

线性回归的L2正则称为Ridge回归（岭回归），其与普通线性回归模型的区别是在损失函数上增加了一个L2正则项，其损失函数为：

$L(\theta )=\frac{1}{2}\sum_{i=1}^m(\sum_{i=1}^m\theta_ix_i-y_i)^2+\sum_{i=1}^m\theta_i^2=\frac{1}{2}(Xθ-Y)^T(Xθ-Y)+\frac{\lambda}{2}||\theta||^2$

Ridge回归（L2正则）会倾向于让模型选择更小的参数，但不会使参数为0，所以L2正则不会减少模型的特征；而Lasso回归（L1正则）能使一些“不重要”的特征的参数为0，相当于丢弃了这个特征，简化了模型。

2 Ridge回归和Lasso回归求解

2.1 Ridge回归求解

根据上面的损失函数可知，Ridge回归就是在原线性回归损失函数的基础上加了个平方项，并不影响对损失函数进行求导，所以最小二乘法和梯度下降法都没问题，对损失函数求导得到：

$\frac{\partial}{\partial\theta}L(\theta) = X^T(X\theta - Y)+\lambda\theta$

使用最小二乘法求解 $\theta$ ：

$θ = (X^TX+\theta E)^{-1}X^TY$

使用梯度下降法求解 $\theta$ ：

$\mathbf\theta= \mathbf\theta - \lambda [X^T(X\theta - \mathbf{Y})+\lambda\theta]$

2.2 Lasso回归求解

Lasso回归的特殊之处在于其损失函数中包含一个绝对值项 $\lambda||\theta||_1$ ，其在0处是非连续可导的，故普通的最小二乘法和梯度下降就都没法用了，所以需要我们来探索一下Lasso回归的参数求解方法。

2.2.1 次梯度方法

1）次导数

首先回想下梯度下降的原理：假设损失函数为多元函数 $L(\theta)$ ，对其进行一阶泰勒展开得到：

$L(\theta+\Delta \theta)\approx L(\theta)+\sum_i\frac{\partial L}{\partial\theta_i}\Delta\theta_i$

所以： $\Delta L(\theta)\approx\sum_i\frac{\partial L}{\partial \theta_i}\Delta \theta_i= \nabla L\Delta \theta$ ，如果 $\Delta \theta=-\lambda \nabla L$ ，则有：

$\Delta L(\theta)\approx \nabla L\Delta \theta=-\lambda \nabla L^2$

梯度 $\nabla L$ 不为0时， $\Delta L(\theta)$ 为负值，所以当 $\theta$ 按负梯度 $-\lambda \nabla L$ 更新时，损失函数在随着不断减小，这就是梯度下降的思想。

梯度即各个变量在一点处的一阶导数，一个一元函数在一阶展开时有：

$f(x+\Delta x)= f(x)+f'(x)\Delta x+R_2(x), \ R_2(x)为二阶拉格朗日余项$

$f'(x)= \frac{f(x+\Delta x)-f(x)}{\Delta x}$

函数可导的充要条件：函数在该点连续且左导数、右导数都存在并相等，稍微有些局限，不可导的函数怎么办呢？为了处理不可导的问题，我们需要引出次导数的概念。

次导数：凸函数 $f:I→R$ 在点 $x_0$ 的次导数是实数 $c$ 使得：

$f(x+\Delta x)-f(x)\geq c*\Delta x$

我们可以证明，在点 $x_0$ 处的次导数的集合是一个非空闭区间 $[a,b]$ ，其中 $a$ 和 $b$ 是单侧极限：

它们一定存在，且满足 $a≤b$ 。所有次导数的集合 $[a,b]$ 称为函数 $f$ 在 $x_0$ 处的次微分。由此可知，凸函数 $f(x)=|x|$ 在原点的次导数是区间 $[−1, 1]$ 。

如上图，函数在某一点的导数可以看成函数在这一点上的切线，那么在原点，因为这一点不是光滑的，所以可以找到实线下方的无数条支撑直线（一维支撑超平面，支撑超平面：一个平面会把空间划分为两部分，能使函数图像仅在其中一部分的超平面），形成一个曲线族。我们就把这些支撑直线斜率的范围定义为这一点的次导数（subgradient）。

次导数性质：

凸函数 $f:I→R$ 在 $x_0$ 可导，当且仅当次微分只由一个点组成，这个点就是函数在 $x_0$ 的导数，即连续可导的点处的支撑直线只能画出来一条；
点 $x_0$ 是凸函数 $f$ 的最小值，当且仅当次微分中包含零，也就是说，在上面的图中，我们可以作一条水平的“次切线”。这个性质是“可导函数在极小值的导数是零”的事实的推广，想象一下 $|x|$ 图像就很容易理解这一点。

2）次梯度

将次导数和次微分的概念推广到多元函数，就可以得到次梯度了。如果 $f$ 是一个实变量凸函数，函数 $f$ 在点 $x_0$ 的次梯度对于所有的 $x$ 都有：

$f(x)\geq f(x_0)+g^T(x-x_0)$

可以想象一下上面的二维的图来理解一下这个定义，其实几何含义就是把那些支撑超平面的向量想成次梯度，次梯度的性质：

凸函数的次梯度总是存在；
如果函数在 $x_0$ 处可微，则次梯度唯一，且等于梯度；
当且仅当0属于函数 $f$ 在点 $x^*$ 处次梯度集合的元素时， $x^*$ 为最优解，因为当次梯度为0时有 $f(x)\geq f(x^*)+0(x-x_0)=f(x^*)$ 对所有 $x$ 成立。

为什么用次梯度可以求最小值呢？定义中说次梯度对所有 $x$ 成立，那么函数最小值对应的 $x^*$ 想必也是成立的，即：

$f(x^*)-f(x_0)\leq 0\geq g^T(x^*-x_0)=|g^T|*|x^*-x_0|*cos\theta$

所以可知次梯度 $-g^T$ 与 $x^*-x_0$ 之间的夹角 $\theta$ 小于等于90°，因此 $-g^T$ 是与 $x^*-x_0$ 方向不背离的，即从 $x_0$ 可能向 $x^*$ 靠近，因此可以认为沿着负次梯度方向也可能是在逼近最小值（不绝对，不像梯度下降那样能保证损失减小）。

3）次梯度方法

次梯度方法 (subgradient method) 的做法与梯度下降类似：

$x^{t+1}=x^{t}-\lambda_{t} g^t$

其中， $g^t$ 是次梯度集合中的一个， $\lambda$ 一般是设定好的步长。因为次梯度方向不一定使函数值减小，所以并不是迭代到最后的 $x$ 就是最优的，需要保留每一步的结果进行对比：

$f(x^k_{best})=min(f(x^i)),i=1,2,...,k$

至于算法会不会收敛，可以看下方参考资料中的证明。次梯度法的优势是比传统方法处理问题范围大，劣势是算法收敛速度慢。

2.2.2 坐标下降法（coordinate descent）

1）坐标下降法原理

坐标下降法，其含义就是让函数值沿着坐标轴下降，其基本思想是：一个可微的凸函数 $f(x)$ ，其中 $x$ 是n维向量，可以理解为 $x$ 有n个坐标轴，如果在某一点 $x^*$ ，使得 $f(x^*)$ 在每一个坐标轴 $x_i(i = 1,2,...n)$ 上都是最小值，那么 $f(x^*)$ 就是一个全局的最小值，如下图，在这一点对可微的凸函数有：

对于不可微的凸函数，这一结论并不成立，即收敛点并不一定是全局最优，如下图所示，两个坐标轴方向的迭代会在红色虚线的交叉处停止，因为在这两个方向单独来看，都已经找不到更小的点了，实际上并没有到全局最优点：

让我们回忆一下Lasso回归的损失函数形式：

$L(\theta )=\frac{1}{2}\sum_{i=1}^m(\sum_{i=1}^m\theta_ix_i-y_i)^2+\sum_{i=1}^m|\theta_i|$

其损失函数的形式是： $y=g(x)+\sum_i^n h_i(x_i)$ ，其中 $g(x)$ 是可微的凸函数，每个 $h_i(x_i)$ 都是不可微的凸函数，这种形式可不可以使用坐标下降法呢？答案是可以的，如下图所示：

从几何上理解：因为加上的每个 $h_i(x_i)$ 都是凸函数，也就是在每个坐标轴上都是

理论上来看：要证明收敛点 $x$ 为全局最优解，则要有对任意 $y$ ： $f(y) -f(x)\geq 0$ ，而且对于凸函数，其必然满足一阶条件： $g(y)-g(x)\geq \nabla g(x)^T(y-x)$ ，故综合可得：

$f(y) -f(x)= g(y)-g(x)+\sum_i^n [h_i(y_i)-h_i(x_i)]$

$f(y) -f(x)\geq \nabla g(x)^T(y-x)+\sum_i^n [h(y_i)-h(x_i)]=\sum_i^n [\nabla_i g(x_i)(y_i-x_i)+h_i(y_i)-h_i(x_i)]$

后面这个式子将任意的点y与收敛点x比较大小的问题转移到了各个坐标轴上，因为收敛点是各个坐标轴的最小值，所以 $\nabla_i g(x_i)(y_i-x_i)+h_i(y_i)-h_i(x_i)\geq 0$ ，所以收敛点是全局最优。

2）坐标下降法用法

每一轮迭代中，分别把损失函数看做 $x$ 的 $n$ 个维度 $x_i$ 的函数，对每个函数求极小值，当所有的坐标轴上的 $x_i(i = 1,2,...n)$ 都达到收敛时，损失函数最小，此时的 $x$ 即为我们要求的结果。

具体的算法过程：

随机取一个初值 $x^{(0)}$ ，(0)代表我们迭代的轮数；
对于第k轮的迭代：我们从 $x^{(k)}_1$ 开始，到 $x^{(k)}_n$ 为止，依次求 $x^{(k)}_i$ ， $x^{(k)}_i$ 的表达式如下：

如果达到了设定的终止条件，则终止迭代，得到收敛点 $x$ ，比如设定一个阈值，如果在所有维度上变化都小与这个值，那么终止迭代。

小结：

坐标下降每次只进行一个坐标轴的优化，如果多个一起优化不一定能收敛；
每次迭代中坐标轴的顺序可以是任意的，即可以按{1,2,...,n}的任何顺序进行下降；
坐标下降每一轮迭代的效果类似于梯度下降的一次迭代；
坐标下降法的优点是非常简单高效，适用性也比较广。

3 总结

本篇主要介绍了Ridge回归和Lasso回归的概念，当我们需要正则降低模型结构风险的时候，他们是非常合适的。此外，本文介绍了他们的求解方法，其中Lasso回归的求解较为复杂，除了本文提到的次梯度方法和坐标下降法之外，还有别的方法可用，比如最小角回归法、近端梯度下降法等，以后有时间了再加上吧，下一篇打算说说逻辑回归了。

主要参考
【机器学习】次梯度（subgradient）方法
 坐标下降法(Coordinate descent)