本次Lecture主要讲解了解决overfitting问题的方法——Regularization正则化

Regularized Hypothesis Set

我们在上节课知道，当用一个高次的多项式对target function进行拟合的时候，就会出现小而大的情况，这就是过拟合（overfitting）。而当用较低次的多项式进行拟合的时候，就能够得到左边这样比较良好的效果。

于是，这种获得regularized fit的方法就是试着将高次的多项式退化到低次多项式。根据之前所学，多项式拟合这种假设空间，是nested hypothesis，也就是是包含在中的，如下图——

所以，我们可以对添加一些限制条件（constraints）退化成。

和分别可以表示为：

那么只要有就能得到，也就是将高阶项的系数限制为0，这样高阶就转化为了低阶，图形更加平滑了。但是，这种条件比较严格，等价于转化为二阶多项式了。

现在提出一种宽松一点的限制条件，限定了的个数，并不限定必须是高阶的。这个Looser Constraint的方程写为：

（这里[ ]表示布尔计数）

这种hypothesis记为，称为sparse hypothesis set。它与和的关系为：。

最优化问题就转化为求解，这被证明是NP-hard，求解非常困难。

于是，我们就u一种更容易求解的宽松的限定条件Softer Constraint，即：

最优化问题转化为。

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

这被称为regularized hypothesis set，这种条件下的是可解的，我们将取得满足条件的最优解时的记作。

那么接下来就讨论如何求解。

Weight Decay Regularization

我们知道，，并且有，于是就可以转化为：

这个限定条件从几何角度上的意思是，权重被限定在半径为的球内，而球外的都不符合要求，即它是靠近的。

 从几何的角度来辅助解释求解最小的过程：

• 红圈表示限制条件的边界，蓝圈表示是当前下的取值
• 假设在空间内有一点（当然它是满足限制条件的），根据梯度下降算法，是当前下的移动方向（图中蓝色箭头）
• （我们之前学过）在没有约束条件的时候，随着的不断变化，最终会使到达“谷底”，也就是
• 现在加上了约束条件，被限制在红色的球内，不会达到的位置，最大只可能在红圈的边缘沿着切线方向移动（图中绿色箭头），而不可能沿着法线方向移动（图中红色箭头）。当然，这个法线的方向其实就是的方向，这是由原点指向的。
• 于是在切线方向产生投影，在投影向量的作用下不断移动，直到为止
• 也就是说，移动的终止条件是

于是，取得最优解就要满足条件，其中被称为拉格朗日乘子（Lagrange multiplier），于是我们只要求解方程中的即可。

》》如果是线性的，我们将代入得，因为是半正定矩阵，如果，那么一定是正定矩阵，即一定可逆。

于是有最优解：

统计学上把这叫做ridge regression，可以看成是linear regression的进阶版。

》》对于更一般的情况，是非线性的，就不能用之前的方法求解。所以从另一个角度来看平行方程——

已知是对的导数，而也可以看成是的导数。那么等式左边可以看成一个函数的导数，导数为零，即求该函数的最小值。

于是方程转换为取函数的最小值，这个函数被称为augmented error，其中第二项就是限定条件regularizer，也称为weight-decay regularization。

用一个例子来体现不同的的作用效果：

我们可以把看成是一种penalty，即对hypothesis复杂度的惩罚。

• 越大，就越小，对应于C值越小，即这种惩罚越大，拟合曲线就会越平滑，高阶项就会削弱，容易发生欠拟合。
• 一般取比较小的值就能达到良好的拟合效果，过大过小都有问题，但究竟取什么值，要根据具体训练数据和模型进行分析与调试。

我们目前讨论的多项式是形如的形式，若，那么可能导致相对于低阶的值要小得多，则其对应的非常大，相当于要给高阶项设置很大的惩罚。

为了避免出现这种数据大小差别很大的情况，可以使用Legendre Polynomials代替这种形式，Legendre Polynomials各项之间是正交的，用它进行多项式拟合的效果更好。

Legendre Polynomials这里不做详细介绍，感兴趣的同学可以看维基百科。

至此，我们将一个有限制的最优化转化为了无限制的最优化。

Regularization and VC Theory

下面研究一下Regularization与VC Theory之间的关系——

• Augmented Error表达式：
• VC Bound表达式：

我们可以从另一个角度来看待Augmented error

• 可以被视作单个的假设有多复杂；而VC中的则是假设集的复杂程度。将两者相类比，可以将记作。
• 而根据两者的表达式，被包含在，也就是能够很好地表现。
• 从而可以用来代理，相比之前用来得到的更好。

由于“代理人”的存在，我们就能够对整个假设集H有一个评判，知道哪个比较好，可以自由选择。

根据VC Dimension理论，整个hypothesis set的模型复杂度，这是因为在最小化的过程中考虑了所有的，没有任何限制条件。

但是实际上，并不是将所有都考虑，实际上只要考虑就可以，于是就有，也就是综合了假设集和学习算法综合的复杂度，时总有。

学习算法中包含了regularized的过程，也就像给算法加上了“踩刹车”的功能（记不得这个功能可以复习以下上一讲的内容），减少了模型复杂度，也避免了过拟合的可能。

General Regularizers

那么在一般的时候，Regularizers应该如何选取呢？（也就是这些条件如何选取呢？）当然我们在做机器学习的时候往往不知道target function，所以一般都是在限制内朝着target function的方向来选取。

主要有三种方式：

• target-dependent：比如我们需要一个偶函数的结果，那我们只要给奇次方系数加上权重，让他们变小就好了。
• plausible：选择一些可以说服我们自己的条件，让我们相信能得到更平滑更简单的结果就可以减少噪声了。（下一页的L1 Regularizer就是这样）
• friendly：找到一个容易优化的regularizer，就像之前介绍的weight-decay regularizer就是这样。

那万一选到一个不好的regularizer怎么办？这个大可以放心，因为我们对regularizer有系数来限制，不理想的时候把它调小甚至为0就可以，最差就是不用罢了。

Regularizer的选取方式跟error measure的选取原则相似的原则，error measure是user-dependent, plausible, or friendly。

我们在第二节的时候已经看过了一种weight-decay的regularizer，被称为L2 regularizer（下图左）。这种形式的regularizer计算的是的平方和，是凸函数，比较平滑，易于微分，容易进行最优化计算。

我们再看L1 Regularizer的表达式：。这是对求绝对值之和，也就是长度之和，也是凸函数，但并不是圆形而是正方形，也就不是处处可微的了。（上图右）

L1的解是稀疏的（sparse）。这是因为：根据之前的推导，我们知道与垂直于平面（红线）的方向平行才会达到最优，而在边上是很难的，在靠近顶点的位置才会达到（有一些w是0）。

于是，在需要一些稀疏解的时候，L1就比较有用。

关于这两个regularizer更多讲解可以看这篇帖子：机器学习中的范数规则化之（一）L0、L1与L2范数。

接下来的问题是，应该怎么选择比较好？

我们看到， stochastic和deterministic两种噪声越大的时候，就越大。我们可以理解为，路面越不平整的时候，刹车踩得就越多。那么很多时候我们并不知道noise的情况，这种时候如何来设置呢？下次课继续讲解。