机器学习中的正则化

关于正则化的理解

正则化是为了防止过拟合
如下图，红色这条“想象力”过于丰富上下横跳的曲线就是过拟合情形。结合上图和正则化的英文 Regularizaiton-Regular-Regularize，直译应该是：规则化（加个“化”字变动词，自豪一下中文还是强）。什么是规则？你妈喊你6点前回家吃饭，这就是规则，一个限制。同理，在这里，规则化就是说给需要训练的目标函数加上一些规则（限制），让他们不要自我膨胀。正则化，看起来，挺不好理解的，追其根源，还是“正则”这两字在中文中实在没有一个直观的对应，如果能翻译成规则化，更好理解。但我们一定要明白，搞学术，概念名词的准确是十分重要，对于一个重要唯一确定的概念，为它安上一个不会产生歧义的名词是必须的，正则化的名称没毛病，只是从如何理解的角度，要灵活和类比。

相关概念

1.强凸性

强凸性多用在优化中(Optimization)，特别是保证很多基于梯度下降方法的算法的线形收敛速率的条件之一。

一个可微函数强凸的定义是：

$$f(y)≥f(x)+∇f(x)T(y−x)+u2 \begin{Vmatrix}y−x\end{Vmatrix}2$$

值得注意的是，强凸性并不要求函数处处可微(differentiable),当函数不光滑的时候，梯度即用次梯度(sub-gradient)代替。从表达式来看，强凸比一般的凸函数更严格在于其中的的二次项$$u2∥y−x∥22u​∥y−x∥2$$.因此可以将其表述为u-strong convex。
这个强凸的性质是很重要的。直观从一维函数来说，一般凸函数只要求函数曲线在其切线之上，至于“上”多少没有要求，也就意味着曲线可以无限“贴着”切线，只要保持在其上就行了。
直观来讲，convex 性质是指函数曲线位于该点处的切线，也就是线性近似之上，而 strongly convex 则进一步要求位于该处的一个二次函数上方，也就是说要求函数不要太“平坦”而是可以保证有一定的“向上弯曲”的趋势。专业点说，就是convex 可以保证函数在任意一点都处于它的一阶泰勒函数之上，而strongly convex可以保证函数在任意一点都存在一个非常漂亮的二次下界quadratic lower bound。当然这是一个很强的假设，但是同时也是非常重要的假设。可能还不好理解，那我们画个图来形象的理解下。

毫无疑问，在优化特别是梯度优化中，这种微弱的梯度变化很难实现快速优化，有可能在有限次数还达不到收敛。如果我们取一个接近最小值的解，这也很难。“非常”接近只是一个定性理解，在这种情况下会出现最优解很近似但是决策变量相差巨大的糟糕情况。这时候，多加一个二次项的，保证有一个二次下界，那么不会出现“贴着”切线的情况，优化也变得更加简单。
有的情况下，没有强凸的条件，可以人为加上一个二次项，以获得强凸特性。
我们取我们的最优解w的地方。如果我们的函数f(w)，见左图，也就是红色那个函数，都会位于蓝色虚线的那根二次函数之上，这样就算wt和w离的比较近的时候，f(wt)和f(w*)的值差别还是挺大的，也就是会保证在我们的最优解w附近的时候，还存在较大的梯度值，这样我们才可以在比较少的迭代次数内达到w。但对于右图，红色的函数f(w)只约束在一个线性的蓝色虚线之上，假设是如右图的很不幸的情况（非常平坦），那在wt还离我们的最优点w很远的时候，我们的近似梯度(f(wt)-f(w))/(wt-w*)就已经非常小了，在wt处的近似梯度∂f/∂w就更小了，这样通过梯度下降wt+1=wt-α*(∂f/∂w)，我们得到的结果就是w的变化非常缓慢，像蜗牛一样，非常缓慢的向我们的最优点w*爬动，那在有限的迭代时间内，它离我们的最优点还是很远。

2.ill-conditioned

优化有两大难题，一是：局部最小值，二是：ill-condition病态问题。前者就不说了，大家都懂吧，我们要找的是全局最小值，如果局部最小值太多，那我们的优化算法就很容易陷入局部最小而不能自拔，这很明显不是观众愿意看到的剧情。那下面我们来聊聊ill-condition。ill-condition对应的是well-condition。那他们分别代表什么？假设我们有个方程组AX=b，我们需要求解X。如果A或者b稍微的改变，会使得X的解发生很大的改变，那么这个方程组系统就是ill-condition的，反之就是well-condition的。我们具体举个例子吧：

