林轩田《机器学习基石》（十四）—— Regularization

上次说到在机器学习中最大的危险之一是overfitting，之前把overfitting比作出了车祸，我们分析了产生的原因与解决方法：

油门太重，即使用了太大的vcdimension。解决方法：开慢点，即从简单的模型开始学起。道路崎岖，也就是有太多noise。解决方法：把这些崎岖的地方搞清楚，即数据清洗。数据提纯（data cleaning/pruning）。对路况不熟悉，在机器学习中就是资料太少。解决方法：增加路况资料，即现有的资料或对这个问题的了解中产生新的、多的资料（datahinting）。开太快。解决方法：适时地踩刹车，即添加正则项。其他。解决方法：时时刻刻看看仪表板，即validation验证/交叉验证。

一、正则化hypothesisset

今天讲的就是第四种情况，开太快，要适时地踩刹车，即添加Regularization，正则项。

上面左边给出了一个过拟合的情况（红线是过拟合的），在右边是“规则化后的fit”，可以看出右边图中的红线更加平滑，也更贴近蓝线。上节课说过左边那个图中的红线是高次多项式作出的hypothesis，右边是低次多项式作出的hypothesis，两个图中的蓝线就是target函数f。我们需要做的就是，如果我们找到一个hypothesis的次数太高了，我们就想要从这个高次再走回低次。

在第十二节课的时候我们说过hypothesis之间有如下关系。

regularization要做的事情：

有很多函数都满足我们想要的解，但是我们不知道应该选择哪个，解太多会造成一些问题。回到机器学习问题，对于有限个点，穿过这些点的函数非常多，我们如何从这些函数中选择一个比较好的函数呢？即结合上面的hypothesis之间的关系，我们如何从高次回到低次？

我们依旧用上节讲的问题分析，即我们把x空间资料转化到z空间再做线性分类（），特征变换公式如下：

，Q次多项式。

10次hypothesis有11个权重

2次hypothesis有3个权重

因此当时，10次hypothesis就变为了2次的hypothesis。即2次hypothesis = 10次hypothesis+一些限制（）。

为什么不直接解2次多项式呢，而是要先解一个10次多项式然后再加一些限制？

答：为了拓展视野，在推导后面的问题时候变得容易一些。（我们先看一下后面的问题，回过头再看这个问题）

刚才我们说，解一个2次hypothesis的问题就是在 10次hypothesis问题上加上条件，要求这特定的8个w是0。现在，把条件放松一点，现在不要求特定的哪些w是0，而是说中任意的8个w是0即可。于是整个机器学习问题就变为：

这个约束的意思是：w不等于0的至多有3个，即w等于0的至少有8个。

我们把用上面特定的8个w：生成的hypothesis叫做。对w完全没有约束的叫做。

显然有比有更大的复杂度，比风险更少。即是一个中间选项。称为稀疏hypothesisset，但是一个不好的消息是，解这个机器学习问题是NP-hard的。

所以，我们看看还可不可以转换为其他更易于求解的约束条件。

我们可以把原来的问题（左边）转化为现在的问题（右边），我们现在计算w的大小（给定一个心里的预设C，使这些w的大小加起来不要超过C），而不再关注它到底是不是0。

的一些性质：

与之间有重叠，有交集的部分，但是没有完全包含的关系，也不一定相等。之间也有如下包含关系（括号里为C，显然C是一个实数），当C无限大的时候可以看做根本没有约束，也就是此时和相等。

二、让权重w减小的正则项

现在，针对，即加上限定条件，我们的问题变成向量-矩阵的形式：

即：

我们的目的是计算的最小值，限定条件是。这个限定条件从几何角度上的意思是，权重w被限定在半径为的圆内。

之前我们在没有约束条件的情况下解问题，是通过梯度下降法，即朝着谷底的方向走下去（），就像在图中的的蓝色椭圆部分，蓝色椭圆部分可以看做等高线的一部分，其中越往椭圆圆心，的值越小，显然图中如果没有约束条件的话，是最优解。但现在加了约束即红色圆部分（只有在圆内的才满足条件，圆外的通通不要）。

如果现在一个w已经在圆的边缘了，那么还可以继续往山谷走吗？答：我们可以朝着圆的法向量的垂直方向滚动（即若位于图中w点，可以沿着图中绿色箭头的所在直线上走）。

我们想要又不出圆，又会下降：我们可以看如果在圆的法向量的垂直方向有分量的话，还是可以继续往山谷走的（走的大小为在法向量的垂直方向上的投影，即图中绿色箭头）。

什么时候不能再往下滚了？答：在这个点上，与法向量是平行的。

我们先要明确的原点是红色圆的圆心，如果当一个点w的与圆的法向量是平行的，那么向量和是平行的。如果我现在已经到了一个点，是最好的点，那么它不能再往下滚了，此时向量与是平行的。

所以由于在一条直线上，所以存在一个参数＞0（拉格朗日参数），有

所以我们要找到一个＞0使得求解

结合表达式（求导），即，

如果此时你还知道是多少（如果我们规定其为超参数，它就是一个常数值），那么可以直接求解

由于括号里通过调整大小，可以使得它通常是正定的，所以是可逆的，可以求逆矩阵。

