前言
上一篇文章主要记录了多元线性回归（链接），在处理较为复杂的数据的回归问题时，普通的线性回归算法通常会出现预测精度不够，如果模型中的特征之间有相关关系，就会增加模型的复杂程度。当数据集中的特征之间有较强的线性相关性时，即特征之间出现严重的多重共线性时，用最小二乘法估计模型参数往往会使得参数估计的方差太大。此时求解出来的模型就很不稳定。在线性回归中如果参数过大、特征过多也易造成过拟合。
岭回归和 Lasso 回归的出现是为了解决线性回归出现的过拟合以及在通过正规方程方法求解 \(w\) 的过程中出现的 \(\mathbf{X}^T \mathbf{X}\) 不可逆这两类问题的。在这两种回归中引入正则化项来达到目的。
范数
什么是范数
我们知道距离的定义是一个宽泛的概念，只要满足非负、自反、三角不等式就可以称之为距离。范数是一种强化了的距离概念，它在定义上比距离多了一条数乘的运算法则。有时候为了便于理解，我们可以把范数当作距离来理解。
在数学上，范数包括向量范数和矩阵范数，向量范数表征向量空间中向量的大小，矩阵范数表征矩阵引起变化的大小。一种非严密的解释就是，对应向量范数，向量空间中的向量都是有大小的，这个大小如何度量，就是用范数来度量的，不同的范数都可以来度量这个大小，就好比米和尺都可以来度量远近一样；对于矩阵范数，学过线性代数，我们知道，通过运算 \(AX=B\)，可以将向量 \(X\) 变化为 \(B\)，矩阵范数就是来度量这个变化大小的。
这里简单地介绍以下几种向量范数的定义和含义
L-P 范数
与闵可夫斯基距离的定义一样，L-P范数不是一个范数，而是一组范数，其定义如下：
\[ Lp=\sqrt[p]{\sum\limits_{1}^n x_i^p}，x=(x_1,x_2,\cdots,x_n) \]
根据P 的变化，范数也有着不同的变化，一个经典的有关P范数的变化图如下:
LP
上图表示了p从无穷到0变化时，三维空间中到原点的距离（范数）为1的点构成的图形的变化情况。以常见的L-2范数（p=2）为例，此时的范数也即欧氏距离，空间中到原点的欧氏距离为1的点构成了一个球面。
但是实际上，在 \(0 \leq p < 1\) 时，Lp并不满足三角不等式的性质，也就不是严格意义下的范数。以p=0.5，二维坐标(1,4)、(4,1)、(1,9)为例，\(\sqrt[0.5]{(1+\sqrt{4})} + \sqrt[0.5]{(\sqrt{4} + 1)}<\sqrt[0.5]{(1+\sqrt{9})}\)。因此这里的L-P范数只是一个概念上的宽泛说法。
L0 范数
当P=0时，也就是L0范数，由上面可知，L0范数并不是一个真正的范数，它主要被用来度量向量中非零元素的个数。用上面的L-P定义可以得到的L-0的定义为:
\[ ||x||=\sqrt[0]{\sum\limits_1^nx_i^0}，x=(x_1,x_2,\cdots,x_n) \]
通常写作
\[ ||x||_0=\#(i|x_i\neq 0) \]
代表非零元素的数量。
L1 范数
L1范数是我们经常见到的一种范数，它的定义如下:
\[ ||x||_1=\sum_i|x_i| \]
表示向量x中非零元素的绝对值之和。
L2 范数
L2范数是我们最常见最常用的范数了，我们用的最多的度量距离欧氏距离就是一种L2范数，它的定义如下:
\[ ||x||_2=\sqrt{\sum_ix_i^2} \]
L \(\infty\) 范数
当 \(P=\infty\) 时，也就是\(L\infty\) 范数，它主要被用来度量向量元素的最大值。
\[ ||x||_\infty=\sqrt[\infty]{\sum\limits_1^nx_i^\infty}，x=(x_1,x_2,\cdots,x_n) \]
通常写作
\[ ||x||_\infty=max(|x_i|) \]
岭回归
岭回归(英文名：ridge regression, Tikhonov regularization)是一种专用于共线性数据分析的有偏估计回归方法，实质上是一种改良的最小二乘估计法，通过放弃最小二乘法的无偏性，以损失部分信息、降低精度为代价获得回归系数更为符合实际、更可靠的回归方法，对病态数据的拟合要强于最小二乘法。
岭回归就是在线性回归的基础上加上 L2 范数约束，损失函数是（习惯上一般会去掉前面线性回归目标函数中的 \(\frac{1}{n}\)，但是为了方便推导会加一个 \(\frac{1}{2}\)）:
\[ J_R(w)=\frac{1}{2}\|y-Xw\|^2+\frac{\lambda}{2}\|w\|^2 \]
有解析解:
\[ \hat{w}_R = (X^{T}X+\lambda I)^{-1}X^{T}y \]
其中 \(\lambda>0\) 是一个常数，有了正则项以后解就有了很好的性质，首先是对 \(w\) 的模做约束，使得它的数值会比较小，很大程度上减轻了过拟合的问题；其次是上面求逆部分肯定可以解，在实际使用中岭回归的作用很大，通过调节参数 \(\lambda\)，可以得到不同的回归模型。
实际上岭回归可以用下面的优化目标形式表达:
\[ \min_{w} \frac{1}{2}\|y-Xw\|^2, \quad s.t. \|w\|_2<\theta \]
也就是说，我依然优化线性回归的目标，但是条件是 \(w\) 的模长不能超过限制 \(\theta\)。上面两种优化形式是等价的，可以找到一一对应的 \(\lambda\) 和 \(\theta\)。
Lasso 稀疏约束
如前面的ridge regression，对 \(w\) 做2范数约束，就是把解约束在一个l2-ball里面，放缩是对球的半径放缩，因此 \(w\) 的每一个维度都在以同一个系数放缩，通过放缩不会产生稀疏的解——即某些 \(w\) 的维度是0。而实际应用中，数据的维度中是存在噪音和冗余的，稀疏的解可以找到有用的维度并且减少冗余，提高回归预测的准确性和鲁棒性（减少了过拟合）。在压缩感知、稀疏编码等非常多的机器学习模型中都需要用到稀疏约束。
稀疏约束最直观的形式应该是约束0范数，如上面的范数介绍，\(w\) 的0范数是求 \(w\) 中非零元素的个数。如果约束\(‖w‖_0≤k\) ，就是约束非零元素个数不大于k。不过很明显，0范数是不连续的且非凸的，如果在线性回归中加上0范数的约束，就变成了一个组合优化问题：挑出小于等于k个系数然后做回归，找到目标函数的最小值对应的系数组合，是一个NP问题。
有趣的是，l1-norm（1范数）也可以达到稀疏的效果，是0范数的最优凸近似
L0L1范数
很重要的是1范数容易求解，并且是凸的，所以几乎看得到稀疏约束的地方都是用的1范数。
回到本文对于线性回归的讨论，就引出了Lasso(least absolute shrinkage and selection operator) 的问题:
\[ \min_{w} \frac{1}{2}\|y-Xw\|^2, \quad s.t. \|w\|_1<\theta \]
也就是说约束在一个l1-ball里面。ridge和lasso的效果见下图:
L0L1 picture
红色的椭圆和蓝色的区域的切点就是目标函数的最优解，我们可以看到，如果是圆，则很容易切到圆周的任意一点，但是很难切到坐标轴上，因此没有稀疏；但是如果是菱形或者多边形，则很容易切到坐标轴上，因此很容易产生稀疏的结果。这也说明了为什么1范数会是稀疏的。