咱们先看左边的那个。第一行假设是我们的AX=b，第二行我们稍微改变下b，得到的x和没改变前的差别很大，看到吧。第三行我们稍微改变下系数矩阵A，可以看到结果的变化也很大。换句话来说，这个系统的解对系数矩阵A或者b太敏感了。又因为一般我们的系数矩阵A和b是从实验数据里面估计得到的，所以它是存在误差的，如果我们的系统对这个误差是可以容忍的就还好，但系统对这个误差太敏感了，以至于我们的解的误差更大，那这个解就太不靠谱了。所以这个方程组系统就是ill-conditioned病态的，不正常的，不稳定的，有问题的，哈哈。这清楚了吧。右边那个就叫well-condition的系统了。
还是再啰嗦一下吧，对于一个ill-condition的系统，我的输入稍微改变下，输出就发生很大的改变，这不好啊，这表明我们的系统不能实用啊。你想想看，例如对于一个回归问题y=f(x)，我们是用训练样本x去训练模型f，使得y尽量输出我们期待的值，例如0。那假如我们遇到一个样本x’，这个样本和训练样本x差别很小，面对他，系统本应该输出和上面的y差不多的值的，例如0.00001，最后却给我输出了一个0.9999，这很明显不对呀。就好像，你很熟悉的一个人脸上长了个青春痘，你就不认识他了，那你大脑就太差劲了，哈哈。所以如果一个系统是ill-conditioned病态的，我们就会对它的结果产生怀疑。那到底要相信它多少呢？我们得找个标准来衡量吧，因为有些系统的病没那么重，它的结果还是可以相信的，不能一刀切吧。终于回来了，上面的condition number就是拿来衡量ill-condition系统的可信度的。condition number衡量的是输入发生微小变化的时候，输出会发生多大的变化。也就是系统对微小变化的敏感度。condition number值小的就是well-conditioned的，大的就是ill-conditioned的。

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

也就是矩阵A的norm乘以它的逆的norm。所以具体的值是多少，就要看你选择的norm是什么了。如果方阵A是奇异的，那么A的condition number就是正无穷大了。实际上，每一个可逆方阵都存在一个condition number。但如果要计算它，我们需要先知道这个方阵的norm（范数）和Machine Epsilon（机器的精度）。为什么要范数？范数就相当于衡量一个矩阵的大小，我们知道矩阵是没有大小的，当上面不是要衡量一个矩阵A或者向量b变化的时候，我们的解x变化的大小吗？所以肯定得要有一个东西来度量矩阵和向量的大小吧？对了，他就是范数，表示矩阵大小或者向量长度。OK，经过比较简单的证明，对于AX=b，我们可以得到以下的结论：

也就是我们的解x的相对变化和A或者b的相对变化是有像上面那样的关系的，其中k(A)的值就相当于倍率，看到了吗？相当于x变化的界。

对condition number来个一句话总结：conditionnumber是一个矩阵（或者它所描述的线性系统）的稳定性或者敏感度的度量，如果一个矩阵的condition number在1附近，那么它就是well-conditioned的，如果远大于1，那么它就是ill-conditioned的，如果一个系统是ill-conditioned的，它的输出结果就不要太相信了。

3.范数

一、L0范数与L1范数

