台湾大学林轩田《机器学习基石》学习笔记第14讲——Regularization

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

In general, regularization is a technique that applies to objective functions in ill-posed optimization problems.
The mathematical term well-posed problem stems from a definition given by Jacques Hadamard. He believed that mathematical models of physical phenomena should have the properties that:
1.a solution exists,
2.the solution is unique,
3.the solution’s behavior changes continuously with the initial conditions.
Problems that are not well-posed in the sense of Hadamard are termed ill-posed problems.
——from Wikipedia

一、Regularized Hypothesis Set
台湾大学林轩田《机器学习基石》学习笔记第14讲——Regularization

如右图所示，在数据量不够大的情况下，如果我们使用一个高阶多项式（图中红色曲线所示），例如10阶，对目标函数（蓝色曲线）进行拟合。拟合曲线波动很大，虽然Ein很小，但是Eout很大，也就造成了overfitting.
那么如何对过拟合现象进行修正，使hypothesis更接近于target function呢？一种方法就是左图的regularized fit。
注意到左图的红色曲线比右图的红色曲线要更平滑，因为使用了更低阶的多项式，例如2阶；那么如何把10阶的hypothesis set转化成2阶呢？
我们注意到不同阶数的hypothesis set是有包含关系的，如果我们在 $H_{10}$ 的w向量做一些限制条件，例如规定 $w_3=w_4=...=w_{10}=0$ ，那么 $H_{10}$ 就转化成了 $H_2$ 了，我们把这种操作叫做constraint；
但为什么不直接使用 $H_2$ 的hypothesis呢？
上图对刚才的限制条件做了一些宽松化：即不再要求固定的 $w_q=0$ 了，而是只要求w向量中的其中至少8个元素要等于0，从而得到一个新的hypothesis set $H_2 '$ ，我们称这种操作为Looser constraint.
这样有两个好处：一方面 $H_2 '$ 要比 $H_2$ 更灵活，另一方面 $H_2 '$ 也比 $H_{10}$ 更不容易出现overfitting。
但缺点是这样的hypothesis set不容易求解，NP-hard to solve.
既然looser constraint还是难以求解，这里再介绍一种constraint操作，我们称之为softer constraint；
这个限制条件如上图，要求 $\sum w_q^2≤C$ ，C为常数，即所有的权重的平方和不能超过常数C，我们把这个限制条件产生的hypothesis set称作 $H(C)$ ；
$H(C)$ 和 $H_2 '$ 存在交叠部分，但不完全相，同时 $H(C)$ 中的C取不同大小的值也存在包含关系，当C无穷大时，即没有存在限制条件；
H© 称为regularized hypothesis set，这种形式的限定条件是可以进行求解的，我们把求解的满足限定条件的权重w记为 $w_{REG}$ 接下来就要探讨如何求解 $w_{REG}$ 。

二、Weight Decay Regularization
如何如何求解 $w_{REG}$ ，转化成如下的问题：
台湾大学林轩田《机器学习基石》学习笔记第14讲——Regularization

我们目标是求解Ein(w)的最小值，前提的限制条件是 $\sum w_q^2≤C$ ；
这个限定条件从几何角度上的意思是，权重w被限定在半径为 $\sqrt{C}$ 的圆内，而球外的w都不符合要求，即便它是靠近Ein(w)梯度为零的w。
我们把几何图形表示如下：
上图中，蓝色区域是Ein(w)的取值，而红色圆圈范围内则是w的限定条件，圆心位置则是坐标的原点；
假设在空间中的一点w，根据梯度下降算法，w会朝着−∇Ein的方向移动（图中蓝色箭头指示的方向），在没有限定条件的情况下，w最终会取得最小值Wlin，即“谷底”的位置；
那么加上限制条件之后，w最大只能在红色圆周上移动，因此只要蓝色的-▽Ein在沿着w的方向上的分量是正的（即红色箭头），w的移动方向就只能是-▽Ein沿着圆周的切线方向的分量（即绿色箭头）；
这样的迭代直到w的方向和-▽Ein保持平行，这时候的w就是我们的目标 $w_{REG}$ 。
在几何上的分析，得到了上图中的代数形式；
上面公式中的λ称为Lagrange multiplier（拉格朗日乘数），是用来解有条件的最佳化问题常用的数学工具，2/N是方便后面公式推导。那么我们的目标就变成了求解满足上面公式的 $w_{REG}$ 。
上式中包含了求逆矩阵的过程，因为 $Z^TZ$ 是半正定矩阵，如果λ大于零，那么 $(Z^TZ+\lambda I)$ 一定是正定矩阵，即一定可逆。另外提一下，统计学上把这叫做ridge regression，可以看成是linear regression的进阶版。

台湾大学林轩田《机器学习基石》学习笔记第14讲——Regularization

