Question

上节课我们介绍了过拟合发生的原因：excessive power, stochastic/deterministic noise 和 limited data。并介绍了解决 overfitting 的简单方法。本节课，我们将介绍解决 overfitting 的另一种非常重要的方法：Regularization 规则化。

一、Regularized Hypothesis Set

先来看一个典型的 overfitting 的例子：

如图所示，在数据量不够大的情况下，如果我们使用一个高阶多项式（图中红色曲线所示），例如 10 阶，对目标函数（蓝色曲线）进行拟合。拟合曲线波动很大，虽然很小，但是很大，也就造成了过拟合现象。

那么如何对过拟合现象进行修正，使 hypothesis 更接近于 target function 呢？一种方法就是 regularized fit。

这种方法得到的红色 fit 曲线，要比 overfit 的红色曲线平滑很多，更接近与目标函数，它的阶数要更低一些。那么问题就变成了我们要把高阶（10 阶）的 hypothesis sets 转换为低阶（2 阶）的 hypothesis sets。通过下图我们发现，不同阶数的 hypothesis 存在如下包含关系：

我们发现 10 阶多项式 hypothesis sets 里包含了 2 阶多项式 hypothesis sets 的所有项，那么在中加入一些限定条件，使它近似为即可。这种函数近似曾被称之为不适定问题（ill-posed problem）。

如何从 10 阶转换为 2 阶呢？首先，可表示为：

而可表示为：

所以，如果限定条件是，那么就有。也就是说，对于高阶的 hypothesis，为了防止过拟合，我们可以将其高阶部分的权重 w 限制为 0，这样，就相当于从高阶的形式转换为低阶，fit 波形更加平滑，不容易发生过拟合。

那有一个问题，令高阶权重 w 为 0，为什么不直接使用呢？这样做的目的是拓展我们的视野，为即将讨论的问题做准备。刚刚我们讨论的限制是高阶部分的权重 w 限制为 0，这是比较苛刻的一种限制。下面，我们把这个限制条件变得更宽松一点，即令任意 8 个权重 w 为 0，并不非要限定，这个 Looser Constraint 可以写成：

也就只是限定了 w 不为 0 的个数，并不限定必须是高阶的 w。这种 hypothesis 记为，称为 sparse hypothesis set，它与和的关系为：

Looser Constraint 对应的 hypothesis 应该更好解一些，但事实是 sparse hypothesis set 被证明也是 NP-hard，求解非常困难。所以，还要转换为另一种易于求解的限定条件。

那么，我们寻找一种更容易求解的宽松的限定条件 Softer Constraint，即：

其中，C 是常数，也就是说，所有的权重 w 的平方和的大小不超过 C，我们把这种 hypothesis sets 记为。

与的关系是，它们之间有重叠，有交集的部分，但是没有完全包含的关系，也不一定相等。对应，C 值越大，限定的范围越大，即越宽松：

当 C 无限大的时候，即限定条件非常宽松，相当于没有加上任何限制，就与没有什么两样。称为 regularized hypothesis set，这种形式的限定条件是可以进行求解的，我们把求解的满足限定条件的权重 w 记为。接下来就要探讨如何求解。

二、Weight Decay Regularization

现在，针对 H(c)，即加上限定条件，我们的问题变成：

我们的目的是计算的最小值，限定条件是。这个限定条件从几何角度上的意思是，权重 w 被限定在半径为的圆内，而球外的 w 都不符合要求，即便它是靠近梯度为零的 w。

下面用一张图来解释在限定条件下，最小化的过程：

如上图所示，假设在空间中的一点 w，根据梯度下降算法，w 会朝着的方向移动（图中蓝色箭头指示的方向），在没有限定条件的情况下，w 最终会取得最小值，即“谷底”的位置。现在，加上限定条件，即 w 被限定在半径为的圆内，w 距离原点的距离不能超过圆的半径，球如图中红色圆圈所示。那么，这种情况下，w 不能到达的位置，最大只能位于圆上，沿着圆的切线方向移动（图中绿色箭头指示的方向）。与绿色向量垂直的向量（图中红色箭头指示的方向）是圆切线的法向量，即 w 的方向，w 不能靠近红色箭头方向移动。那么随着迭代优化过程，只要与 w 点切线方向不垂直，那么根据向量知识，一定在 w 点切线方向上有不为零的分量，即 w 点会继续移动。只有当与绿色切线垂直，即与红色法向量平行的时候，在切线方向上没有不为零的分量了，也就表示这时 w 达到了最优解的位置。

有了这个平行的概念，我们就得到了获得最优解需要满足的性质：

上面公式中的称为 Lagrange multiplier，是用来解有条件的最佳化问题常用的数学工具，是方便后面公式推导。那么我们的目标就变成了求解满足上面公式的。

之前我们推导过，线性回归的的表达式为：

计算梯度，并代入到平行条件中，得到：

这是一个线性方程式，直接得到为：

上式中包含了求逆矩阵的过程，因为是半正定矩阵，如果大于零，那么一定是正定矩阵，即一定可逆。另外提一下，统计学上把这叫做 ridge regression，可以看成是 linear regression 的进阶版。

如果对于更一般的情况，例如逻辑回归问题中，不是线性的，那么将其代入平行条件中得到的就不是一个线性方程式，不易求解。下面我们从另一个角度来看一下平行等式：