L1范数是指向量中各个元素绝对值之和，也称街区距离（city-block），也有个美称叫“稀疏规则算子”（Lasso regularization）。 L0范数是指向量中非0的元素的个数。如果我们用L0范数来规则化一个参数矩阵W的话，就是希望W的大部分元素都是0。这太直观了，太露骨了吧，换句话说，让参数W是稀疏的。OK，看到了“稀疏”二字，大家都应该从当下风风火火的“压缩感知”和“稀疏编码”中醒悟过来，原来用的漫山遍野的“稀疏”就是通过这玩意来实现的。但你又开始怀疑了，是这样吗？看到的papers世界中，稀疏不是都通过L1范数来实现吗？脑海里是不是到处都是||W||1影子呀！几乎是抬头不见低头见。没错，这就是这节的题目把L0和L1放在一起的原因，因为他们有着某种不寻常的关系。那我们再来看看L1范数是什么？它为什么可以实现稀疏？为什么大家都用L1范数去实现稀疏，而不是L0范数呢？
现在我们来分析下这个价值一个亿的问题：为什么L1范数会使权值稀疏？有人可能会这样给你回答“它是L0范数的最优凸近似”。实际上，还存在一个更美的回答：任何的规则化算子，如果他在Wi=0的地方不可微，并且可以分解为一个“求和”的形式，那么这个规则化算子就可以实现稀疏。这说是这么说，W的L1范数是绝对值，|w|在w=0处是不可微，但这还是不够直观。这里因为我们需要和L2范数进行对比分析。所以关于L1范数的直观理解，请待会看看第二节。
对了，上面还有一个问题：既然L0可以实现稀疏，为什么不用L0，而要用L1呢？个人理解一是因为L0范数很难优化求解（NP难问题），二是L1范数是L0范数的最优凸近似，而且它比L0范数要容易优化求解。所以大家才把目光和万千宠爱转于L1范数。

OK，来个一句话总结：L1范数和L0范数可以实现稀疏，L1因具有比L0更好的优化求解特性而被广泛应用。

L1正则化数学解释

设损失函数为：

$$\ell = \ell_0 + {\lambda}\sum_w{|w|}$$

其中L0表示没有正则化时的损失函数。对它求w的偏导：

$$\frac{\partial{\ell}}{\partial{w}} = \frac{\partial{\ell_0}}{\partial{w}} + {\lambda}\cdot sgn(w)$$

$sgn(w)$表示w的符号。对w进行更新：

$$w = w -\eta\frac{\partial{\ell}}{\partial{w}} = w-{\eta \lambda}\cdot sgn(w)-\eta\frac{\partial{\ell_0}}{\partial{w}}$$

可以看出，L1正则化是通过加上或减去一个常量${\eta \lambda}$,让w向0靠近；对比L2正则化，它使用了一个乘性因子 $(1-{\eta \lambda})$去调整权重，使权重不断衰减。因此可以得出：当$|w|$很大时,L2对权重的衰减速度比L1大得多，当$|w|$很小时，L1对权重的缩小比L2快得多。

这也就解释了为什么L1正则能让模型变得稀疏。L1对于小权重减小地很快，对大权重减小较慢，因此最终模型的权重主要集中在那些高重要度的特征上，对于不重要的特征，权重会很快趋近于0。所以最终权重w会变得稀疏。

好，到这里，我们大概知道了L1可以实现稀疏，但我们会想呀，为什么要稀疏？让我们的参数稀疏有什么好处呢？这里扯两点：

1）特征选择(Feature Selection)：

大家对稀疏规则化趋之若鹜的一个关键原因在于它能实现特征的自动选择。一般来说，xi的大部分元素（也就是特征）都是和最终的输出yi没有关系或者不提供任何信息的，在最小化目标函数的时候考虑xi这些额外的特征，虽然可以获得更小的训练误差，但在预测新的样本时，这些没用的信息反而会被考虑，从而干扰了对正确yi的预测。稀疏规则化算子的引入就是为了完成特征自动选择的光荣使命，它会学习地去掉这些没有信息的特征，也就是把这些特征对应的权重置为0。

2）可解释性(Interpretability)：

另一个青睐于稀疏的理由是，模型更容易解释。例如患某种病的概率是y，然后我们收集到的数据x是1000维的，也就是我们需要寻找这1000种因素到底是怎么影响患上这种病的概率的。假设我们这个是个回归模型：y=w1x1+w2x2+…+w1000x1000+b（当然了，为了让y限定在[0,1]的范围，一般还得加个Logistic函数）。通过学习，如果最后学习到的w就只有很少的非零元素，例如只有5个非零的wi，那么我们就有理由相信，这些对应的特征在患病分析上面提供的信息是巨大的，决策性的。也就是说，患不患这种病只和这5个因素有关，那医生就好分析多了。但如果1000个wi都非0，医生面对这1000种因素，累觉不爱。

