正则化之L1,L2

参考：https://www.cnblogs.com/callyblog/p/8094745.html

1. 基本概念

    监督式机器学习的问题本质在于：在规则化参数的同时最小化误差；最小化误差是为了让模型拟合训练数据，规则化参数则是防止模型过分拟合训练数据。因为参数太多，会导致模型复杂度上升引起过拟合，即训练误差会很小。可训练误差小并不是最终目标，我们的目标是测试误差小，也就是可以准确预测新样本。所以，我们需要保证模型“简单”的基础上最小化训练误差，这样得到的参数才具有好的泛化性能（也就是测试误差也小），而模型“简单”就是通过规则函数来实现。另外，规则项的使用还可以约束模型的特性，如此就可以将人对该模型的先验知识（经验）融入到模型的学习当中，强行让学习到的模型具有人想要的特性——稀疏、低秩、平滑等——有时候人的先验知识很重要，前人的经验可以让整个过程少走弯路；这个规则对机器学习也适用，稍稍点拨一下，它可以更快学习相应的任务，此时规则项就充当了人和机器的媒介。

    另外几种角度看规则化，它符合奥卡姆剃刀（Occam's razor）原理，不过它的思路更加平易近人：在所有可能选择的模型中，应该选择能够很好解释已知数据并且十分简单的模型。从贝叶斯估计的角度看来，规则化项对应于模型的先验概率。民间还有一种说法：规则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项（Regularizer）或惩罚项（Penalty Term）。

    一般来说，监督学习可以看做最小化下边的目标函数：

$w^* = arg \underset{w}{\min} \sum_{i} L(y_i, f(x_i;w)) + \lambda \Omega(w)$

    第一项$L(y_i, f(x_i;w))$衡量模型（分类或回归）对第$i$个样本预测值$f(x_i;w)$和真是标签值$y_i$之间的误差，因为模型是要拟合训练样本的，所以要求这一项最小，也就要求模型尽量地拟合训练数据。

    不仅保证训练误差最小，更希望测试误差小，于是引入第二项，也就是对参数w的规则化函数$\Omega(w)$去约束模型使得模型尽可能简单。

    对第一项损失函数（Loss函数）：

函数名	含义
Square Loss	最小二乘算法
Hinge Loss	SVM算法
Exp-Loss	Boosting算法
Log-Loss	逻辑回归Logistic Regression算法

    不同损失函数具有不同的拟合特性，这需要结合具体问题具体分析，本文不详细讲解损失函数，而是集中在第二项$\Omega(w)$——规则项。规则化函数$\Omega(w)$也有很多种选择，一般是模型复杂度的单调递增函数，模型越复杂，规则化值就越大。规则化项可以是模型参数向量的范数，然而不同的选择对参数$w$的约束不同，取得的效果也不同，通常论文写作中会提到：

• 零范数

• 一范数

• 二范数

• 迹范数

• Frobenius范数

• 核范数

文本主要讲解前三种范数。

2. L0/L1范数

这两个范数都是为了对向量的特征进行收集、或者说规则化，使得达到一定规则，减轻过拟合状况。

    L0范数是指向量中非零元素的个数（规则）。如果用L0范数来规则化一个参数矩阵$W$的话，就是希望$W$的大部分元素都是0，换句话说让参数$W$是稀疏矩阵。所以通常看到的“压缩感知”和“稀疏编码”就是通过这种方式来实现的，这和我们通常理解的L1范数实现稀疏有点区别，可能您一直在意$||W||_1$，实际上L0和L1范数有着某种不寻常的关系。

    L1范数是指向量中各个元素绝对值之和（规则），也有个美称叫“稀疏规则算子”（Lasso Regularization）。思考一个问题：为什么L1范数会使权值稀疏？有人可能会这样给你回答“它是L0范数的最优凸近似”，实际上，还存在一个更美的答案：任何规则化算子，如果在$W_i = 0$的地方不可微，并且可以分解为一个“求和”的形式，那么这个规则化算子就可以实现稀疏。所以：$W$的L1范数是绝对值，$|w|$在$w = 0$的地方是不可微的——对比L2范数就能够更直观理解L1范数了。

    既然L0可以实现稀疏，为什么不使用L0，而要使用L1呢？主要原因（原文作者理解）

