本文参考机器学习中的范数规则化之（一）L0、L1与L2范数，博主细致看了这篇博文，个人觉得实在太过精彩，就‘据为己有’了。
监督学习实际上就是在规则化参数的同时最小化误差，最小化误差是为了让我们的模型拟合我们的训练数据，而规则化参数是防止我们的模型过分拟合我们的训练数据。下面简单介绍机器学习中常用的几种正则化方法。因为参数太多，会导致我们的模型复杂度上升，容易过拟合，也就是我们的训练误差会很小。但训练误差小并不是我们的最终目标，我们的目标是希望模型的测试误差小，也就是能准确的预测新的样本。所以，我们需要保证模型“简单”的基础上最小化训练误差，这样得到的参数才具有好的泛化性能（也就是测试误差也小），而模型“简单”就是通过规则函数来实现的。另外，规则项的使用还可以约束我们的模型的特性。这样就可以将人对这个模型的先验知识融入到模型的学习当中，强行地让学习到的模型具有人想要的特性，例如稀疏、低秩、平滑等等。
一般来说，监督学习可以看做最小化下面的目标函数：
$$w^*=arg\min_{w}\sum_{i}L(y_i,f(x_i;w))+\lambda\Omega(w)$$
其中，第一项$L(yi,f(xi;w))$衡量我们的模型（分类或者回归）对第$i$个样本的预测值$f(xi;w)$和真实的标签$y_i$之前的误差。因为我们的模型是要拟合我们的训练样本的嘛，所以我们要求这一项最小，也就是要求我们的模型尽量的拟合我们的训练数据。但正如上面说言，我们不仅要保证训练误差最小，我们更希望我们的模型测试误差小，所以我们需要加上第二项，也就是对参数$w$的规则化函数$\Omega(w)$去约束我们的模型尽量的简单。
机器学习的大部分带参模型都十分相似，对于第一项损失(loss)函数，如果是Square loss，那就是最小二乘了；如果是Hinge Loss，那就是著名的SVM了；如果是exp-Loss，那就是牛逼的Boosting了；如果是log-Loss，那就是Logistic Regression了；等等。不同的loss函数，具有不同的拟合特性，这个也得就具体问题具体分析的。但这里，我们先不究loss函数的问题，我们把目光转向“规则项$\Omega(w)$”。
规则化函数$\Omega(w)$也有很多种选择，一般是模型复杂度的单调递增函数，模型越复杂，规则化值就越大。比如，规则化项可以是模型参数向量的范数。然而，不同的选择对参数$w$的约束不同，取得的效果也不同，但我们在论文中常见的都聚集在：零范数、一范数、二范数、迹范数、Frobenius范数和核范数等等。
L0范数与L1范数
L0范数是指向量中非0的元素的个数。如果我们用L0范数来规则化一个参数矩阵W的话，就是希望W的大部分元素都是0，也就是让参数W是稀疏的。
L1范数是指向量中各个元素绝对值之和，也叫“稀疏规则算子”(Lasso regularization)。为什么L1范数会使权值稀疏？有人可能会这样给你回答“它是L0范数的最优凸近似”。实际上，还存在一个更美的回答：任何的规则化算子，如果他在$W_i=0$的地方不可微，并且可以分解为一个“求和”的形式，那么这个规则化算子就可以实现稀疏。这说是这么说，$W$的L1范数是绝对值，$|w|$在$w=0$处是不可微。还有一个问题：既然L0可以实现稀疏，为什么不用L0，而要用L1呢？个人理解一是因为L0范数很难优化求解（NP难问题），二是L1范数是L0范数的最优凸近似，而且它比L0范数要容易优化求解。所以大家才把目光和万千宠爱转于L1范数。
一句话总结：L1范数和L0范数可以实现稀疏，L1因具有比L0更好的优化求解特性而被广泛应用。好，到这里，我们大概知道了L1可以实现稀疏，但我们会想呀，为什么要稀疏？让我们的参数稀疏有什么好处呢？这里扯两点：
特征选择(Feature Selection)
大家对稀疏规则化趋之若鹜的一个关键原因在于它能实现特征的自动选择。一般来说，$x_i$的大部分元素（也就是特征）都是和最终的输出$y_i$没有关系或者不提供任何信息的，在最小化目标函数的时候考虑$x_i$这些额外的特征，虽然可以获得更小的训练误差，但在预测新的样本时，这些没用的信息反而会被考虑，从而干扰了对正确$y_i$的预测。稀疏规则化算子的引入就是为了完成特征自动选择的光荣使命，它会学习地去掉这些没有信息的特征，也就是把这些特征对应的权重置为0。
可解释性(Interpretability)
另一个青睐于稀疏的理由是，模型更容易解释。例如患某种病的概率是$y$，然后我们收集到的数据x是1000维的，也就是我们需要寻找这1000种因素到底是怎么影响患上这种病的概率的。假设我们这个是个回归模型：$y=w_1x_1+w_2x_2+\cdots+w_{1000}x_{1000}+b$（当然了，为了让$y$限定在[0,1]的范围，一般还得加个Logistic函数）。通过学习，如果最后学习到的$w^*$就只有很少的非零元素，例如只有5个非零的$w_i$，那么我们就有理由相信，这些对应的特征在患病分析上面提供的信息是巨大的，决策性的。也就是说，患不患这种病只和这5个因素有关，那医生就好分析多了。但如果1000个wi都非0，医生面对这1000种因素，累觉不爱。
L2范数
除了L1范数，还有一种更受宠幸的规则化范数是L2范数：$|W|^2$。它也不逊于L1范数，它有两个美称，在回归里面，有人把有它的回归叫“岭回归”（Ridge Regression），有人也叫它“权值衰减weight decay”。这用的很多吧，因为它的强大功效是改善机器学习里面一个非常重要的问题：过拟合。至于过拟合是什么，上面也解释了，就是模型训练时候的误差很小，但在测试的时候误差很大，也就是我们的模型复杂到可以拟合到我们的所有训练样本了，但在实际预测新的样本的时候，糟糕的一塌糊涂。通俗的讲就是应试能力很强，实际应用能力很差。擅长背诵知识，却不懂得灵活利用知识。
L2范数是指向量各元素的平方和然后求平方根。我们让L2范数的规则项$|W|^2$最小，可以使得$W$的每个元素都很小，都接近于0，但与L1范数不同，它不会让它等于0，而是接近于0，这里是有很大的区别的哦。而越小的参数说明模型越简单，越简单的模型则越不容易产生过拟合现象。为什么越小的参数说明模型越简单？我也不懂，我的理解是：限制了参数很小，实际上就限制了多项式某些分量的影响很小。
这里也一句话总结下：通过L2范数，我们可以实现了对模型空间的限制，从而在一定程度上避免了过拟合。L2范数的好处是什么呢？这里也扯上两点：
学习理论的角度：
从学习理论的角度来说，L2范数可以防止过拟合，提升模型的泛化能力。
优化计算的角度：
从优化或者数值计算的角度来说，L2范数有助于处理条件数(condition number)_(ps:条件数是一个矩阵(或者它所描述的线性系统)的稳定性或者敏感度的度量，如果一个矩阵的condition number在1附近，那么它就是well-conditioned的，如果远大于1，那么它就是ill-conditioned(病态)的，如果一个系统是ill-conditioned的，它的输出结果就不要太相信了。)_不好的情况下矩阵求逆很困难的问题。因为目标函数如果是二次的，对于线性回归来说，那实际上是有解析解的，求导并令导数等于零即可得到最优解为：
$$W^*=(X^TX)^{-1}X^TY$$
然而，如果当我们的样本X的数目比每个样本的维度还要小的时候，矩阵$X^TX$将会不是满秩的，也就是$X^TX$会变得不可逆，所以$w^*$就没办法直接计算出来了。或者更确切地说，将会有无穷多个解(因为我们方程组的个数小于未知数的个数)。也就是说，我们的数据不足以确定一个解，如果我们从所有可行解里随机选一个的话，很可能并不是真正好的解，总而言之，我们过拟合了。
但如果加上L2规则项，就变成了下面这种情况，就可以直接求逆了：
$$W^*=(X^TX+\lambda I)^{-1}X^TY$$
这里面，专业点的描述是：要得到这个解，我们通常并不直接求矩阵的逆，而是通过解线性方程组的方式(例如高斯消元法)来计算。考虑没有规则项的时候，也就是$\lambda=0$的情况，如果矩阵$X^TX$的 condition number很大的话，解线性方程组就会在数值上相当不稳定，而这个规则项的引入则可以改善condition number。
另外，如果使用迭代优化的算法，condition number太大仍然会导致问题：它会拖慢迭代的收敛速度，而规则项从优化的角度来看，实际上是将目标函数变成$\lambda$-strongly convex($\lambda$强凸)的了。$\lambda$强凸定义如下：当函数$f$满足：
$$f(y) \ge f(x)+\nabla f(x)*(y-x)+\frac{\lambda}{2}|y-x|^2$$
时，我们就称函数$f$是$\lambda$强凸函数，其中参数$\lambda> 0$。当$\lambda=0$时退回到普通convex函数的定义。
在直观的说明强凸之前，我们先看看普通的凸是怎样的。假设我们让$f$在$x$的地方做一阶泰勒近似($f(x)=f(a)+f’(a)(x-a)+o(|x-a|)$)：
$$f(y) \ge f(x)+\nabla f(x)*(y-x)+o(|y-x|)$$
直观来讲，convex 性质是指函数曲线位于该点处的切线，也就是线性近似之上，而 strongly convex 则进一步要求位于该处的一个二次函数上方，也就是说要求函数不要太“平坦”而是可以保证有一定的“向上弯曲”的趋势。专业点说，就是convex 可以保证函数在任意一点都处于它的一阶泰勒函数之上，而strongly convex可以保证函数在任意一点都存在一个非常漂亮的二次下界quadratic lower bound。-1.png "示例")
从图中我们可以看到，仅仅靠convex性质并不能保证在梯度下降和有限的迭代次数的情况下得到的点$w$会是一个比较好的全局最小点$w^*$的近似点（插个话，有地方说，实际上让迭代在接近最优的地方停止，也是一种规则化或者提高泛化性能的方法）。正如上面分析的那样，如果$f(w)$在全局最小点$w^*$周围是非常平坦的情况的话，我们有可能会找到一个很远的点。但如果我们有“强凸”的话，就能对情况做一些控制，我们就可以得到一个更好的近似解。至于有多好嘛，这里面有一个bound，这个 bound 的好坏也要取决于strongly convex性质中的常数$\alpha$的大小。看到这里，不知道大家学聪明了没有。如果要获得strongly convex怎么做？最简单的就是往里面加入一项$(\alpha/2)*|w|^2$。
讲个strongly convex花了那么多的篇幅。实际上，在梯度下降中，目标函数收敛速率的上界实际上是和矩阵$X^TX$的 condition number有关，$X^TX$的 condition number 越小，上界就越小，也就是收敛速度会越快。
这一个优化说了那么多的东西。还是来个一句话总结吧：L2范数不但可以防止过拟合，还可以让我们的优化求解变得稳定和快速。
好了，这里兑现上面的承诺，来直观的聊聊L1和L2的差别，为什么一个让绝对值最小，一个让平方最小，会有那么大的差别呢？我看到的有两种几何上直观的解析：
下降速度
我们知道，L1和L2都是规则化的方式，我们将权值参数以L1或者L2的方式放到代价函数里面去。然后模型就会尝试去最小化这些权值参数。而这个最小化就像一个下坡的过程，L1和L2的差别就在于这个“坡”不同，如下图：L1就是按绝对值函数的“坡”下降的，而L2是按二次函数的“坡”下降。所以实际上在0附近，L1的下降速度比L2的下降速度要快。所以会非常快得降到0。不过我觉得这里解释的不太中肯，当然了也不知道是不是自己理解的问题。-2.png "示例")
L1在江湖上人称Lasso，L2人称Ridge。不过这两个名字还挺让人迷糊的，看上面的图片，Lasso的图看起来就像ridge，而ridge的图看起来就像lasso。
模型空间限制
实际上，对于L1和L2规则化的代价函数来说，我们可以写成以下形式：
$$Lasso:\quad \min_W\frac{1}{n}|Y-XW|^2,\quad s.t.|W|_1 \le C \\
Ridge:\quad \min_W\frac{1}{n}|Y-XW|^2,\quad s.t.|W|_2 \le C \\
$$
也就是说，我们将模型空间限制在$W$的一个L1-ball 中。为了便于可视化，我们考虑两维的情况，在$(W1, W2)$平面上可以画出目标函数的等高线，而约束条件则成为平面上半径为$C$的一个 norm ball 。等高线与 norm ball 首次相交的地方就是最优解：-3.png "示例")
可以看到，L1-ball 与L2-ball 的不同就在于L1在和每个坐标轴相交的地方都有“角”出现，而目标函数的测地线除非位置摆得非常好，大部分时候都会在角的地方相交。注意到在角的位置就会产生稀疏性，例如图中的相交点就有$W1=0$，而更高维的时候（想象一下三维的L1-ball 是什么样的？）除了角点以外，还有很多边的轮廓也是既有很大的概率成为第一次相交的地方，又会产生稀疏性。
相比之下，L2-ball 就没有这样的性质，因为没有角，所以第一次相交的地方出现在具有稀疏性的位置的概率就变得非常小了。这就从直观上来解释了为什么L1-regularization 能产生稀疏性，而L2-regularization 不行的原因了。
因此，一句话总结就是：L1会趋向于产生少量的特征，而其他的特征都是0，而L2会选择更多的特征，这些特征都会接近于0。Lasso在特征选择时候非常有用，而Ridge就只是一种规则化而已。