二、L2范数
除了L1范数，还有一种更受宠幸的规则化范数是L2范数: $||W||_2$。它也不逊于L1范数，它有两个美称，在回归里面，有人把有它的回归叫“岭回归”（Ridge Regression），有人也叫它“权值衰减weight decay”。
L2范数是指向量各元素的平方和然后求平方根(也称欧几里得范数，欧氏距离)。我们让L2范数的规则项$||W||_2$最小，有选择地让某些 w 变小[^1]，但与L1范数不同，它不会让它等于0，而是接近于0，这里是有很大的区别的哦。而越小的参数说明模型越简单，越简单的模型则越不容易产生过拟合现象。
L2正则化可以解决模型训练中的过拟合现象，它也被称为权重衰减。在回归模型中，这也被称为岭回归。我们先介绍L2正则化的实现方式，然后定性地介绍一下为什么L2正则化可以防止过拟合。
设损失函数为

$$\ell = \ell_0 + \frac{\lambda}{2}\sum_w{w^2}$$

其中L0表示没有正则化时的损失函数。对它求w的偏导：

$$\frac{\partial{\ell}}{\partial{w}} = \frac{\partial{\ell_0}}{\partial{w}} + {\lambda w}$$

对w进行更新：

$$w = w - \eta\frac{\partial{\ell}}{\partial{w}} = (1-\eta \lambda)w-\eta\frac{\partial{\ell_0}}{\partial{w}}$$

我们知道，没有正则化的参数更新为:

$$w = w - \eta\frac{\partial{\ell_0}}{\partial{w}}$$

而L2正则化使用了一个乘性因子 $(1-{\eta \lambda})$去调整权重，因此权重会不断衰减，并且在权重较大时衰减地快，权重较小时衰减得慢。

下面换一种方式来理解L2正则化对权重的限制。我们的目标是最小化下面的损失函数：

$$\min {L = L_0(w) + {\lambda}\sum_w{w^2} }$$

为了L最小，需要让L0和正则化项的和能够最小。若w变大让L0减小，$\sum_w{w^2}$也会变大，后者就会抑制前者，从而让w不会上升地过大。此时$\lambda$就像是一个调整模型拟合精度与泛化能力的权重因子。

现在我们知道了，L2正则化能够限制参数的大小。那么，为什么参数大小被限制了，这个模型就是一个简单的模型，就能够防止过拟合了呢？回到我们最初开始介绍的多项式回归$$y = a_0x^9 + a_1x^8 + …+ a_9$$,当参数很小时，高次方项的影响就会变得十分微弱，这使模型不会对某一个输入太过敏感，从而近似学习到一条简单的曲线，类似最开始的线性模型。也就是说，即使你预设的回归模型是一个9次的多项式回归，通过正则化学习，高次项前的系数 会变得很小，最后的曲线类似一条直线，这就是让模型变成了一个简单的模型。

总结一下:
正则化让模型根据训练数据中常见的模式来学习相对简单的模型，无正则化的模型用大参数学习大噪声。
L2正则化通过权重衰减，保证了模型的简单，提高了泛化能力。

三、L1,L2正则化的形象理解
理解一：解的表示

L1、L2正则化还有另一种表示方式：
L1：$\arg\min{\sum_x{(y-wx)^2}},\ \ \ \ s.t.||w||_1\leq{t}$
L2：$\arg\min{\sum_x{(y-wx)^2}},\ \ \ \ s.t.||w||_2\leq{t}$
如上图所示，假设w是一个二维的向量，则目标函数可以用一圈圈等值线表示，约束条件用图中黑线表示，而我们要找的最优解，就在等值线和约束线第一次相交的地方。

左图是L1正则化的情况，在特征为二维时，约束线是一个菱形，等值线极有可能最先与顶点相交，在这种情况下有一个维度的特征就会为0，这就带来了稀疏。当特征的维度变高，坐标轴上角与边都会变多，这更会加大等值线与他们先相交的概率，从而导致了稀疏性。
  L2正则化不同，如右图所示，它的约束线是一个圆形，等值线可能与它任意一个位置的点首先相切，这个切点在坐标轴上的概率大大 减小，从而不太容易导致稀疏。

理解二：下降速度

另外从下降速度来看，L1正则化是绝对值函数，L2正则化是二次函数，他们的函数图形如上图所示。可以看出L1正则化的下降速度一直都是一致的，这也符合之间得出的结论：L1正则化通过一个常数
${\eta \lambda}\cdot sgn(w)$
来让权重减小：