1. 是L0范数很难优化求解（NP难问题）

2. 是L1范数是L0范数的最优凸近似，而且比L0范数容易优化求解

$\min||x||_0 = \min||x||_1$

    总之L1范数和L0范数都可以实现稀疏，L1因为具有比L0更好的优化求解特性而被广泛使用。

    稀疏矩阵的好处：

• 特征选择（Feature Selection）：稀疏规则可以实现特征的自动选择，一般来说，$x_i$的大部分元素（也就是特征）都是和最终输出$y_i$没有关系或者不提供任何信息的，在最小化目标函数的时候考虑$x_i$这些额外的特征，虽然可以获得更小的训练误差，但在预测新的样本时，这些没用的信息反而会被考虑，从而干扰了对正确$y_i$的预测。稀疏规则化算子的引入就是为了完成特征自动选择的任务，它会去学习掉这些没有信息的特征，也就是把这种类型的特征权重设置为0。

• 可解释性（Interpretability）：另一个青睐于稀疏的理由是，模型更容易解释。如某种病的概率是$y$，然后收集到的数据$x$是1000维，也就是我们需要寻找这1000种因素到底是怎么影响患上这种病的概率。假设这个是回归模型，等价于：$y = w_1 \times x_1 + w_2 \times x_w + ... + w_{1000} \times x_{1000} + b$（当然为了让$y$限定在[0,1]中，还需要加一个Logistic函数），通过学习，如果最后学习到的$w^*$就只有很少的非零元素，如5个，那么就有理由相信，这些对应特征在患病分析上面提供的信息是巨大的，决策性的。也就是说，患不患这种病只和这五个因素有关，医生就更容易分析。

3. L2范数

    除了L1范数，还有一种更受宠幸的规则化范数：$||W||_2$，它也不逊于L1范数，在回归模型中，有人把这种回归称为“岭回归（Ridge Regression）”，也有人叫它“权值衰减Weight Decay”（通过一定的规则化，让权值达到泛化度很好的情况）——它可以解决机器学习中一个很重要的问题：过拟合。

    线性回归（预测）：

    逻辑回归（分类）：

    从左到右一次是：

1. 欠拟合（Underfitting，也称High-Bias）

2. 合适的拟合（模型表现良好）

3. 过拟合（Overfitting，也称High-Variance）

    如果模型复杂（可以拟合任意复杂函数），它可以让我们模型拟合所有的数据点，也就基本没有误差，对回归而言，函数曲线通过了所有数据点，对分类而言，函数曲线把所有数据点都分类正确。那么为什么L2可以防止过拟合？先理解一下L2范数：

    L2范数是指向量各元素的平方和然后求平方根（求平方根，达到一定的规则），我们让L2范数规则项$||W||_2$最小，可以使得$W$的每个元素都很小，都接近于0，但和L1范数不同，它不会等于0（只接近），这里有很大的区别。越小的参数说明模型越简单，越简单的模型则越不容易产生过拟合（原文作者理解）：限制了参数很小，实际上就限制了多项式某些分量的影响很小，这样相当于减少了参数的个数，通过L2范数，可以实现对模型空间的限制，而在一定程度上避免了过拟合。

    L2范数的好处：

• 学习理论的角度：L2范数可以防止过拟合，提升模型的泛化能力。

• 优化计算的角度：从优化或者数值计算来考虑，L2范数有助于处理数值条件不好情况下矩阵求逆很困难的问题。

    优化有两大难题：