我们从求解的问题，重新推优化问题。（即优化问题要长什么样，才能让求解的问题变为上面带的问题呢？）

即要最小化上面的问题。加号右边的那一项叫做regularizer，正则化子。整个的新问题，变为augmentederr，增广误差，记作。所以我这次不是解‘优化问题＋约束’了，而是求解带正则项的目标函数的无约束优化问题。同时也不需要知道C了，直接知道即可（对于问题来说，知道和知道C的力气差不多）。

下面给出一个曲线拟合的例子，取不同的值时，得到的曲线也不相同：从过拟合到欠拟合

从上面可以看出，只要加一点点的正则化就可以对hypothesis有很强的约束。我们可以把看成是一种penality，即对hypothesis复杂度的惩罚。越大，就有更短的w，C值也越小（他们三个的关系是相互的，充要的）。上述称为‘把w变小的正则化方法’。这种方法也可以和其他的特征变换和线性模型进行搭配。

考虑一种特殊情况，如果这些点都在[-1,+1]之间，很显然经过如下变换后，那些高阶的每一项都会很小，从而为了计算一个比较合理的分数，w通常会变得很大，对于高阶的变换来讲产生的惩罚就会很大。

为了避免出现这种数据大小差别很大的情况，我们用Legendre多项式（多项式彼此之间垂直）的特征变换来代替上述变换。这里不再赘述，有兴趣可以研究。

三、正则项与VC的理论

绿色是我们最开始提出的带约束优化问题，红色是我们把原问题变为好求解的、几乎等价的无约束优化问题。黄色部分是原问题VC Bound的保证。现在来看看增广误差augmentederr与VC Bound的一些相同和不同之处：

正则项是一个hypothesis的复杂度，不妨记作。代表hypothesisset有多复杂（也就是有多少种选择）。根据Augmentederr和VC Bound的表达式，包含于之内，发现与之间的误差更小。相当于用了一个代理人替换掉之前的，且效果更好。就是说原来我们只把做好，这样某种角度就把做好了，但现在我们把做好，因为它更接近。而且的方式更自由，因为它自己参与选了w。

模型复杂度：上述问题中对应空间中所有的w都可以选，那么理论上最多要付出代价为。但实际上只考虑了在“谷底”附近的w（因为有约束，所以满足约束的似乎才是真正与付出的代价有关），所以实际的代价为，其中A表示regularized算法，这才是有效的VC dimension。看起来后者要比前者的VC dimension小很多。综上，我们的vc维现在不仅仅和hypothesisset有关系了，而且和算法A也有关。

四、一般正则项

刚才讲的正则项都集中在“减小权重”的方面。那么我如果想要更一般的正则项，应该加些什么条件呢？或者我们问目标含糊应该变成什么样呢？当然最好的方式是直接告诉target函数f，如果达不到，那么它最好：

告诉我们好的hypothesis在哪个方向target-dependent：如果今天想要一个接近偶函数的函数，那么我加上去的正则项最好可以使得奇数次方的对应的w小一点。是有说服力的正则项plausible：它可以让我们选出比较平滑或者简单的hypothesis。比如一些stochastic/deterministicnoise都会让目标函数变得不平滑，我们希望多选一些平滑的，波动的则不要选。（比如稀疏的L1正则化子）是容易求解的 friendly：因为它最终也是要加到优化问题里求解的，所以我们希望找到的正则化项可以很好求解问题。比如L2正则项。如果我最终选择的正则项不好怎么办？没关系，我们还有正则项的系数，最极端的情况我们可以让它等于0.

看起来正则项最好是target-dependent, plausible,或者friendly，这三个要求很眼熟，在之前误差度量的时候，我们也提出了这三个要求。

接下来，介绍两种Regularizer：L2和L1。

L2 Regularizer一般比较通用，其形式如下：

约束在几何上如下：

性质：它是凸的、可微的、易于求解的。

L1 Regularizer的形式如下：

约束在几何上如下：

性质：它是凸的、不可微的（在尖角上）、解是稀疏的（w中0元素多）。已知围成的是圆形，而围成的是正方形，那么在正方形的四个顶点处，是不可微分的（不像圆形，处处可微分）。

如果今天，那么说明点在红色正方形的边缘上，然后我们看与垂直于我们平面的方向是不是平行的，垂直平面的方向就是图中红色箭头的方向（从数值上来说，有很多实数，红色箭头就是对w取sign的方向，很难是平行的，除非与红色箭头代表的向量（-1,1,1，...,-1）之类的成比例，要求中这些实数的绝对值都相等，且符号还得与前者一致，这很难做到），所以w会沿着正方形的边一直走直到顶点才会得到最佳解，在顶点上有一些w的分量会是0（可以在上面图中画一个坐标轴，横坐标是x，纵坐标是y，原点在正方形的中心，会发现图中最后到达的顶点的横坐标是0）。

接着，我们分别作了stochastic/deterministicnoise，来看看我们该如何选择（图中的部分）：

可以发现，noise越大，越大（即正则项要大，就像是noise很多，路况不好，踩的刹车应该越大）。具体怎么选择，在之后会讲。

总结：