另外一种求解的方法，这里我们把梯度的求解转化成最初求最小值的求解方式，这里的w需要转化成积分形式，即内积，得到： $E_{aug}(w)=E_{in}(w)+\frac{λ}{N}w^Tw$
该函数中第二项就是限定条件regularizer，也称为weight-decay regularization。我们把这个函数称为Augmented Error，即 $E_{aug}(w)$ ;
如果λ不为零，对应于加上了限定条件，若λ等于零，则对应于没有任何限定条件，问题转换成之前的最小化Ein(w)。
从图中可以看出，当λ=0时，发生了过拟合；当λ=0.0001时，拟合的效果很好；当λ=0.01λ=0.01时，发生了欠拟合;
我们可以把λ看成是一种penality，即对hypothesis复杂度的惩罚，λ越大，w就越小，对应于C值越小，即这种惩罚越大，拟合曲线就会越平滑，高阶项就会削弱，容易发生欠拟合;
λ一般取比较小的值就能达到良好的拟合效果，过大过小都有问题，但究竟取什么值，要根据具体训练数据和模型进行分析与调试。
针对logistics regression的应用中，我们目前讨论的多项式是形如 $x、x^2、x^3......x^n$ 的形式，若x的范围限定在[-1,1]之间，那么可能导致 $x^n$ 相对于低阶的值要小得多，则其对于的w非常大，相当于要给高阶项设置很大的惩罚;
为了避免出现这种数据大小差别很大的情况，可以使用*Legendre Polynomials(拉格朗日多项式)*代替 $x、x^2、x^3......x^n$ 这种形式，Legendre Polynomials各项之间是正交的，用它进行多项式拟合的效果更好。

三、Regularization and VC Theory
下面我们研究一下Regularization与VC理论之间的关系。
台湾大学林轩田《机器学习基石》学习笔记第14讲——Regularization

其中 $w^Tw$ 表示的是单个hypothesis的复杂度，记为Ω(w)，而Ω(H)表示整个hypothesis set的复杂度；
根据Augmented Error和VC Bound的表达式，Ω(w)包含于Ω(H)之内，所以， $E_{aug}(w)$ 比 $E_{in}$ 更接近于 $E_{out}$ ，即更好地代表 $E_{out}$ ， $E_{aug}(w)$ 与 $E_{out}$ 之间的误差更小。
根据VC Dimension理论，整个hypothesis set的 $d_{VC}=\breve d+1$ ，这是因为所有的w都考虑了，没有任何限制条件。
而引入限定条件的 $d_{VC}(H(C))=d_{EFF}(H,A)$ ，即有效的VC dimension。也就是说， $d_{VC}(H)$ 比较大，因为它代表了整个hypothesis set，但是 $d_{EFF}(H,A)$ 比较小，因为由于regularized的影响，限定了w只取一小部分。
其中A表示regularized算法。当λ>0时，有： $d_{EFF}(H,A)<d_{VC}$
这些与实际情况是相符的，比如对多项式拟合模型，当λ=0时，所有的w都给予考虑，相应的 $Cd_{VC}$ 很大，容易发生过拟合。当λ>0且越来越大时，很多w将被舍弃， $d_{EFF}(H,A)$ 减小，拟合曲线越来越平滑，容易发生欠拟合。

四、General Regularizers
那么通用的Regularizers，即Ω(w)，应该选择什么样的形式呢？一般地，我们会朝着目标函数的方向进行选取。
台湾大学林轩田《机器学习基石》学习笔记第14讲——Regularization
寻找一个通用的regularization有三个考虑的方法：

target-dependent
plausible
friendly

接下来，介绍两种Regularizer：L2和L1：
台湾大学林轩田《机器学习基石》学习笔记第14讲——Regularization

L2 regularizer计算的是w的平方和，是凸函数，比较平滑，易于微分，容易进行最优化计算；
L1 regularizer计算的是w的绝对值和，即长度和，也是凸函数。但||w||1=C 围成的是正方形，那么在正方形的四个顶点处，是不可微分的（不像圆形，处处可微分）；
根据之前介绍的平行等式推导过程，对应这种正方形，它的解大都位于四个顶点处，因为正方形边界处的w绝对值都不为零，若−∇Ein不与其平行，那么w就会向顶点处移动，顶点处的许多w分量为零，所以，L1 Regularizer的解是稀疏的，称为sparsity。优点是计算速度快。

下面来看一下λ怎么取值：
台湾大学林轩田《机器学习基石》学习笔记第14讲——Regularization

从图中可以看出，sochastic/deterministic noise越大，λ越大。
这也很好理解，如果在开车的情况下，路况也不好，即noise越多，那么就越会踩刹车，这里踩刹车指的就是regularization。
但是大多数情况下，noise是不可知的，这种情况下如何选择λ？这部分内容，我们下节课将会讨论。

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

reference：https://blog.****.net/red_stone1/article/details/72765542?utm_source=copy

台湾大学林轩田《机器学习基石》学习笔记第14讲——Regularization

相关推荐