1. 局部最小值：我们的目的是找全局最小值，如果局部最小值太多，那么优化算法会陷入局部最小而不能自拔。

2. ill-condition病态问题：它对应well-condition，假设有个方程组$AX=b$，我们需求解$X$，如果$A$或$b$稍微改变，会使得$X$的解发生很大改变，这种情况就是ill-condition。

    示例：

    参考上图，第一行假设是我们的$AX=b$，第二行稍微改变下$b$，得到的$x$和没改变的差别很大，而第三行稍微改变下系数矩阵$A$，结果变化也很大。换句话来说，这个系统的解对系数矩阵$A$或者$b$太敏感，有因为一般系数矩阵$A$和$b$是从实验数据中得到，所以它是存在误差的，如果系统对这个误差是可以容忍还好，但系统对误差的敏感使得误差更大，这个解就变得越发不靠谱。——因此我们说这个方程组系统是ill-condition病态不正常的（不稳定且有问题），相比之下右边那个就是well-condition的。

    对于一个ill-condition的系统，稍微改变下输出就发生了很大的改变，这表明系统本身实用性不强，对于一个标准的回归问题$y=f(x)$，我们使用训练样本$x$去训练模型时，期望$y$的输出尽可能符合预期且波动很小，对这种ill-condition对的系统，它的结果会让我们产生怀疑，所以需要一个标准让我们信任这个结果（也不能说直接放弃ill-condition的系统）。这里的condition number就是衡量输入发生微小变化时，输出发生多大的变化，即系统对微小变化的敏感度：

• condition number小就是well-condition

• condition number大就是ill-condition

    如果方阵$A$是非奇异的，那么$A$的condition number定义为：

$K(A) = ||A|| \times ||A^{-1}||$

即矩阵A的范数乘以它的逆的范数，所以具体值是多少就在于您选择的范数是什么了。如果方阵$A$是奇异的，那么$A$的condition number就是正无穷大，实际上，每一个可逆方阵都存在一个condition number，但如果要计算它，我们需要先知道这个方阵的范数（norm）和机器的精度（Machine Epsilon）。为什么需要范数？范数就相当于衡量一个矩阵的大小，我们知道矩阵是没有大小的，当上面不是要衡量一个矩阵$A$或者向量$b$变化的时候，解$x$不久有了大小么？所以肯定得要有一个东西来衡量矩阵和向量的大小吧？对的，他就是范数，表示矩阵大小和向量长度（在非欧式空间范围内，大小和长度的计算并非平方和再求均方根这么简单）。于是对于$AX=b$，可以得到如下结论：

也就是我们的解$x$的相对变化和$A$或者$b$的相对变化具备上述式子中的关系，其中$k(A)$就相当于倍率（当$A$变化时，$x$的变化速率）。

    所以conidtion number实际是一个矩阵（或者它所描述的线性系统）的稳定性或者敏感度的度量，如果一个矩阵的condition number在1附近，那么它就是well-condition的，如果远大于1，那么它就是ill-condition的，如果一个系统是ill-condition，那么它的输出结果就不太可信了。从优化或者数值计算的角度来说，L2范数有助于处理condition number不好的情况下矩阵求逆很困难的问题，因为目标函数如果是二次的，对于线性回归来说，实际上是有解析解的，求导并令导数等于零即可得到最优解：

$\hat{w} = (X^T X)^{-1} X^T y$

    然而，如果样本$X$的数目比每个样本的维度还小的时候，矩阵$X^TX$将会不是满秩的，也就是$X^TX$会变得不可逆，所以$w^*$就没办法直接计算出来了。确切说，将会有无穷多个解，必须要在数据不足时确定一个解，如果从所有可行解中随机选一个的话，就不是真正好的解，于是就出现了过拟合。引入了L2正则项之后，就变成了下边这种情况：