$$w = w -\eta\frac{\partial{\ell}}{\partial{w}} = w-{\eta \lambda}\cdot sgn(w)-\eta\frac{\partial{\ell_0}}{\partial{w}}$$

而L2正则化的下降速度不同，当w大的时候，下降较快，当w小的时候，下降较慢，这也符合我们之前推导的，L2正则化通过一个乘性因子$(1-{\eta \lambda})$去衰减权重：

$$w = w -\eta\frac{\partial{\ell}}{\partial{w}} = (1-{\eta \lambda})w-\eta\frac{\partial{\ell_0}}{\partial{w}}$$

这种差异就导致当w较大时，L2的斜率大于L1，L2正则化权重衰减地比L1正则化快；w小时，L2斜率小于L1，L1正则化权重衰减地比L2正则化快。因此L1正则化最终会导致模型保留了重要的大权重连接，不重要的小权重都被衰减为0，产生了稀疏。而L2正则化可以通过限制权重大小让模型变得简单，但却不会导致稀疏。

四、L2范数的好处
1）学习理论的角度：

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

2）优化计算的角度：

从优化或者数值计算的角度来说，L2范数有助于处理 condition number不好的情况下矩阵求逆很困难的问题。因为目标函数如果是二次的，对于线性回归来说，那实际上是有解析解的，求导并令导数等于零即可得到最优解为：

然而，如果当我们的样本X的数目比每个样本的维度还要小的时候，矩阵XTX将会不是满秩的，也就是XTX会变得不可逆，所以w*就没办法直接计算出来了。或者更确切地说，将会有无穷多个解（因为我们方程组的个数小于未知数的个数）。也就是说，我们的数据不足以确定一个解，如果我们从所有可行解里随机选一个的话，很可能并不是真正好的解，总而言之，我们过拟合了。
但如果加上L2规则项，就变成了下面这种情况，就可以直接求逆了：

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

正则化
范数
L0,L1,L2范数在机器学习中的应用
L2范数的理解
数值分析：矩阵求逆-奇异性、条件数
[^1]:如何理解有选择性的降低: 按照上文预测疾病的例子，样本中的特征有很多，但大部分特征都是无关紧要的，只有一小部分关键的特征支撑起了整个预测模型。表现在系数 w 上就是，大部分的 w_i 都是不幸的，因为它们刚好与那些无关紧要的特征结对，它们的大小对整个模型的效果影响不大，于是在正则项的约束下它们都变小了，甚至趋近于0；而只有小部分的 w_i 比较幸运，它们刚好对应到了好的特征，于是它们肩负起了非常重大的责任，它们的微小变化会引起模型曲线在走势上的根本性变化，损失函数会急剧增大。如果正则项妄图约束这些关键的 w_i，使它们变小，那么由此造成的损失函数的扩大将远大于从正则项上获得的微小收益，所以这些关键的 w_i 可以几乎不受正则项的干涉。 但也不尽然，如果你把正则项之前的系数 λ 调到非常大，那么它就会敢于压迫那些关键的 w_i，最终造成的结果是，模型确实变简单了，但也严重偏离了预期方向，没什么卵用了。相反，如果你把 λ 调得非常小，那么正则项对每个 w_i 都惹不起，即使是那些无关紧要的 w_i 它也无力约束，最终就会导致模型过拟合（试想 λ 等于0的情况）。所以，损失函数与正则项就像是博弈的双方，它们之间的力量对比通过参数 λ 进行调和。只有把 λ 调合适了，才能得到既不过拟合，又相对简单的好模型。从这种意义上来说，L2正则项与L1正则项类似，也有“特征选择”的效果。 上面的描述比较感性，是我为了方便直观理解做的一些比喻，如果把模型的预测曲线做出来会更加严谨一些。即每个 w_i 都影响着曲线的形态，但是有主次之分。那些低阶的、关键的 w_i 控制着曲线的整体走势；而那些高阶的、次要的 w_i 则是在曲线整体走势的基础上稍微扭曲曲线的形态；当然，还会有更高阶的 w_i，它们负责在大的扭曲之上制造更小的扭曲，以此类推。 这样看来L2正则项的作用就很明显了，要改变预测曲线的整体走势肯地会造成损失函数的不满，但是把曲线的形态熨平似乎并没有什么不妥。而 λ 的大小则决定了正则项的视野，即多大的弯曲算作走势？多小的弯曲算作扭曲？