已知是对的导数，而也可以看成是的导数。那么平行等式左边可以看成一个函数的导数，导数为零，即求该函数的最小值。也就是说，问题转换为最小化该函数：

该函数中第二项就是限定条件 regularizer，也称为 weight-decay regularization。我们把这个函数称为 Augmented Error，即。

如果不为零，对应于加上了限定条件，若等于零，则对应于没有任何限定条件，问题转换成之前的最小化。

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

从图中可以看出，当时，发生了过拟合；当时，拟合的效果很好；当和时，发生了欠拟合。我们可以把看成是一种 penality，即对 hypothesis 复杂度的惩罚，越大，w 就越小，对应于 C 值越小，即这种惩罚越大，拟合曲线就会越平滑，高阶项就会削弱，容易发生欠拟合。一般取比较小的值就能达到良好的拟合效果，过大过小都有问题，但究竟取什么值，要根据具体训练数据和模型进行分析与调试。

事实上，这种 regularization 不仅可以用在多项式的 hypothesis 中，还可以应用在 logistic regression 等其他 hypothesis 中，都可以达到防止过拟合的效果。

我们目前讨论的多项式是形如的形式，若 x 的范围限定在[-1,1]之间，那么可能导致相对于低阶的值要小得多，则其对于的 w 非常大，相当于要给高阶项设置很大的惩罚。为了避免出现这种数据大小差别很大的情况，可以使用 Legendre Polynomials 代替这种形式，Legendre Polynomials 各项之间是正交的，用它进行多项式拟合的效果更好。关于 Legendre Polynomials 的概念这里不详细介绍，有兴趣的童鞋可以看一下 维基百科 。

三、Regularization and VC Theory

下面我们研究一下 Regularization 与 VC 理论之间的关系。Augmented Error 表达式如下：

VC Bound 表示为：

其中表示的是单个 hypothesis 的复杂度，记为；而表示整个 hypothesis set 的复杂度。根据 Augmented Error 和 VC Bound 的表达式，包含于之内，所以，比更接近于，即更好地代表，与之间的误差更小。

根据 VC Dimension 理论，整个 hypothesis set 的，这是因为所有的 w 都考虑了，没有任何限制条件。而引入限定条件的，即有效的 VC dimension。也就是说，比较大，因为它代表了整个 hypothesis set，但是比较小，因为由于 regularized 的影响，限定了 w 只取一小部分。其中 A 表示 regularized 算法。当时，有：

这些与实际情况是相符的，比如对多项式拟合模型，当时，所有的 w 都给予考虑，相应的很大，容易发生过拟合。当且越来越大时，很多 w 将被舍弃，减小，拟合曲线越来越平滑，容易发生欠拟合。

四、General Regularizers

那么通用的 Regularizers，即，应该选择什么样的形式呢？一般地，我们会朝着目标函数的方向进行选取。有三种方式：

• target-dependent
• plausible
• friendly

其实这三种方法跟之前 error measure 类似，其也有三种方法：

• user-dependent
• plausible
• friendly

regularizer 与 error measure 是机器学习模型设计中的重要步骤。

接下来，介绍两种 Regularizer：L2 和 L1。L2 Regularizer 一般比较通用，其形式如下：

这种形式的 regularizer 计算的是 w 的平方和，是凸函数，比较平滑，易于微分，容易进行最优化计算。

L1 Regularizer 的表达式如下：

L1 计算的不是 w 的平方和，而是绝对值和，即长度和，也是凸函数。已知围成的是圆形，而围成的是正方形，那么在正方形的四个顶点处，是不可微分的（不像圆形，处处可微分）。根据之前介绍的平行等式推导过程，对应这种正方形，它的解大都位于四个顶点处（不太理解，欢迎补充赐教），因为正方形边界处的 w 绝对值都不为零，若不与其平行，那么 w 就会向顶点处移动，顶点处的许多 w 分量为零，所以，L1 Regularizer 的解是稀疏的，称为 sparsity。优点是计算速度快。

下面来看一下如何取值，首先，若 stochastic noise 不同，那么一般情况下，取值有如下特点：

从图中可以看出，stochastic noise 越大，越大。

另一种情况，不同的 deterministic noise，取值有如下特点：

从图中可以看出，deterministic noise 越大，越大。

以上两种 noise 的情况下，都是 noise 越大，相应的也就越大。这也很好理解，如果在开车的情况下，路况也不好，即 noise 越多，那么就越会踩刹车，这里踩刹车指的就是 regularization。但是大多数情况下，noise 是不可知的，这种情况下如何选择？这部分内容，我们下节课将会讨论。

五、总结

本节课主要介绍了 Regularization。首先，原来的 hypothesis set 加上一些限制条件，就成了 Regularized Hypothesis Set。加上限制条件之后，我们就可以把问题转化为最小化问题，即把 w 的平方加进去。这种过程，实际上回降低 VC Dimension。最后，介绍 regularization 是通用的机器学习工具，设计方法通常包括 target-dependent，plausible，friendly 等等。下节课将介绍如何选取合适的来建立最佳拟合模型。

注明：

文章中所有的图片均来自台湾大学林轩田《机器学习基石》课程