$w^* = (X^TX + \lambda I)^{-1} X^T y$

    要得到这个解，通常不直接求矩阵的逆，而是通过解线性方程组的方式（高斯消元法）来计算，考虑没有规则项的时候，也就是$\lambda=0$的情况，如果矩阵$X^TX$的condition number很大的话，解线性方程组就会在数值上相当不稳定，而这个规则项的引入则可以改善condition number。另外，如果使用迭代优化的算法，condition number太大仍然会导致问题：它拖慢了收敛的速度，而规则项从优化角度看来，实际上是将目标函数变成$\lambda$-strongly convex（$\lambda$强凸）的，当$f$满足：

时，我们称$\lambda$为$\lambda$-strongly convex函数，其中参数$\lambda > 0$，当$\lambda = 0$时回到普通凸函数的定义。凸函数定义，假设让$f$在$x$的地方做一阶泰勒展开：

    直观来讲，凸性质是指函数曲线位于点处的切线，也就是线性近似之上，而$strongly convex$则进一步要求位于该处的一个二次函数上方，也就是说要求函数不要太平坦而是可以保证有一定的向上弯曲的趋势。专业点说，就是$convex$可以保证函数在任意一点都处于它的一阶泰勒函数之上，而$strongly convex$可以保证函数在任意一点都存在一个非常漂亮的二次下界$quadratic lower bound$，当然这是一个很强的假设，但是同时也是十分重要的假设。

    参考上图，如果函数$f(x)$（左图红色）都会位于蓝色虚线的二次函数之上，则$w_t$和$w^*$比较接近时，$f(w_t)$和$f(w^*)$的值差别还是挺大，也就是会保证在我们最优解$w^*$附近的时候还存在很大的梯度值，这样才可以在比较少的迭代次数达到最优解。

    而在右图中，红色函数$f(w)$只约束在一个线性的蓝色虚线之上，假设是如右图的很不幸的情况（平坦），在$w_t$还离最优解$w^*$很远的时候，近似梯度$(f(w_t)-f(w^*))/(w_t - w^*)$就已经非常小了，在$w_t$处的近似梯度$\partial f/\partial w$就更小了，这样通过梯度下降$w_t + 1 = w_t - \alpha \times (\partial f/\partial w)$得到的结果$w$就是变化非常缓慢向最优点$w^*$移动，在有限的迭代次数下，离最优解还是很远。

    总结：L2范数不但可以防止过拟合，还可以让我们的优化求解变得稳定和快速。

4. L1对比L2

• L1范数是让绝对值最小（权值）

• L2范数是让平方最小（权值）

4.1.下降速度

    L1和L2都是规则化的方式，我们将权值参数以L1或者L2的方式放到代价函数中去，然后模型就会去最小化这些权值参数，而这个最小化就像一个下坡的过程，L1和L2的差别就在于这个“坡”度不同。

4.2.模型空间的限制

    实际上，对于L1和L2规则化的代价函数来说，可以写成如下形式：

    也就是说，我们将空间限制在一个$L1-ball$中，我了可视化，考虑两维的情况，在$(w_1,w_2)$的平面上可以画出目标函数的等高线，而约束条件则称为平面上半径为$C$的一个$norm ball$，等高线和$norm ball$相交的地方就是最优解：

    可以看到，$L1-ball$和$L2-ball$不同就在于$L1$在和每个坐标轴相交的地方都有“角”出现，而目标函数的测地线除非位置摆得非常好，大部分时候都会在角的地方相交，叫角的位置就会产生稀疏性，除了角点以外的，还有很多轮廓也有极大概率称为第一次相交的地方，又会产生稀疏性。相比之下，$L2-ball$就没有这样的性质，因为没有角，所以第一次相交的地方出现在具有稀疏性的位置的概率就变得非常小了，这就从直观上解释了为什么L1正则化可产生稀疏性，而L2不行的原因。

    最终：L1会趋向于产生少量的特征，其他特征都是0，L2会选择更多的特征，这些特征都会接近于0，做特征选择，Lasso更好用。